c-显示循环链表时崩溃

Question

我正在尝试创建一个循环链表。当我在创建列表后尝试显示它时，程序会不断崩溃。这是我的代码：

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node * next;
} node;
node * createList(int);
void display(node * head);
int main() {
struct node * head;
head = createList(5);
display(head);
}
node * createList(int n) {
int i = 0,data = 0;
struct node * head = NULL;
struct node * temp = NULL;
struct node * p = NULL;
for (i = 0; i < n; i++) {
temp = (node*)malloc(sizeof(node));
temp->data = data++;
temp->next = head;
if (head == NULL) {
head = temp;
} else {
p = head;
while (p->next != NULL) {
p = p->next;
}
p->next = temp;
}
}
return head;
}
void display(node * head) {
struct node * temp = head->next;
while (temp != head) {
printf("%d-> t",temp->data);
temp = temp->next;
}
printf("n");
}

我做错了什么？

Answer 1

1. 您已经在temp->next = head;中将每个temp的next设置为head，但做得太早(第一个只是NULL(。然后，您在while (p->next != NULL) {中针对NULL测试了p->next，但您本应针对head进行测试。或者，您可以继续针对NULL进行测试，但随后需要将temp->next初始化为NULL，并仅在for循环之后将head分配给temp->next。

2. 您的显示代码从第二个链接开始。

这是一个使用上面1.中第一个选项的固定代码：

for (i = 0; i < n; i++) {
temp = (node*)malloc(sizeof(node));
temp->data = data++;
if (head == NULL) {
head = temp;
} else {
p = head;
while (p->next != head) {
p = p->next;
}
p->next = temp;
}
temp->next = head;
}

以下是使用上述1.中的备选选项的固定代码。您仍然需要将temp->next初始化为NULL，因为malloc()不会初始化。

for (i = 0; i < n; i++) {
temp = (node*)malloc(sizeof(node));
temp->data = data++;
temp->next = NULL;
if (head == NULL) {
head = temp;
} else {
p = head;
while (p->next != NULL) {
p = p->next;
}
p->next = temp;
}
}
if (temp != NULL) {
temp->next = head;
}

但在现实中，没有必要"；步行；从头部到每一个创造。您可以简单地保留上一个并将其链接到下一个：

for (i = 0; i < n; i++) {
temp = (node*)malloc(sizeof(node));
temp->data = data++;
if (head == NULL) {
head = p = temp;
} else {
p = p->next = temp;
}
}
if (temp != NULL) {
temp->next = head;
}

以下是display():的修复程序

void display(node * head) {
struct node * temp = head;
if (temp != NULL) {
do {
printf("%d-> t",temp->data);
temp = temp->next;
} while (temp != head);
}
printf("n");
}

Answer 2

问题出现在初始化的第一个节点上：

struct node *head = NULL;
...
for (i = 0; i < n; i++) {
...
temp->next = head;

所以CCD_ 21在第一次迭代时离开CCD_。这对循环列表无效。当您尝试插入第二个节点时：

p = head;
while (p->next != NULL) {

head->next又是什么？？(哦，NULL(取消引用NULL指针(BOOM Segfault！(

正确填写你的循环清单。插入第一个节点集时：

if (head == NULL) {
head = temp;
head->next = temp;              /* you must set head->next to temp */
} ...

因此，在插入剩下的节点时，您只需要：

} else {
p = head;
while (p->next != head) {       /* iterate to last node */
p = p->next;
}
p->next = temp;                 /* now set p->next = temp */
}

现在，您以相同的方式处理display()功能，例如

void display (node *head)
{
if (!head) {                            /* validate list not empty */
puts ("(list-empty)");
return;
}

struct node *temp = head;

do {                                    /* same loop problem fixed in display() */
printf ("%d-> t", temp->data);
temp = temp->next;
} while (temp != head);

putchar ('n');
}

如果你做了更改，那么你可以用测试你的列表

int main (void) {
struct node *head, *tmp;
head = createList(5);
display (head);
puts ("niterate from mid-list");
tmp = head;
tmp = tmp->next;
tmp = tmp->next;
display (tmp);
}

示例使用/输出

$ ./bin/lls_circular_fix
0->     1->     2->     3->     4->
iterate from mid-list
2->     3->     4->     0->     1->

最后，在struct node * head = NULL;中，您没有将类型node乘以head。将其写成struct node *head = NULL;(对于所有函数声明也是如此(可读性更强。

从列表中删除注释时，必须为head和tail(最后一个节点(创建一个特例。从这个意义上说，由于没有prev节点指针来跟踪先前的节点，单链表比双链表花费更多的精力。

仔细看看，如果你有问题，请告诉我。

一个完整的例子是：

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} node;
node *createList (int);
void display (node *head);
int main (void) {
struct node *head, *tmp;
head = createList(5);
display (head);
puts ("niterate from mid-list");
tmp = head;
tmp = tmp->next;
tmp = tmp->next;
display (tmp);
}
node *createList (int n)
{
int i = 0,data = 0;
struct node *head = NULL;
struct node *temp = NULL;
struct node *p = NULL;
for (i = 0; i < n; i++) {
if (!(temp = malloc (sizeof *temp))) {
perror ("malloc-temp");
return NULL;
}
temp->data = data++;
temp->next = head;                  /* head is NULL on 1st node insertion */
if (head == NULL) {
head = temp;
head->next = temp;              /* you must set head->next to temp */
} else {
p = head;
while (p->next != head) {       /* iterate to last node */
p = p->next;
}
p->next = temp;                 /* now set p->next = temp */
}
}
return head;
}
void display (node *head)
{
if (!head) {                            /* validate list not empty */
puts ("(list-empty)");
return;
}

struct node *temp = head;

do {                                    /* same loop problem fixed in display() */
printf ("%d-> t", temp->data);
temp = temp->next;
} while (temp != head);

putchar ('n');
}