目录

一、什么是静态链表

1.单链表和静态链表

二、如何定义一个静态链表

1.第一种方式

2.第二种方式

         3.验证

三、基本操作的实现 

四、总结

单链表：各个结点在内存中星罗棋布、散落天涯

静态链表：分配一整片连续的内存空间，各个结点集中安置

每个数据元素4B，每个游标4B（每个结点功8B），设起始地址为addr，e1的存放地址为addr+8*2

1）定义结构体

2）声明一个数组，作为静态链表，占用连续存储空间

1）定义结构体

等价于

2）声明一个数组，作为静态链表，占用连续存储空间

等价于

结论：SLinkList b —— 相当于定义了一个长度为MaxSize的Node型数组

1）初始化静态链表

把a[0]的next设为-1

2）查找

从头节点出发挨个往后遍历结点

注：某一个位序的结点不是某一数组下标的结点

位序：结点在逻辑上的顺序

数组下标反映各个结点在物理上的顺序

3）插入位序为i的结点

①找到一个空的结点，存入数据元素

②从头结点出发找到位序为i-1的结点

③修改新结点的next

④修改i-1号结点的next

注：找空结点时候，可能会存在脏数据，所以在声明变量时，可让next为某个特殊值

4）删除某个结点

①从头节点出发找到前驱结点

②修改前驱结点的游标

③被删除结点next设为-2

静态链表：用数组的方式实现的链表

注：

①0号结点充当头结点

②游标为-1表示已经到达表尾

③游标充当“指针”

④用一个特殊的数值标记空闲结点

优点：增、删操作不需要大量移动元素

缺点：不能随机存取，只能从头节点开始依次往后查找；容量固定不可变

适用场景：

①不支持指针的低级语言

②数据元素数量固定不变的场景（如操作系统的文件分配表FAT）