c - 将链表实现与 malloc 函数分离

Question

我被告知要设计一个链表模块，其中链表函数都在一个头文件中，但内存分配（malloc）不会发生在这些模块中。内存分配应该只发生在主函数中。我无法弄清楚。帮帮我吧。

Answer 1

您应该一次性main分配足够大的内存（A 内存池）。现在在您的模块中，您需要管理（分配和释放）该池中的内存块，而不是为malloc.

如果您不了解内存池，请阅读此内容 - http://en.wikipedia.org/wiki/Memory_pool。

但是存在碎片问题，您需要解决这个问题。在下面的步骤中，我使用一个位数组来标记空闲和分配的节点。

例子-

• 在main您分配 50*sizeof(node) （50 取决于应用程序）
• 现在，您将分配池的指针传递给您的函数。
• 保留一个计数器，用于计算分配节点的数量，将其初始化为 0
• 还保留一个大小为 50 的位数组，初始化为 0（全部免费）
• 分配时，检查溢出，遍历位数组，找到第一个空闲节点。如果第j位为 0，则将新节点的地址作为 Base + j (*sizeof node) 传递，并递增计数器。将第j位设置为 1。
• 解除分配时，只需将计数器递减，并将相应位设置为 0。

高温高压

Answer 2

您可以将其作为结构数组执行，并通过数组索引链接它。然后可以在main函数中分配该数组。请注意，您必须跟踪列表中的条目数，因为列表将限制为您分配的条目数。

Answer 3

已经实现了：看看<sys/queue.h>那是一个只有标题的链表。