C中的空闲内存并得到未知错误，免费(&p->数据)不起作用

Question

我这里有一个节点结构：

struct N *mknode(struct N *xp, struct N *yp, struct N *zp, long n)
{
struct N *p = malloc(sizeof(struct N));
p->x = xp;
p->y = yp;
p->z = zp;
p->data = n;
return p;
}

我的任务是精确释放每个节点一次，这样既没有双重释放也没有内存泄漏

而且我的代码只能包含stdlib.h和"freegraph.h"，我放stdio.h是因为我需要使用printf函数来显示哪一行代码不起作用

#include <stdlib.h>
#include "freegraph.h"
#include <stdio.h>
// construct a linked list
typedef struct node {
struct N * val;
struct node * next;
} node_t;
typedef enum { false, true } bool;
node_t head = { NULL, NULL };

// check if any duplicated in the linked list
bool check_duplicate (node_t * head, struct N * val) {
bool duplicate = false;
node_t * current = head;
while (current != NULL) {
if ( current->val == val) {
duplicate = true;
return duplicate;
}
else {
current = current->next;
}
}
return duplicate;
}
// adding an item to the end of the linked list
void push (node_t * head, struct N * val) {
node_t * current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = malloc(sizeof(node_t));
current->next->val = val;
current->next->next = NULL;
}
//deallocate recursive function, printf to see which line is working
void deallocate(struct N *p)
{
if (p != NULL) {
if (!check_duplicate(&head, p)) {
deallocate (p->x);
printf("1n");
deallocate (p->y);
printf("2n");
deallocate (p->z);
printf("3n");
free(&p->data);
printf("4n");
push (&head, p);
printf("5n");
}
}

}

但是我的程序只打印出 1,2,3，然后它会停止并退出。 所以我假设free(&p->data)不起作用，但我真的不知道我做错了什么。

这是我的测试代码：

p1 = mknode(NULL, NULL, NULL, 1);
p2 = mknode(NULL, NULL, NULL, 10);
p3 = mknode(NULL, NULL, NULL, 100);
p4 = mknode(p1, p2, p3, 3000);
p1 = mknode(NULL, NULL, NULL, 1);
p2 = mknode(NULL, NULL, NULL, 10);
p3 = mknode(NULL, NULL, NULL, 100);
p5 = mknode(p1, p2, p3, 4000);
p5 = mknode(p4, p5, NULL, 50000);
p6 = mknode(p5, NULL, NULL, 100000);
// now make it harder by sharing and cycles
p1->x = p5;
p2->y = p4;
p2->z = p2;
p6->y = p5;
p6->z = p6; 
deallocate(p6);

Answer 1

鉴于不能对提供的函数和数据类型进行其他修改，有效解决此问题所需的(抽象)数据结构是一个集合。它们始终只包含每个唯一元素的一个副本。

程序：

• 创建空集
• 在给定的起始节点上执行递归深度优先搜索
• 对于访问的每个节点，如果集合包含递归，请停止递归，否则将其添加到集合中并继续
• 递归完全完成后，在集合中的每个节点上调用free(不对其子指针执行任何操作)

C 风格的伪代码：

static void dealloc_recursive(struct N *p, Set* s)
{
if (p == NULL) return;
if (set_contains(s, p)) return;
dealloc_recursive(p->x, s);
dealloc_recursive(p->y, s);
dealloc_recursive(p->z, s);
}
void deallocate(struct N *p)
{
Set* set = set_create_empty();
dealloc_recursive(p, set);
for (struct N *p in set)
free(p);
set_destroy(set);
}

两种常见的集合类型浮现在脑海中(存在于Java的库中;有关C解决方案的更多信息，请参阅这篇文章)：

• 哈希集：哈希表。包含查询是(摊销的)常量时间。可能会使用更多内存来解决冲突和链接问题。
树
• 集：(平衡的)二叉搜索树(通常)。包含查询是对数时间。为节点元数据使用固定百分比的内存。

快速的谷歌搜索会产生此示例实现。如果您有非常多的节点，请考虑使用Judy 数组。还有无数其他的，可能更有效率。