数据结构：静态链表

一、回顾

简单回顾一下前面学习到的知识。我们已经知道数据结构中的线性表包含 顺序存储结构 和 链式存储结构 。其中链式存储结构中包含了单链表。

在顺序存储结构的实现中，主要是申请了一块连续的内存来存储数据元素。而单链表的存储结构中是不需要提前申请内存的。它可随时随地申请一块连续或不连续的物理内存来存储数据元素。单链表可以通过 头插法 和 尾插法 来实现数据元素的顺序储存格式或逆序的存储格式。和顺序存储结构相比，都秉持着各自的优缺点。

二、静态链表的诞生

基于 顺序储存结构 和 链式存储结构 之后。那么有没有一种可能用于兼容顺序表的优点又兼容单链表的优点于一身的存储方式呢？答案是肯定的。它就是我们要说的 静态链表 。

C语言的特点有很多，其中指针的能力就证明了它可以非常容易的操作内存中的地址和数据。比起面向对象语言如Java和C#就显得更高级一点。java和C#它们启用了对象引用机制，从某种角度上也间接的实现了指针的某些作用。

但是像Basic和Fortran等更早的高级编程语言，它们没有操作指针的能力，也没有基于面向对象的引用机制，那它们又是如何操作内存来存储数据的呢？

然而有人却想到了，用数组来模仿单链表的相关操作并形成了一种新的链表。所以通常我们把这种 用数组表述的链表叫做静态链表 。它是基于 顺序表 和 单链表 二者的优点解决了其他高级语言对内存操作问题。下面将具体介绍静态链表的实现。

2.1 静态链表的存储结构

用数组来实现单链表的存储方式，那就需要将这个初始化的数组设置的更大一些，以便于不时之需所造成内存溢出问题。

/*线性表的静态链表存储结构*/

#default MAXSIZE 1000 #假设链表的最大长度是1000

typedef struct {

ElemType data;

int cur; # 游标（cursor）,为 0 时表示无指向

} Component,StaticLinkList[MAXSIZE];

从上面代码中可看出静态链表的存储元素类似于单链表。其中data用于存储具体元素，而cur 用于存储下游数据的地址，简称 游标 。

另外我们对数组的 第一个元素 和 最后一个元素 作为 特殊元素 处理，不存数据。静态链表通常会维护数组链表的两种模式。一个叫 备用链表 ，一个叫 数据链表 。数据链表是指已经存储了元素的单元集合。备用链表是剩余没有储存元素的单元集合。下图中描述了一个备用链表的样子。

/*将一维数组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.2 静态链表的存储分析

下面假设我们已经将数据存储到静态链表中，比如：春、夏、秋、冬数据元素。

由图可看到下标为0的第一个元素，和最后一个元素前面有说了它们需特殊处理且不存任何元素。

这里首先说最后一个元素，假设它是指向下标为0的地址则说明此链表为空链表。然而它的游标指向了下标为1的地址。则说明此静态链表不是空表，所以指向链表的下标为1，是整个链表的开始地址。

第一个元素的游标指向了下标为5的地址，则说明下标为5的地址是空地址。这就体现了备用链表的作用，一旦有新元素插入则优先使用第一个元素指向的游标地址。

从第二个元素可以看到“春”的游标指向了下标为2的地址，通过查找下标为2的地址发现存储的元素是“夏”。而夏所储存的游标指向了下标为3的地址，找到下标为3的地址可以看到下一个元素是“秋”。而秋所存储的游标指向了下标为4的地址，再找到下标为4的地址可以看到下一个元素是“冬”。而冬所存储的游标却指向了下标为0的地址。这个指，冬是整个链表的最后一个元素。所以没有后继元素需要跟踪了。

三、静态链表的操作

3.1 静态链表的插入

举例子，如果我们要插入一个 “夏至” 在 “夏” 和 “秋” 之间。设想一下会有哪些动作呢。

对于数组结构的静态链表，它却不能像单链表那样添加元素时通过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;

}

插入操作实现代码如下。

/* 在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; # 将新元素插入到备用链表所给的下标地址

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;

}

基于上面的例子，当我们将 “夏至” 插入在 “夏” 和 “秋” 之间将会发生些什么呢。下面将具体分析整个过程逻辑。

由第8 行代码可知，首先获得备用链表的第一个元素的待使用下标 5。

由第10行代码可知，其次将 “夏至” 存储在下标地址为 5 的内存中。

由第12-14行代码可知，再找到 “夏” 所存储的游标地址 3 赋值给新元素 “夏至” 的游标。

由第15行代码可知，最后将新元素 “夏至” 的下标地址 5 赋值给 “夏” 的游标。

就这样，实现了数组在不移动元素的情况下成功插入新元素的操作。完成图如下。

3.2 静态链表的删除

接下来，继续看静态链表删除元素的操作。前面提到静态链表不像单链表那样可以自动释放内存，所以接下来我们自己实现一个释放内存的函数。

/* 将下标为k 的空闲结点回收到备用链表 */

void Free_ssl ( StaticLinkList space, int k ) {

space[k].cur = space[0].cur; # 把第一个元素cur 赋值给要删除的分量

space[0].cur = k; # 把要删除的分量下标赋值给第一个元素的cur

}

/* 删除在L 中第 i 个元素 e */

Status ListDelete( StaticLinkList L, int i ) {

int j, k;

if ( i < 1 || i > ListLength(L) ) {

return ERROR;

}

k = MAX_SIZE - 1; # k 首先是最后一个元素的下标

for ( j = 1; j <= i -1 ; j++ ) { # 找到第 i 个元素之前的位置

k = L(k).cur;

}

j = L[k].cur; # 把第 i 个元素之前的 cur 赋值给j

L[k].cur = L[j].cur;

Free_ssl(L, j);

return OK;

}

仍然是采用上面的季节例子，这个时候想要删除 “春” 元素。通过删除函数最终得到如下结果图。

• 因为 “春” 被删除后，“夏” 就晋升为第一个元素值。

• 此时最后一个元素将不能在指向第一个元素值“春”，而要指向“夏”的下标2地址。

• 而春的下标1 地址也将被释放到备用的链表当中。

• 同时还要将“春” 分量的元素cur 重新指向下一个备用链表的分量游标 6 地址。

• 最后在将链表的第一个元素的游标指向“春”的下标1 地址。

• 如果有新插入的数据则优先使用 下标 1 的地址。

四、静态链表的优缺点

优点

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

缺点

• 并没有解决连续存储分配带来的表长难以确定的问题
  

• 失去了顺序存储结构随机存取的特性

五、参考文献

《大话数据结构》