循环链表显示时崩溃

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

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

这里是使用上面 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;
    }

但实际上，没有必要在每一个创作上都从头“走”。您可以简单地保留上一个，link 到下一个：

    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;

所以 tmp->next == NULL 在第一次迭代中离开 head->next == NULL。这不适用于循环列表。当您尝试插入第二个节点时：

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

又是什么head->next？？（哦，NULL）取消引用 NULL 指针（BOOM 段错误！）

正确地做你的循环列表。在插入第一个节点集时：

        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);
}

示例Use/Output

$ ./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');
}

循环链表显示时崩溃

Circular linked list crashes when displayed

c

data-structures

linked-list

circular-list