递归打印链表时出现分段错误

Question

我用 C 编写了一个链表（使用 gcc 编译器）并尝试递归打印它。它告诉 "segmentation fault"，也只打印第一个值。谁能建议一个选项来纠正它..？这是我的代码。

#define MAX 10
#include <stdio.h>
#include <stdlib.h>
struct node {
    int value;
    struct node *next;
};

void printRecursively(struct node *start) {
    if (start != NULL) {
        printf("%d\n", start->value);
        start = start->next;
        printRecursively(start);
    }
}

void main() {
    struct node *nodes[MAX];
    for (int i = 0; i < MAX; i++) {
        nodes[i] = malloc(sizeof(struct node));
        nodes[i]->value = i + 1;
        nodes[i]->next = nodes[i + 1];
    }
    printRecursively(nodes[0]);
}

Answer 1

你正在创建一个节点，并告诉他指向节点[i+1]，但是节点[i+1]还没有初始化，所以它等于 nodes[i]->next = garbage

Answer 2

您的代码将每个新分配代码的 next 指针初始化为未初始化的值。运行向后循环并确保将 ast 节点的 next 指针初始化为 NULL.

int main(void) {
    struct node *nodes[MAX];
    for (int i = MAX; i-- > 0;) {
        nodes[i] = malloc(sizeof(struct node));
        nodes[i]->value = i + 1;
        nodes[i]->next = (i == MAX - 1) ? NULL : nodes[i + 1];
    }
    printRecursively(nodes[0]);

    /* for good style, free the allocated memory */
    for (int i = 0; i < MAX; i++) {
        free(nodes[i]);
    }
    return 0;
}

如您所述，有一个简单的解决方案，增加索引值并检查内存分配失败：

int main(void) {
    struct node *nodes[MAX];
    for (int i = 0; i < MAX; i++) {
        nodes[i] = malloc(sizeof(struct node));
        if (nodes[i] == NULL) {
            fprintf(stderr, "memory allocation failure\n");
            exit(1);
        }
        nodes[i]->value = i + 1;
        nodes[i]->next = NULL;
        if (i > 0) {
            nodes[i - 1]->next = nodes[i];
        }
    }
    printRecursively(nodes[0]);

    /* for good style, free the allocated memory */
    for (int i = 0; i < MAX; i++) {
        free(nodes[i]);
    }
    return 0;
}

Answer 3

您的代码存在三个问题。

第一个是当您创建节点时 nodes[i] nodes[i+1] 具有不确定的值。

因此这个声明

nodes[i]->next = nodes[i + 1];

当您尝试使用数据成员 next.

访问节点时会导致未定义的行为

第二个是当索引i等于MAX-1时循环尝试访问数组之外的内存。

第三个是你没有将最后一个节点的数据成员next设置为NULL。

要解决这些问题，您应该使用 MAX+! 个元素声明数组并从数组末尾开始分配节点。

另外你应该释放所有分配的内存。

并且根据 C 标准，不带参数的函数 main 应声明为

int main( void )

程序可以这样看

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

struct node
{
    int value;
    struct node *next;
};

void printRecursively( struct node *start )
{
    if ( start != NULL )
    {
        printf( "%d ", start->value );
        printRecursively( start->next );
    }
}

int main(void) 
{
    struct node * nodes[MAX + 1];

    int i = MAX;
    nodes[i] = NULL;

    for ( ; i != 0; i-- )
    {
        nodes[i-1] = malloc( sizeof( struct node ) );
        nodes[i-1]->value = i;
        nodes[i-1]->next = nodes[i];
    }

    printRecursively( nodes[0] );

    for ( i = 0; i < MAX; i++ ) free( nodes[i] );

    return 0;
}

程序输出为

1 2 3 4 5 6 7 8 9 10

Answer 4

以下建议代码：

干净地编译
执行所需的功能
不执行任何未定义的行为
合并对 OP 问题的评论

现在，建议代码：

#define MAX 10
#include <stdio.h>
#include <stdlib.h>


struct node
{
    int value;
    struct node *next;
};


void printRecursively(struct node *start)
{
    if (start != NULL)
    {
        printf("%d\n", start->value);
        start = start->next;
        printRecursively(start);
    }
} // end function: printRecursively


int main( void )
{
    struct node *nodes[MAX] = { NULL };

    for (int i = 0; i < MAX; i++)
    {
        nodes[i] = malloc(sizeof(struct node));
        nodes[i]->value = i + 1;
        nodes[i]->next = NULL;

        if( i > 0 )
        {
            nodes[ i-1 ]->next = nodes[i];
        }
    }

    printRecursively(nodes[0]);
} // end function: main

以上代码的执行结果如下：

递归打印链表时出现分段错误

Segmentation Fault when printing a linked list recursively

c

recursion

pointers

linked-list

singly-linked-list