链表中的节点不知何故被修改，导致分段错误

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("MENUnn");
        printf("1 - deleten");
        printf("2 - insertn");
        printf("3 - searchn");
        printf("0 - quitnn");
        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("nn");
}

下面是一个说明这个bug的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
$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;

如果函数是左的，内存是"gone"。这意味着不允许您访问它。但是你用

将它传递回主上下文

*first      = &myNode;

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

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

Answer 2

节点myNode;在insertnode可能会反复指向相同的内存中，尝试使用malloc来代替，这样插入的节点的每个实例都保证是一个唯一的内存位置。

Answer 3

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

即函数具有未定义行为。

而且它太复杂了。

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

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()函数中使用了一个局部变量的地址。

//声明新节点

节点myNode;

。.

if (prevNode == NULL)

{

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

}

一旦函数结束，"myNode"的内存将被释放。千万不要这样做。

为myNode尝试动态内存分配。

node * myNode =NULL;

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

myNode->n = n;

myNode->next = NULL;

当分配myNode时，

*first = myNode;

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

当你试图获取存储在那里的值时，很有可能你会得到一个分段错误。