静态链表
++在没有指针类型的语言中，可以用顺序存储结构模拟链表。有人想出来用数组代替指针，来描述单链表，首先我们让数组的元素都是由两个数据域组成，由data和cur,也就是说，数组的每一个下标都对应着一个data和一个cur。数据域data，用来存放数据元素，也就是我们通常要来处理的数据，而游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。这种用数组描述的链表叫做静态链表，这种描述方法还叫游标实现法，为了方便插入数据，我们通常将数组建立得稍大一些，以便有一些空闲空间可以便于插入时不至于溢出。++
//线性表的静态链表存储结构
#define MAXSIZE 1000
typedef struct
{
ElemType data;
int cur;//游标，为0时表示无指向
}Component,SLinkList[MAXSIZE];
我们对数组第一个和最后一个元素做特殊处理，不存数据。我们通常把未使用的的数组元素称为备用链表。而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标。而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用。S[0].cur指示第一个结点在数组中的位置，如果说i=S[0].cur，则S[i].data存储线性表第一个元素，且S[i].cur指示第二个结点在数组中的位置。一般来说，若第i个分量表示链表的第k个结点，则S[i].cur指示第k+1个结点的位置。
Status InitList(SLinkList space)
{
int i;
for(i=0;i<MAZSIZE-1;i++)
space[i].cur=i+1;
space[MAXSIZE-1].cur=0;
return OK;
}
静态链表的插入操作
如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。在动态链表中，结点的申请和释放用malloc()和free()两个函数来实现。而在静态链表中操作的是数组，不存在动态链表的结点申请和释放问题，所以需要我们自己实现这两个函数，才可以做删除和插入操作。 为了辨明数组中那些分量未被使用，解决方法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。
int Malloc_SL(SLinkList sapce)
{
int i;
i=space[0].cur;//当前数组第一个元素的cur存的值，也就是要返回的第一个备用空闲的下标
if(space[0].cur)
space[0].cur=space[i].cur;
return i;
}
status ListInsert(SLinkList L,int i,ElemType e)
{
int j,k,l;
k=MAXSIZE-1;//k是最后一个元素的下标
if（i<1||i>ListLength(L)+1)
return ERROR;
j=Malloc_SL(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;
return OK;
}
return ERROR;
}
静态链表的删除操作
删除元素时，需要释放结点的函数free()，如何实现？ //删除在L中第i个数据元素e
Status ListDelete(SLinkList L,int i)
{
int j,k;
if(i<1||i>ListLength(L))
return ERROR;
k=MAXSIZE-1;
for(j=1;j<=i-1;j++)
k=L[k].cur;
j=L[k].cur;
L[k].cur=L[j].cur;
Free_SL(L,j);
return OK;
}
void Free_SL(SlinkList space,int k)
{
space[k].cur=space[0].cur;//把第一个元素cur值赋给要删除的分量cur
space[0].cur=k;//把删除的分量下标赋值给第一个元素的cur
}
//初始条件：静态链表已经存在。操作结果：返回L中数据元素个数
int ListLength(SLinkList L)
{
int j=0;
int i=L[MAXSIZE-1].cur;
while(i)
{
i=L[i].cur;
j++;
}
return j;
}
静态链表的优缺点
优点：在插入和删除操作中，只需要修改游标，不需要移动元素。 缺点：没有解决连续存储分配带来的表长难以确定的问题，失去了顺序存储结构随机存取的特性。