在C语言中，因为它具有指针的能力，使得它可以非常容易地操作内存中的地址和数据，这比其他高级语言更加灵活方便。
后来的面向对象语言，如Java、C#等，虽然不使用指针，但因为启用了对象引用机制，从某些角度也间接实现了指针的某些作用。
但对一些语言，如Basic、Fortran等早期的编程高级语言，由于没有指针，链表结构中的指针域也就没办法实现了。怎么办呢？

静态链表的结构分析

为了解决指针域无法表示的问题，有人就想出用数组来代替指针，来描述单链表。
首先我们让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下标都对应一个data和一个cur。
数据域data用来存放数据元素；而游标cur相当于单链表中的next指针，存放该元素在数组中的下标。

这种用数组描述的链表，就叫静态链表，描述的方法叫游标实现法。

为了方便插入数据，我们通常会把数组建立的大一些，以便有一些空闲空间可以便于插入时不至于溢出。

用C语言描述的静态链表的存储结构：

#define MAXSIZE 1000
typedef struct{
	ElemType data;
	int cur; //为0表示无指向
}Component,StaticLinkList[MAXSIZE];

另外我们对数组第一个和最后一个元素最为特殊元素处理，不存数据。
我们通常把未使用的数组元素称为备用链表。而数组的第一个元素，即下标为0的元素cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的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;
	return OK;
} 

假设我们已经将数据存入静态链表，比如方便存放着”甲“、”乙“、”丁“、”戊“、”己“、”庚“等数据，则它将处于下图所示这种状态：

此时各元素的游标cur都存着下一元素的下标，而“庚”这个元素是元素中的最后一个，所以它的cur是0。
而下标为0的第一个元素，存放的是第一个空闲结点的下标，而第一个空闲结点的下标是7，所以它的cur存放的是7；下标为999的元素，存放的是第一个结点的下标，而第一个结点是“甲”，下标为1，所以最后一个元素的cur是1。

静态链表结点的申请和释放

在动态链表中，结点的申请和释放分别借用malloc和free这两个函数来实现。
在静态链表中，操作的是数组，不能像动态链表那样申请和释放，我们需要自己实现这两个函数，才能完成插入和删除操作。

为了辨明数组中的哪些结点未被使用，解决的办法是将所以未被使用过的及被删除的结点用游标链成一个备用的链表。

• 当申请新结点时，从备用链取第一个结点，然后更新备用链即可；
• 当回收结点时，把回收结点的游标置为备用链的第一个结点的下标，备用链的第一个结点更新为回收的结点即可。

静态链表实际上是两个链组成：
一个是用链上的第一个结点作为头结点的备用链；
另一个是用链上的最后一个结点作为头结点的数据链。

新结点的申请

int Malloc_SSL (StaticLinkList space)
{
	int i = space[0].cur;
	
	if(space[0].cur)
		space[0].cur = space[i].cur;
		
	return i;
}

思路：

1. 取出备用链的第一个结点的下标
2. 更新备用链头结点的游标
3. 返回新结点的下标

回收结点

void Free_SSL(StaticLinkList space, int k)
{
	space[k].cur = space[0].cur;
	space[0].cur = k;
}

思路：

1. 回收结点的cur置为备用链第一个结点的下标
2. 备用链的第一个结点置为回收结点

静态链表长度的计算

int ListLength(StaticLinkList L)
{
	int j = 0;
	int i = L[MAXSIZE - 1].cur;
	while(i)
	{
		i = L[i].cur;
		j++;
	}
	return j;
}

静态链表的长度计算，就是在数据链简单的向后迭代计数，即可完成。

静态链表的插入操作

Status ListInsert(StaticLinList L, int i, ElemType e)
{
	int j, k, l;
	k = MAX_SIZE - 1;
	if(i < 1 || i > ListLength(L) + 1)
		return ERROR;
	j = Malloc_SSL(L);
	if(j)
	{
		L[j].data = e;
		for(l = 1; l <= i - 1; l++)
			k = L[k].cur;
		L[j].cur = L[k].cur;
		L[k].cur = j;
		return OK;
	}
	return ERROR;
}

思路：

1. 如果插入的位置小于1或者大于数据链的长度，插入错误，结束
2. 如果插入位置合法，先申请一个新结点，记录下它的下标j
3. 如果新结点申请成功，把插入元素的数据赋值给新结点的数据域
4. 找到插入位置结点的前一个位置，k为这个位置结点的cur
5. 把新结点的cur置为k位置结点的cur
6. k位置结点的cur置为新结点的下标j，插入成功

静态链表的删除操作

Status ListDelete(StaticLinkList 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_SSL(L, j);
	return OK;
}

思路：

1. 判断删除的位置是否合法
2. 找到删除结点的前一个结点的下标k
3. j存下删除结点的下标
4. 把k结点的cur置为要删除节点j的cur
5. 释放删除的节点j，删除完成

静态链表的优缺点

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

缺点：
没有解决连续存储分配带来的表长难以确定的问题；
失去了顺序存储结构随机存储的特性

总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。尽管大家不一定会用得上，但是这样的思考方式是非常巧妙地，应该理解其思想，以备不时之需。

实现代码

静态链表的C语言代码实现