数组模拟链表--静态链表
提交数: 70, 通过率: 14.29%, 平均分: 25.71
题目描述:
静态链表是使用顺序存储结构的数组来模拟链表。下面是一个姓氏列表。
图1是静态链表示例，图（a）是初始化后插入了8个姓氏的链表，图（b）是在第5个元素前插入了“SHI”而删除了“zheng”的结果。
图1：静态链表示例
（a）修改前的状态；（b）修改后的状态
现在，我们就来实现一下这个静态链表。实际上静态链表与一般含有指针的链表没有太大的差别，只是静态链表的结点存放的空间不是在使用时临时分配的，而是在一开始就分配固定了，一般是用数组。同时一般的链表使用指针来指向下一个结点而在静态链表中则使用数组下标了。下面展示一种静态链表的实现算法。
最重要的是模拟系统分配内存的过程。可以预先定义一个全局数组（space）作为后面分配的空间，然后再初始化这个数组，为以后分配做准备，如图2。初始化后，这个数组中的状态应该如图3(a)一样。这样，数组的第0个节点就是用来标识哪个结点可用来存储数据的。那么如果是含有头结点的静态链表，则一般开始时数组的第1个节点就是用来存放头结点的，此时数组第0个结点标识第2个结点可以用来存储数据，而第1个结点（静态链表的头结点）的下一个结点下标为0，标识着这个静态链表为空，如图3(b)。静态链表的初始化以及插入删除各种算法与一般的链表是相似的。具体描述如下：
图2：类型定义、用来模拟内存的数组定义
输入格式:
静态链表的存储空间（图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
********************
提示:
提示：
1、要求每个指令输出后跟一个空行，别忘了。
2、姓氏占8个字符，数字占2个字符，姓氏左对齐，可以这样输出printf("%-8s%2d");对于指令search也要输出占2个字符的数字。
3、静态链表初始化时将所有内存设为空：
memset(space, 0 ,sizeof(space));
总结：
静态链表与一般链表极为相似：使用数组来模拟内存，使用数组下表来模拟内存中的地址。
时间限制: 1000ms空间限制: 32MB