C语言 添加到排序链表

Question

我试图让我的程序将分数插入有序链表中的某个位置。它编译良好，但在我启动它时崩溃。链表并不完全是我的专长，所以我确定我在某处犯了一个错误。p[i].score 和 p[i].name 定义在此段代码之前，列表最初为空。

struct highScore
{
    char name[10];
    int score;
    struct highScore *next;
};
struct highScore *head,*currentScore,*newScore, *temp;
if(head==NULL)
{
    head = currentScore = newScore;
    currentScore->score = p[i].score;
    strcpy(currentScore->name, p[i].name);
}
else
{
    currentScore = head;      
    while (currentScore->next != NULL)
    {
        while(p[i].score < currentScore->score)
        {
            currentScore = currentScore->next;
            if (currentScore->next->score < p[i].score)
            {
                newScore = (struct highScore *)malloc(sizeof(struct highScore));
                newScore->score = p[i].score;
                strcpy(newScore->name, p[i].name);
                temp = currentScore->next;
                currentScore->next = newScore;
                currentScore = newScore;
                currentScore->next = temp;
            }
        }
    }
}

Answer 1

您当前的代码有点混乱(正如其他人指出的那样(。

在伪代码中，你需要的是这样的：

new_entry = create_new_entry(data); /* allocate the new stuff */
for (some loop to find where new_entry is to insert)
    ... loop contents ...
insert new_entry;

单链表的棘手之处在于您只能执行"插入之前"操作，如下所示：

new_entry->next = what_new_goes_before;
what_new_goes_after->next = new_entry;

这需要有"new_entry追求的东西"。 这是特殊情况测试的地方：

if (head == NULL)

来自：如果head NULL，则没有可以追求的现有条目。 不幸的是，还有新条目先行的情况，因此您需要测试以下两个

：

if (head == NULL || goes_before(new_entry, head)) {
    /* i.e., there is no head yet, or new_entry goes before head */
    new_entry->next = head;
    head = new_entry;
} else {
    /* there is something for new_entry to go after, so find it */
    for (old_entry = head; !goes_before(new_entry, old_entry);)
        prev = old_entry;
        if ((old_entry = old_entry->next) == NULL)
            break;
    new_entry->next = old_entry;
    prev->next = new_entry;
}

但是，这里有一个非常有用的技巧，即在 C 中使用指针到指针。 与其编写一个必须至少运行一次的循环(设置上面的prev - 请注意，我们知道第一次行程中!goes_before()的结果(，我们可以有一个指针变量pp指向一些struct highScore *指针：

struct highScore **pp, *p;

最初，我们将有这一点 head . 当我们运行循环试图找到新条目之前的项目时，我们将它更改为指向每个旧条目的struct highScore *指针，称为 next ：

for (pp = &head; !goes_before(new_entry, p = *pp); pp = &p->next)
    continue;

当new_entry在 *pp 之前(其值现在在 p 中(时，循环终止，所以现在我们只需要设置新条目的next并更新*pp：

new_entry->next = p;
*pp = new_entry;

整个事情分四行完成(加上第五行声明(。

Answer 2

1. 将代码分解为函数。 例如，"initialize(("，"insert(("，"find(("和"delete(("可能都是有用的函数。

2. 不要使用全局变量。 例如，"*head"和"*currentScore"可能是你甚至考虑全局的唯一变量。

3. 为每个函数编写测试程序。

4. 单步完成调试器下的每个测试程序。

恕我直言..PSM

附注：例如：

struct *highScore
insert (struct ** head, struct *highScore newScore)
{
  struct *hiScore currentScore;
  // Assumes "newScore" element is already filled in
  if(*head==NULL)
  {
    *head = newScore;
    newScore->next = NULL;
    return newScore;
  }
  else
  {
    currentScore = *head;      
    while (currentScore->next != NULL)
    {
       ...

Answer 3

1. 该行

   head = currentScore = newScore;

   您尚未初始化 newScore - 因此该if语句的其余部分注定要失败。

2. 您是按顺序添加项目，还是列表应该按顺序结束？