静态链表的实现（用一维数组描述链表）

数据类型

typedef struct {	ElemType data;	//数据	int cur;		//下标 链表的顺序存储(一维数组描述链表)}component,SLinkList[MAXSIZE];

静态链表和普通链表所不同的是需要用户自定义malloc和free这两个函数。。

//在备用链表中取出一个节点使用int Malloc_SL(SLinkList space){	//将可以使用的链表的空间下标返回	int i = space[0].cur;	if (i)	{		space[0].cur = space[i].cur;	}	return i;}//将该节点回收备用链表void Free_SL(SLinkList space, int k){	//将下标为k的空闲节点回收备用链表	space[k].cur = space[0].cur;	space[0].cur = k;}

上述两个函数描述了两个链表(一个是备用链表一个使用中的链表)使用游标cur(指示器)代替指针只是结点在数组中的想对位置。。。

添加数据:只需要改变游标值不需要移动位置:

//在指定位置插入元素Status Insert_SL(SLinkList L,int pos, ElemType e){	/*if (pos < 0 || pos > getLenghtSL(L)+1)	{		return ERROR;	}*/	// 找到要插入指定位置的地址	int i = 0;	int k = MAXSIZE - 1;	int j = Malloc_SL(L);	//首先要有元素	if (j)	{		for (i = 1; i < pos; i++)		{			//遍历查找(k这里相当于指针)			k = L[k].cur;		}		//插入元素		L[j].data = e;		L[j].cur = L[k].cur; //把最后一个位置永远的往后移动(理解)		L[k].cur = j;				return  OK;	}		return ERROR;}

删除元素:原理和添加元素一样(改变游标的位置):

//删除元素并返回被删除元素void Del_SL(SLinkList L,int pos ,ElemType *e){	//删除第i个元素	//if (pos < 1 || pos > getLenghtSL(L))	//{	//	return ERROR;	//}	int i = 0;	int j = L[MAXSIZE - 1].cur;	for (i = 1; i < pos; i++)	{		j = L[j].cur;	}	int k = L[j].cur;	//删除j节点	*e = L[j].data;	L[j].cur = L[k].cur;	Free_SL(L,k);}

静态链表必要的其他操作:

//初始化void InitSpace_SL(SLinkList space){	//将一维数组转化为链表	//0 表示空指针	int i = 0;	for (i = 0; i < MAXSIZE-2; i++)	{		space[i].cur = i + 1;	}	space[MAXSIZE - 1].cur = 0;//0表示NULL	space[MAXSIZE - 2].cur = 0;}

//打印数据

void print_Sp(SLinkList space)

{

//将数组初始化为一个备用链表 space[0]为头指针

int k = MAXSIZE - 1;

while (space[k].cur)

{

k = space[k].cur;

printf("%d:%d ", space[k].data,space[k].cur);

}

}

　测试数据:

Status main(){	int i = 0;	//数组转换为链表		SLinkList  space;	ElemType e;	InitSpace_SL(space);	printf("表长:%d \n", getLenghtSL(space));	Insert_SL(space,1,100);	Insert_SL(space,2,200);	Insert_SL(space,3,300);	Insert_SL(space,4,400);	Insert_SL(space,5,500);	printf("表长:%d \n", getLenghtSL(space));		print_Sp(space);	printf("\n");	Del_SL(space, 2, &e);	printf("删除%d\n", e);	print_Sp(space);	printf("\n");	system("pause");	return OK;}