C链表中的分段错误

vqlkdk9b  于 2023-10-16  发布在  其他
关注(0)|答案(4)|浏览(88)

我用C写了一段关于交换链表中相邻节点的代码,但由于分段错误,该代码无法在VSCode中运行。我不知道是什么原因造成的,代码在在线编译器上运行时输出正确。

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

typedef struct node
{
    int val;
    struct node *next;
} node;

void insert_end(node **head, int d)
{
    node *new_node = (node *)malloc(sizeof(node)), *temp;
    new_node->val = d;
    if (*head == NULL)
        *head = new_node;
    else
    {
        temp = *head;
        while (temp->next != NULL) //segmentation fault
            temp = temp->next;
        temp->next = new_node;
        new_node->next = NULL;
    }
}

node *swap(node **head)
{
    node *temp = (node *)malloc(sizeof(node));
    temp->next = *head;
    node *start = (*head)->next;
    while (temp->next != NULL && temp->next->next != NULL)
    {
        node *ptr1 = temp->next;
        node *ptr2 = temp->next->next;
        temp->next = ptr2;
        ptr1->next = ptr2->next;
        ptr2->next = ptr1;
        temp = ptr1;
    }

    return start;
}

void disp(node *head)
{
    while (head != NULL)
    {
        printf("%d\n", head->val);
        head = head->next;
    }
}

void main()
{
    int arr[] = { 1, 2, 3 };
    int size = sizeof(arr) / sizeof(arr[0]);
    node *head = NULL;

    for (int i = 0; i < size; i++)
    {
        insert_end(&head, arr[i]);
    }

    node *ptr = swap(&head);
    disp(ptr);
}
atmip9wb

atmip9wb1#

代码中存在多个问题:

  • 没有参数的main的原型应该是:
int main(void)
  • 在函数insert_end()中,当分配列表的第一个节点时,您不初始化temp->nextmalloc()不会初始化内存块,因此无法预测temp->next在分配后可能包含什么。这导致测试while (temp->next)while循环的第二次迭代中插入下一项时具有未定义的行为。根据具体情况,temp可能是空指针,问题不会发生(如在线编译器),或者temp可能包含无效指针,导致您在系统上观察到的分段错误。

始终将temp->next初始化为NULL,并检查潜在的分配失败。

void insert_end(node **head, int d) {
    node *new_node = malloc(sizeof(*new_node));
    if (new_node != NULL) {
        new_node->val = d;
        new_node->temp = NULL;
        if (*head == NULL) {
            *head = new_node;
        } else {
            node *temp = *head;
            while (temp->next != NULL)
                temp = temp->next;
            temp->next = new_node;
        }
    }
}
  • node *swap(node **head)函数应该实现什么是相当模糊的。其意图似乎是交换节点对。在任何情况下,都不需要分配新的node,并且根据编码,该节点不会被释放,并且可能会丢失。也不清楚为什么swap应该返回一个node *,它应该更新head指针。

下面是一个修改后的版本,它返回更新后的头节点。

node *swap(node **head) {
    node *first, *second;
    node **pp = head;
    while ((first = *pp) != NULL && (second = first->next) != NULL) {
        first->next = second->next;
        second->next = first;
        *pp = second;
        pp = &first->next;
    }
    return *head;
}
p8ekf7hl

p8ekf7hl2#

对于符合C标准的启动器,应将不带参数的函数main声明为

int main( void )

函数insert_end可以调用未定义的行为。
首先,它不会检查新节点是否已成功分配。其次,如果*head等于NULL,则新节点的数据成员next保持未初始化

if (*head == NULL)
    *head = new_node;

这就是为什么这个while循环

while (temp->next != NULL) //segmentation fault
        temp = temp->next;

产生分段故障。
请注意,在单链表的尾部添加新节点是低效的。在这种情况下,最好定义一个双边单链表。
函数swap的返回类型node *令人困惑。由于函数通过指向头节点的指针的引用来接受指向头节点的指针,因此假设在调用函数之后,指向头节点的指针将在函数内正确地更新,这在逻辑上是正确的。
但主要问题是在函数中分配额外的节点

