c - 释放c中的内存并出现未知错误，free(&p->data) 不起作用

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("1\n");
            deallocate (p->y);
            printf("2\n");
            deallocate (p->z);
            printf("3\n");
            free(&p->data);
            printf("4\n");
            push (&head, p);
            printf("5\n");
        }
    }

}

但是我的程序只打印出 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 解决方案的更多信息，请参阅 this post):

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

Google 快速搜索得出 this示例实现。如果您有大量节点，请考虑使用 Judy 数组。还有无数其他的，可能更有效。