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

Question

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

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

这是我对节点的定义:

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 session :

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
$1 = (node *) 0x22fdf0
(gdb) n
85          node* prevNode = NULL;
(gdb)
87          while (curNode != NULL)
(gdb) p *first
$2 = (node *) 0x0
(gdb) p curNode
$3 = (node *) 0x0
(gdb) n
116         if (prevNode == NULL)
(gdb)
119             *first = &myNode;
(gdb)
126     }
(gdb) p *first
$4 = (node *) 0x22fdf0
(gdb) n
main () at linked_list.c:52
52                      break;
(gdb)
66              printList(first);
(gdb) p first
$5 = (node *) 0x22fdf0
(gdb) p *first
$6 = {n = 1, next = 0x0}
(gdb) s
printList (ptr=0x22fdf0) at linked_list.c:200
200         printf("\nLIST IS NOW: ");
(gdb) p ptr
$7 = (node *) 0x22fdf0
(gdb) p *ptr
$8 = {n = 1, next = 0x0}
(gdb) n

LIST IS NOW: 202            while (ptr != NULL)
(gdb) p ptr
$9 = (node *) 0x22fdf0
(gdb) p *ptr
$10 = {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() 函数的中间确实发生了变化。这是怎么/为什么会发生？？？

Answer 1

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

node myNode;

如果函数离开了，内存就“消失了”。这意味着您无权访问它。但是你用

把它传回主上下文

*first      = &myNode;

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

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