线性表--顺序表--静态链表(八)
1.介绍
前面的链表都是使用指针类型实现的，并且都是由系统提供的函数malloc和free动态实现，被称之为动态链表，像C，C++，是拥有“指针”这类数据类型的，不需要使用静态链表，而对于BASIC，FORTRAN之类的高级语言中，并没有提供“指针”这类数据类型，若要继续采用链表作为数据的存储结构，只能采用数组来模拟实现链表，所以下面的知识是针对没有“指针”类型的高级语言而用数组设计的拥有链表存储结构的静态链表。一起往下看。
图1是空闲数组，使用静态链表存储数据时，虽然和顺序表一样，数据都被存储在数组中，但是存储位置是随机的，并使用游标找到找到下一个存储的数据，游标为0代表着链表到头，如图2所示。
2.备用链表
只有一条数据链表是不行的，这样没有考虑对已释放空间的回收，只拿出来用，却不记谁在用，这样在经过多次插入和删除后，会造成静态链表“假满”的情况，为此，还需要有一条连接各个空闲位置的链表，称为备用链表。备用链表的作用是回收数组中未使用或之前使用过（目前未使用）的存储空间，留待后期使用。简单来说就是前台，客人来了先问问有没有房，前台会告诉你哪里有房或者没有房给你。还有就是数据链表和备用链表是存在于一个数组里的，千万不要以为这是两个数组。
3.图示工作流程
注意：arr[7]的游标应该为0。 1.空闲的静态链表如图1所示，在通常情况下备用链表的表头位于数组下标为 0（arr[0]） 的位置，而数据链表的表头位于数组下标为 1（arr[1]）的位置。
2.红色区域为数据域，也就是存放数据的，绿色区域为游标，存放的是数组的下角标，相当于指针链表中的next。
3.在数据链表未初始化之前，数组中所有位置都处于空闲状态，因此都应被链接在备用链表上。通过arr[0]可知道整条链表没有数据为空闲状态，
4.当空闲链表存储第一个数据，如图2所示，数据链表的数据存储始于arr[1],所有arr[1]存放了a，它的游标为0，代表着结束，备用链表的头结点的游标变为2，意味着下一个存储要在arr[2]上经行，存储第二个数据时如图3，存储第三个数据时如图4。 如果还有疑惑，再上一张动态图：
文字说明就到这里，我们来上代码。
4.代码实现
（1）初始化空闲链表
void initial(StaticList space)
{
int k;
for (k = 0; k < Maxsize - 1; k++)
{
space[k].cursor = k + 1;//连链(将每个数组分量链接到一起)
}
space[Maxsize - 1].cursor = 0;//标记链尾，最后一个结点的游标时0
}（2）分配结点
int getnode(StaticList space, int * av)//分配结点
{//从备用链表摘下一个结点空间，分配给待插入静态链表中的元素
int i;
i = *av;
*av = i + 1;
return i;
}
//对系统而言，在空闲结点链表中分配结点空间相当于空闲结点链表中减少（删除）一个结点，对使用者而言，相当于申请的到了一个可用的新结点。（3）存储数据
int datalist(StaticList space, int i, int k)//存储数据
{
space[i].data = k;
space[i].cursor = 0;
if (i == 1)return 0;
space[i - 1].cursor = i;
return 0;
}（4）遍历数据
int showlist(StaticList space)
{
int i = 1;
if (space[i].cursor == 0)return 0;
while (i)
{
printf("在S[%d] 数据为：%d 下一个位于：%d\n", i,space[i].data, space[i].cursor);
i = space[i].cursor;
}
return 0;
}（5）收回结点
int freenode(StaticList space, int * av, int k)//回收结点
{//从space备用链表中回收序号为k的结点，av为备用链表的头指针。
if (k < 1)return 0;
int i = 1;
while (i)
{
if (space[i].cursor == k)
{
space[i].cursor = space[k].cursor;
}
i = space[i].cursor;
}
space[k].cursor = *av;
*av = k;
return 0;
}5.程序演示
int main()
{
StaticList S;
int i;
initial(S);//初始化为空闲链表
for (int k = 10; k <=15; k++)
{
i = getnode(S, &(S[0].cursor));//分配结点
datalist(S,i, k);//存储数据
}
for (int k = 0; k <= Maxsize - 1; k++)
{
printf("S[%d] %d %d\n", k,S[k].data, S[k].cursor);
}
printf("\n\n");
showlist(S);
freenode(S, &(S[0].cursor), 3);
printf("\n\n");
showlist(S);
printf("\n\n");
for (int k = 0; k <= Maxsize - 1; k++)
{
printf("S[%d] %d %d\n", k, S[k].data, S[k].cursor);
}
return 0;
}6.运行结果
1.可以看到，存入数据后，整个数组显示为第一块数据。 2.显示数据链表时，为第二块数据。 3.回收掉下角标为3号的数据后，为第三块数据，确实显示数据链中没有了3号的数据。 4.再看整个数组的数据，备用链表开头的游标指向3号，所以结点回收成功。 5.需要注意的是，数据链表的头结点的数据不可回收。好了，静态链表就写到这里。
若有错误，欢迎指正批评，欢迎讨论。 失败，是因为欠缺耐心；烦恼，是因为欠缺开心。
腾讯云开发者
