静态链表 | eleven26

单链表可以用指针来存储节点间的关联。如果不使用指针的话，我们也可以用数组来代替指针，描述单链表。

首先我们让数组的元素都是由两个数据域组成，data 和 cur。也就是说，数组的每个下标都对应一个 data 和一个 cur。数据域 data，用来存放输出，也就是通常我们要处理的数据；而游标 cur 相当于单链表中的 next 指针，存放该元素的后继在数组中的下标。

我们把这种用数组描述的链表叫做静态链表，这种描述方法还有起名叫做游标实现法。

为了我们方便插入数据，我们通常会把数组建立得大一些，以便有一些空闲空间可以便于插入时不至于溢出。

// 线性表的静态链表存储结构
#define MAXSIZE 1000 // 假设链表的最大长度是 1000
typedef struct
{
    ElemType data;
    int cur; // 游标，为 0 时表示无指向
} Component, StaticLinkList[MAXSIZE];

另外我们对数组第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为 0 的元素的 cur 就存放备用链表的第一个节点的下标；而数组的最后一个元素的 cur 则存放第一个有数值的元素的下标，相当于单链表中的头节点作用，当整个链表为空时，则为 0。

我们已经知道了静态链表实际上是一个数组，现在来考虑一下静态链表的逻辑存储结构，思考一下以下问题：

1、初始化的时候除了分配一个数组的空间外，还需要做哪些操作？

我们知道，在链表中，初始化的时候有一个头节点。这个头节点是链表存储的起始位置，而静态链表初始化的时候，我们就已经分配了一个数组，而这个数组的位置是否就可以拿来做静态链表的头节点呢？我们知道，头节点是不存储具体数据的，存储的只是指向链表第一个元素的指针。

这样的话，如果我们把数组第一个元素来做头节点，事实上就意味着，链表的实际数据是从数组的第二个元素（下标为 1）开始存储的，这样其实会给我们理解上带来一定的困难，不是很直观。

当然实际上，数组里面也不一定是按顺序存储的。

如果我们把数组第一个元素拿来做实际存储的起始元素的时候，我们就可以很直观的知道链表的存储位置。

所以，我们还需要一个节点来作为头节点，数组起始位置不合适，那中间的元素呢？也是不合适，大家想想，你在中间拿出一个元素来做头节点，这样一来破坏了线性表的连续性（链表实际上还是线性表的），二来我们需要记忆是哪一个位置的元素是头节点，会给我们的开发维护带来很多问题。

既然起始和中间的元素都不适合做头节点，那就只有最后一个元素了。一来我们不需要记忆，没有记忆的心智负担，而来，数组的结构和线性表的存储结构刚好对应上，非常的直观，对我们写入等各种操作带来很多便利。

如何找到空闲的节点？

我们已经知道，静态链表中的每一个元素都保存了下一个元素的下标。刚初始化的时候，除了数组最后一个元素（头节点外），其它的都是空闲的节点，我们自然地想到存储的时候，先存入数组第一个位置，然后第二个，第三个... 这样一直插入，直到下标到达了 i-1 （i 为数组长度）的时候，我们发现链表已经满了，这个时候就不能再插入了。但是还有一种情况就是，如果我们中途从中删除了某一个元素的话，我们怎么知道当前哪一个位置已空可以插入新数据呢？

因为通过每个元素我们只能找到下一个元素，而不知道物理存储结构是否是连续的。

我们想起了，在我们未插入元素的时候，我们的数组起始也是可以看作一个链表，这个链表全都是空闲的元素，可以插入新的数据。直到我们开始插入数据的时候，这个空闲链表的长度 -1，这个时候我们似乎明白了，一个静态链表中实际上存在了两个链表，一个是空闲节点的链表，另外一个是实际有数据的链表。

要实现这种目的，我们已经有了一个实际有数据链表的头节点，我们还需要一个节点来作为空闲链表的头节点。

因此，我们插入新数据的时候，需要同时变更数据链表和空闲节点链表。

