c - 双向链表的数组实现

Question

我需要一种方法来实现一个双链表，只使用数组，在C中没有指针。托马斯·科尔门（Thomas Cormen）中提到了这一点，但我想不出实际实现它的方法。

Answer 1

不要使用指针，在 C 中，指针通常是索引到地址空间的数字，而是使用数组中的整数索引作为对上一个和下一个成员的引用，例如

struct Element 
{
    int next;
    int prev;
    // Any data you want for this element in the list 
};
struct Element array[MAX_ELEMENTS];

然后，对于数组中索引 i 处的元素，列表中的下一个元素为

array[array[i].next]

而上一个元素是

array[array[i].prev]

不要使用 NULL 来表示 null 指针，而是使用 -1 来表示"null"索引。