一、静态链表的由来
某些高级语言里面并没有指针，只有数组，静态链表就是利用数组来实现类似链表的操作
二、如何建立静态链表
1.要分配足够大的内存，用来存放变量，内存大小记为MAXSIZE；
2.内存不仅要存放数据，而且要存放' 指针 '，把它称为游标，满足这一条件的变量类型是结构体，其定义如下：
typedef struct{
ElemType data;
int cur; //游标
}Component,StaticLinkList[MAXSIZE];//StaticLinkList可以用来定义结构体数组；
3.接下来需要对静态链表进行初始化，使它成为一个真正的‘ 链表 ’；
(1)' 链表 ’需要一个头结点，将数组最后一个元素作为头结点，它不存储数据，但是它的游标要等于链表第一个有值元素的下 标，没有元素则设为0；
(2)数组第一个元素的游标要存放备用来链表首结点的下标；
(3)除最后一个元素和倒数第二个元素外，更新所有元素的游标值，代码如下：
Status InitList(StaticLinkList L)
{
int i;
for(i = 0;i < MAXSIZE-1; i++)
{
L[i].cur = i+1; //除最后元素，所有结点游标赋值为下一结点的下标
}
L[MAXSIZE-2].cur = 0; //判断备用链表是否为空
L[MAXSIZE-1].cur = 0; //它存放首元素的下标，现在链表为空，设置为0
return OK;
}
三、.在静态链表第 i 个位置插入元素
1.首先得判断 i 的值是不是合理的，它不能小于1，也不能大于加 1 的链表长度；
2.因为要把待插入的值存储到备用链表的首结点，因此需要得到该首结点的下标，还要更新首结点；
3.把这些操作放到一个函数里，既然要获取首结点的下标，首先得判断备用链表还存不存在，代码如下：
//返回备用链表首结点的下标,若备用链表为空，则返回0
int Molloc_L(StaticLinkList L)
{
int i = L[0].cur;
if(L[0].cur) //备用链表非空
{
L[0].cur = L[i].cur; //更新备用链表首结点下标
}
return i;
}
4.现在已经得到了备用链表首结点的下标(假设存在)，从头结点(最后一个元素)开始，遍历到第i-1个元素，然后把数据存储到备用链表的首结点，该节点的不再是首结点，令它的游标赋值为第i个元素的下标，同时第i-1个元素的游标赋值为该节点的下标，代码如下：
Status InsertList(StaticLinkList L,int i,ElemType e)
{
if(i<1||i>ListLength(L)+1)
return ERROR;
int j = Molloc_L(L);
int k = MAXSIZE-1;
if(j)//备用链表非空
{
L[j].data = e;
for(int s=1;s<=i-1;s++)
k = L[k].cur; //从头结点遍历到第i-1个元素
L[j].cur = L[k].cur;
L[k].cur = j;
return OK;
}
printf("备用链表为空!\n");
return ERROR; //备用链表为空
}
5.元素插入图解，并且说明为什么倒数第二个元素的游标要设置为0
四、删除静态链表中第i个元素
1.有了插入的思想，删除就比较好理解了，同样首先判断 i 的位置是否合理；
2.如果合理，那么也是从头结点遍历到第 i-1 个元素，让它的游标赋值为第i个元素的游标，相当于直接跳过第i个元素；
3.销毁第i个元素，并让它成为备用链表的首结点，具体代码如下：
Status DeleteList(StaticLinkList L,int i)
{
if(i<1||i>ListLength(L)+1)
return ERROR;
int k = MAXSIZE-1;
int j;
for(int s=1;s<=i-1;s++)
k = L[k].cur;
j = L[k].cur;
L[k].cur = L[j].cur;
Free_L(L,j);
return OK;
}
void Free_L(StaticLinkList L,int j)
{
L[j].cur = L[0].cur;
L[0].cur = j;
}
五、求链表的长度
1.从头结点开始遍历，遍历到最后一个有值元素，它的标志是游标为0；
int ListLength(StaticLinkList L)
{
int j=0;
int i = L[MAXSIZE-1].cur;
while(i)
{
i = L[i].cur;
j++;
}
return j;
}
六、具体实现代码及效果
/*
项目名称：静态链表基本操作
编译环境：VC++ 2008速成版
作者相关：。。。
最后修改：2019.5.24
学习目标：1.理解静态链表的基本操作
注意事项：1.静态链表往往适应于没有指针的高级语言
*/
#include <stdio.h>
#define MAXSIZE 5
#define ERROR 0
#define OK 1
typedef bool Status;
typedef int ElemType;
typedef struct{
ElemType data;
int cur;
}Component,StaticLinkList[MAXSIZE];//Component为结构体数据类型的别名,用来定义结构体变量；
//StaticLinkList为结构体数组类型的别名，用来定义结构体数组
Status visit(ElemType c);
Status InitList(StaticLinkList L);
int Molloc_L(StaticLinkList L);
Status InsertList(StaticLinkList L,int i,ElemType e);
Status DeleteList(StaticLinkList L,int i);
void Free_L(StaticLinkList L,int j);
int ListLength(StaticLinkList L);
void OutList(StaticLinkList L);
int main()
{
StaticLinkList L;
InitList(L);
printf("初始化后长度为：%d\n",ListLength(L));
for(int i=1;i<=3;i++)
{
InsertList(L,1,i);
}
OutList(L);
DeleteList(L,2);
OutList(L);
printf("链表的长度为：%d\n",ListLength(L));
return 0;
}
Status InitList(StaticLinkList L)
{
int i;
for(i = 0;i < MAXSIZE-2; i++)
{
L[i].cur = i+1; //除最后元素，所有结点游标赋值为下一结点的下标
}
L[MAXSIZE-2].cur = 0; //判断备用链表是否为空
L[MAXSIZE-1].cur = 0; //它存放首元素的下标，现在链表为空，设置为0
return OK;
}
//返回备用链表首结点的下标,若备用链表为空，则返回0
int Molloc_L(StaticLinkList L)
{
int i = L[0].cur;
if(L[0].cur) //备用链表非空
{
L[0].cur = L[i].cur; //更新备用链表首结点下标
}
return i;
}
Status InsertList(StaticLinkList L,int i,ElemType e)
{
if(i<1||i>ListLength(L)+1)
return ERROR;
int j = Molloc_L(L);
int k = MAXSIZE-1;
if(j)//备用链表非空
{
L[j].data = e;
for(int s=1;s<=i-1;s++)
k = L[k].cur; //从头结点遍历到第i-1个元素
L[j].cur = L[k].cur;
L[k].cur = j;
return OK;
}
printf("备用链表为空!\n");
return ERROR; //备用链表为空
}
Status DeleteList(StaticLinkList L,int i)
{
if(i<1||i>ListLength(L)+1)
return ERROR;
int k = MAXSIZE-1;
int j;
for(int s=1;s<=i-1;s++)
k = L[k].cur;
j = L[k].cur;
L[k].cur = L[j].cur;
Free_L(L,j);
return OK;
}
void Free_L(StaticLinkList L,int j)
{
L[j].cur = L[0].cur;
L[0].cur = j;
}
int ListLength(StaticLinkList L)
{
int j=0;
int i = L[MAXSIZE-1].cur;
while(i)
{
i = L[i].cur;
j++;
}
return j;
}
void OutList(StaticLinkList L)
{
int j = 0;
int i = L[MAXSIZE-1].cur;
while(i)
{
visit(L[i].data);
i=L[i].cur;
j++;
}
printf("\n");
}
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