可以通过空闲节点链表找到空闲的节点，但是怎么找呢？在刚初始化的时候，我们可以把第一个节点当作是空闲链表的头节点；但是一旦我们插入了新的数据，空闲链表的头节点就变了，到这个时候我们就完全没有办法知道空闲链表头节点在哪里了，这个时候我们可以考虑借助外部变量来记录空闲链表的起始位置，但是这就脱离了链表本身了。从其它地方操作链表的时候，也需要传递该变量，所以不考虑这种方式。

还有一种方式就是，在数组中专门留出一个节点来记录空闲链表的起始位置，这样一来，我们的数组，就真的是有一个数据链表、一个空闲链表了，这才是合理的做法。

结论：使用数组第一个元素来保存空闲链表的起始节点。

如何知道静态链表是否已满？

通过上面的讨论，我们知道了，保存静态链表的数组中第一个元素保存了空闲链表的起始节点。我们可以通过查看该起始节点的 cur 是否等于 0 来判断静态链表是否已满。

上图相当于初始化的数组状态：

// 将一维数组 space 中各分量链成一备用链表
// space[0].cur 为头指针，"0" 表示空指针
Status InitList(StaticLinkList space)
{
    int i;
    for (i = 0; i < MAXSIZE - 1; i++)
        space[i].cur = i + 1;
    space[MAXSIZE - 1].cur = 0; // 目前静态链表为空，最后一个元素的 cur 为 0
    return OK;
}

假设我们已经将数据存入静态链表，比如分别存放着 "甲"、"乙"、"丁"、"戊"、"己"、"庚" 等数据：

此时 "甲" 这里就存有下一元素 "乙" 的游标 2，"乙" 则存有下一元素 "丁" 的下标 3。而 "庚" 是最后一个有值元素，所以它的 cur 设置为 0。而最后一个元素的 cur 则因 "甲" 是第一有值元素而存有它的下标为 1。而第一个元素则因空闲空间的第一个元素下标为 7，所以它的 cur 存有 7。

静态链表的插入操作

静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。

我们前面说过，在动态链表中，节点的申请和释放分别借用 malloc() 和 free() 两个函数来实现。在静态链表中，操作的是数组，不存在像动态链表的节点申请和释放问题，所以我们需要自己实现这两个函数，才可以做插入和删除的操作。

为了辨明数组中，哪些分量未被使用，解决的办法是将所有未被使用过的以及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个节点作为待插入的新节点。

// 若备用空间链表非空，则返回分配的节点下标，否则返回 0
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur; // 当前数组第一个元素的 cur 存的值，就是要返回的第一个备用空闲的下标
    if (space[0].cur)
        space[0].cur = space[i].cur; // 由于要拿出一个分量来使用了，所以我们就得把它的下一个分量用来做备用
    return i;
}

这段代码有意思，一方面它的作用就是返回一个下标值，这个值就是数组头元素的 cur 存的第一个空闲的下标。从上面的图来看，其实就是 7。

那么既然下标为 7 的分量要准备使用了，就得有接替者，所以就把分量 7 的 cur 值赋值给头元素，也就是把 8 给 space[0].cur，之后就可以继续分配新的空闲分量，实现类似 malloc() 函数的作用。

现在我们如果需要在 "乙" 和 "丁" 之间，插入一个值为 "丙" 的元素，按照以前顺序存储结构的做法，应该要把 "丁"、"戊"、"己"、"庚" 这些元素都往后移一位。但目前不需要，因为我们有了新的手段。

新元素 "丙"，想插队是吧？可以，你先悄悄地在队伍最后一排第 7 个游标位置待着，我一会就能帮你搞定。我接着找到了 "乙"，告诉它，你的 cur 不是游标为 3 的 "丁" 了，你把你的下一位的游标改为 7 就可以了。此时再回到 "丙" 那里，说你把你的 cur 改为 3。就这样，在绝大多数人都不知道的情况下，整个排队的次序发生了改变。

步骤： * 判断下标合法性 * 获取空闲节点的下标 * 写入数据到空闲节点 * 将上面空闲节点的 cur 修改为原 i 位置的 cur * 将写入位置前一个节点的 cur 修改为新节点所在位置

