c - 使用指针在链表中排序插入，C 程序崩溃

Question

我正在从伪 Pascal 语言“翻译”这个程序。最近我学习了 C 结构和指针特性，从一开始我就注意到指针很烦人。所以这是链表算法中排序插入的递归版本，它仍然给我带来问题，比如崩溃。

typedef struct node Node;

struct node
{
  int info;
  struct node *link;
};

void ordered_insert_rec(Node *head, Node *new_node)
{
  if(!head)
  {
    new_node->link = head;
    head = new_node;
  }

  if(new_node->info < head->info)
  {
    new_node->link = head;
    head = new_node;
  }
  else
  {
    ordered_insert_rec(head->link, new_node);
  }

这是主要的:

int main()
{
  Node head;
  Node node;
  Node node2;
  Node inserting_node;

  head.info = 1;
  head.link = &node;

  node.info = 3;
  node.link = &node2;

  node2.info = 7;

  inserting_node.info = 5;

  ordered_insert_rec(&head, &inserting_node);

  Node *front = &head;
  while(front)
  {
    printf("%d ", front->info);
    front = front->link;
    if(!front)
    {
      exit(1);
    }
  }
}

也许我在算法末尾打印列表时做错了什么，是吗？在提示中输出为“1 3 7”，但程序在一段时间后崩溃。它必须是“1 3 5 7”，通过这种方式我注意到过程“ordered_insert_rec”不能正常工作。

感谢您的帮助。 :)

Answer 1

修改后的代码:

#include <stdio.h>

typedef struct node Node;

struct node
{
  int info;
  struct node *link;
};

void ordered_insert_rec(Node **head, Node *new_node)
{
  // You are inserting at head. So you need to update head pointer.
  // If you don't use double pointers, you only change it locally.
  if(!(*head))
  {
    new_node->link = *head;
    *head = new_node;
    return;
  }

  if(new_node->info < (*head)->info)
  {
    new_node->link = *head;
    *head = new_node;
  }
  else
  {
    ordered_insert_rec(&((*head)->link), new_node);
  }
}

int main()
{
  Node head;
  Node node;
  Node node2;
  Node inserting_node;

  head.info = 1;
  head.link = &node;

  node.info = 3;
  node.link = &node2;

  node2.info = 7;
  node2.link = 0;

  inserting_node.info = 5;
  inserting_node.link = 0;

  Node * start = &head;

  ordered_insert_rec(&start, &inserting_node);

  Node *front = &head;
  while(front)
  {
    printf("%d ", front->info);
    front = front->link;
  }

  return 0;
}

我没有改进您的代码，只是将其更改为一个工作代码作为指针教程。你可以更好地编写这段代码。

问题:

1. 未初始化的链接(head 和insertion_node)。
2. 您的代码更新函数中的head，它是一个指针。所以你需要使用双指针，否则你只会在函数中更改它，结果不会发送回 main。
3. while 循环中用于打印列表的 break 是无用的。 while 的条件将在下一次迭代中不满足，它将停止。
4. 当您插入一个空列表时，您错过了一个返回。
5. 一般来说，人们不使用堆栈变量作为列表成员。通常你需要分配它们。但在这种特定情况下，您可以使用它。