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

Question

我"translating" 这个程序来自伪 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;
}

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

问题：

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

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

Sorted Insertion in linked list with pointers, C program crashes

c

sorting

crash

pointers

linked-list