为什么我使用以下代码从 valgrind 获得 "invalid read" 和 "invalid write"？

Question

我正在编写一个程序以确保我了解如何在 C 中正确实现单链表。我目前正在哈佛的 CS50 课程中学习，并且使用本教程，因为 CS50 的人不解释链表数据结构详解：https://www.youtube.com/watch?v=7Fz7JSvlr9g

代码似乎运行正常，但是当我使用 valgrind 检查它时出现 "invalid read" 和 "invalid write" 错误。

这是我的代码：

// creating and using a singly linked list in C

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

// create structure for nodes
typedef struct sllist
{
    int val;
    struct sllist *next;
}
sllnode;

// function declarations
sllnode *create(int sz);
void display(sllnode *head);

int main(void)
{
    // declare head node and set to NULL
    sllnode *head = NULL;

    // prompt for size of list
    printf("how many numbers would you like to store? ");
    int sz;
    scanf("%i", &sz);

    // create linked list (create passes head pointer back to head)
    head = create(sz);
    // display linked list
    display(head);
}

// function for creating a linked list
sllnode *create(int sz)
{
    // initialize head pointer to NULL
    sllnode *head = NULL;
    // initialize temp pointer (for creating new nodes in the upcoming for loop)
    sllnode *temp = NULL;
    // initialize p for iterating through the list
    sllnode *p = NULL;

    for (int i = 0; i < sz; i++)
    {
        // allocate space for individual node
        temp = (sllnode *)malloc(sizeof(sllnode));

        // check to make sure we haven't run out of memory
        if (temp == NULL)
        {
            printf("Couldn't allocate memory\n");
            exit(1);
        }

        // prompt user for value to store
        printf("enter the value #%i: ", i + 1);
        scanf("%i", &(temp->val));

        // intialize temp's next pointer to NULL
        temp->next = NULL;

        // if running first time (linked list is empty) temp becomes the head node
        if (head == NULL)
        {
            head = temp;
        }
        // if the loop has run a few times (list not empty)
        else
        {
            // start at the head
            p = head;
            // iterate through the list to find the last node
            while (p->next != NULL)
            {
                p = p->next;
            }
            // set that node's pointer to the new node
            p->next = temp;
        }
        free(temp);
    }
    // give the head pointer back to main
    return head;
}

// function for displaying the linked list
void display(sllnode *head)
{
    // initialize pointer p to head (coming from main)
    sllnode *p = head;

    // iterate through the list, printing a new value each time
    while(p != NULL)
    {
        printf("%i -> ", p->val);
        p = p->next;
    }
    printf("\n");
}

这是 valgrind 的输出：

==4407== Memcheck, a memory error detector
==4407== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==4407== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==4407== Command: ./ll0
==4407== 
how many numbers would you like to store? 2
enter the value #1: 1
enter the value #2: 6
==4407== Invalid read of size 8
==4407==    at 0x4209DA: create (ll0.c:74)
==4407==    by 0x420713: main (ll0.c:29)
==4407==  Address 0x6183048 is 8 bytes inside a block of size 16 free'd
==4407==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4407==    by 0x420B73: create (ll0.c:81)
==4407==    by 0x420713: main (ll0.c:29)
==4407== 
==4407== Invalid write of size 8
==4407==    at 0x420B65: create (ll0.c:79)
==4407==    by 0x420713: main (ll0.c:29)
==4407==  Address 0x6183048 is 8 bytes inside a block of size 16 free'd
==4407==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4407==    by 0x420B73: create (ll0.c:81)
==4407==    by 0x420713: main (ll0.c:29)
==4407== 
==4407== Invalid read of size 4
==4407==    at 0x420CAA: display (ll0.c:96)
==4407==    by 0x420720: main (ll0.c:31)
==4407==  Address 0x6183040 is 0 bytes inside a block of size 16 free'd
==4407==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4407==    by 0x420B73: create (ll0.c:81)
==4407==    by 0x420713: main (ll0.c:29)
==4407== 
1 -> ==4407== Invalid read of size 8
==4407==    at 0x420D62: display (ll0.c:97)
==4407==    by 0x420720: main (ll0.c:31)
==4407==  Address 0x6183048 is 8 bytes inside a block of size 16 free'd
==4407==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4407==    by 0x420B73: create (ll0.c:81)
==4407==    by 0x420713: main (ll0.c:29)
==4407== 
6 -> 
==4407== 
==4407== HEAP SUMMARY:
==4407==     in use at exit: 0 bytes in 0 blocks
==4407==   total heap usage: 2 allocs, 2 frees, 32 bytes allocated
==4407== 
==4407== All heap blocks were freed -- no leaks are possible
==4407== 
==4407== For counts of detected and suppressed errors, rerun with: -v
==4407== ERROR SUMMARY: 6 errors from 4 contexts (suppressed: 0 from 0)

好像和我访问临时节点的方式有关，但我不太明白这个问题。

Answer 1

因为在 create 函数中，您释放了刚刚添加到列表中的节点。

只需从函数中删除 free(temp);。

变量名 temp 在这里具有误导性。它根本不是一个临时节点。此变量的正确名称应为 newnode.

你应该再读一遍你的 C 教科书中关于动态内存分配的章节。

注意 1： 顺便说一句：在您提到的视频中，create 函数中没有 free。

注 2： 请注意，此创建列表的算法效率极低。为了找到最后一个元素，整个列表从头部遍历到最后一个元素。为了提高效率，您应该维护指向最后一个元素的指针。

为什么我使用以下代码从 valgrind 获得 "invalid read" 和 "invalid write"？

Why am I getting "invalid read" and "invalid write" from valgrind with the following code?

c

valgrind

linked-list

singly-linked-list

cs50