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)。 插入操作包括寻找空闲节点、连接与前一个节点以及更新链表大小。 静态链表的操作相较于动态链表来说更为复杂，但是在没有动态内存分配的环境下很有用。 在实践中，应用静态链表需要仔细管理空闲节点列表，避免内存的浪费和碎片化。 静态链表虽然不如动态链表灵活，但在某些限制内存的场景下可能非常有用。
推荐阅读
您阅读本篇文章共花了：
发表评论