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

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（）。每个列表元素都是一个节点，可以容纳一个“项”。我需要能够使用next和previous遍历节点，并具有“current”、“tail”、“head”的概念。

还有两个数组。。。一个指向“头”的指针数组，因此每个头都有一个“节点”数组。我还需要能够将当前项更改为列表中间（或前端或后端）的任何位置，能够删除该节点，然后（这是我最困惑的部分）能够再次使用数组中的该点，但是，我无法遍历列表以找到“空闲”节点，因为这不是有效的。

我还需要对“head”数组执行相同的操作，因此，有一个最大列表数的概念（这意味着head数组已满），我还需要能够删除整个节点数组，（这反过来意味着，我必须能够从该列表中删除一个头部节点，并且如果我需要那个空间的话，能够以某种方式将一个放回那里）。

问题是我已经经历了一段可怕的时间试图实现这个！上面的代码是我到目前为止一直使用的结构，我尝试了两种不同的想法：

1：每次我们从数组中“删除”一个节点（就我而言，这只是将其项设置为NULL，并将其连接的节点nexts和previous相互切换），我们都会将数组中最右边的节点移动到此位置。当我们添加一个新节点时，我们总是将其添加到该点。因此，没有搜索，但绝对是一个噩梦来实现（以我的经验）。

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

我真正想做的事情，但我想不出来，如下所示：

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

但是，我仍然无法确定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++;
    }