一、线性表的静态单链表存储结构
1 #define MAXSIZE 100 /* 链表的最大长度 */ 2 typedef struct 3 { 4 ElemType data; 5 int cur; 6 }component,SLinkList[MAXSIZE];
二、代码实现
1 2 /* bo2-31.c 一个数组只生成一个静态链表(数据结构由c2-3.h定义)的基本操作(11个) */ 3 int Malloc(SLinkList space) /* 算法2.15 */ 4 { /* 若备用链表非空,则返回分配的结点下标(备用链表的第一个结点),否则返回0 */ 5 int i=space[0].cur; 6 if(i) /* 备用链表非空 */ 7 space[0].cur=space[i].cur; /* 备用链表的头结点指向原备用链表的第二个结点 */ 8 return i; /* 返回新开辟结点的坐标 */ 9 } 10 11 void Free(SLinkList space,int k) /* 算法2.16 */ 12 { /* 将下标为k的空闲结点回收到备用链表(成为备用链表的第一个结点) */ 13 space[k].cur=space[0].cur; /* 回收结点的＂游标＂指向备用链表的第一个结点 */ 14 space[0].cur=k; /* 备用链表的头结点指向新回收的结点 */ 15 } 16 17 void InitList(SLinkList L) 18 { 19 /* 构造一个空的链表，表头为L的最后一个单元L[MAXSIZE-1]，其余单元链成 */ 20 /* 一个备用链表，表头为L的第一个单元L[0]，“0”表示空指针 */ 21 int i; 22 L[MAXSIZE-1].cur=0; /* L的最后一个单元为空链表的表头 */ 23 for(i=0;i<MAXSIZE-2;i++) /* 将其余单元链接成以L[0]为表头的备用链表 */ 24 L[i].cur=i+1; 25 L[MAXSIZE-2].cur=0; 26 } 27 28 Status ClearList(SLinkList L) 29 { /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */ 30 int i,j,k; 31 i=L[MAXSIZE-1].cur; /* 链表第一个结点的位置 */ 32 L[MAXSIZE-1].cur=0; /* 链表空 */ 33 k=L[0].cur; /* 备用链表第一个结点的位置 */ 34 L[0].cur=i; /* 把链表的结点连到备用链表的表头 */ 35 while(i) /* 没到链表尾 */ 36 { 37 j=i; 38 i=L[i].cur; /* 指向下一个元素 */ 39 } 40 L[j].cur=k; /* 备用链表的第一个结点接到链表的尾部 */ 41 return OK; 42 } 43 44 Status ListEmpty(SLinkList L) 45 { /* 若L是空表，返回TRUE；否则返回FALSE */ 46 if(L[MAXSIZE-1].cur==0) /* 空表 */ 47 return TRUE; 48 else 49 return FALSE; 50 } 51 52 int ListLength(SLinkList L) 53 { /* 返回L中数据元素个数 */ 54 int j=0,i=L[MAXSIZE-1].cur; /* i指向第一个元素 */ 55 while(i) /* 没到静态链表尾 */ 56 { 57 i=L[i].cur; /* 指向下一个元素 */ 58 j++; 59 } 60 return j; 61 } 62 63 Status GetElem(SLinkList L,int i,ElemType *e) 64 { /* 用e返回L中第i个元素的值 */ 65 int l,k=MAXSIZE-1; /* k指向表头序号 */ 66 if(i<1||i>ListLength(L)) 67 return ERROR; 68 for(l=1;l<=i;l++) /* 移动到第i个元素处 */ 69 k=L[k].cur; 70 *e=L[k].data; 71 return OK; 72 } 73 74 int LocateElem(SLinkList L,ElemType e) /* 算法2.13（有改动） */ 75 { /* 在静态单链线性表L中查找第1个值为e的元素。若找到，则返回它在L中的 */ 76 /* 位序，否则返回0。（与其它LocateElem()的定义不同) */ 77 int i=L[MAXSIZE-1].cur; /* i指示表中第一个结点 */ 78 while(i&&L[i].data!=e) /* 在表中顺链查找(e不能是字符串) */ 79 i=L[i].cur; 80 return i; 81 } 82 83 Status PriorElem(SLinkList L,ElemType cur_e,ElemType *pre_e) 84 { /* 初始条件：线性表L已存在 */ 85 /* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */ 86 /* 否则操作失败，pre_e无定义 */ 87 int j,i=L[MAXSIZE-1].cur; /* i指示链表第一个结点的位置 */ 88 do 89 { /* 向后移动结点 */ 90 j=i; 91 i=L[i].cur; 92 }while(i&&cur_e!=L[i].data); 93 if(i) /* 找到该元素 */ 94 { 95 *pre_e=L[j].data; 96 return OK; 97 } 98 return ERROR; 99 } 100 101 Status NextElem(SLinkList L,ElemType cur_e,ElemType *next_e) 102 { /* 初始条件：线性表L已存在 */ 103 /* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */ 104 /* 否则操作失败，next_e无定义 */ 105 int j,i=LocateElem(L,cur_e); /* 在L中查找第一个值为cur_e的元素的位置 */ 106 if(i) /* L中存在元素cur_e */ 107 { 108 j=L[i].cur; /* cur_e的后继的位置 */ 109 if(j) /* cur_e有后继 */ 110 { 111 *next_e=L[j].data; 112 return OK; /* cur_e元素有后继 */ 113 } 114 } 115 return ERROR; /* L不存在cur_e元素,cur_e元素无后继 */ 116 } 117 118 Status ListInsert(SLinkList L,int i,ElemType e) 119 { 120 /* 在L中第i个元素之前插入新的数据元素e */ 121 int l,j,k=MAXSIZE-1; /* k指向表头 */ 122 if(i<1||i>ListLength(L)+1) 123 return ERROR; 124 j=Malloc(L); /* 申请新单元 */ 125 if(j) /* 申请成功 */ 126 { 127 L[j].data=e; /* 赋值给新单元 */ 128 for(l=1;l<i;l++) /* 移动i-1个元素 */ 129 k=L[k].cur; 130 L[j].cur=L[k].cur; 131 L[k].cur=j; 132 return OK; 133 } 134 return ERROR; 135 } 136 137 Status ListDelete(SLinkList L,int i,ElemType *e) 138 { /* 删除在L中第i个数据元素e，并返回其值 */ 139 int j,k=MAXSIZE-1; /* k指向表头 */ 140 if(i<1||i>ListLength(L)) 141 return ERROR; 142 for(j=1;j<i;j++) /* 移动i-1个元素 */ 143 k=L[k].cur; 144 j=L[k].cur; 145 L[k].cur=L[j].cur; 146 *e=L[j].data; 147 Free(L,j); 148 return OK; 149 } 150 151 Status ListTraverse(SLinkList L,void(*vi)(ElemType)) 152 { /* 初始条件:线性表L已存在 */ 153 /* 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */ 154 int i=L[MAXSIZE-1].cur; /* 指向第一个元素 */ 155 while(i) /* 没到静态链表尾 */ 156 { 157 vi(L[i].data); /* 调用vi() */ 158 i=L[i].cur; /* 指向下一个元素 */ 159 } 160 printf(" "); 161 return OK; 162 }