1

我相信你们中的一些人已经经历过。我有两个不同类型的链表,我有两个不同的函数来释放它们使用的内存。这两个功能是相同的,除了一件事。

通常,释放列表的函数如下所示:

void free_list(T *p)
{
    T *next;    /* here */
    while (p != NULL) {
        next = p->next;
        free(p);
        p = next;
    }
}

T节点类型在哪里。这些功能之间的唯一区别是标记线。
有没有办法编写一个函数/宏来获取指向任何链表头部的指针并释放它?

我尝试了几个想法,但我会从你那里放过它们,因为它们是错误的和失败的,而不是给细节带来负担。

4

7 回答 7

3

您可以创建一个结构,如

struct my_item
{
    void * item; // put pointer to your generic item here
    struct my_item * next; // NULL = end of list
};

然后有功能

void free_my_list (struct my_item * first)
{
    struct my_item * cur = first;
    while (cur != NULL)
    {
         cur = cur->next;
         free(cur->item);
         free(cur);
    }
}
于 2009-07-30T13:17:21.280 回答
3

鉴于“C”的局限性,我的第一个镜头将是一个类似的宏

#define FREE_LIST(T, p)\
do {\
    T *next;\
    while (p != NULL) {\
        next = p->next;\
        free(p);\
        p = next;\
    }\
} while(0)

即您必须在 1990 年左右(在模板之前)编写 C++ 通用代码的方式。


(编辑)历史注释——对于病态的好奇,Dewhurst & Stark Programming in C++试图成为 C++ 的一种 K&R,详细介绍了如何使用宏来模拟(在撰写本文时仍是推测性的)模板我们现在喜欢的行为。大多数原则将自然地向后移植到“C”。

于 2009-07-30T13:17:23.167 回答
1

如果您的所有 Node 结构都使用 'next' 指针作为第一个“成员”声明,这样:

struct _Node{
    struct _Node *next;
    /* more data */
};

那么你可以有这样的功能

void free_list(void *p)
{
    void *next;
    while (p != NULL) {
        /*getting the content of the first field, assuming that
          sizeof(void*)==sizeof(unsigned long)*/
        next = (void*)*((unsigned long*)p); 
        free(p);
        p = next;
    }
}

通过这种方式,您可以调用free_list(head_of_list)任何遵循此模式的列表。

于 2009-07-30T13:26:47.777 回答
1

只要您的所有节点类型都以 next 指针开头,您就可以创建一个通用的释放函数,如下所示:

struct generic_node {
    struct generic_node *next;
};

void free_list(void *head)
{
    struct generic_node *p = head, *next;
    while (p != NULL) {
        next = p->next;
        free(p);
        p = next;
    }
}

struct t_node {
    struct t_node *next;

    /* members of thing t */
};

struct q_node {
    struct q_node *next;

    /* different members of thing q */
};

/* Can happily pass t_node or q_node lists to free_list() */
于 2009-07-30T13:39:54.130 回答
1

我想提出一种不同的方法。与其为不同类型的数据创建多个列表类型并使用强制转换或宏体操对它们应用相同的算法,不如创建一个通用列表类型,将特定类型的行为委托给不同的函数,并将这些函数附加到具有函数的列表类型指针。例如:

struct generic_node {
  void                *data;
  struct generic_node *next;
};
struct generic_list {
  struct generic_node head;
  int   (*cmp)(void * const a, void * const b);
  void *(*cpy)(void * const);
  void  (*del)(void *);
};

cmp 指向一个函数,如果 *a < *b 则返回 -1,如果 *a == *b 则返回 0,如果 *a > *b 则返回 1,其中 a 和 b 已从 void * 转换为正确的指针类型. 例如,

int compareInts(void * const a, void * const b)
{
  int * const la = a;
  int * const lb = b;
  if (*a < *b) return -1;
  if (*a == *b) return 0;
  if (*a > *b) return 1;
}

int compareMyStruct(void * const a, void * const b)
{
  struct myStruct * const la = a;
  struct myStruct * const lb = b;

  if (la->foo < lb->foo && strcmp(la->bar,lb->bar) < 0 && ...) return -1;
  if (la->foo == lb->foo && strcmp(la->bar,lb->bar) == 0 && ...) return 0;
  if (la->foo > lb->foo && strcmp(la->bar, lb->bar) > 0 && ...) return 1;
}

cpy 指向一个对输入参数进行深拷贝的函数:

void *copyInt(void * const data)
{
  int *theCopy = malloc(sizeof *theCopy);
  *theCopy = *((int *) data);
  return theCopy;
}

void *copyMyStruct(void * const data)
{
  struct myStruct * const lData = data;
  struct myStruct *newStruct = malloc(sizeof *newStruct);
  newStruct->foo = lData->foo;
  newStruct->bar = malloc(strlen(lData->bar) + 1);
  strcpy(newStruct->bar, lData->bar);
  ...
  return newStruct;
}

最后,del 指向一个释放数据项的函数:

void delInt(void * data)
{
  free(data);
}

void delMyStruct(void * data)
{
  struct myStruct * lData = data;
  free(lData->bar);
  ...
  free(lData);
}

现在您的列表算法不必担心特定类型的行为;他们只是通过函数指针调用适当的函数:

void listAdd(struct generic_list * const theList, void * const data)
{
  struct generic_node *cur = &(theList->head);
  struct generic_node *entry = malloc(sizeof *entry);
  entry->data = theList->cpy(data);
  while (cur->next != NULL && theList->cmp(cur->next->data, entry->data) < 0)
    cur = cur->next;
  entry->next = cur->next;
  cur->next = entry;
}
/** */
void listClear(struct generic_list * const theList)
{
  struct generic_node *cur = theList->head.next;
  while (cur != NULL)
  {
    struct generic_node *entry = cur;
    cur = cur->next;
    theList->del(entry->data);
    free(entry);
  }
}
于 2009-07-30T16:05:59.827 回答
0

您想要的正是 C++ 模板所提供的。在 C 语言中,你会被 void 指针和宏做一些讨厌的事情。

于 2009-07-30T13:14:33.447 回答
0

如果您使用的是链表,请相信我您想使用托管内存。使用链表的有效方法是结构共享——随着您的程序变得越来越复杂,您最终会得到数百万个共享和部分共享的列表。列表将被构造成共享许多其他列表的一部分……这很混乱。

Lisp 很早就开发了使用垃圾收集来处理这个问题,现在你可以在 C/C#/Java 环境中得到它,为什么还要回去呢?

如果你真的不能,那么你可以通过在指针周围放置引用计数包装器来进行穷人的垃圾收集。查找“智能指针”。但这比管理内存要麻烦得多。

于 2009-07-30T13:51:03.820 回答