会员网站建设百度开户联系方式
1.定义：
（1）单链表：各个结点散落在内存中的各个角落，每个结点有指向下一个节点的指针(下一个结点在内存 中的地址);
（2）静态链表：用数组的方式来描述线性表的链式存储结构: 分配一整片连续的内存空间，各个结点集中安置，包括了——数据元素and下一个结点的数组下标(游标)
其中数组下标为0的结点充当"头结点"
游标为-1表示已经到达表尾
若每个数据元素为4B，每个游标为4B，则每个结点共8B；假设起始地址为addr，则数据下标为2的存放地址为：addr+8*2
注意： 数组下标——物理顺序，位序——逻辑顺序； 优点：增、删操作不需要大量移动元素；
缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不变！
2.静态链表用代码表示：
也可以这样：
也等同于：
注意：SLinkList a 强调a是静态链表；struct Node a 强调a是一个Node型数组；
3.静态链表基本操作的实现
（1）初始化静态链表：把a[0]的next设为-1
void InitList(StaticLinkedList *list) {
list->head = -1; // 设置头节点的next为-1表示空链表
list->size = 0;
// 初始化所有节点为未使用状态，通常将next设置为下一个节点的索引表示空闲
for (int i = 0; i < MAXSIZE - 1; i++) {
list->nodes[i].next = i + 1;
}
list->nodes[MAXSIZE - 1].next = -1; // 最后一个节点的next设置为-1
}
（2）查找某个位序（不是数组下标，位序是各个结点在逻辑上的顺序）的结点：从头结点出发挨个往后遍历结点，时间复杂度O=(n)
Index FindByPosition(StaticLinkedList *list, int position) {
if (position < 0 || position >= list->size) {
return -1; // 位序无效
}
int curPosition = 0;
Index currentIndex = list->head;
while (currentIndex != -1 && curPosition < position) {
currentIndex = list->nodes[currentIndex].next;
curPosition++;
}
return currentIndex;
}
（3）在位序为i上插入结点：① 找到一个空的结点，存入数据元素；② 从头结点出发找到位序为i-1的结点；③修改新结点的next；④ 修改i-1号结点的next；
void Insert(StaticLinkedList *list, ElementType element, int position) {
if (position < 0 || position > list->size) {
return; // 位序无效
}
// 找到一个空闲节点用于插入新元素
Index newNodeIndex = list->nodes[0].next;
if (newNodeIndex != -1) { // 确保还有空闲节点
list->nodes[0].next = list->nodes[newNodeIndex].next;
list->nodes[newNodeIndex].data = element; // 存储数据
if (position == 0) { // 如果是在头部插入
list->nodes[newNodeIndex].next = list->head; // 新节点指向原头节点
list->head = newNodeIndex; // 头节点更新为新节点
} else {
Index prevNodeIndex = FindByPosition(list, position - 1); // 找到前一个节点
list->nodes[newNodeIndex].next = list->nodes[prevNodeIndex].next; // 新节点指向前节点的下一节点
list->nodes[prevNodeIndex].next = newNodeIndex; // 前节点指向新节点
}
list->size++;
}
}
（4）删除某个结点：① 从头结点出发找到前驱结点；② 修改前驱节点的游标；③ 被删除节点next设为-2；
4.学习总结：
静态链表使用数组模拟链表，每个元素包含数据和游标（下一个节点的索引）。
初始化时需设置一个头节点，并将所有节点串联起来作为一个空闲节点列表。
查找时需要遍历链表直到达到指定位置。这个操作的时间复杂度为O(n)。
插入操作包括寻找空闲节点、连接与前一个节点以及更新链表大小。
静态链表的操作相较于动态链表来说更为复杂，但是在没有动态内存分配的环境下很有用。
在实践中，应用静态链表需要仔细管理空闲节点列表，避免内存的浪费和碎片化。
静态链表虽然不如动态链表灵活，但在某些限制内存的场景下可能非常有用。