本程序托管在开源中国http://git.oschina.net/cryt/c_adt
该程序包含list.h头文件，包含结构体以及函数的声明， list.c文件，包含具体函数的实现，demo.c为演示程序。
本链表数据结构如下：
list结构体 表示整体的一个链表
listnode是结点定义
而listnode中的指针pelem指向的是元素的具体内容。
Pelem声明为void *类型。这可以使得链表可以是不同的类型。也就是说，可以在同一个程序中使用不同类型的多个链表。
本程序中链表设置了头结点和尾结点，这给许多操作带来方便。头结点和尾结点并不包含数据。链表初始化的时候，头结点指向尾结点，尾结点指向头结点。头结点的后继是首节点，尾结点的前驱是末节点。头结点和尾结点只是为了方便操作，它们存在于链表的整体定义中，地址保持不变。
list.h
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <stdio.h> #include <stdlib.h> #include <malloc.h> #define BOOL int #define TRUE 1 #define FALSE 0 //链表结点结构 存储一个结点 typedef struct listnode{ void * pelem; //抽象的数据域 可以指向任何类型 struct listnode * pre; //指向上一个结点 struct listnode * next; //指向下一个结点 } listnode; //链表结构 储存整个链表 typedef struct list{ int elemsize; //链表结点指向的数据域的大小 int listsize; //链表中元素的个数 struct listnode header; //头结点 struct listnode trailer; //尾结点 } list; list * list_init(int elemsize); //初始化链表 BOOL getpos_invalid(list * pL, int i); //判断取值元素的位置是否符合要求 BOOL list_exist(list * pL); //判断链表是否存在 BOOL list_empty(list * pL); //判断链表是否为空 若不存在则不为空 BOOL getpos_invalid(list * pL, int i); //判断元素位置是否合法 BOOL putpos_invalid(list * pL, int i); //判断要插入的位置是否合法 尾指针算一个 BOOL list_getelem(list * pL, int i, void * pe); //取第几个元素放到pe指向的结构 listnode * list_getp(list * pL, int i); //根据位置返回该位置的结点指针，可能是尾指针 BOOL list_insert(list * pL, listnode * p, void * pe); //在某结点位置前插入结点 可能是尾结点之前 BOOL list_travel(list * pL, void visit()); //遍历链表 执行visit操作 BOOL list_clear(list * pL); //清空链表 BOOL list_destroy(list ** pL); //销毁链表 BOOL list_remove(list * pL, listnode * pnode, void *p); //删除一个元素 int list_length(list * pL); //判断列表长度 int list_locateelem(list * pL, void * pe, BOOL compare()); BOOL list_priorelem(list * pL, void * pe, void * pre_e); BOOL list_nextelem(list * pL, void * pe, void * next_e); BOOL equal(void * a, void * b); BOOL savelist(list * pL); BOOL loadlist(list ** pL); |
list.c
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 |
//初始化链表 list * list_init(int elemsize) { list * pL; if((pL = (list *)malloc(sizeof(list))) == NULL) exit(-1); pL->elemsize = elemsize; pL->listsize = 0; pL->header.pelem = NULL; pL->header.next = &(pL->trailer); pL->header.pre = NULL; pL->trailer.pelem = NULL; pL->trailer.pre = &(pL->header); pL->trailer.next = NULL; return pL; } //清空链表 链表不存在时 返回错误 BOOL list_clear(list * pL) { listnode * p, *q; int i; if (list_exist(pL) == FALSE) return FALSE; if (pL->listsize == 0) return TRUE; p = pL->header.next; i = 1; while (i <= pL->listsize) { free(p->pelem); q = p; p = p->next; free(q); i++; } pL->header.next = &pL->trailer; pL->trailer.pre = &pL->header; pL->listsize = 0; return TRUE; } //销毁链表 若本来就不存在 返回成功 BOOL list_destroy(list ** pL) { if (list_exist(*pL) == FALSE) return TRUE; if (list_clear(*pL) == FALSE) return FALSE; free(*pL); *pL = NULL; return TRUE; } //判断列表是否存在 BOOL list_exist(list * pL) { return (pL == NULL) ? FALSE : TRUE; } //判断链表是否为空 BOOL list_empty(list * pL) { if (list_exist(pL) == FALSE) return FALSE; if (pL->listsize == 0) return TRUE; return FALSE; } //判断位置是否在合理区间 1到元素总数 BOOL getpos_invalid(list * pL, int i) { if (list_exist(pL) == FALSE) return FALSE; if (i < 1 || i > pL->listsize) return FALSE; else return TRUE; } //判断位置是否合理 1到总数+1 尾指针 BOOL putpos_invalid(list * pL, int i) { if (list_exist(pL) == FALSE) return FALSE; if (i < 1 || i > pL->listsize + 1) return FALSE; else return TRUE; } //根据位置返回该位置结点指针 可能是尾指针 listnode * list_getp(list * pL, int i) { int j; listnode * p; //可能指向尾指针 if (putpos_invalid(pL, i) == FALSE) return NULL; j = 1; p = pL->header.next; while (j < i) { p = p->next; j++; } return p; } //根据位置把该位置的元素复制到pe指向的内存 BOOL list_getelem(list * pL, int i, void * pe) { int j; listnode * p; if (getpos_invalid(pL, i) == FALSE) return FALSE; j = 1; p = pL->header.next; while (j < i) { p = p->next; j++; } memcpy(pe, p->pelem, pL->elemsize); return TRUE; } //插入元素 插入在p结点之前 p可能是尾指针 BOOL list_insert(list * pL, listnode * p, void * pe) { listnode * pnode; if((pnode = (listnode *)malloc(sizeof(listnode))) == NULL) exit(-1); pnode->pelem = malloc(pL->elemsize); memcpy(pnode->pelem, pe, pL->elemsize); p->pre->next = pnode; pnode->pre = p->pre; pnode->next = p; p->pre = pnode; pL->listsize++; return TRUE; } //遍历对元素进行visit()操作 BOOL list_travel(list * pL, void visit()) { listnode * p; int i; if (list_exist(pL) == FALSE) { printf("链表不存在!"); return FALSE; } if (list_empty(pL) == TRUE) { printf("是空表!"); return FALSE; } i = 1; p = pL->header.next; while (i <= pL->listsize) { printf("第%d个:\t", i); visit(p->pelem); p = p->next; i++; } return TRUE; } //保存到文件 BOOL savelist(list * pL) { FILE * out; listnode * p; int i; if (list_exist(pL) == FALSE) return FALSE; if ((out = fopen("list.dat", "wb")) == NULL) return FALSE; fwrite(&pL->listsize, sizeof(pL->listsize), 1, out); fwrite(&pL->elemsize, sizeof(pL->elemsize), 1, out); p = pL->header.next; i = 1; while (i <= pL->listsize) { fwrite(p->pelem, pL->elemsize, 1, out); p = p->next; i++; } fclose(out); return TRUE; } //从文件加载 BOOL loadlist(list ** pL) { FILE * in; listnode * p, * q; int i; if (list_destroy(pL) == FALSE) return FALSE; if ((in = fopen("list.dat", "rb")) == NULL) return FALSE; if (((*pL) = (list *)malloc(sizeof(list))) == NULL) exit(-1); fread(&(*pL)->listsize, sizeof((*pL)->listsize), 1, in); fread(&(*pL)->elemsize, sizeof((*pL)->elemsize), 1, in); (*pL)->header.pelem = NULL; (*pL)->header.next = &((*pL)->trailer); (*pL)->header.pre = NULL; (*pL)->trailer.pelem = NULL; (*pL)->trailer.pre = &((*pL)->header); (*pL)->trailer.next = NULL; i = 1; q = &((*pL)->header); while (i <= (*pL)->listsize) { if((p = (listnode *)malloc(sizeof(listnode))) == NULL) exit(-1); p->pelem = malloc((*pL)->elemsize); fread(p->pelem, (*pL)->elemsize, 1, in); q->next = p; p->pre = q; q = p; i++; } q->next = &(*pL)->trailer; (*pL)->trailer.pre = q; return TRUE; } //删除单个元素 根据元素内容*pnode找到该节点 并将删除的元素放到p BOOL list_remove(list * pL, listnode * pnode, void *p) { if (list_exist(pL) == FALSE || list_empty(pL) == TRUE) return FALSE; pnode->pre->next = pnode->next; pnode->next->pre = pnode->pre; memcpy(p, pnode->pelem, pL->elemsize); free(pnode); pL->listsize--; return TRUE; } //返回列表有效元素个数 int list_length(list * pL) { if (list_exist(pL) == TRUE) return pL->listsize; else return -1; } //根据规则查找列表中第一个满足要求的元素 放到pe中 int list_locateelem(list * pL, void * pe, BOOL compare()) { listnode * p; int i; p = pL->header.next; i = 1; while (i <= pL->listsize) { if (compare(p->pelem, pe) == TRUE) return i; p = p->next; i++; } return 0; } //求前驱元素 BOOL list_priorelem(list * pL, void * pe, void * pre_e) { int i; if (list_exist(pL) == FALSE || list_empty(pL) == TRUE) return FALSE; if((i = list_locateelem(pL, pe, &equal)) == 0 || i == 1) return FALSE; if (list_getelem(pL, i-1, pre_e) == TRUE) return TRUE; else return FALSE; } //求后继元素 BOOL list_nextelem(list * pL, void * pe, void * next_e) { int i; if (list_exist(pL) == FALSE || list_empty(pL) == TRUE) return FALSE; if((i = list_locateelem(pL, pe, &equal)) == 0 || i == pL->listsize) return FALSE; if (list_getelem(pL, i+1, next_e) == TRUE) return TRUE; else return FALSE; } |
demo.c
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 |
#include "list.h" #include "list.c" #define ElemType student typedef struct { char name[20]; int age; } student; void display(void *stu); void menu(void); void inputstu(student * p); //输入学生信息 void inputindex(int *); //输入位置信息 int main(void){ list * pL; student * pe; listnode * pnode; student pre_e, next_e; int op; int i; op = 0; pL = NULL; if ((pe = (student *)malloc(sizeof(student))) == NULL) exit(-1); do{ system("cls"); menu(); printf(" Please input your option[0-12]:"); scanf("%d",&op); switch(op){ case 0: break; case 1: //初始化列表 if (list_exist(pL) == TRUE || list_empty(pL) == FALSE) list_destroy(&pL); if ((pL = list_init(sizeof(student))) != NULL) { printf("初始化成功!"); getchar();getchar(); } else { printf("初始化失败!"); getchar();getchar(); } break; case 2: //插入元素 inputindex(&i); inputstu(pe); if ((pnode = (list_getp(pL, i))) == NULL) { printf("位置不对或者链表不存在!"); getchar();getchar(); break; } if (list_insert(pL, pnode, pe) == TRUE) printf("插入成功!"); else printf("插入失败!"); getchar();getchar(); break; case 3: //销毁列表 if(list_destroy(&pL) == TRUE) printf("销毁成功!"); getchar();getchar(); break; case 4: //清空列表 if(list_clear(pL) == TRUE) { printf("清空成功!"); getchar();getchar(); } else { printf("列表不存在!"); getchar();getchar(); } break; /* case 5: //删除区间 printf("请输入区间"); scanf("%d %d", &lo, &hi); if(list_delete(pL, lo, hi) == FALSE) { printf("删除失败"); getchar();getchar(); } else { printf("删除成功!"); getchar();getchar(); } break;*/ case 6: //删除某元素 inputindex(&i); if (getpos_invalid(pL, i) == FALSE) { printf("位置不合法或列表不存在"); getchar();getchar(); break; } if ((pnode = list_getp(pL, i)) == NULL) { printf("删除失败!"); getchar();getchar(); break; } if(list_remove(pL, pnode, pe) == TRUE) { printf("第%d个元素", i); display(pe); printf("删除成功"); getchar();getchar(); } else { printf("删除失败!"); getchar();getchar(); } break; case 7: //判断列表是否存在 if (list_exist(pL) == TRUE) { printf("列表存在!"); getchar();getchar(); } else { printf("列表不存在!"); getchar();getchar(); } break; case 8: //判断列表是否为空 if (list_exist(pL) == FALSE) { printf("列表不存在!"); getchar();getchar(); break; } if (list_empty(pL) == TRUE) { printf("列表为空!"); getchar();getchar(); } else { printf("列表不为空!"); getchar();getchar(); } break; case 9: //遍历元素 list_travel(pL, &display); getchar();getchar(); break; case 10: //求列表长度 if (list_exist(pL) == FALSE) { printf("列表不存在!"); getchar();getchar(); break; } printf("列表长度是%d", list_length(pL)); getchar();getchar(); break; case 11: //按位置查找元素 inputindex(&i); if (getpos_invalid(pL, i) == FALSE) { printf("位置不合法或列表不存在"); getchar();getchar(); break; } if ((pnode = list_getp(pL, i)) == NULL) { printf("失败!"); getchar();getchar(); break; } display(pnode->pelem); getchar();getchar(); break; case 12: //按元素查找位置 inputstu(pe); if ((i = list_locateelem(pL, (void *)pe, &equal)) == 0) { printf("查找失败!"); getchar(); getchar(); } else { printf("是第%d个元素", i); getchar(); getchar(); } break; case 13: //求前驱元素 inputstu(pe); if(list_priorelem(pL, pe, &pre_e) == TRUE) { display(pe); printf("的前驱元素是"); display(&pre_e); getchar(); getchar(); } else { printf("查找前驱元素失败!"); getchar(); getchar(); } break; case 14: //求后继元素 inputstu(pe); if(list_nextelem(pL, pe, &next_e) == TRUE) { display(pe); printf("的后继元素是"); display(&next_e); getchar(); getchar(); } else { printf("查找后继元素失败!"); getchar(); getchar(); } break; case 15: //保存到文件 if(savelist(pL) == TRUE) { printf("保存成功!"); getchar(); getchar(); } else { printf("保存失败!"); getchar(); getchar(); } break; case 16: //从文件加载 if(loadlist(&pL) == TRUE) { printf("加载成功!"); getchar(); getchar(); } else { printf("加载失败!"); getchar(); getchar(); } break; default: ; } }while(op); printf("\n--------------------Welcome again!--------------------\n"); getchar();getchar(); return 0; } void display(void *stu) { printf("姓名:%s\t年龄%d\n", ((student *)stu)->name, ((student *)stu)->age); } void menu(void){ printf("\n\n"); printf(" Menu for Linear Table On Sequence Structure \n"); printf("------------------------------------------------------\n"); printf("\t修改类\t\t\t查找类\n"); printf("\t1. 初始化列表\t\t7. 判断列表是否存在\n"); printf("\t2. 插入元素\t\t8. 判断列表是否为空\n"); printf("\t3. 销毁列表\t\t9. 遍历列表元素\n"); printf("\t4. 清空列表\t\t10. 列表长度\n"); printf("\t5. 删除区间\t\t11. 按位置查找元素\n"); printf("\t6. 删除某元素\t\t12. 按元素查找位置\n"); printf("\t\t\t\t13. 求某元素前驱元素\n"); printf("\t\t\t\t14. 求某元素后继元素\n"); printf("\t文件类"); printf("\n\t15. Savelist\t\t16. Loadlist\n"); printf(" 0. Exit\n"); printf("------------------------------------------------------\n"); } void inputstu(student * p) { printf("请输入学生姓名:"); scanf("%s", p->name); printf("请输入年龄:"); scanf("%d", &p->age); } void inputindex(int * i) { printf("请输入位置:"); scanf("%d", i); } //判断两个元素是否相等 BOOL equal(void * a, void * b) { student * p1 , * p2; p1 = a; p2 = b; if ((strcmp(p1->name, p2->name) == 0) && p1->age == p2->age) return TRUE; else return FALSE; } |
支付宝打赏 
微信打赏