静态链表

静态链表

用数组描述的链表为静态链表，也称游标实现法。

这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。

假设我们初始化完的链表为：

初始化的结构体数组大小为10

假设我们要在d后面插入e的话：

那我们要在b后面插入x呢？

我们已经看懂了插入，再来看一下删除操作，把c删掉:

下面为静态链表主要的一些代码：

#include<stdio.h>
#define MAX_SIZE 10
typedef int ElemType;
typedef struct Node{
	ElemType e;
	int cur;
}StaticList[MAX_SIZE];
void init(StaticList L){
	for(int i=0;i<MAX_SIZE;i++){
		L[i].cur=i+1;
		L[i].e=' ';
	}
	char c[]={'A','B','C','D','E','F'};
	for(int i=0;i<6;i++){
		if(i==0){
			int index=L[0].cur;
			L[index].e=c[i];
			L[0].cur=L[index].cur;
			L[index].cur=0;
			L[MAX_SIZE-1].cur=index;
		}else{
			int index=L[0].cur;
			L[index].e=c[i];
			L[0].cur=L[index].cur;
			L[index-1].cur=index;
			L[index].cur=0;
		}
	}
	L[0].e++;//代表长度
}
void show(StaticList L){
	for(int i=0;i<MAX_SIZE;i++){
		printf("%3d",L[i].cur);//游标
	}
	printf("\n");
	for(int i=0;i<MAX_SIZE;i++){
		printf("%3c",L[i].e);//元素
	}
	printf("\n");
	for(int i=0;i<MAX_SIZE;i++){
		printf("%3d",i);//角标
	}
	printf("\n");
}
void print(StaticList L){
	int k=MAX_SIZE-1;
	while(k!=0){
		k=L[k].cur;
		if(k==0){
			break;
		}else{
			printf("%c",L[k].e);
		}
	}
	printf("\n");
}
void insert(StaticList L,int position,ElemType e){
	int k=MAX_SIZE-1;
	for(int i=1;i<=position-1;i++){
		k=L[k].cur;
	}
	int index=L[0].cur;
	L[index].e=e;
	L[0].cur=L[index].cur;
	L[index].cur=L[k].cur;
	L[k].cur=index;
}
void delete(StaticList L,int position){
	int k=MAX_SIZE-1;
	for(int i=1;i<position;i++){
		k=L[k].cur;
	}
	int index=L[k].cur;
	L[k].cur=L[index].cur;
	L[index].cur=L[0].cur;
	L[0].cur=index;
	L[index].e=' ';
}
void main(){
	StaticList L;//代表一个结构体数组
	init(L);
	show(L);
	printf("打印：\n");
	print(L);
	insert(L,4,'G');
	show(L);
	printf("打印：\n");
	print(L);
	delete(L,3);
	show(L);
	printf("打印：\n");
	print(L);
}

运行结果为：

该代码和运行结果与我之前的例子不是同一种问题！