c - 如何静态且高效地实现两个节点数组？

Question

typedef struct NodeStruct NODE;
typedef struct ListStruct LIST; 

struct NodeStruct {
  void *item;
  NODE *previous;
  NODE *next;
  int location;
};

struct ListStruct {
  int ListSize;
  NODE *HeadNode;
  NODE *CurrentNode;
  NODE *TailNode;
  NODE NodeArray[MaxNode];
};

NODE *HeadArray[MaxHead];
static int HeadCount = -1;
int HeadCurrent = 0;
int i;

在 C 方面相当新，很抱歉提前听起来非常缺乏经验......

我想在不使用 malloc() 或 free() 的情况下实现 LIST 抽象数据类型，因此将节点存储在静态分配的数组中。每个列表元素都是一个节点，并且可以容纳一个“项目”。我需要能够使用 next 和 previous 遍历节点，并具有“当前”、“尾部”、“头”的概念。

还有两个数组...一个指向“头”的指针数组，因此对于每个头，都有一个“节点”数组。我还需要能够将当前项目更改为列表中间(或前端或末尾)的任何位置，能够删除该节点，然后不知何故(这是最令人困惑的部分对我来说)能够再次使用数组中的那个位置，但是，我无法遍历列表来查找“空闲”节点，因为这效率不高。

我还需要对“head”数组做同样的事情，所以，有一个列表最大数量的概念(这意味着头数组已满)，并且我还需要能够删除一个整个节点数组(反过来，这意味着我也必须能够从该列表中删除一个头节点，并且如果我需要该空间，也能够以某种方式将一个头节点放回那里)。

问题是我在尝试实现这个时经历了非常糟糕的时间!上面的代码是我迄今为止一直在使用的结构，我尝试了两种不同的想法:

1:每次我们从数组中“删除”一个节点(就我而言，这只是将其 ITEM 设置为 NULL 并将其连接的节点 nexts' 和 previous' 相互切换)，我们将数组中最右边的节点到此位置。当我们添加一个新节点时，我们总是将其添加到该位置。因此，无需搜索，但实现起来绝对是一场噩梦(根据我的经验)。

2:有一个单独的“空闲节点”列表(堆栈)，当我需要新节点时我可以从中获取。然而，这意味着我必须首先创建所有这些节点，并且可能不使用它们，这在内存方面不太好。

我真正想做但无法弄清楚的事情如下:

对于“heads”数组:我们有一个指向每个节点“head”的指针数组。对于每个“头”，我们最初有一个空的节点数组。对于每个空节点数组，我们还有一个“空闲”指针列表，它们是指向数组中每个空闲点的指针，当我们插入一个新项目时，我们获取该指针数组的顶部地址，这就是新节点将被放置在节点数组中。当我们从节点数组中删除时，我们将该节点地址放在堆栈顶部。

但是，我对 ListCreate 的外观感到困惑，因为那只是一个空的节点数组，并且头数组实际上不会指向任何东西。

这些是我正在研究的规范，因此我不能对要求进行太多更改。即，我不能没有头指针数组。

关于如何有效地实现这一点并满足这些要求有什么想法吗？我只需要帮助设置结构和“列表创建”的外观，以及节点操作背后的一般思想。我希望能弄清楚其他一切。我只是真的坚持一个通用的、有效的想法。

感谢任何帮助。谢谢。

Answer 1

如果您要为每个列表使用指向节点的指针数组，我认为不需要在节点中使用链表概念，例如前一个和下一个指针，而是代码可以是面向数组的。

问题指出，删除节点是通过将要删除的节点替换为数组中的最后一个节点来完成的，因此不会保留数组顺序。我假设添加节点是通过将节点附加到数组末尾来完成的。

每个数组结构都可以有元素计数、当前元素的索引以及指针数组。

可能有一个用于元素空闲池的结构(静态分配)，其余结构最初将为空(count == 0)。元素将从空闲池的指针数组的末尾删除或添加到末尾，类似于堆栈。

项目信息可以包含在元素结构中，而不是通过元素结构中的指针进行处理。

从当前位置删除节点的逻辑:

    free[count] = list[current];
    free.count++;
    list.count--;
    if(list.count != 0)
        list[current] = list[count];

追加节点的逻辑:

    if(free.count != 0){
        free.count--;
        list[count] = free[count];
        list.count++;
    }