我正在编写一个程序，以确保我了解如何在 C 中正确实现单向链表。我目前正在哈佛的CS50课程中，并且使用本教程，因为CS50的人没有详细解释链表数据结构：https://www.youtube.com/watch?v=7Fz7JSvlr9g
代码似乎运行正常，但是当我使用 valgrind 检查它时，我收到"无效读取"和"无效写入"错误。
这是我的代码：
// 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 memoryn");
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");
}
这是瓦尔格林德的输出：
==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)
似乎这与我访问临时节点的方式有关，但我并不真正了解这个问题。
因为在create函数中，您可以释放刚刚添加到列表中的节点。
只需从函数中删除free(temp);即可。
变量名称temp在这里具有误导性。它根本不是一个临时节点。此变量的正确名称为newnode。
您应该再次阅读 C 教科书中有关动态内存分配的章节。
注1：顺便说一句：在视频中，您提到create功能没有free。
注意 2：请注意，这种用于创建列表的算法效率非常低。为了找到最后一个元素，整个列表是从头部遍历到最后一个元素。为了提高效率，您应该维护指向最后一个元素的指针。