静态链表实现（C语言）

静态链表

对于线性链表，也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。

实现代码

先上代码

#include <stdio.h>

#define maxsize 7

typedef struct
{
	int data;
	int cur;
}SLinkList[maxsize];

//初始化静态链表
void list_init(SLinkList list);

//插入数据
int list_insert(SLinkList list);

//获取静态链表的长度
int list_size(SLinkList list);

//分配链表空间
int list_molloc(SLinkList list);

//输出函数
void displayArr(SLinkList list);

//释放链表的某个空间
void list_free(SLinkList list, int i);

//删除链表的某个空间
int list_delete(SLinkList list, int k);

//查找链表中第i个元素
int list_get(SLinkList list, int i);

//修改第i个元素的值
int list_change(SLinkList list, int data, int i);


int main(void)
{
	SLinkList list;
	list_init(list);
	int size = list_size(list);
	printf("size = %d\n", size);

	printf("插入结果=%d\n", list_insert(list, 10, 2));
	printf("插入结果=%d\n", list_insert(list, 11, 2));
	printf("插入结果=%d\n", list_insert(list, 12, 2));
	printf("插入结果=%d\n", list_insert(list, 13, 2));
	printf("插入结果=%d\n", list_insert(list, 14, 2));
	printf("插入结果=%d\n", list_insert(list, 15, 2));

	printf("删除前-----\n");
	displayArr(list);
	printf("删除的元素=%d\n", list_delete(list, 2));
	printf("删除的元素=%d\n", list_delete(list, 4));

	printf("删除后-----\n");
	displayArr(list);

	printf("修改元素----\n");
	printf("修改前的值list[3]=%d\n", list_change(list, 20, 3));
	printf("修改后-----\n");
	displayArr(list);


	printf("插入结果=%d\n", list_insert(list, 16, 2));
	displayArr(list);
	printf("插入结果=%d\n", list_insert(list, 16, 2));
	displayArr(list);

	return 0;
}


//初始化静态链表（初始化静态链表）
void list_init(SLinkList list) {
	list[0].data = NULL;
	list[0].cur = 1;
	int i;
	for (i = 1; i < maxsize - 1; i++)
	{
		list[i].data = NULL;
		list[i].cur = i + 1;
	}
	list[i].cur = 0;
	list[i].data = NULL;
}

//插入数据 data:要插入的数据  pos:数据要插入的位置，从0开始
int list_insert(SLinkList list, int data, int pos)
{

	int size = list_size(list);
	int i = list_molloc(list);
	if (i < 0) {
		printf("分配空间出错code=%d\n", i);
		return i;
	}
	list[i].data = data;

	int insertFlag = 0;
	//如果pos位置非法，则直接插入数据
	if (pos <0 || pos>maxsize - 2 || pos > size - 1)
	{
		pos = list_size(list);
		insertFlag = 1;
	}

	//位置pos在正常范围，则修改游标
	int tempCur = 1;
	int j;
	for (j = 0; j < pos - 1; j++)
	{
		if (!list[tempCur].cur) {
			break;
		}
		tempCur = list[tempCur].cur;
	}

	if (size) {
		//新分配的空间的游标指向其上一个元素所指向的空间
		if (insertFlag)
		{
			list[i].cur = 0;
		}
		else
		{
			list[i].cur = list[tempCur].cur;
		}
		//上一个元素的游标指向新分配的空间
		list[tempCur].cur = i;
	}
	else {
		list[i].cur = 0;
	}
	return 1;
}

//获取静态链表的长度
int list_size(SLinkList list)
{
	int i = 1, length = 0;
	while (list[i].data)
	{
		length++;
		i = list[i].cur;
		if (i == 0) break;
	}
	return length;
}

//分配链表空间
int list_molloc(SLinkList list)
{
	//获取链表的长度
	int size = list_size(list);
	//获取备用链表的游标
	int i = list[0].cur;

	//如果不是0，则说明还有空间
	if (i) {
		//备用链表游标修改为下一个可分配空间
		list[0].cur = list[i].cur;
		return i;
	}
	return -1;
}

//输出链表
void displayArr(SLinkList list)
{
	int index = 0;
	int cur = 1;
	if (list[1].data != NULL) {
		index++;
		printf("list[%d]=%d\n", index, list[cur].data);
	}
	while (list[cur].cur)
	{
		index++;
		cur = list[cur].cur;
		printf("list[%d]=%d\n", index, list[cur].data);
	}
}

//释放链表的某个空间,i是要释放空间的索引
void list_free(SLinkList list, int i)
{
	list[i].cur = list[0].cur;
	list[0].cur = i;
}

//删除链表的第k个元素，k从0开始，返回删除的元素的值
int list_delete(SLinkList list, int k)
{
	int returnData;
	int size = list_size(list);
	if (k<0 || size == 0 || k> size - 1)
	{
		printf("删除节点失败，节点不存在，k=%d\n", k);
		return 0;
	}

	//将链表的data设置为NULL
	int deleteCur = list_get(list, k);
	returnData = list[deleteCur].data;
	list[deleteCur].data = NULL;

	//如果删除的是首元素
	if (k == 0)
	{
		//如果只有一个元素，则直接释放空间
		if (size == 1)
		{
			list_free(list, 1);
		}
		else {
			int firstCur = list[1].cur;
			list[1].data = list[firstCur].data;
			list[1].cur = list[firstCur].cur;
			list_free(list, firstCur);
		}
	}
	//删除的不是首元素
	else {
		//删除元素的前后两个元素对接
		int lastCur = list_get(list, k - 1);
		list[lastCur].cur = list[deleteCur].cur;
		list_free(list, deleteCur);
	}
	return returnData;
}

//查找链表中第i个元素的位置,i从0开始
int list_get(SLinkList list, int i) {
	int j = 0;
	int getCur = 1;
	for (j = 0; j <= i - 1; j++)
	{
		getCur = list[getCur].cur;
		if (!getCur) {
			printf("查找元素失败，位置i=%d", i);
			return -1;
		}
	}
	return getCur;
}

//修改第i个元素的值，返回修改前的值
int list_change(SLinkList list, int data, int i)
{
	int getCur = list_get(list, i);
	int oldValue = list[getCur].data;
	list[getCur].data = data;
	return oldValue;
}

初始化备用链表

备用链表：是一些未使用的空间和被删除的空间所组成的一条链表

插入数据

list的第二个元素为静态链表的首元素，静态链表的最后一个元素游标cur指向0，代表结尾

插入第二和第三个数据

插入数据时，修改备用链表的cur指向，和静态链表的前后指向

只有一个元素时删除元素

只有一个元素时，删除元素只需要将备用链表指向第一个元素，并且释放元素的空间，使原来有数据的空间的cur归属到备用链表中

删除首元素

因为静态链表首元素比较特殊，如果如果不是只有一个元素，删除首元素时需要将第二个元素，移动到list[1]的位置

删除非首元素

删除非首元素时，需要将删除元素的前后两个元素对接，并修改备用链表的指向