c - 使用指向结构的指针在 C 中创建链表和内存分配

Question

我想我有一个概念问题。当我需要创建一个链表时，我只是得到了一个指向结构的指针(并且该结构包含一些数据类型和指针“next”)。我如何确保我正在创建其他链接而不仅仅是根节点？我没有使用 malloc 否则这将是更明显的答案。此列表充当 malloc 本身。

提前致谢!

澄清:

将有一个一维数组，它将充当固定大小的内存块。然后，链表将通过删除节点并将其放入数组中来“分配”，或者通过从数组中删除节点以添加回列表来“释放”数据。

示例

(由某些数据类型和指针定义的结构)结构称为节点

node array[10];  //this acts as memory
node* linked_list;  //this gives or removes data to memory (array)

Answer 1

这类似于我们使用 FORTRAN 77(回到白垩纪中期)在我的数据结构类中做的事情；我们分配了一个固定大小的数组并将其用作我们的内存池。

基本上，您必须维护一个“免费”列表；这些是可供使用的节点。当您第一次启动时，您初始化数组中的每个元素以明确指向下一个元素:

struct node {T data; struct node *next; } pool[N]; // for some type T
...
for (i = 0; i < N-1; i++)
  pool[i].next = &pool[i+1];
pool[i].next = NULL;

您的空闲列表最初指向池中的第一个元素:

struct node *free = &pool[0];

当您分配一个节点时，您会检索 free 指向的元素，更新 free 以指向列表中的下一个可用元素(如果存在)，然后根据需要初始化元素:

if (free) // is there a free node available
{
  struct node *newNode = free;
  free = free->next;
  newNode->data = ...;
  newNode->next = NULL;
  ...
}

当你完成一个节点时，你将它添加回 free 列表的头部:

node->next = free;
free = node;

自然地，实际代码会比这更好地组织，但这应该足以让您知道要做什么。