2022年数据结构C语言实现系列——线性表 .pdf

《2022年数据结构C语言实现系列——线性表 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构C语言实现系列——线性表 .pdf（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、个人收集整理仅供参考学习1 / 16 数据结构 C 语言实现系列 线性表#include #include typedef int elemType; /*/ /* 以 下 是 关 于 线 性 表 顺 序 存 储 操 作 的16种 算 法*/ /*/ struct List elemType *list; int size; int maxSize; ; void againMalloc(struct List *L) /* 空间扩展为原来的2 倍，并由 p 指针所指向，原内容被自动拷贝到p 所指向的存储空间*/ elemType *p = realloc(L-list, 2 * L-maxS

2、ize * sizeof(elemType); if(!p) /* 分配失败则退出运行*/ printf( 存储空间分配失败！); exit(1); L-list = p; /* 使 list 指向新线性表空间*/ L-maxSize = 2 * L-maxSize; /* 把线性表空间大小修改为新的长度*/ /* 1.初始化线性表L，即进行动态存储空间分配并置L 为一个空表*/ void initList(struct List *L, int ms) /* 检查 ms 是否有效，若无效的则退出运行*/ if(ms maxSize = ms; /* 设置线性表空间大小为ms */ L-siz

3、e = 0; L-list = malloc(ms * sizeof(elemType); if(!L-list) printf( 空间分配失败！); exit(1); return; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 16 页个人收集整理仅供参考学习2 / 16 /* 2.清除线性表L 中的所有元素，释放存储空间，使之成为一个空表*/ void clearList(struct List *L) if(L-list != NULL) free(L-list); L-list = 0; L-size = L-maxSize

4、 = 0; return; /* 3.返回线性表L 当前的长度，若L 为空则返回*/ int sizeList(struct List *L) return L-size; /* 4.判断线性表L 是否为空，若为空则返回1, 否则返回0 */ int emptyList(struct List *L) if(L-size =0) return 1; else return 0; /* 5.返回线性表L 中第 pos 个元素的值，若pos 超出范围，则停止程序运行*/ elemType getElem(struct List *L, int pos) if(pos L-size) /* 若 po

5、s越界则退出运行*/ printf( 元素序号越界！); exit(1); return L-listpos - 1; /* 返回线性表中序号为pos 值的元素值*/ /* 6.顺序扫描（即遍历）输出线性表L 中的每个元素*/ void traverseList(struct List *L) int i; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 16 页个人收集整理仅供参考学习3 / 16 for(i = 0; i size; i+) printf(%d , L -listi); printf( ); return; /* 7

6、.从线性表L 中查找值与x 相等的元素，若查找成功则返回其位置，否则返回-1 */ int findList(struct List *L, elemType x) int i; for(i = 0; i size; i+) if(L-listi = x) return i; return -1; /* 8.把线性表L 中第 pos个元素的值修改为x 的值，若修改成功返回1，否则返回0 */ int updatePosList(struct List *L, int pos, elemType x) if(pos L-size) /* 若 pos越界则修改失败*/ return 0; L-li

7、stpos - 1 = x; return 1; /* 9.向线性表L 的表头插入元素x */ void inserFirstList(struct List *L, elemType x) int i; if(L-size = L-maxSize) againMalloc(L); for(i = L-size - 1; i = 0; i-) L-listi + 1 = L -listi; L-list0 = x; L-size +; return; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 16 页个人收集整理仅供参考学习4 /

8、 16 /* 10.向线性表L 的表尾插入元素x */ void insertLastList(struct List *L, elemType x) if(L-size = L -maxSize) /* 重新分配更大的存储空间*/ againMalloc(L); L-listL-size = x; /* 把 x 插入到表尾*/ L-size+; /* 线性表的长度增加*/ return; /* 11.向线性表L 中第 pos 个元素位置插入元素x，若插入成功返回，否则返回*/ int insertPosList(struct List *L, int pos, elemType x) int

9、 i; if(pos L-size + 1) /* 若 pos 越界则插入失败*/ return 0; if(L-size = L-maxSize) /* 重新分配更大的存储空间*/ againMalloc(L); for(i = L-size - 1; i = pos - 1; i-) L-listi + 1 = L-listi; L-listpos - 1 = x; L-size+; return 1; /* 12.向有序线性表L 中插入元素x,使得插入后仍然有序*/ void insertOrderList(struct List *L, elemType x) int i, j; /*

10、 若数组空间用完则重新分配更大的存储空间*/ if(L-size = L-maxSize) againMalloc(L); /* 顺序查找出x 的插入位置*/ for(i = 0; i size; i+) if(x listi) break; /* 从表尾到下标i 元素依次后移一个位置，把 i 的位置空出来*/ for(j = L-size - 1; j = i; j-) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 16 页个人收集整理仅供参考学习5 / 16 L-listj+1 = L-listj; /* 把 x 值赋给下标为i

11、的元素*/ L-listi = x; /* 线性表长度增加1 */ L-size+; return; /* 13.从线性表L 中删除表头元素并返回它，若删除失败则停止程序运行*/ elemType deleteFirstList(struct List *L) elemType temp; int i; if(L -size = 0) printf( 线性表为空，不能进行删除操作！); exit(1); temp = L-list0; for(i = 1; i size; i+) L-listi-1 = L-listi; L-size-; return temp; /* 14.从线性表L 中删

12、除表尾元素并返回它，若删除失败则停止程序运行*/ elemType deleteLastList(struct List *L) if(L -size = 0) printf( 线性表为空，不能进行删除操作！); exit(1); L-size-; return L -listL-size; /* 返回原来表尾元素的值*/ /* 15.从线性表L 中删除第pos 个元素并返回它，若删除失败则停止程序运行*/ elemType deletePosList(struct List *L, int pos) elemType temp; int i; if(pos L-size) /* pos 越界

13、则删除失败*/ printf(pos 值越界，不能进行删除操作！); exit(1); temp = L-listpos-1; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 16 页个人收集整理仅供参考学习6 / 16 for(i = pos; i size; i+) L-listi-1 = L-listi; L-size-; return temp; /* 16.从线性表L 中删除值为x 的第一个元素，若成功返回1，失败返回0 */ int deleteValueList(struct List *L, elemType x) in

14、t i, j; /* 从线性表中顺序查找出值为x 的第一个元素*/ for(i = 0; i size; i+) if(L-listi = x) break; /* 若查找失败，表明不存在值为x 的元素，返回0 */ if(i = L-size) return 0; /* 删除值为x 的元素 L-listi */ for(j = i + 1; j size; j+) L-listj-1 = L-listj; L-size-; return 1; /*/ void main() int a10 = 2, 4, 6, 8, 10, 12, 14, 16, 18, 20; int i; struct

15、 List L; initList(&L, 5); for(i = 0; i 10; i+) insertLastList(&L, ai); insertPosList(&L, 11, 48); insertPosList(&L, 1, 64); printf(%d , getElem(&L, 1); traverseList(&L); printf(%d , findList(&L, 10); updatePosList(&L, 3, 20); printf(%d , getElem(&L, 3); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第

16、 6 页，共 16 页个人收集整理仅供参考学习7 / 16 traverseList(&L); deleteFirstList(&L); deleteFirstList(&L); deleteLastList(&L); deleteLastList(&L); deletePosList(&L, 5); ;deletePosList(&L, 7); printf(%d , sizeList(&L); printf(%d , emptyList(&L); traverseList(&L); clearList(&L); return 0; #include #include #define NN

17、12 #define MM 20 typedef int elemType ; /*/ /* 以下是关于线性表链接存储（单链表）操作的16 种算法*/ /*/ struct sNode /* 定义单链表结点类型*/ elemType data; struct sNode *next; ; /* 1.初始化线性表，即置单链表的表头指针为空*/ void initList(struct sNode* *hl) *hl = NULL; return; /* 2.清除线性表L 中的所有元素，即释放单链表L 中所有的结点，使之成为一个空表*/ void clearList(struct sNode* *

18、hl) /* cp 和 np 分别作为指向两个相邻结点的指针*/ struct sNode *cp, *np; cp = *hl; /* 遍历单链表，依次释放每个结点*/ while(cp != NULL) np = cp-next; /* 保存下一个结点的指针*/ free(cp); cp = np; *hl = NULL; /* 置单链表的表头指针为空*/ return; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 16 页个人收集整理仅供参考学习8 / 16 /* 3.返回单链表的长度*/ int sizeList(struc

19、t sNode *hl) int count = 0; /* 用于统计结点的个数*/ while(hl != NULL) count+; hl = hl-next; return count; /* 4.检查单链表是否为空，若为空则返回，否则返回*/ int emptyList(struct sNode *hl) if(hl = NULL) return 1; else return 0; /* 5.返回单链表中第pos 个结点中的元素，若pos 超出范围，则停止程序运行*/ elemType getElem(struct sNode *hl, int pos) int i = 0; /* 统

20、计已遍历的结点个数*/ if(pos next; if(hl != NULL) return hl-data; else printf(pos 值非法，退出运行！); exit(1); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 16 页个人收集整理仅供参考学习9 / 16 /* 6.遍历一个单链表*/ void traverseList(struct sNode *hl) while(hl != NULL) printf(%5d, hl-data); hl = hl-next; printf( ); return; /* 7.从单

21、链表中查找具有给定值x 的第一个元素， 若查找成功则返回该结点data域的存储地址，否则返回NULL */ elemType* findList(struct sNode *hl, elemType x) while(hl != NULL) if(hl-data = x) return &hl-data; else hl = hl-next; return NULL; /* 8.把单链表中第pos个结点的值修改为x 的值，若修改成功返回，否则返回*/ int updatePosList(struct sNode *hl, int pos, elemType x) int i = 0; stru

22、ct sNode *p = hl; while(p != NULL) /* 查找第 pos 个结点*/ i+; if(pos = i) break; else p = p-next; if(pos = i) p-data = x; return 1; else 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 16 页个人收集整理仅供参考学习10 / 16 return 0; /* 9.向单链表的表头插入一个元素*/ void insertFirstList(struct sNode* *hl, elemType x) struct sN

23、ode *newP; newP = malloc(sizeof(struct sNode); if(newP = NULL) printf( 内存分配失败，退出运行！); exit(1); newP-data = x; /* 把 x 的值赋给新结点的data域 */ /* 把新结点作为新的表头结点插入*/ newP-next = *hl; *hl = newP; return; /* 10.向单链表的末尾添加一个元素*/ void insertLastList(struct sNode* *hl, elemType x) struct sNode *newP; newP = malloc(si

24、zeof(struct sNode); if(newP = NULL) printf( 内在分配失败，退出运行！); exit(1); /* 把 x 的值赋给新结点的data域，把空值赋给新结点的next 域 */ newP-data = x; newP-next = NULL; /* 若原表为空，则作为表头结点插入*/ if(*hl = NULL) *hl = newP; /* 查找到表尾结点并完成插入*/ else struct sNode *p = NULL; while(p-next != NULL) p = p-next; p-next = newP; 精选学习资料 - - - -

25、- - - - - 名师归纳总结 - - - - - - -第 10 页，共 16 页个人收集整理仅供参考学习11 / 16 return; /* 11.向单链表中第pos 个结点位置插入元素为x 的结点，若插入成功返回， 否则返回*/ int insetPosList(struct sNode* *hl, int pos, elemType x) int i = 0; struct sNode *newP; struct sNode *cp = *hl, *ap = NULL; /* 对 pos 值小于等于的情况进行处理*/ if(pos next; /* 产生新结点，若分配失败，则停止插入

26、*/ newP = malloc(sizeof(struct sNode); if(newP = NULL) printf( 内存分配失败，无法进行插入操作！); return 0; /* 把 x 的值赋给新结点的data域 */ newP-data = x; /* 把新结点插入到表头*/ if(ap = NULL) newP-next = cp; /* 或改为 newP-next = *hl; */ *hl = newP; /* 把新结点插入到ap 和 cp 之间 */ else newP-next = cp; ap-next = newP; return 1; /* 插入成功返回1 */

27、精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 16 页个人收集整理仅供参考学习12 / 16 /* 12.向有序单链表中插入元素x 结点，使得插入后仍然有序*/ void insertOrderList(struct sNode* *hl, elemType x) /* 把单链表的表头指针赋给cp，把 ap 置空*/ struct sNode *cp = *hl, *ap = NULL; /* 建立新结点*/ struct sNode *newP; newP = malloc(sizeof(struct sNode); if(new

28、P = NULL) printf( 内在分配失败，退出运行！); exit(1); newP-data = x; /* 把 x 的值赋给新结点的data域 */ /* 把新结点插入到表头*/ if(cp = NULL) | (x data) newP-next = cp; *hl = newP; return; /* 顺序查找出x 结点的插入位置*/ while(cp != NULL) if(x data) break; else ap = cp; cp = cp-next; /* 把 x 结点插入到ap 和 cp 之间 */ newP-next = cp; ap-next = newP; r

29、eturn; /* 13.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行*/ elemType deleteFirstList(struct sNode* *hl) elemType temp; struct sNode *p = *hl; /* 暂存表头结点指针，以便回收*/ if(*hl = NULL) printf( 单链表为空，无表头可进行删除，退出运行！); exit(1); *hl = (*hl)-next; /* 使表头指针指向第二个结点*/ 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 16 页

30、个人收集整理仅供参考学习13 / 16 temp = p-data; /* 暂存原表头元素，以便返回*/ free(p); /* 回收被删除的表头结点*/ return temp; /* 返回第一个结点的值*/ /* 14.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行*/ elemType deleteLastList(struct sNode* *hl) elemType temp; /* 初始化 cp 和 ap 指针，使cp 指向表头结点，使ap 为空*/ struct sNode *cp = *hl; struct sNode *ap = NULL; /* 单链表为空则停

31、止运行*/ if(cp = NULL) printf( 单链表为空，无表头进行删除，退出运行！); exit(1); /* 从单链表中查找表尾结点，循环结束时cp 指向表尾结点，ap 指向其前驱结点*/ while(cp-next != NULL) ap = cp; cp = cp-next; /* 若单链表中只有一个结点，则需要修改表头指针*/ if(ap = NULL) *hl = (*hl)-next; /* 或改为 *hl = NULL; */ /* 删除表尾结点*/ else ap-next = NULL; /* 暂存表尾元素，以便返回*/ temp = cp-data; free(

32、cp); /* 回收被删除的表尾结点*/ return temp; /* 返回表尾结点的值*/ /* 15.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行*/ elemType deletePosList(struct sNode* *hl, int pos) int i = 0; elemType temp; /* 初始化 cp 和 ap 指针，使cp 指向表头结点，使ap 为空*/ struct sNode *cp = *hl; struct sNode *ap = NULL; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第

33、 13 页，共 16 页个人收集整理仅供参考学习14 / 16 /* 单链表为空或pos值非法则停止运行*/ if(cp = NULL) | (pos next; /* 单链表中没有第pos个结点*/ if(cp = NULL) printf(pos 值不正确，退出运行！); exit(1); /* 若 pos 等于 1，则需要删除表头结点*/ if(pos = 1) *hl = (*hl)-next; /* 或改为 *hl = cp-next; */ /* 否则删除非表头结点，此时cp 指向该结点， ap 指向前驱结点*/ else ap-next = cp-next; /* 暂存第 pos

34、 个结点的值，以便返回*/ temp = cp-data; free(cp); /* 回收被删除的第pos个结点*/ return temp; /* 返回在 temp 中暂存的第pos个结点的值*/ /* 16.从单链表中删除值为x 的第一个结点，若删除成功则返回1,否则返回0 */ int deleteValueList(struct sNode* *hl, elemType x) /* 初始化 cp 和 ap 指针，使cp 指向表头结点，使ap 为空*/ struct sNode *cp = *hl; struct sNode *ap = NULL; /* 从单链表中查找值为x 的结点，找

35、到后由cp 指向该结点，由ap指向其前驱结点*/ while(cp != NULL) if(cp-data = x) break; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 16 页个人收集整理仅供参考学习15 / 16 ap = cp; cp = cp-next; /* 若查找失败，即该单链表中不存在值为x 的结点，则返回0 */ if(cp = NULL) return 0; /* 如果删除的是表头或非表头结点则分别进行处理*/ if(ap = NULL) *hl = (*hl)-next; /* 或改为 *hl= cp-n

36、ext */ else ap-next = cp-next; free(cp); /* 回收被删除的结点*/ return 1; /* 返回 1 表示删除成功*/ /*/ int main(int argc, char* argv) int aNN; int i; struct sNode *p, *h, *s; srand(time(NULL); initList(&p); for(i = 0; i NN; i+) ai = rand() & MM; printf( 随机数序列： ); for(i = 0; i NN; i+) printf(%5d, ai); printf( ); prin

37、tf( 随机数逆序： ); for(i = 0; i next) while(deleteValueList(&(h-next), h-data) ; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 16 页个人收集整理仅供参考学习16 / 16 printf( 去除重复数： ); traverseList(p); printf( 单链表长度： %5d , sizeList(p); h = NULL; for(s = p; s != NULL; s = s-next) insertOrderList(&h, s-data); printf( 有序表序列： ); traverseList(h); clearList(&p); system(pause); return 0; 资料个人收集整理，勿做商业用途精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 16 页