// c2-3.h 线性表的静态单链表存储结构(见图2.23)
#define MAX_SIZE 100 // 链表的最大长度
typedef struct
{
ElemType data;
int cur;
}component,SLinkList[MAX_SIZE];// algo2-7.cpp 教科书中图2.10静态链表示例
// 第1个结点的位置在[0].cur中。成员cur的值为0，则到链表尾
#include"c1.h"
#define N 6 // 字符串长度
typedef char ElemType[N];
#include"c2-3.h"
void main()
{
SLinkList s={{"",1},{"ZHAO",2},{"QIAN",3},{"SUN",4},{"LI",5},{"ZHOU",6},{"WU",7},
{"ZHENG",8},{"WANG",0}}; // 教科书中图2.10(a)的状态
int i;
i=s[0].cur; // i指示第1个结点的位置
while(i)
{ // 输出教科书中图2.10(a)的状态
printf("%s ",s[i].data); // 输出链表的当前值
i=s[i].cur; // 找到下一个
}
printf("
");
s[4].cur=9; // 按教科书中图2.10(b)修改(在"LI"之后插入"SHI")
s[9].cur=5;
strcpy(s[9].data,"SHI");
s[6].cur=8; // 删除"ZHENG"
i=s[0].cur; // i指示第1个结点的位置
while(i)
{ // 输出教科书中图2.10(b)的状态
printf("%s ",s[i].data); // 输出链表的当前值
i=s[i].cur; // 找到下一个
}
printf("
");
}运行结果如下：
/*ZHAO QIAN SUN LI ZHOU WU ZHENG WANG ZHAO QIAN SUN LI SHI ZHOU WU WANG Press any key to continue */
/* algo2-7.cpp 输出不是按数组下标的顺序输出的，而是像链表一样，由当前结点cur 域 的值决定下一个结点的位置确定输出。这就是链表的特点。但algo2-7.cpp 插入新结点是 完全靠人工判断该结点是否为空闲结点，而不是“自动地”找到空闲结点作为新结点，该 方法不能满足实际应用的需要。为了解决这个问题，将所有空闲结点链接形成一个备用链 表，数组下标为0 的单元为备用链表的头结点(这时，链表的头结点就不能再是数组下标 为0 的单元了，需要另外定义)。静态数组实际有2 个链表，一个链表上链接的是线性表 的结点，另一个链表(备用链表)上链接的是所有没被使用的结点。静态数组的每一个元素 都链接在这2 个链表中的一个上。当线性表需要新结点时，把备用链表中的首元结点(由 [0].cur 指示)从备用链表中删除，作为新结点，插入线性表。当删除线性表中的结点时， 被删除的结点插入备用链表中，成为备用链表的首元结点。之所以从备用链表删除结点或 向备用链表插入结点都在表头进行，是因为这样效率最高。开辟新结点和回收空闲结点的 操作如算法2.15、2.16 所示，在程序func2-2.cpp 中实现。 */