C - 链表中的节点以某种方式修改，导致分段错误

Question

我正在学习 C 中的链表和指针，并且正在尝试实现一个简单的程序，让用户可以在整数的（单）链表中插入、删除或搜索整数。当我尝试插入数字时，我相当确定我的插入功能正常工作。

但是，我有一个将列表打印到终端的函数，在该函数的执行过程中，插入的节点以某种方式被修改，因此它的整数 ('n') 变成了一些垃圾值，它的 'next' 指针被更改为指向它自己！然后 print 函数继续打印这个节点的 'n' 值，因为它的 'next' 指针总是指向它自己，但是 'n' 值不断变化，在第三次迭代时我得到一个段错误（见 gdb会话在底部）。

这是我对节点的定义：

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

这是我的主要功能：

int main(void)
{
    // declare a linked list
    node* first = NULL;

    int command;
    int n;

    while (true)
    {
        printf("MENU\n\n");

        printf("1 - delete\n");
        printf("2 - insert\n");
        printf("3 - search\n");
        printf("0 - quit\n\n");

        printf("Enter a command: ");
        scanf("%i", &command);

        switch(command)
        {
            case 0:
                printf("Hope u had fun (:\n");
                return 0;
            case 1:
                printf("Number to delete: ");
                scanf("%i", &n);
                deleteNode(n, &first);
                break;
            case 2:
                printf("Number to insert: ");
                scanf("%i", &n);
                insertNode(n, &first);
                break;
            case 3:
                printf("Number to search for: ");
                scanf("%i", &n);
                if (searchList(n, first))
                {
                    printf("Found %i in list!\n", n);
                }
                else
                {
                    printf("Did not find %i in list :(\n", n);
                }
        }

        printList(first);
    }
}

这是我的 insertNode() 函数：

void insertNode(int n, node** first)
{
    // declare our new node
    node myNode;
    myNode.n = n;
    myNode.next = NULL;

    // initialize curNode to a pointer to the first node in the list
    node* curNode = *first;

    // initialize a pointer that will point to the previous node in the list if we need it
    node* prevNode = NULL;

    while (curNode != NULL)
    {
        if (n <= curNode->n)
        {
            // if prevNode is null, there's one element in the list
            // and we're inserting before it (i.e. at first position)
            if (prevNode == NULL)
            {
                *first      = &myNode;
                myNode.next = curNode;
                return;
            }
            // else, we're inserting between prevNode and curNode
            else
            {
                prevNode->next = &myNode;
                myNode.next    = curNode;
                return;
            }
        }
        // if n > curNode->n, move on to next node
        else
        {
            curNode  = curNode->next;
            prevNode = curNode;
        }
    }

    // curNode is null down here, so we're either at the end of the list, or the list is empty
    if (prevNode == NULL)
    {
        // empty list, only have to update first
        *first = &myNode;
    }
    else
    {
        // end of the list, only have to update previous node
        prevNode->next = &myNode;
    }
}

这是我的 printList() 函数：

void printList(node* ptr)
{
    printf("\nLIST IS NOW: ");

    while (ptr != NULL)
    {
        printf("%i ", ptr->n);
        ptr = ptr->next;
    }
    printf("\n\n");
}

这是一个说明错误的 gdb 会话：

35              printf("Enter a command: ");
(gdb)
Enter a command: 36             scanf("%i", &command);
(gdb)
2
38              switch(command)
(gdb) n
49                      printf("Number to insert: ");
(gdb)
Number to insert: 50                    scanf("%i", &n);
(gdb)
1
51                      insertNode(n, &first);
(gdb) s
insertNode (n=1, first=0x22fe48) at linked_list.c:78
78          myNode.n = n;
(gdb) n
79          myNode.next = NULL;
(gdb)
82          node* curNode = *first;
(gdb) p &myNode
 = (node *) 0x22fdf0
(gdb) n
85          node* prevNode = NULL;
(gdb)
87          while (curNode != NULL)
(gdb) p *first
 = (node *) 0x0
(gdb) p curNode
 = (node *) 0x0
