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

Question

我想我有一个概念问题。当我需要创建一个链表，但我只是给一个指针结构(和结构包含一些数据类型和指针"next")。如何确保创建的是其他链接，而不仅仅是根节点?我没有使用malloc，否则这将是更明显的答案。此列表充当malloc本身。

提前感谢!

澄清:

将有一个单维数组，它将作为一个固定大小的内存块。然后链表将通过移除一个节点并将其放入数组来"分配"，或者通过从数组中移除数据并将其添加回链表来"释放"数据。

(由某种数据类型和指针定义的结构体)结构称为node

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;

当然，真正的代码会比这更好地组织，但这应该足以让您了解该怎么做。

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( "%dn", head->value );
        head = head->next;
    }
}

EDIT:为了使用数组作为"分配"或"释放"链表节点的位置，您可以在节点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。然后链表负责节点的分配和取消分配。

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

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

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

修改后编辑:看来你正在使用上面的版本3。谷歌"使用数组的链表"或类似的