node *temp = (node *)malloc(sizeof(node));

这会导致内存泄漏。该函数不应分配任何节点。
这份声明

node *start = (*head)->next;

可以为空列表调用未定义的行为。你需要检查 *head是否等于NULL
你也应该把这个函数分成两个函数。这将使你的代码更加清晰和可读。main函数将遍历列表,其他函数将交换两个相邻的节点。
另外,如果使用全名display而不是缩写名称disp,则代码将更具可读性。至少函数参数应该用限定符const声明,因为在函数中传递的列表不会被改变。

void disp(const node *head);

您还需要一个函数,当不再需要列表时,它将释放列表的所有已分配内存。
下面是一个演示程序,展示了如何声明和定义上述函数。

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

typedef struct node
{
    int val;
    struct node *next;
} node;

int insert_end( node **head, int val )
{
    node *new_node = malloc( sizeof( *new_node ) );
    int success = new_node != NULL;

    if (success)
    {
        new_node->val  = val;
        new_node->next = NULL;

        while( *head != NULL ) head = &( *head )->next;

        *head = new_node;
    }

    return success;
}

FILE *display( const node *head, FILE *fp )
{
    for (; head != NULL; head = head->next)
    {
        fprintf( fp, "%d -> ", head->val );
    }

    fputs( "null", fp );

    return fp;
}

void swap_adjacent_nodes( node **head )
{
    node *current = *head;
    *head = ( *head )->next;

    current->next = ( *head )->next;
    ( *head )->next = current;
}

void swap_node_pairs( node **head )
{
    for ( ; *head && ( *head )->next; head = &( *head )->next->next )
    {
        swap_adjacent_nodes( head );
    }
}

void clear( node **head )
{
    while( *head )
    {
        node *current = *head;
        *head = ( *head )->next;
        free( current );
    }
}

int main( void )
{
    node *head = NULL;

    insert_end( &head, 1 );

    fputc( '\n', display( head, stdout ) );

    swap_node_pairs( &head );
    fputc( '\n', display( head, stdout ) );

    putchar( '\n' );

    insert_end( &head, 2 );

    fputc( '\n', display( head, stdout ) );

    swap_node_pairs( &head );
    fputc( '\n', display( head, stdout ) );

    putchar( '\n' );

    insert_end( &head, 3 );

    fputc( '\n', display( head, stdout ) );

    swap_node_pairs( &head );
    fputc( '\n', display( head, stdout ) );

    putchar( '\n' );

    insert_end( &head, 4 );

    fputc( '\n', display( head, stdout ) );

    swap_node_pairs( &head );
    fputc( '\n', display( head, stdout ) );

    putchar( '\n' );

    free( head );
}

程序输出为

9rbhqvlz

9rbhqvlz3#

考虑您的insert_end函数,您发现分段错误发生。

void insert_end(node **head, int d)
{
    node *new_node = (node*)malloc(sizeof(node)), *temp;
    new_node->val = d;
    if (*head == NULL)
        *head = new_node;
    else
    {
        temp = *head;
        while (temp->next != NULL) //segmentation fault
            temp = temp->next;
        temp->next = new_node;
        new_node->next = NULL;
    }
}
  • 你用mallocnode分配内存(你不应该在C中强制转换malloc的结果,这与C++不同)。
  • 初始化val
  • 你不初始化next。这不能假定为NULL

如果它不是NULL,那么你的循环会给temp分配一个随机地址,然后temp->next解引用这个随机地址。未定义的行为可能会引发错误,但很可能是分段错误,这就是您遇到的问题。
为了解决这个问题,根据评论,你有两个选择:

  • 使用calloc分配,将所有内存分配给0
  • new_node->next初始化为NULL
qlckcl4x

qlckcl4x4#

第1步:使用警告和调试符号编译:

$ gcc tt.c -Wall -Wextra -Werror -g
tt.c:53:6: error: return type of ‘main’ is not ‘int’ [-Werror=main]
   53 | void main()
      |      ^~~~
