使用指向结构的指针创建链表和 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<的元素/code> 指向，更新 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;

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

Answer 2

我不确定这是否适用于您的特定问题，但我确实想指出有关在不使用 malloc 的情况下创建链接列表的一些信息。

如何分配链表的节点（无论是动态还是静态）并不重要。重要的是每个节点都实际存在并且指针有效。

例如，我们可以从数组构建一个链表。

#include <stdio.h>

typedef struct node_t {
    int value;
    struct node_t *next;
} node;

int main() {

    int i;
    node linked_list[10];

    // build the linked list
    for ( i = 0; i < 10; i++ ) {
        linked_list[i].value = i * i;
        linked_list[i].next = ( i < 9 ) ? &linked_list[i+1] : 0;
    }

    // now traverse it
    node *head = &linked_list[0];
    while ( head ) {
        printf( "%d\n", head->value );
        head = head->next;
    }
}

编辑：为了使用数组作为“分配”或“释放”链表节点的位置，您可以使用一个标志来扩充节点struct指示该节点是否正在使用。

typedef struct node_t {
    char in_use;
    int value;
    struct node_t *next;
} node;

EDIT2：让我们最后一次尝试。下面是从数组中“分配”一个节点的函数（如果没有可用的节点，则返回 NULL）。假设 linked_list 是全局的。

node *get_node() {
    int i;
    for ( i = 0; i < 10; i++ )
        if ( !linked_list[i].in_use ) {
            linked_list[i].in_use = true;
            return &linked_list[i];
        }
    return 0;
}

EDIT3：如果数组要用作内存池，那么约翰·博德的答案就是要走的路。

Answer 3

有几种可能的情况：

• 链表正在使用 malloc。然后链表负责节点的分配和取消分配。这是标准实现。

• 链表使用静态分配的内存块，即固定大小的静态数组。这样的链表更加复杂，因为您必须跟踪数组的哪些部分包含数据。您还需要跟踪链接列表的大小。

• 链表是一个“带有索引查找表的节点数组”。然后，它不会分配任何数据，而是每个节点包含数组索引。链表需要跟踪列表大小。

• 链表未执行任何分配。分配由调用者完成（静态或动态）。在这种情况下，链表仅跟踪下一个指针并且不分配任何内容。这个版本是糟糕的面向对象设计，因为它破坏了数据的私有封装。

op 更改后编辑：
看来您使用的是上面的版本 3。谷歌搜索“使用数组的链接列表”或类似内容。