// func2-2.cpp 实现算法2.15、2.16的程序，main2-31.cpp和main2-32.cpp调用int Malloc(SLinkList space) // 算法2.15(见图2.24){ // 若备用链表非空，则返回分配的结点下标(备用链表的第一个结点)；否则返回0 int i=space[0].cur; if(i) // 备用链表非空 space[0].cur=space[i].cur; // 备用链表的头结点指向原备用链表的第二个结点 return i; // 返回新开辟结点的坐标}void Free(SLinkList space,int k) // 算法2.16(见图2.25){ // 将下标为k的空闲结点回收到备用链表(成为备用链表的第一个结点) space[k].cur=space[0].cur; // 回收结点的＂游标＂指向备用链表的第一个结点 space[0].cur=k; // 备用链表的头结点指向新回收的结点} 
生成静态链表的方法可有两种：一种是在一个数组中只生成一个静态链表，这种情况
可以固定静态链表的头指针位置，如最后一个单元([MAX_SIZE-1])；另一种是在一个数 组中可根据需要生成若干个独立的链表，每个链表的头指针在生成链表时才指定。第一种 方法指定数组名就指定了链表，函数的形参简单。但若在一个程序中用到多个链表，就需 要定义多个数组，每个数组的备用链表不能互相调剂，空间浪费较大。第二种方法指定一 个链表必须在指定数组名的同时指定链表的头指针位置，函数要多一个形参。bo2-31.cpp 是第一种情况的基本操作，main2-31.cpp 是验证bo2-31.cpp 的主函数。// bo2-31.cpp 一个数组只生成一个静态链表(数据结构由c2-3.h定义)的基本操作(11个)包括算法2.13#define DestroyList ClearList // DestroyList()和ClearList()的操作是一样的void InitList(SLinkList L){ // 构造一个空的链表L，表头为L的最后一个单元L[MAX_SIZE-1]，其余单元链成 // 一个备用链表，表头为L的第一个单元L[0]，“0”表示空指针(见图2.26) int i; L[MAX_SIZE-1].cur=0; // L的最后一个单元为空链表的表头 for(i=0;i ListLength(L)) return ERROR; for(l=1;l<=i;l++) // 移动到第i个元素处 k=L[k].cur; e=L[k].data; return OK;}int LocateElem(SLinkList L,ElemType e) // 算法2.13(有改动){ // 在静态单链线性表L中查找第1个值为e的元素。若找到，则返回它在L中的 // 位序；否则返回0。(与其它LocateElem()的定义不同) int i=L[MAX_SIZE-1].cur; // i指示表中第一个结点 while(i&&L[i].data!=e) // 在表中顺链查找(e不能是字符串) i=L[i].cur; return i;}Status PriorElem(SLinkList L,ElemType cur_e,ElemType &pre_e){ // 初始条件：线性表L已存在 // 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱； // 否则操作失败，pre_e无定义 int j,i=L[MAX_SIZE-1].cur; // i指示链表第一个结点的位置 do { // 向后移动结点 j=i; i=L[i].cur; }while(i&&cur_e!=L[i].data); if(i) // 找到该元素 { pre_e=L[j].data; return OK; } return ERROR;}Status NextElem(SLinkList L,ElemType cur_e,ElemType &next_e){ // 初始条件：线性表L已存在 // 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继； // 否则操作失败，next_e无定义 int j,i=LocateElem(L,cur_e); // 在L中查找第一个值为cur_e的元素的位置 if(i) // L中存在元素cur_e { j=L[i].cur; // cur_e的后继的位置 if(j) // cur_e有后继 { next_e=L[j].data; return OK; // cur_e元素有后继 } } return ERROR; // L不存在cur_e元素，cur_e元素无后继}Status ListInsert(SLinkList L,int i,ElemType e){ // 在L中第i个元素之前插入新的数据元素e(见图2.27) int l,j,k=MAX_SIZE-1; // k指向表头 if(i<1||i>ListLength(L)+1) return ERROR; j=Malloc(L); // 申请新单元 if(j) // 申请成功 { L[j].data=e; // 赋值给新单元 for(l=1;l ListLength(L)) return ERROR; for(j=1;j 
// main2-31.cpp 检验func2-2.cpp和bo2-31.cpp的主程序#include"c1.h"typedef int ElemType;#include"c2-3.h"#include"func2-2.cpp" // 两种方法都适用的函数在此文件中#include"bo2-31.cpp"#include"func2-3.cpp" // 包括equal()、comp()、print()、print2()和print1()函数void main(){ int j,k; Status i; ElemType e,e0; SLinkList L; InitList(L); for(j=1;j<=5;j++) i=ListInsert(L,1,j); printf("在L的表头依次插入1～5后：L="); ListTraverse(L,print); i=ListEmpty(L); printf("L是否空:i=%d(1:是0:否)表L的长度=%d\n",i,ListLength(L)); ClearList(L); printf("清空L后：L="); ListTraverse(L,print); i=ListEmpty(L); printf("L是否空:i=%d(1:是0:否)表L的长度=%d\n",i,ListLength(L)); for(j=1;j<=10;j++) ListInsert(L,j,j); printf("在L的表尾依次插入1～10后：L="); ListTraverse(L,print); GetElem(L,5,e); printf("第5个元素的值为%d\n",e); for(j=0;j<=1;j++) { k=LocateElem(L,j); if(k) printf("值为%d的元素在静态链表中的位序为%d\n",j,k); else printf("没有值为%d的元素\n",j); } for(j=1;j<=2;j++) // 测试头两个数据 { GetElem(L,j,e0); // 把第j个数据赋给e0 i=PriorElem(L,e0,e); // 求e0的前驱 if(!i) printf("元素%d无前驱\n",e0); else printf("元素%d的前驱为%d\n",e0,e); } for(j=ListLength(L)-1;j<=ListLength(L);j++) // 最后两个数据 { GetElem(L,j,e0); // 把第j个数据赋给e0 i=NextElem(L,e0,e); // 求e0的后继 if(!i) printf("元素%d无后继\n",e0); else printf("元素%d的后继为%d\n",e0,e); } k=ListLength(L); // k为表长 for(j=k+1;j>=k;j--) { i=ListDelete(L,j,e); // 删除第j个数据 if(i) printf("第%d个元素为%d,已删除。\n",j,e); else printf("删除第%d个元素失败(不存在此元素)。\n",j); } printf("依次输出L的元素："); ListTraverse(L,print); // 依次对元素调用print()，输出元素的值} 运行结果如下： /*在L的表头依次插入1～5后：L=5 4 3 2 1L是否空:i=0(1:是0:否)表L的长度=5清空L后：L=L是否空:i=1(1:是0:否)表L的长度=0在L的表尾依次插入1～10后：L=1 2 3 4 5 6 7 8 9 10第5个元素的值为5没有值为0的元素值为1的元素在静态链表中的位序为5元素1无前驱元素2的前驱为1元素9的后继为10元素10无后继删除第11个元素失败(不存在此元素)。第10个元素为10,已删除。依次输出L的元素：1 2 3 4 5 6 7 8 9Press any key to continue*/