使用C语言实现静态链表

目录

1.静态链表

2.静态链表的相关操作

（1）数据结构

（2）初始化操作

（3）分配空闲节点

（4）释放节点（回收）

（5）插入节点

（6）在第i个位置处插入节点

（7）删除第i个节点

（8）定位元素和打印

（9）主函数

（10）测试

---

1.静态链表

单链表是不要求地址是连续的，也就是各个节点之间是离散的分布在内存中的。

静态链表则是分配一整片连续的内存空间，各个节点的地址是连续的，集中存放。

注：静态链表也是通过遍历查找到删除的节点位置和插入节点的位置。

其中上面的空闲表头的指针域为6，表示指向的数组下标为6的位置空闲；而头结点的指针域为2，表示头结点的下一个节点在数组下标为2的地方。

2.静态链表的相关操作

（1）数据结构

#include
#include
 
#define MAXSIZE 10 
 
typedef int ElemType;
 
typedef struct Node {
	ElemType data;
	int cur;
}SLinkList[MAXSIZE];

（2）初始化操作

注：这里的空闲表头指针指向的是下一个空闲的位置，在申请节点空间的时候只需要找到空闲表头指针指向的位置即可。

//初始化
void InitSLinkList(SLinkList&space,ElemType&headNode){
	//初始化游标 
	for(int i=0;i-1;i++){
		space[i].cur=i+1;
	}
	//确定链尾 
	space[MAXSIZE-1].cur=0; 
	//申请头结点 
	headNode=MallocSLinkList(space);
} 

（3）分配空闲节点

//判断备用空间链表非空，则返回分配的节点下标，否则返回0
int MallocSLinkList(SLinkList&space){
	//从头结点开始
	int i=space[0].cur;
	if(space[0].cur){
		space[0].cur=space[i].cur;
	}
	return i;
} 

（4）释放节点（回收）

比如现在释放节点a5，其数组下标为7，那么k=7:

（1）首先是将数组下标为7的位置的指针域修改为空闲表头指针指向的空闲位置：space[7].cur=space[0].cur=6;

（2）其次是将空闲表头的指针域修改为刚才释放的节点位置：space[0].cur=7.

//将空闲节点收回到备用链表
void FreeSLinkList(SLinkList&space,int k){
	space[k].cur=space[0].cur;
	space[0].cur=k;
}

（5）插入节点

//创建一个静态链表
int CreateList(SLinkList&space,ElemType e,int j){
	int k=j;
	//申请空间 
	int r=MallocSLinkList(space);
	//将节点插入到r位置 
	space[r].data=e;
	//将前驱指针k指向r 
	space[k].cur=r;
	//移动指针k到r位置 
	k=r;
	space[k].cur=0;
	printf("插入节点成功!\n");
	return k;
} 

（6）在第i个位置处插入节点

//查找第i-1节点
int FindNode(SLinkList&space,int i,int headNode){
	if(i<1||i>MAXSIZE){
		printf("插入位置不合法!\n");
		return -1;
	}
	int k=headNode;
	int j=0;
	//从头结点开始找到第i-1指针指向的位置 
	while(k!=0&&j-1){
		j++;
		k=space[k].cur;
	}
	return k;
} 
//在第i个节点之前插入节点e
void InsertNode(SLinkList&space,int headNode,int i,ElemType e){
	int k=FindNode(space,i,headNode);
	if(k==0)return;
	int m=MallocSLinkList(space);
	if(m!=0){
		//将节点e插入到位置k后 
		space[m].data=e;
		//将m的指针指向k的指针后继 
		space[m].cur=space[k].cur;
		//将k指针指向m 
		space[k].cur=m;
		printf("插入节点成功!\n");
		return ;
	}else{
		printf("插入节点失败!\n");
		return ;
	}
}

（7）删除第i个节点

//删除节点
void DeleteNode(SLinkList&space,int headNode,int i,ElemType&e){
	int k=FindNode(space,i,headNode);
	if(k==0)return;
	int m=space[k].cur;
	//将k指针指向m指针的后继 
	space[k].cur=space[m].cur;
	//获取要删除的元素 
	e=space[m].data;
	//释放 
	FreeSLinkList(space,m);
	printf("删除节点成功!\n");
	return ;
} 

（8）定位元素和打印

//定位元素的位置 
int LocateElem(SLinkList space,ElemType e,int headNode){
	int i=space[headNode].cur;
	while(i&&space[i].data!=e){
		i=space[i].cur;
	}
	return i;
}
 
//打印操作 
void PrintSLinkListNode(SLinkList space,int headNode){
	int i=space[headNode].cur;
	while(i!=0){
		printf("%d\t",space[i].data);
		i=space[i].cur;
	}
	printf("\n");
}

（9）主函数

int main(){
	SLinkList space;
	int i;
	int j;
	ElemType e;
	ElemType headNode;
	InitSLinkList(space,headNode);
	j=headNode;
	while(1){
		int flag=0;
		MenuSLinkList();
		printf("请输入操作: ");
		scanf("%d",&flag);
		switch(flag){
			case 1:
				InitSLinkList(space,headNode);
				printf("初始化成功!\n");
				break;
			case 2:
				printf("请输入元素(-1_end): ");
				scanf("%d",&e);
				while(e!=-1){
					j=CreateList(space,e,j);
					printf("请输入元素(-1_end): ");
					scanf("%d",&e);
				}
				break;
			case 3:
				printf("请输入插入的位置: ");
				scanf("%d",&i);
				printf("请输入插入的值: ");
				scanf("%d",&e);
				InsertNode(space,headNode,i,e);
				break;
			case 4:
                printf("请输入删除的节点位置: ");
				scanf("%d",&i); 
				DeleteNode(space,headNode,i,e);
				printf("删除的节点 = %d\n",e);
				break;
			case 5:
				PrintSLinkListNode(space,headNode);
				break;
			default:
				printf("结束操作\n");
		}
		if(flag==6){
			break;
		}
	}
	return 0;
}

（10）测试