(gdb) n
116         if (prevNode == NULL)
(gdb)
119             *first = &myNode;
(gdb)
126     }
(gdb) p *first
 = (node *) 0x22fdf0
(gdb) n
main () at linked_list.c:52
52                      break;
(gdb)
66              printList(first);
(gdb) p first
 = (node *) 0x22fdf0
(gdb) p *first
 = {n = 1, next = 0x0}
(gdb) s
printList (ptr=0x22fdf0) at linked_list.c:200
200         printf("\nLIST IS NOW: ");
(gdb) p ptr
 = (node *) 0x22fdf0
(gdb) p *ptr
 = {n = 1, next = 0x0}
(gdb) n

LIST IS NOW: 202            while (ptr != NULL)
(gdb) p ptr
 = (node *) 0x22fdf0
(gdb) p *ptr
 = {n = 4210908, next = 0x22fdf0}
(gdb) n
204             printf("%i ", ptr->n);
(gdb)
4210908 205             ptr = ptr->next;
(gdb)
202         while (ptr != NULL)
(gdb)
204             printf("%i ", ptr->n);
(gdb)
1397312522 205          ptr = ptr->next;
(gdb)
202         while (ptr != NULL)
(gdb)
204             printf("%i ", ptr->n);
(gdb)

Program received signal SIGSEGV, Segmentation fault.
0x0000000000401864 in printList (ptr=0x2500203a574f4e20) at linked_list.c:204
204             printf("%i ", ptr->n);

正如您在上面看到的，节点在 printList() 函数的中间确实发生了变化。 How/why 是这样吗？？？

Answer 1

节点我的节点； in insertnode 可能一遍又一遍地指向相同的内存尝试使用 malloc 代替，以便保证插入节点的每个实例都是唯一的内存位置。

Answer 2

我没有仔细查看您写的每一行，就注意到您没有为列表动态分配内存。在 insertNode 函数中，您定义了一个元素，该元素将驻留在堆栈中：

node myNode;

如果保留函数，内存为"gone"。这意味着您无权访问它。但是你用

把它传回主上下文

*first      = &myNode;

函数必须自己分配内存（例如使用 malloc）。为了使函数更简单，不要将双指针传递给该函数。

相反，delteNode函数必须将内存还给操作系统（例如free）。同样在这里：不要传递指针的地址，而只是应该删除元素的位置（指针）。

Answer 3

函数 insertNode 至少是错误的，因为它使用指向局部变量 myNode 的指针将其包含在列表中，尽管这个局部变量将在退出函数后被销毁并且指针将是无效。

那是函数有未定义的行为。

而且太复杂了

可以这样写。考虑到第一个参数应该是 "list"，添加的数字应该是第二个参数。否则就是一种糟糕的编程风格。

void insertNode( node** first, int n )
{
    node *tmp = malloc( sizeof( node ) );
    tmp->n = n;

    if ( *first == NULL || n < ( *first )-> n )
    {
        tmp->next = *first;
        *first = tmp;
    }
    else
    {
        node *current = *first;
        while ( current->next != NULL && !( n < current->n ) ) current = current->next;

        tmp->next = current->next;
        current->next = tmp;
    }
}

Answer 4

在您的 insertNode() 函数中，您使用的是局部变量的地址。

// 声明我们的新节点

node myNode;

。 .

if (prevNode == NULL)

{

    // empty list, only have to update first
    first = &myNode;  // Trying to assign address of a local variable

}

一旦函数 over.Never 执行此操作，"myNode" 的内存就会被释放。

相反，尝试为 myNode 动态分配内存。

node * myNode =NULL;

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

myNode->n = n;

myNode->next = NULL;

在分配 myNode 时，

*first = myNode;

局部变量的内存分配在堆栈上，它的生命周期只到函数执行。

当您尝试获取存储在那里的值时，您很可能会遇到分段错误。

C - 链表中的节点以某种方式修改，导致分段错误

C - Node in a linked list somehow modified, results in segmentation fault

c

pointers

linked-list