静态链表概念与实现

"2.3.5 静态链表1" 静态链表是一种特殊的链式存储结构，与传统的单链表不同，它不是通过指针来连接各个节点，而是利用数组的下标来模拟指针的效果。这种数据结构在内存中占用的是连续的空间，与单链表相比，它的节点在内存中的分布更为集中。 在静态链表中，每个节点由两部分组成：数据元素和下一个节点的数组下标，这个下标被称为游标。游标为-1表示该节点是链表的末尾，而0号节点通常作为静态链表的头节点。例如，如果一个静态链表的起始地址是addr，那么e1节点的实际地址将是addr + 8 * 2，因为每个节点包括4字节的数据元素和4字节的游标，总计8字节。 用代码定义一个静态链表，可以创建一个固定大小的数组，如SLinkList，其中每个元素代表一个节点，包含数据元素和游标。例如，SLinkList b 实际上是一个长度为MaxSize的Node型数组。初始化时，需要将a[0]的next设为-1表示链表结束，其他节点的next设为特殊值（如-2）来标记它们为空闲。 在静态链表中插入一个位序为i的结点时，需要遵循以下步骤： 1. 寻找一个空闲的节点，即next值为特殊空闲标志的节点，然后将数据元素存入该节点。 2. 从头结点开始，遍历到位序为i-1的节点。 3. 修改新插入节点的next，将其设置为原本位序为i的节点的数组下标。 4. 修改位序为i-1的节点，将其next改为新节点的数组下标，从而将新节点链接到链表中。 删除操作类似，需要找到要删除节点的前驱节点，改变前驱节点的next指向被删除节点的后继节点，然后标记被删除节点为空闲。 静态链表的优点在于其内存管理相对简单，因为所有节点都在同一块内存区域，这使得内存分配和回收更加高效。然而，由于节点的位置是固定的，插入和删除操作可能涉及较多的元素移动，效率相对较低。此外，静态链表的容量在创建时必须预先确定，无法动态扩展。 总结来说，静态链表是一种节省内存空间、便于内存管理的链式数据结构，它利用数组下标来模拟链式连接，适用于内存有限或者对内存管理有特定要求的场景。其主要操作包括初始化、插入和删除，这些操作都需要考虑到节点的空闲状态以及如何通过数组下标来维护链表的结构。