在带有指针的链表中排序插入，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中断是没有用的。while的条件在下一次迭代中将不满足，它将停止。
4. 您错过了插入空列表时的return。
5. 通常，人们不会使用堆栈变量作为列表成员。通常您需要分配它们。但在这种特定情况下，您可以使用它。