2.3.5 静态链表：用数组下标模拟指针

静态链表把一组结点放在数组中，每个结点的 next 不存地址，而存后继结点的数组下标，也称游标：

typedef struct { int data; int next; } SNode;
SNode pool[100];

数组位置与逻辑位序没有必然关系。若 head=3，pool[3].next=8，那么逻辑首结点在下标 3，第二个结点在下标 8；不能按 3,4,5 顺序读取。

它适合没有指针能力、内存需要集中管理或共享存储的环境。已知前驱游标时插入删除仍只改常数个 next，但容量固定，按位查找仍需沿游标走 $O(n)$。

还要管理未使用结点。常见做法是维护空闲链表 freeHead：申请结点时取出空闲链首，令 freeHead=pool[x].next；释放结点时把它插回空闲链首。这样“数据链”和“空闲链”共享同一数组，却必须保证一个槽位不会同时属于两条链。

陪做：数据链 head=2，且 2->7->4->-1；空闲链 freeHead=0，且 0->1->3->...。在 7 后插入新值，先从空闲链取下 0，再令 0.next=4、7.next=0，结果数据链是 2->7->0->4。

错解反馈：把下标 0 一律当空指针会与数组 0 号槽冲突，应明确约定如 -1 表示结束；只改数据链却未从空闲链摘除，会造成同一槽位被重复分配；数组连续不代表逻辑结点相邻。

迁移练习：删除上述数据链中的下标 7，并把它归还空闲链。答案先令 pool[2].next=pool[7].next，再令 pool[7].next=freeHead; freeHead=7。独立验收：能画出两条链在同一数组中的游标图，并检查无重复、无丢失。