题目 1677:
数据结构-静态链表
时间限制: 3s
内存限制: 96MB 提交: 1606 解决: 765
题目描述
静态链表是使用顺序存储结构来实现的链表。严蔚敏《数据结构（C语言版）》在介绍静态链表时使用的是一个姓氏列表。
图1是书本上的静态链表示例，图（a）是初始化后插入了8个姓氏的链表，图（b）是在第5个元素前插入了“SHI”而删除了“WANG”的结果。
图1：静态链表示例
（a）修改前的状态；（b）修改后的状态
现在，我们就来实现一下这个静态链表。实际上静态链表与一般含有指针的链表没有太大的差别，只是静态链表的结点存放的空间不是在使用时临时分配的，而是在一开始就分配了固定的一些，一般是用数组。同时一般的链表使用指针来指向下一个结点而在静态链表中则使用数组下标了。大家如果看严蔚敏的书会发现书上的算法还是有些问题的。下面我就直接给大家展示一种静态链表的实现算法。
最重要的是模拟系统分配内存的过程。可以预先定义一个全局数组（space）作为后面分配的空间，然后再初始化这个数组，为以后分配做准备，如图2。初始化后，这个数组中的状态应该如图3(a)一样。这样，数组的第0个节点就是用来标识哪个结点可用来存储数据的。那么如果是含有头结点的静态链表，则一般开始时数组的第1个节点就是用来存放头结点的，此时数组第0个结点标识第2个结点可以用来存储数据，而第1个结点（静态链表的头结点）的下一个结点下标为0，标识着这个静态链表为空，如图3(b)。静态链表的初始化以及插入删除各种算法与一般的链表是相似的。具体描述如下：
图2：类型定义、用来模拟内存的数组定义以及初始化
图3：模拟内存的数组状态。(a)初始化后的状态，(b)给静态链表分配头结点后的状态
图4：在静态链表中查找元素在space中的位置（相当于地址）
图5：给静态链表中的结点分配存储空间，实际上返回的是数组中可用的结点下标
图6：释放静态链表中结点的存储空间
输入格式
静态链表的存储空间（图2中的space）始终只有11个节点，起始为空表。insert a e代表在第a个姓氏前插入姓氏e；delete a代表删除第a个姓氏；search e代表查找姓氏e的位置；show代表输出静态链表存储空间的状态。输入保证操作都合法。
输出格式
只遇到search和show时才输出。当遇到search时输出姓氏e在space中的位置；当遇到show时输出这11个结点的状态。姓氏占8个字符而数字占2个字符，姓氏左对齐。每个指令输出后面跟着含有20个星号的行。
样例输入
show insert 1 ZHAO show insert 2 QIAN show insert 3 SUN show insert 4 LI insert 5 ZHOU insert 6 WU insert 7 ZHENG insert 8 WANG show insert 1 ZHANG show search LI show
样例输出
2
0
3
4
5
6
7
8
9
10
0
********************
3
2
ZHAO 0
4
5
6
7
8
9
10
0
********************
4
2
ZHAO 3
QIAN 0
5
6
7
8
9
10
0
********************
5
2
ZHAO 3
QIAN 4
SUN 0
6
7
8
9
10
0
********************
10
2
ZHAO 3
QIAN 4
SUN 5
LI 6
ZHOU 7
WU 8
ZHENG 9
WANG 0
0
********************
0
10
ZHAO 3
QIAN 4
SUN 5
LI 6
ZHOU 7
WU 8
ZHENG 9
WANG 0
ZHANG 2
********************
5
********************
0
10
ZHAO 3
QIAN 4
SUN 5
LI 6
ZHOU 7
WU 8
ZHENG 9
WANG 0
ZHANG 2
********************