C语言 数据结构与算法---静态链表

一.基本概念

静态链表 ：用数组描述的链表
备用链表 ：未被使用的数组元素

• 每一个元素的游标域存储着下一个元素的下标;
• 最后一个元素的游标为0;
• 第一个和最后一个元素不存数据；
• 0号元素存储着 备用链表 的第一个元素的下标；
• 最后一个元素的游标存放第一个有数值元素的下标（相当于链表中的头结点）；
• 静态链表中操作的是数组，不存在动态链表中的结点申请和释放问题，需要自己实现这两个函数

二.实现

创建：

#define SIZE 1000   //为了方便插入数据通常会把数组建立的大些

typedef struct
{
	int data;
	int cur; //游标 ：为 0 时表示无指向
}StList;

StList space[SIZE];

初始化：

//初始化静态链表
void inilist()
{
	//space[0].cur为头指针，“0”表示空指针
	int i;
	for (i = 0; i < SIZE - 1; i++)
	{
		space[i].cur = i + 1;   ///每一个元素的游标存储着下一个元素的下标
	}
	space[SIZE - 1].cur = 0; ///目前静态链表为空，最后一个元素的游标为零
}

分配：

//若备用链表非空，则返回分配节点的下标，否则返回0
int malloc_list()
{
	int i = space[0].cur;//第一个结点存放着备用链表的第一个结点
	if (space[0].cur)
	{
		space[0].cur = space[i].cur;//由于要拿出一个分量来使用了，所以我们就得把它的下一个分量用来做备用

	}
	return i;
}

链表表长：

//返回数据元素个数
int ListLength()

{
	int j = 0;
	int i =space[SIZE - 1].cur;
	while (i)
	{
		i = space[i].cur;
		j++;
	}
	return j;
}

malloc：

//在静态链表中第i个元素之前插入元素e
int Insert(int i, int e)

{

	int j, k, l;

	k = SIZE - 1;  //最后一个元素的下标

	if (i<1 || i>ListLength())
	{		
		return 0;
	}
	j = malloc_list(); //获得空闲分量的下标

	if (j)
	{
		space[j].data = e;

		for (l = 1; l <= i - 1; l++)
		{
			k = space[k].cur;  //找到第i个元素之前的位置
		}
		space[j].cur = space[k].cur;//把第i个元素之前的游标给新元素
		space[k].cur = k;//把新元素的下标给第i个元素之前的元素的cur
		return 1;
	}

	return 0;

}

free：

//将下标为 k 的备用节点回收到备用链表
void Free( int k)
{
	space[k].cur = space[0].cur;  //把第一个元素的游标赋值给要删除的分量
	space[0].cur = k; //把要删除的游标赋值给第一个元素的cur
}

删除：

int ListDelete( int i)

{
	int j, k;
	if (i<1 || i>ListLength())

	{
		return false;
	}
	k = SIZE - 1;
	for (j = 1; j <= i - 1; j++)

	{
		k = space[k].cur;
	}
	j = space[k].cur;
	space[k].cur = space[j].cur;
	Free(j);
	return true;
}

注：本文是作者学习时，借鉴大话数据结构所做