C语言实现静态链表

定义静态链表的结构体

#define MAX_SIZE 30
#define ElemType char
//定义静态链表的节点，由数据和游标组成
typedef struct StaticNode {
	ElemType data;
	int cur;
}Node;

//这个结构包含了30个Node类型的节点，如图所示
typedef Node StaticList[MAX_SIZE];
           

初始化

cur游标指向下一个数组元素的index（利用下标模拟指针）

//引用，给main函数调用的mylist起别名，指向同一块内存空间
void InitList(StaticList  &space) {
	for (int i = 0; i < MAX_SIZE - 1; i++) {
		space[i].cur = i + 1;
	}
	space[MAX_SIZE - 1].cur = 0;
	space[0].cur = -1;
}
           

插入（头插）

head表示真实有数据的位置起始

pool表示剩余空间的位置起始

先插入A

如果再插入B（头插）-1表示已经是最后一个元素了

void Insert(StaticList &space, ElemType x) {
	int i = Malloc(space);
	if (i == 0) {
		printf("申请节点失败\n");
		return;
	}

	space[i].data = x;
	if (space[0].cur == -1) {//如果插入的是第一个节点
		space[i].cur = -1;//新插入的元素cur为-1
		space[0].cur = i;//头结点指向第一个节点在space数组中的位置
	}
	else {
	//因为是头插，新插入的元素直接被头结点指向，space[0].cur是原来被头指针指向的元素，现在放在新插入元素后
		space[i].cur = space[0].cur;
		space[0].cur = i;
	}
}

void showlist(StaticList &space) {
	int i = space[0].cur;
	while (i != -1) {
		printf("%c-->", space[i].data);
		i = space[i].cur;
	}
	printf("NULL\n");
}
//分配一个新节点空间
int  Malloc(StaticList &space) {
	int i = space[1].cur;//space[1]的下标为2，space[2]的下标为3，
	if (space[1].cur != 0) {
		space[1].cur = space[i].cur;//space[2]的下标为3赋值给space[1]的下标，即space[1]，cur=3
		//space[1]用于指向下一个可插入的节点的位置，在这里是space[3]
	}
	return i;//返回2，从space[2]的地方开始插入
}
//测试
void main() {

	StaticList mylist;
	InitList(mylist);

	for (int i = 0; i < 3; i++) {
		Insert(mylist, 'A'+i);
	}
	showlist(mylist);
}
           

一开始内存中

插入一个数据后

插入两条数据后（因为是头插，新元素放在头结点后面）

插入数据完毕

删除（头删）

void Delete(StaticList &space) {
	//1.找到现在头结点指向的元素（即要删除的元素）
	int i = space[0].cur;
	//2.把要删除元素的cur赋值给头结点，换种说法是让指针指向删除元素的cur所指向的下一个元素
	space[0].cur = space[i].cur;
	//3.让没有存放数据的节点（按照初始化的顺序）连续起来  即原来4->cur指向5，现在变成原来这样
	space[i].cur = space[1].cur;
	//4.以前没有存放数据的位置是5，现在是4（即要删除节点的位置），space[1].cur永远指向下一个能存放结点的位置。
	space[1].cur = i;

}
           

2.

3.

4.