C语言 免费链表

Question

我有一个链表，我想删除它的所有节点。问题是，如果我调用删除，它只会打印出 1，然后冻结。我读过其他一些类似的问题，但我不知道为什么会这样。我想我只是瞎子什么的。

#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
int id;
struct _node *next;
} *node;
typedef struct {
node first;
} *head;
head newHead(node n) {
head h = malloc(sizeof(node));
h->first = n;
return h;
}
node newNode(int id) {
node n = malloc(sizeof(node));
n->id = id;
n->next = NULL;
return n;
}
void delete(head h) {
if(h->first == NULL) return;
node current = h->first;
while(current != NULL) {
printf("%i", current->id);
node tmp = current;
current = current->next;
free(tmp);
}
// free(h);
}
int main() {
node n = newNode(1);
head h = newHead(n);
node n2 = newNode(2);
node n3 = newNode(3);
node n4 = newNode(4);
n->next = n2;
n2->next = n3;
n3->next = n4;
printf("%i", h->first->id);
printf("%i", h->first->next->id);
printf("%i", h->first->next->next->id);
printf("%i", h->first->next->next->next->id);
delete(h);
return 0;
}

Answer 1

head h = malloc(sizeof(node));

为结构分配了错误的大小;您可能打算head h = malloc(sizeof(head));。使用some_type *foo = malloc(sizeof(*foo))可以帮助避免此类错误。

除此之外，还有修剪代码的空间。我没有看到head抽象增加任何价值;这是一个额外的间接层。

if(h->first == NULL) return;

也是多余的，因为循环将处理这种情况。

请不要键入定义指针。这使得代码很难遵循，如果没有变量旁边的显式*。 实际上，我会更进一步，也不会对结构进行类型定义。抑制有用信息会损害可读性。

#include <stdio.h>
#include <stdlib.h>
struct node {
int id;
struct node *next;
};
struct node *make_node(int id) {
struct node *n = malloc(sizeof(*n));
n->id = id;
n->next = NULL;
return n;
}
void free_linked_list(struct node *head) {
while (head) {
struct node *tmp = head;
head = head->next;
free(tmp);
}
}
int main() {
struct node *head = make_node(1);
head->next = make_node(2);
head->next->next = make_node(3);
printf("%d, ", head->id);
printf("%d, ", head->next->id);
printf("%dn", head->next->next->id);
free_linked_list(head);
return 0;
}

Answer 2

在函数newNode中，您分配的内存大小无效

node n = malloc(sizeof(node));
^^^^ 

也就是说，您不是为struct _node类型的对象分配内存，而是为指向类型为struct _node *的此类对象的指针分配内存。

你需要写

node n = malloc(sizeof(struct _node));

'

并且您需要释放指针指向的内存h.

delete可能看起来像

void delete( head *h ) 
{
for ( node current = ( *h )->first; current != NULL; ) 
{
printf("%i", current->id);
node tmp = current;
current = current->next;
free( tmp );
}
free( *h );
*h = NULL;
}

并被称为喜欢

delete( &h );

在这种情况下，退出函数后，指针h将等于NULL。

这是您更新的程序。

#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
int id;
struct _node *next;
} *node;
typedef struct {
node first;
} *head;
head newHead(node n) {
head h = malloc(sizeof(node));
h->first = n;
return h;
}
node newNode(int id) {
node n = malloc(sizeof(struct _node));
n->id = id;
n->next = NULL;
return n;
}
void delete( head *h ) 
{
for ( node current = ( *h )->first; current != NULL; ) 
{
printf("%i", current->id);
node tmp = current;
current = current->next;
free( tmp );
}
free( *h );
*h = NULL;
}
int main() {
node n = newNode(1);
head h = newHead(n);
node n2 = newNode(2);
node n3 = newNode(3);
node n4 = newNode(4);
n->next = n2;
n2->next = n3;
n3->next = n4;
printf("%i", h->first->id);
printf("%i", h->first->next->id);
printf("%i", h->first->next->next->id);
printf("%in", h->first->next->next->next->id);
delete( &h );
return 0;
}

它的输出是

1234
1234

输出的第二行包含来自函数delete的测试消息。

Answer 3

现在它可以工作了，我不得不改变这个：

n->next = n2;
n2->next = n3;
n3->next = n4;

对此：

h->first->next = n2;
h->first->next->next = n3;
h->first->next->next->next = n4;