gpt4 book ai didi

我们可以在没有动态内存分配的情况下在 C 中使用双向链表吗?

转载 作者:行者123 更新时间:2023-12-04 10:51:48 25 4
gpt4 key购买 nike

我正在尝试使用双向链表数据结构在缓冲区管理器中实现替换策略。

但是我的C程序没有链表库,所以我自己定义了数据结构。

问题是:我能否避免进行任何[动态?]内存分配以使用双向链表?

使用 palloc() 而不是 malloc() 有什么好处?

最佳答案

你当然可以创建一个双向链表而不使用动态内存分配;这样做很常见。

#include <stdio.h>
#include <assert.h>
#include <inttypes.h>

enum { NODEBUG = 0, DEBUG = 1 };

static const int debug = NODEBUG;

typedef struct DList DList;
struct DList
{
int data;
DList *next;
DList *prev;
};

enum { MAX_DLIST = 100 };
struct DList dlist[MAX_DLIST];

static void add_node(DList *head, DList *node)
{
assert(head != 0 && node != 0);
if (head->next == 0)
{
assert(head->prev == 0);
head->next = node;
head->prev = node;
node->next = head;
node->prev = head;
}
else
{
assert(head->prev != 0);
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
}

static void diagnode(DList *node)
{
if (debug)
printf(" (T = 0x%.12" PRIXPTR ", N = 0x%.12" PRIXPTR ", P = 0x%.12" PRIXPTR ")\n",
(uintptr_t)node, (uintptr_t)node->next, (uintptr_t)node->prev);
}

static void print_list(DList *head)
{
assert(head != 0);
printf("List:");
if (head->next != 0)
{
DList *node;
int counter = 0;
if (debug)
printf("\nHEAD");
diagnode(head);
for (node = head->next; node != head; node = node->next)
{
printf(" %3d", node->data);
diagnode(node);
assert(counter++ < MAX_DLIST);
}
}
printf(" <EOL>\n");
}

int main(void)
{
DList head = { 0, 0, 0 };

for (int i = 0; i < MAX_DLIST; i++)
{
dlist[i].data = (i * 13 + 7) % 100;
add_node(&head, &dlist[i]);
if (debug)
print_list(&head);
}
print_list(&head);
}

看不到内存分配!当你有类似缓冲区管理器的东西时,你可以使用它的一个变体,其中有一个固定的数据缓冲区数组,但你想要一个 LRU(最近最少使用)替换策略。 data 元素将指向缓冲池中的条目,而不是像本示例中那样将数据直接放在双向链表结构中。然后,您可以在列表中添加和删除条目,而无需更改列表链接到的主要数据结构中的任何内容。


如果 palloc() 是一个池内存分配器,使用它优于 malloc() 的优点是您可以释放分配给给定池的所有内存一个函数调用,而不是必须管理所有单独的释放自己。有时,池分配器比使用 malloc() 单独分配内存更有效;它可能会分配一个固定大小结构的大数组,然后根据请求分发条目,减少分配次数,从而减少开销。

关于我们可以在没有动态内存分配的情况下在 C 中使用双向链表吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12991054/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com