首页 文章

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

提问于
浏览 次
0

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

提前致谢！

To Clarify:

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

example

（由某些数据类型和指针定义的struct）struct称为node

node array[10];  //this acts as memory
node* linked_list;  //this gives or removes data to memory (array)
c memory-management linked-list structure

3 回答

  • 2

    这类似于我们使用FORTRAN 77在我的Data Structures类中做的事情（回到白垩纪中期）;我们分配了一个固定大小的数组并将其用作我们的内存池 .

    基本上，你必须保持一个“免费”列表;这些是可供使用的节点 . 首次启动时，初始化数组中的每个元素以显式指向下一个元素：

    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;

    当然，真正的代码组织比这更好，但这应该足以让你知道该怎么做 .

    回复于
  • 1

    有几种可能的情况：

    • 链表使用malloc . 然后链表负责节点的分配和解除分配 . 这是标准实现 .

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

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

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

    操作更改后编辑：似乎您正在使用上面的版本3 . 谷歌用于“使用数组的链表”或类似的 .

    回复于
  • 0

    我不能确定这是否适用于您的特定问题，但我想指出一些关于创建链接列表而不使用 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;
    }
}

    EDIT ：为了使用数组作为链接列表节点"allocate"或"free"的位置，可以使用标志扩充节点 struct ，以指示节点是否正在使用 .

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

    EDIT2 ：让我们最后一次尝试 . 下面是"allocates"数组中一个节点的函数（如果没有，则返回 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 ：如果要将数组用作内存池，那么可以采用John Bode的答案 .

    回复于

相关问题