cc1: all warnings being treated as errors

第二步和第三步:解决这个问题,然后运行valgrind

$ valgrind ./a.out
==5607== Memcheck, a memory error detector
==5607== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5607== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==5607== Command: ./a.out --leak-check=full
==5607== 
==5607== Conditional jump or move depends on uninitialised value(s)
==5607==    at 0x1091F0: insert_end (tt.c:19)
==5607==    by 0x10935B: main (tt.c:61)
==5607==

第4步:第19行(你标记的那个)中的一个未初始化的变量似乎有问题。别这样初始化变量。
第五步:你也会泄漏内存。但可能你还没有到那个地步。
通过静态代码分析工具可以获得更多的见解,如clang-tidy

$ clang-tidy tt.c
Error while trying to load a compilation database:
Could not auto-detect compilation database for file "tt.c"
No compilation database found in /home/moooeeeep or any parent directory
fixed-compilation-database: Error while opening fixed database: No such file or directory
json-compilation-database: Error while opening JSON database: No such file or directory
Running without flags.
3 warnings generated.
/home/moooeeeep/tt.c:19:27: warning: The left operand of '!=' is a garbage value [clang-analyzer-core.UndefinedBinaryOperatorResult]
        while (temp->next != NULL) //segmentation fault
                          ^
/home/moooeeeep/tt.c:59:5: note: Loop condition is true.  Entering loop body
    for (int i = 0; i < size; i++)
    ^
/home/moooeeeep/tt.c:61:9: note: Calling 'insert_end'
        insert_end(&head, arr[i]);
        ^
/home/moooeeeep/tt.c:12:29: note: Uninitialized value stored to field 'next'
    node *new_node = (node*)malloc(sizeof(node)), *temp;
                            ^
/home/moooeeeep/tt.c:14:5: note: Taking true branch
    if (*head == NULL)
    ^
/home/moooeeeep/tt.c:61:9: note: Returning from 'insert_end'
        insert_end(&head, arr[i]);
        ^
/home/moooeeeep/tt.c:59:5: note: Loop condition is true.  Entering loop body
    for (int i = 0; i < size; i++)
    ^
/home/moooeeeep/tt.c:61:9: note: Calling 'insert_end'
        insert_end(&head, arr[i]);
        ^
/home/moooeeeep/tt.c:14:5: note: Taking false branch
    if (*head == NULL)
    ^
/home/moooeeeep/tt.c:19:27: note: The left operand of '!=' is a garbage value
        while (temp->next != NULL) //segmentation fault
                          ^
/home/moooeeeep/tt.c:41:12: warning: Potential leak of memory pointed to by 'temp' [clang-analyzer-unix.Malloc]
    return start;
           ^
/home/moooeeeep/tt.c:28:25: note: Memory is allocated
    node *temp = (node*)malloc(sizeof(node));
                        ^
/home/moooeeeep/tt.c:31:18: note: Field 'next' is not equal to NULL
    while (temp->next != NULL && temp->next->next != NULL)
                 ^
/home/moooeeeep/tt.c:31:12: note: Left side of '&&' is true
    while (temp->next != NULL && temp->next->next != NULL)
           ^
/home/moooeeeep/tt.c:31:34: note: Assuming field 'next' is equal to NULL
    while (temp->next != NULL && temp->next->next != NULL)
                                 ^
/home/moooeeeep/tt.c:31:5: note: Loop condition is false. Execution continues on line 41
    while (temp->next != NULL && temp->next->next != NULL)
    ^
/home/moooeeeep/tt.c:41:12: note: Potential leak of memory pointed to by 'temp'
    return start;
           ^
/home/moooeeeep/tt.c:53:1: warning: return type of 'main' is not 'int' [clang-diagnostic-main-return-type]
void main()
^
/home/moooeeeep/tt.c:53:1: note: change return type to 'int'
void main()
^~~~
int

只要一个接一个地解决任何问题,直到你修复了所有的警告。

相关问题