[线性表](3)静态链式线性表
在接触了动态链式之后，在C语音里面，动态链式主要是以结构体自引用完成链表的实现，每创建一个结点，需要新申请一片空间，而结构体数组也能完成链式线性表
其类型说明如下：
#define MAXSIZE 1000
typedef struct
{
ElemType data;
int cur;
}component,SLinkList[MAXSIZE];这种描述方法在不设“指针”类型的高级程序设计语言中使用链表结构，在如上描述的链表中，数组的一个分量表示一个结点，同时用游标(指示器cur)代替指针指示结点在数组中的相对位置。
数组的第零分量可看成头结点，其指针域指示链表的第一个节点。这种存储结构仍需预先分配一个较大的空间，但在作线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。
如下图所示：
线性表在插入数据元素“SHI”和删除数据元素“ZHENG”之后的状况，为了和指针型描述的线性表相区别，我们给这种数组描述的链表起名为静态链表
假设S为SLinkList型变量，则S[0].cur指示第一个结点在数组中的位置，若设S[0].cur则S[i].data存储线性表的第一个数据元素，且S[i].cur指示第二个结点在数组中的位置。
一般情况，若第i个分量表示链表的第k个结点，则S[i].cur指示k+1个结点的位置。
因此在静态链表中，实现线性表的操作和动态链表相似，以整型游标i代替动态指针p，i=S[i].cur的操作实为指针后移(类似于p->next)，例如，在静态链表中实现定位函数LocateElem如下列算法所示：
int LocateElem_SL(SLinkList S, ElemType e)
//在静态单链线性表L中查找第1个值为e的元素
//若找到，则返回它在L中的为序，否则，返回0;
{
i = S[0].cur;//i指示表中第一个结点
while (i && S[i].data != e)
{
S[i].cur;//在表中顺链查找
}
return i;
}C语言测试实现为：
#define _CRT_SECURE_NO_WARNINGS
#define MAXSIZE 1000
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{
char data[20];
int cur;
}component,SLinkList[MAXSIZE];
SLinkList S;
int LocateElem_SL(SLinkList, char[]);
int main()
{
S[0].cur = 1;
int i;
printf("请输入S的数据域：\n");
for (i = 1; i < 10; i++)
{
scanf("%s", S[i].data);
S[i - 1].cur = i;
}
char e[20];
int c;
printf("请输入需要查找的元素：");
scanf("%s", e);
c = LocateElem_SL(S, e);
printf("元素位置为：%d\n", c);
system("pause");
return 0;
}
int LocateElem_SL(SLinkList S, char e[])
//在静态单链线性表L中查找第1个值为e的元素
//若找到，则返回它在L中的为序，否则，返回0;
{
int i;
i = S[0].cur;//i指示表中第一个结点
while (i && strcmp(S[i].data, e) != 0)
{
i = S[i].cur;//在表中顺链查找
}
return i;
}类似的可写出在静态链表中实现插入和删除操作的算法。如上图所示，指针修改的操作和前面描述的单链表中插入与删除的算法相似
不同的是，动态链式需要用户使用malloc分配空间给结点，free函数回收该结点的空间。
而静态链式为了辨名数组中哪些分量未被使用，解决的方法是将所有未被使用过以及被删除的分量用游标链成一个备用链表。
每当进行插入时，便可从备用链表上取得第一个结点作为数据链表的新结点，反之，在删除时将从链表中删除下来的结点链接到备用链表上。
我们来看下面这个例子。
假设由终端输入集合元素，先建立表示集合A的静态链表S，而后在输入集合B的元素同时查找S表，若存在和B相同的元素，则从S表中删除，否则将此元素插入S表。
思路步骤：
- 将整个数组空间初始化成一个链表
- 从备用空间取得一个结点
- 将空闲结点链结到备用链表上。
可通过以下三个算法来实现静态链表的插入和删除功能：
算法一：初始化静态链表
void InitSpeace_SL(SLinkList sepace)
//将一维数组speace中各个分量链成一个备用链表，speace[0].cur作为头指针
//“0”表示空指针
{
for (i = 0; i < MAXSIZE - 1; ++i)
{
speace[i].cur = i + 1;
}
speace[MAXSIZE - 1].cur = 0;
}算法二：分配结点到数据链表
void malloc_SL(SLinkList speace)
//若备用链表非空，则返回分配的结点下标，否则返回0
{
i = speace[0].cur;
if (speace[0].cur)
{
speace[0].cur = speace[i].cur;
}
return i;
}算法三：回收结点到备用链表
void Free_SL(SLinkList speace, int k)
//将下标为k的节点链接到备用结点中
{
speace[k].cur = speace[0].cur;
speace[0].cur = k;
}接下来我们利用上述三个算法完成这个例子：
void difference(SLinkList speace, int* S)
//依次输出集合A和B的元素，在一维数组speace中建立表示（A-B）U（B-A）的
//静态链表，S为其头指针。假设备用空间足够大，speace[0].cur作为头指针
{
InitSpeace_SL(speace);//初始化链表
S = Malloc_SL(speace);//创建S表，生成头结点
r = S;//定义尾指针，r指向S
scanf(m, n);//输入A表和B表的个数
for (j = 1; j <= m; ++j)
{
i = Malloc_SL(speace);//生成新的结点
scanf(speace[i].data);//输入数据域
speace[r].cur = i;//链接结点
r = i;//尾指针右移
}
for (j = 1; i <= n; ++j)
{
scanf(b);//输入B表中的数据
p = S;//p作为头指针指向S
k = speace[S].cur;//k指向第一个结点
while (k != speace[r].cur && speace[k].data != b)//进入表中寻找b的值
{//第一个条件用于控制边界，第二个用于对比
p = k;
k = speace[k].cur;
}
}
/*有两种情况，第一是没找到，就是到达边界了，则需要进行插入到表中*/
/*第二是找到了，则需要删除表中所述的元素*/
if (k == speace[r].cur)/*没找到*/
{
i = Malloc_SL(sepace);//分配一个新的结点
speace[i].data = b;//将数据读入结点中的数据域
speace[i].cur = speace[r].cur;//将结点插到数据表的尾端
speace[r].cur = i;//且指针r不动
}
else/*找到了*/
{
speace[p].cur = speace[k].cur;//断开两结点中的链接
Free_SL(speace, k);//回收k结点
if (r == k)//若删除的是r指向的结点，则需要改变尾指针的位置
{
r = p;
}
}
}C语言测试实现：
#define MAXSIZE 100
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int data;
int cur;//游标
}componemt,SLinkList[MAXSIZE];
SLinkList space;
void Initspace_SL(SLinkList);
int Malloc_SL(SLinkList);
void Free_SL(SLinkList, int);
int main()
{
Initspace_SL(space);
int m, n;
printf("请输入集合A B的个数：");
scanf_s("%d %d", &m, &n);
/*分配头结点*/
int S, r;
S = Malloc_SL(space);
r = S;
/*链接A集合*/
printf("请输入A集合的值：\n");
for (int i = 1; i <= m; ++i)
{
int j;
j = Malloc_SL(space);
scanf_s("%d", &space[j].data);
space[r].cur = j;
r = j;
}
space[r].cur = 0;
printf("\n链接成功\n");
/*输入B集合*/
printf("请输入B集合的值：\n");
for (int j = 1; j <= n; ++j)
{
int b, p, k;
scanf_s("%d", &b);
p = S;
k = space[S].cur;
while (k != space[r].cur && space[k].data != b)
{
p = k;
k = space[k].cur;
}
if (k == space[r].cur)
{
int i;
i = Malloc_SL(space);
space[i].data = b;
space[i].cur = space[r].cur;
space[r].cur = i;
r = i;
}
else
{
space[p].cur = space[k].cur;
Free_SL(space, k);
if (k == r)
{
r = p;
}
}
}
/*检测*/
int i = space[S].cur;
while (space[i].data != NULL)
{
printf("%d ", space[i].data);
i = space[i].cur;
}
system("pause");
return 0;
}
void Initspace_SL(SLinkList space)
{
for (int i = 0; i < MAXSIZE; ++i)
{
space[i].cur = i + 1;
}
space[MAXSIZE - 1].cur = 0;
}
int Malloc_SL(SLinkList space)
{
int i;
i = space[0].cur;
space[0].cur = space[i].cur;
return i;
}
void Free_SL(SLinkList space,int i)
{
space[i].cur = space[0].cur;
space[0].cur = i;
}在C语言代码里边，我改变了r的位置，如果不改变，则是栈的链接模式，如下图：
改变后，尾指针随着添加的结点后移
当然，不改变的时间复杂度小于改变后的，这里只做测试。
在上述算法中，只有一个处于双重循环中的循环体(在集合A查找依次输入的b)，其最大循环次数为：外循环n次，内循环m次，故时间复杂度为：O(m*n)次
上述例子运算前后如下图所示
上图所示，假设集合A={1、2、3、4、5、6、7、8、9、10}，集合B={1、2、3、4、5、11、12、13、14、15}；
则在运算后，遇到相同的元素则将该结点链接到备用链表，不同的元素则链接到数据链表。
静态链表：线性存储结构的一种，兼顾顺序表和链表的优点，是顺序表和链表的升级；静态链表的数据全部存储在数组中(顺序表)，但存储的位置是随机的，数据直接的一对一关系是通过一个整型变量(称为“游标”，类似指针的功能)维持。