1、编写程序实现顺序表的各种基本运算：初始化、插入、删除、取表元素、求表长、输出表、销毁、判断是否为空表、查找元素。在此基础上设计一个主程序完成如下功能：
（1）初始化顺序表L；
（2）依次在表尾插入a，b，c，d，e五个元素；
（3）输出顺序表L；
（4）输出顺序表L的长度；
（5）判断顺序表L是否为空；
（6）输出顺序表L的第4个元素；
（7）输出元素c的位置；
（8）在第3个位置上插入元素f，之后输出顺序表L；
（9）删除L的第2个元素，之后输出顺序表L；
（10）销毁顺序表L。
2、编写程序实现单链表的各种基本运算：初始化、插入、删除、取表元素、求表长、输出表、销毁、判断是否为空表、查找元素。在此基础上设计一个主程序完成如下功能：
（1）初始化单链表L；
（2）依次在表尾插入a，b，c，d，e五个元素；
（3）输出单链表L；
（4）输出单链表L的长度；
（5）判断单链表L是否为空；
（6）输出单链表L的第4个元素；
（7）输出元素c的位置；
（8）在第3个位置上插入元素f，之后输出单链表L；
（9）删除L的第2个元素，之后输出单链表L；
（10）销毁单链表L。
1 顺序表 2 #include<stdio.h> 3 #include<malloc.h> 4 #include<stdlib.h> 5 6 #define TRUE 1 7 #define FALSE 0 8 #define OK 1 9 #define ERROR 0 10 #define INFEASIBLE -1 11 #define OVERFLOW -2 12 typedef int Status; 13 typedef char ElemType; 14 15 #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 16 #define LISTINCREMENT 10 //线性表存储空间的分配增量 17 typedef struct { 18 ElemType *elem; //存储空间基地址 19 int length; //当前长度 20 int listsize; //当前分配的存储容量 21 } SqList; 22 23 Status InitList_Sq(SqList &L) { //算法2.3 24 L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); 25 if (!L.elem) exit(OVERFLOW); //存储分配失败 26 L.length = 0; //空表长度为0 27 L.listsize = LIST_INIT_SIZE; //初始存储容量 28 return OK; 29 }//InitList_Sq 30 31 Status ListInsert_Sq(SqList &L, int i, ElemType e) { //算法2.4 32 ElemType *newbase, *p, *q; 33 if (i<1 || i>L.length + 1) return ERROR; //i值不合法 34 if (L.length >= L.listsize) 35 { //当前存储空间已满，增加分配 36 newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType)); 37 if (!newbase) exit(OVERFLOW); //存储分配失败 38 L.elem = newbase; //新基址 39 L.listsize += LISTINCREMENT; //增加存储容量 40 } 41 q = &(L.elem[i - 1]); //q为插入位置 42 for (p = &(L.elem[L.length - 1]); p >= q; --p) *(p + 1) = *p; //元素右移 43 *q = e; //插入e 44 ++L.length; //表长增1 45 return OK; 46 } 47 48 void DispSqList(SqList L) 49 { 50 int i; 51 for (i = 0; i < L.length; i++) 52 printf("%c ", L.elem[i]); 53 } 54 55 Status ListDelete(SqList &L, int i, ElemType &e) 56 { 57 ElemType *p,*q; 58 if ((i < 1) || (i > L.length)) return ERROR; 59 p = &(L.elem[i - 1]); 60 e = *p; 61 q = L.elem + L.length - 1; 62 for (++p; p <= q; ++p) 63 *(p - 1) = *p; 64 --L.length; 65 return OK; 66 } //ListDelete_Sq 67 68 Status GetElem(SqList L, int i, ElemType &e) 69 { 70 if (L.length == 0 || i<1 || i>L.length) 71 return ERROR; 72 e = L.elem[i - 1]; 73 return OK; 74 } 75 76 int ListLength(SqList L) 77 { 78 return(L.length); 79 } 80 81 Status DestroyList(SqList &L) 82 { 83 free(L.elem); 84 L.length = 0; 85 return OK; 86 } 87 88 Status ListEmpty(SqList L) 89 { 90 return(L.length == 0); 91 } 92 93 int LocateElem(SqList L, ElemType e) 94 { 95 int i = 0; 96 while (i < L.length && L.elem[i] != e) i++; 97 if (i >= L.length) return 0; 98 else return i + 1; 99 } 100 101 void main() 102 { 103 SqList h; 104 ElemType e; 105 InitList_Sq(h); 106 ListInsert_Sq(h, h.length + 1, 'a'); 107 ListInsert_Sq(h, h.length + 1, 'b'); 108 ListInsert_Sq(h, h.length + 1, 'c'); 109 ListInsert_Sq(h, h.length + 1, 'd'); 110 ListInsert_Sq(h, h.length + 1, 'e'); 111 DispSqList(h); 112 printf("%d\n\n",ListLength(h)); 113 ListEmpty(h); 114 if (ListEmpty(h)) 115 { 116 printf("Empty\n\n"); 117 } 118 else 119 { 120 printf("Not empty\n\n"); 121 } 122 GetElem(h, 4, e); 123 printf("%c\n", e); 124 printf("%d\n",LocateElem(h, 'c')); 125 ListInsert_Sq(h,3,' f'); 126 DispSqList(h); 127 ListDelete(h, 2, e); 128 DispSqList(h); 129 DestroyList(h); 130 } 131 132 133 134 135 136 单链表 137 138 139 140 #include<stdio.h> 141 #include<malloc.h> 142 #include<stdlib.h> 143 144 #define TRUE 1 145 #define FALSE 0 146 #define OK 1 147 #define ERROR 0 148 #define INFEASIBLE -1 149 #define OVERFLOW -2 150 typedef int Status; 151 152 typedef char ElemType; 153 154 155 typedef struct LNode { 156 ElemType data; 157 int length; 158 struct LNode *next; 159 }LNode, *LinkList; 160 161 162 Status InitList_L(LinkList &L) { 163 L = (LinkList)malloc(sizeof(LNode)); 164 L->next = NULL; 165 return OK; 166 } 167 168 Status ListInsert_L(LinkList L, int i, ElemType e) { 169 LinkList p = L,s; 170 int j = 0; 171 while (p && j < i - 1) 172 { 173 p = p->next; 174 ++j; 175 } 176 if (!p || j > i - 1) 177 { 178 return ERROR; 179 } 180 else 181 { 182 s = (LinkList)malloc(sizeof(LNode)); 183 s->data = e; 184 s->next = p->next; 185 p->next = s; 186 return OK; 187 } 188 } 189 190 void DispList_L(LinkList L) 191 { 192 LinkList p = L->next; 193 while (p != NULL) 194 { 195 printf("%c\n", p->data); 196 p = p->next; 197 } 198 199 } 200 201 void DestoryList(LinkList &L) 202 { 203 LinkList p = L, q = p->next; 204 while (q != NULL) 205 { 206 free(p); 207 p = q; 208 q = p->next; 209 } 210 free(p); 211 } 212 213 Status ListLength_L(LinkList L) { 214 LinkList p = L; int n = 0; 215 while (p->next != NULL) 216 { 217 n++; 218 p = p->next; 219 } 220 return (n); 221 } 222 223 Status ListDelete(LinkList L, int i, ElemType &e){ 224 int j; 225 LinkList p, q; 226 p = L; 227 j = 1; 228 while (p->next && j < i) 229 { 230 p = p->next; 231 ++j; 232 } 233 if (!(p->next) || j > i) 234 { 235 return ERROR; 236 } 237 q = p->next; 238 p->next = q->next; 239 e = q->data; 240 free(q); 241 return OK; 242 } 243 244 Status ListEmpty_L(LinkList L) 245 { 246 return(L->length == 0); 247 } 248 249 Status GetElem(LinkList L, int i, ElemType &e) 250 { 251 int j; 252 LinkList p; 253 p = L->next; 254 j = 1; 255 while (p&&j<i) 256 { 257 p = p->next; 258 ++j; 259 } 260 if (!p || j > i) 261 { 262 return ERROR; 263 } 264 e = p->data; 265 return OK; 266 } 267 268 Status LocateElem(LinkList L, int e) 269 { 270 LinkList p = L; 271 int n=0; 272 //p->length = 0; 273 while (p != NULL) 274 { 275 if(p->data != e) 276 { 277 p = p->next; 278 n++; 279 } 280 else 281 { 282 break; 283 } 284 } 285 if(p != NULL) 286 { 287 return n; 288 } 289 else 290 { 291 return ERROR; 292 } 293 } 294 295 void main() 296 { 297 LinkList h; 298 ElemType e; 299 InitList_L(h); 300 ListInsert_L(h, 1, 'a'); 301 ListInsert_L(h, 2, 'b'); 302 ListInsert_L(h, 3, 'c'); 303 ListInsert_L(h, 4, 'd'); 304 ListInsert_L(h, 5, 'e'); 305 DispList_L(h); 306 printf("%d\n", ListLength_L(h)); 307 if (ListEmpty_L(h)) 308 { 309 printf("Empty\n\n"); 310 } 311 else 312 { 313 printf("Not empty\n\n"); 314 } 315 GetElem(h, 4, e); 316 printf("%c\n", e); 317 printf("%d\n", LocateElem(h, 'c')); 318 ListInsert_L(h, 3, 'f'); 319 DispList_L(h); 320 ListDelete(h, 2, e); 321 DispList_L(h); 322 DestoryList(h); 323 }
