c - 没有 malloc 但有另一种方法的链表

Question

我有一个作业要求我使用链表来存储一些数据，但我只能使用 <stdio.h> .

我正在考虑使用数组，但是在到达数组末尾的情况下不可能扩展数组(我从这里读到这是不可能的:How can I change the size of an array in C? 大约 15 分钟前)。

然后我想也许我写malloc功能？但这对我来说很麻烦，因为我是 C 的新手。

另一种猜测是考虑通过在函数中分配给变量而不是返回来创建新节点。我在想，如果我在一个函数中定义一个变量，它会在我每次调用错误的函数时分配一个足够内存大小的新内存。

现在，我不知道该怎么办，我是否应该坚持被允许使用 <stdlib.h> ？或者有没有办法或者我应该只使用带链表的数组？

Answer 1

由于您不能在堆上创建您的列表(malloc、calloc 等)，您将必须声明您的内存要求并在列表结构内部管理该内存。

我会让你开始。

#define LIST_MEM_POOL 1024
#define NODE_MEM_POOL 1024 

typedef struct {
    int item; /* Assuming you are storing integers in the linked list */
    struct Node *next;
} Node, *Pnode;

typedef struct {
    struct Node *head; /* Assuming singly linked list */
    int size;
} List, *Plist;

static List list_memory[LIST_MEM_POOL];
static Node node_memory[NODE_MEM_POOL];

static int used_lists = 0, free_lists = LIST_MEM_POOL;
static int used_nodes = 0, free_nodes = NODE_MEM_POOL;

Plist create_list(void) {
    Plist l = 0;
    if (used_lists < free_lists) {
        l = &list_memory[used_lists++];
        l->size = 0;
        l->head = 0;
    }
    return l;
}

用于创建列表的相同想法可以应用于创建节点。

---

在自行管理此内存方面，您需要担心一些问题:

• 您将如何处理空闲内存？
• 如果有人创建了两个列表，释放了第一个，然后尝试创建一个新列表？
• 当有人试图创建一个列表但没有内存时会发生什么有空吗？