实现代码如下：

// 在 L 中第 i 个元素之前插入新的数据元素 e
Status ListInsert(StaticLinkList L, int i, ElemType e)
{
    int j, k, l;
    k = MAX_SIZE - 1; // 注意 k 首先是最后一个元素的下标
    if (i < 1 || i > ListLength(L) + 1)
        return ERROR;
    j = Malloc_SLL(L); // 获得空闲分量的下标
    if (j) {
        L[j].data = e; // 将数据赋值给此分量的 data
        for (l = 1; l < i - 1; l++) // 找到第 i 个元素之前的位置 
            k = L[k].cur;
        L[j].cur = L[k].cur;  // 把第 i 个元素之前的 cur 赋值给新元素的 cur
        L[k].cur = j; // 把新元素的下标赋值给第 i 个元素之前元素的 cur
        return OK;
    }
    return ERROR;
}

当我们执行插入语句时，我们的目的是要在 "乙" 和 "丁" 之间插入 "丙"。调用代码时，输入 i 值为 3。
第 4 行让 k = MAX_SIZE - 1 = 999
第 7 行，j = Malloc_SLL(L) = 7。此时下标为 0 的 cur 也因为 7 要被占用而更改备用链表的值为 8。
第 11～12 行，for 循环 l 由 1 到 2，执行两次。代码 k = L[k].cur; 使得 k = 999，得到 k = L[999].cur = 1，再得到 k = L[1].cur = 2
第 13 行，L[j].cur = L[k].cur; 因 j=7，而 k = 2 得到 L[7].cur = L[2].cur = 3。这就是刚才说的 "丙" 把它的 cur 修改为 3 的意思。
第 14 行，L[k].cur = j; 意思就是 L[2].cur = 7。把它的 cur 改为指向 "丙" 的下标 7。

就这样，我们实现了在数组中，实现不移动元素，却插入了数据的操作。

静态链表的删除操作

和前面一样，删除元素时，原来是需要释放节点的函数 free()。现在我们也得自己实现它：

// 删除在 L 中第 i 个数据元素 e
Status ListDelete(StaticLinkList L, int i)
{
    int j, k;
    if (i < 1 || i > ListLength(L))
        return ERROR;
    k = MAX_SIZE - 1;
    for (j = 0; j <= i - 1; j++) { // 找到第 i 个元素之前的位置
        k = L[k].cur;
    }
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SLL(L, j);
    return OK;
}

有了刚才的基础，这段代码就很容易理解了。前面代码都一样，for 循环因为 i = 1 而不操作，j=k[999].cur=1, L[k].cur=L[j].cur 也就是 L[999].cur = L[1].cur = 2。这其实就是告诉计算机现在 "甲" 已经离开了，"乙" 才是第一个元素。

释放节点代码：

// 将下标为 k 的空闲节点回收到备用链表
void Free_SLL(StaticLinkList space, int k)
{
    space[k].cur = space[0].cur; // 把第一个元素 cur 值赋给要删除的分量
    space[0].cur = k; // 把要删除的分量下标赋值给第一个元素的 cur
}

意思就是 "甲" 现在要走，这个位置就空出来了，也就是，未来如果有新人来，最优先考虑这里，所以原来的第一个空位分量，即下标是 8 的分量，它降级了，把 8 给 "甲" 所在下标为 1 的分量的 cur，也就是 space[1].cur = space[0].cur = 8，而 space[0].cur = k = 1，其实就是让这个删除的位置称为第一个优先空位，把它存入第一个元素的 cur 中。

当然，静态链表也有相应的其它操作的相关实现。比如我们代码中的 ListLength 就是一个：

// 初始条件：静态链表 L 已存在。操作结果是：返回 L 中数据元素个数
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur;
    while(i) {
        i = L[i].cur;
        j++;
    }
    return j;
}

静态链表的优缺点

优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。

缺点：没有解决连续存储分配带来的表长难以确定的问题。失去了顺序存储结构随机存取的特性。

总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。