1. 静态链表
-
用数组的方式实现的链表
-
单链表： 各个结点在内存中星罗棋布、散落天涯
-
静态链表：分配一整片连续的内存空间， 各个结点集中安置。
1.1 静态链表的优点
- 不需要像动态链表那样频繁地进行内存分配和释放，可以节省内存管理的开销。
- 可以提前分配一定大小的静态存储空间，避免了动态分配内存的不确定性和运行时开销。
- 实现简单，不需要使用指针，减少了指针操作的复杂性和内存占用。
1.2 静态链表的不足
- 大小固定，不支持动态扩展和缩小。
- 需要提前分配一定大小的存储空间，可能造成空间的浪费或不足。
- 插入和删除操作需要重建链表的链接关系，有一定的时间开销。
在静态链表中如果要表示，这个结点是最后一个结点，游标的值可以设为 -1, 表示之后已经没有其他结点了。
用代码定义一个静态链表
#define MaxSize 10 //静态链表的最大长度
typedef struct //静态链表结构类型的定义
{
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize];
#define MaxSize 10 //静态链表的最大长度
2. 静态链表的查找
在静态链表中查找数据可以通过遍历链表的方式来完成。由于静态链表没有指针来直接跳转到下一个节点，所以需要使用游标来遍历链表。
以下是一种在静态链表中查找数据的示例算法：
- 遍历链表，从链表头部开始，通过头节点的索引获取第一个节点的索引。
- 遍历链表中的每个节点，判断节点的数据是否与目标数据相等。
- 如果相等，找到了目标数据，返回节点的索引。
- 如果不相等，获取当前节点的下一个节点，更新当前节点的索引为下一个节点的索引。
- 若遍历完整个链表（即当前节点的索引为-1），仍未找到目标数据，则返回-1表示未找到。
这是一个简单的线性查找算法，时间复杂度为O(n)，其中n是链表中节点的数量。
3. 静态链表的插入
- 查找插入位置：
遍历静态链表，找到要插入位置的前一个节点。可以使用一个游标来遍历链表，初始时指向链表的头节点。
- 分配新节点：
在静态链表的空闲位置上分配一个新节点，为新节点赋值。
- 插入节点：
将新节点的下一个节点指向前一个节点的下一个节点，然后将前一个节点的下一个节点指向新节点的位置。
静态链表的优点：
- 相比于动态链表，静态链表的存储空间是预先分配好的，不需要频繁地进行内存申请和释放，因此在一些内存有限或者对内存分配效率有要求的场景下，静态链表可能更为适用。
- 静态链表在存储空间上是连续的，可以提高数据访问的效率，尤其是在对元素进行遍历、查找和索引访问等操作时，相对于动态链表具有一定的性能优势。
静态链表的缺点：
- 静态链表的长度是固定的，无法随意扩展或缩小，一旦达到最大长度，就无法再插入新节点。
静态链表在插入和删除节点时，需要进行额外的操作来维护节点间的连接关系，可能会增加一定的编程复杂性。 - 静态链表的每个节点需预先分配固定大小的存储空间，可能会造成空间的浪费，特别是在某些节点存储的数据量较小的情况下。
4. 知识回顾
