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

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

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

2、-list, 2 * L-maxSize * sizeofelemType; if.p /* 安排失败就退出运行 */ printf 储备空间安排失败！; exit1; L-list = p; /* 使 list 指向新线性表空间 */ L-maxSize = 2 * L-maxSize; /* 把线性表空间大小修改为新的长度 */ /* 1. 初始化线性表L,即进行动态储备空间安排并置L 为一个空表*/ void initListstruct List *L, int ms /* 检查 ms 是否有效,如无效的就退出运行 */ ifms maxSize = ms; /* 设置线性表空间大小为

3、ms */ L-size = 0; L-list = mallocms * sizeofelemType; if.L-list printf 空间安排失败！; exit1; return; 1 / 16 名师归纳总结 - - - - - - -第 1 页,共 16 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习 /* 2. 清除线性表L 中的全部元素,释放储备空间,使之成为一个空表*/ void clearListstruct List *L ifL-list .= NULL freeL-list; L-list = 0; L-size = L-maxSize

4、= 0; return; /* 3. 返回线性表L 当前的长度,如L 为空就返回*/ int sizeListstruct List *L return L-size; /* 4. 判定线性表L 是否为空,如为空就返回1, 否就返回 0 */ int emptyListstruct List *L ifL-size =0 return 1; else return 0; /* 5. 返回线性表L 中第 pos 个元素的值,如pos 超出范畴,就停止程序运行*/ elemType getElemstruct List *L, int pos ifpos L-size /* 如 pos 越界就退出

5、运行*/ printf 元素序号越界！; exit1; return L-listpos - 1; /* 返回线性表中序号为pos 值的元素值*/ /* 6. 次序扫描（即遍历）输出线性表L 中的每个元素*/ void traverseListstruct List *L int i; 2 / 16 名师归纳总结 - - - - - - -第 2 页,共 16 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习fori = 0; i size; i+ printf%d , L -listi; printf ; return; /* 7. 从线性表L 中查找值与x 相

6、等的元素,如查找胜利就返回其位置,否就返回-1 */ int findListstruct List *L, elemType x int i; fori = 0; i size; i+ ifL-listi = x return i; return -1; /* 8. 把线性表L 中第 pos 个元素的值修改为x 的值,如修改胜利返回1,否就返回0 */ int updatePosListstruct List *L, int pos, elemType x ifpos L-size /* 如 pos 越界就修改失败*/ return 0; L-listpos - 1 = x; return

7、1; /* 9. 向线性表L 的表头插入元素x */ void inserFirstListstruct List *L, elemType x int i; ifL-size = L-maxSize againMallocL; fori = L-size - 1; i = 0; i- L-listi + 1 = L -listi; L-list0 = x; L-size +; return; 3 / 16 名师归纳总结 - - - - - - -第 3 页,共 16 页精选学习资料 - - - - - - - - - /* 10. 向线性表 L 的表尾插入元素个人收集整理仅供参考学习x */

8、 void insertLastListstruct List *L, elemType x ifL-size = L -maxSize /* 重新安排更大的储备空间*/ againMallocL; L-listL-size = x; /* 把 x 插入到表尾 */ L-size+; /* 线性表的长度增加 */ return; /* 11. 向线性表 L 中第 pos 个元素位置插入元素x,如插入胜利返回,否就返回*/ int insertPosListstruct List *L, int pos, elemType x int i; ifpos L-size + 1 /* 如 pos 越

9、界就插入失败*/ return 0; ifL-size = L-maxSize /* 重新安排更大的储备空间*/ againMallocL; fori = L-size - 1; i = pos - 1; i- L-listi + 1 = L-listi; L-listpos - 1 = x; L-size+; return 1; /* 12. 向有序线性表L 中插入元素x,使得插入后仍旧有序*/ void insertOrderListstruct List *L, elemType x int i, j; /* 如数组空间用完就重新安排更大的储备空间 */ ifL-size = L-max

10、Size againMallocL; /* 次序查找出x 的插入位置*/ fori = 0; i size; i+ ifx listi break; /* 从表尾到下标i 元素依次后移一个位置,把 i 的位置空出来*/ forj = L-size - 1; j = i; j- 4 / 16 名师归纳总结 - - - - - - -第 4 页,共 16 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习L-listj+1 = L-listj; /* 把 x 值赋给下标为i 的元素*/ L-listi = x; /* 线性表长度增加 1 */ L-size+; retu

11、rn; /* 13. 从线性表 L 中删除表头元素并返回它,如删除失败就停止程序运行 */ elemType deleteFirstListstruct List *L elemType temp; int i; ifL -size = 0 ; printf 线性表为空,不能进行删除操作！exit1; temp = L-list0; fori = 1; i size; i+ L-listi-1 = L-listi; L-size-; return temp; /* 14. 从线性表 L 中删除表尾元素并返回它,如删除失败就停止程序运行 */ elemType deleteLastListstr

12、uct List *L ifL -size = 0 printf 线性表为空,不能进行删除操作！; exit1; L-size-; return L -listL-size; /* 返回原先表尾元素的值*/ /* 15. 从线性表 L 中删除第 pos 个元素并返回它,如删除失败就停止程序运行 */ elemType deletePosListstruct List *L, int pos elemType temp; int i; ifpos L-size /* pos 越界就删除失败 */ printfpos 值越界,不能进行删除操作！; exit1; temp = L-listpos-1

13、; 5 / 16 名师归纳总结 - - - - - - -第 5 页,共 16 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习fori = pos; i size; i+ L-listi-1 = L-listi; L-size-; return temp; /* 16. 从线性表 L 中删除值为x 的第一个元素,如胜利返回1,失败返回0 */ int deleteValueListstruct List *L, elemType x int i, j; /* 从线性表中次序查找出值为x 的第一个元素*/ fori = 0; i size; i+ ifL-list

14、i = x break; /* 如查找失败,说明不存在值为x 的元素,返回0 */ ifi = L-size return 0; /* 删除值为 x 的元素 L-listi */ forj = 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 List L; initList&L, 5; fori = 0; i 10; i+ insertLastList&L, ai; insertP

15、osList&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; 6 / 16 名师归纳总结 - - - - - - -第 6 页,共 16 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习traverseList&L; deleteFirstList&L; deleteFirstList&L; deleteLast

16、List&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 12 #define MM 20 typedef int elemType ; /*/ /* 以下是关于线性表链接储备（单链表）操作的16 种算法*/ /*/ struct sNode /* 定义单链表结点类型*/ elemType d

17、ata; struct sNode *next; ; /* 1. 初始化线性表,即置单链表的表头指针为空 */ void initListstruct sNode* *hl *hl = NULL; return; /* 2. 清除线性表L 中的全部元素,即释放单链表L 中全部的结点,使之成为一个空表*/ void clearListstruct sNode* *hl /* cp 和 np 分别作为指向两个相邻结点的指针 */ struct sNode *cp, *np; cp = *hl; /* 遍历单链表,依次释放每个结点 */ whilecp .= NULL np = cp-next; /

18、* 储存下一个结点的指针*/ freecp; cp = np; *hl = NULL; /* 置单链表的表头指针为空*/ return; 7 / 16 名师归纳总结 - - - - - - -第 7 页,共 16 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习 /* 3. 返回单链表的长度 */ int sizeListstruct sNode *hl int count = 0; /* 用于统计结点的个数*/ whilehl .= NULL count+; hl = hl-next; return count; /* 4. 检查单链表是否为空,如为空就返回,否

19、就返回 */ int emptyListstruct sNode *hl ifhl = NULL return 1; else return 0; /* 5. 返回单链表中第pos 个结点中的元素,如pos 超出范畴,就停止程序运行*/ elemType getElemstruct sNode *hl, int pos int i = 0; /* 统计已遍历的结点个数*/ ifpos next; ifhl .= NULL return hl-data; else ; printfpos 值非法,退出运行！exit1; 8 / 16 名师归纳总结 - - - - - - -第 8 页,共 16

20、页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习 /* 6. 遍历一个单链表 */ void traverseListstruct sNode *hl whilehl .= NULL printf%5d, hl-data; hl = hl-next; printf ; return; /* 7. 从单链表中查找具有给定值x 的第一个元素, 如查找胜利就返回该结点data 域的储备地址,否就返回NULL */ elemType* findListstruct sNode *hl, elemType x whilehl .= NULL ifhl-data = x re

21、turn &hl-data; else hl = hl-next; return NULL; /* 8. 把单链表中第pos 个结点的值修改为x 的值,如修改胜利返回,否就返回*/ int updatePosListstruct sNode *hl, int pos, elemType x int i = 0; struct sNode *p = hl; whilep .= NULL /* 查找第 pos 个结点*/ i+; ifpos = i break; else p = p-next; ifpos = i p-data = x; return 1; else 9 / 16 名师归纳总结

22、- - - - - - -第 9 页,共 16 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习return 0; /* 9. 向单链表的表头插入一个元素 */ void insertFirstListstruct sNode* *hl, elemType x struct sNode *newP; newP = mallocsizeofstruct sNode; ifnewP = NULL ; printf 内存安排失败,退出运行！exit1; newP-data = x; /* 把 x 的值赋给新结点的 data 域 */ /* 把新结点作为新的表头结点插入

23、*/ newP-next = *hl; *hl = newP; return; /* 10. 向单链表的末尾添加一个元素 */ void insertLastListstruct sNode* *hl, elemType x struct sNode *newP; newP = mallocsizeofstruct sNode; ifnewP = NULL ; printf 内在安排失败,退出运行！exit1; /* 把 x 的值赋给新结点的data 域,把空值赋给新结点的next 域 */ newP-data = x; newP-next = NULL; /* 如原表为空,就作为表头结点插入

24、 */ if*hl = NULL *hl = newP; /* 查找到表尾结点并完成插入 */ else struct sNode *p = NULL; whilep-next .= NULL p = p-next; p-next = newP; 10 / 16 名师归纳总结 - - - - - - -第 10 页,共 16 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习return; /* 11. 向单链表中第pos 个结点位置插入元素为x 的结点,如插入胜利返回, 否就返回*/ int insetPosListstruct sNode* *hl, int p

25、os, elemType x int i = 0; struct sNode *newP; struct sNode *cp = *hl, *ap = NULL; /* 对 pos 值小于等于的情形进行处理 */ ifpos next; /* 产生新结点,如安排失败,就停止插入 */ newP = mallocsizeofstruct sNode; ifnewP = NULL printf 内存安排失败,无法进行插入操作！; return 0; /* 把 x 的值赋给新结点的 data 域 */ newP-data = x; /* 把新结点插入到表头 */ ifap = NULL newP-n

26、ext = cp; /* 或改为 newP-next = *hl; */ *hl = newP; /* 把新结点插入到 ap 和 cp 之间 */ else newP-next = cp; ap-next = newP; return 1; /* 插入胜利返回1 */ 11 / 16 名师归纳总结 - - - - - - -第 11 页,共 16 页精选学习资料 - - - - - - - - - /* 12. 向有序单链表中插入元素个人收集整理仅供参考学习*/ x 结点,使得插入后仍旧有序void insertOrderListstruct sNode* *hl, elemType x /*

27、 把单链表的表头指针赋给 cp,把 ap 置空 */ struct sNode *cp = *hl, *ap = NULL; /* 建立新结点 */ struct sNode *newP; newP = mallocsizeofstruct sNode; ifnewP = NULL printf 内在安排失败,退出运行！; exit1; newP-data = x; /* 把 x 的值赋给新结点的data 域 */ /* 把新结点插入到表头*/ ifcp = NULL | x data newP-next = cp; *hl = newP; return; /* 次序查找出x 结点的插入位置*

28、/ whilecp .= NULL ifx data break; else ap = cp; cp = cp-next; /* 把 x 结点插入到 ap 和 cp 之间 */ newP-next = cp; ap-next = newP; return; /* 13. 从单链表中删除表头结点,并把该结点的值返回,如删除失败就停止程序运行 */ elemType deleteFirstListstruct sNode* *hl elemType temp; struct sNode *p = *hl; /* 暂存表头结点指针,以便回收*/ if*hl = NULL printf 单链表为空,无

29、表头可进行删除,退出运行！; exit1; *hl = *hl-next; /* 使表头指针指向其次个结点*/ 12 / 16 名师归纳总结 - - - - - - -第 12 页,共 16 页精选学习资料 - - - - - - - - - temp = p-data; 个人收集整理仅供参考学习*/ /* 暂存原表头元素,以便返回freep; /* 回收被删除的表头结点*/ */ return temp; /* 返回第一个结点的值 /* 14. 从单链表中删除表尾结点并返回它的值,如删除失败就停止程序运行 */ elemType deleteLastListstruct sNode* *hl

30、 elemType temp; /* 初始化 cp 和 ap 指针,使 cp 指向表头结点,使ap 为空*/ struct sNode *cp = *hl; struct sNode *ap = NULL; /* 单链表为空就停止运行 */ ifcp = NULL printf 单链表为空,无表头进行删除,退出运行！; exit1; /* 从单链表中查找表尾结点,循环终止时cp 指向表尾结点,ap 指向其前驱结点*/ whilecp-next .= NULL ap = cp; cp = cp-next; /* 如单链表中只有一个结点,就需要修改表头指针 */ ifap = NULL *hl =

31、 *hl-next; /* 或改为 *hl = NULL; */ /* 删除表尾结点 */ else ap-next = NULL; /* 暂存表尾元素,以便返回 */ temp = cp-data; freecp; /* 回收被删除的表尾结点*/ return temp; /* 返回表尾结点的值*/ /* 15. 从单链表中删除第pos 个结点并返回它的值,如删除失败就停止程序运行*/ elemType deletePosListstruct sNode* *hl, int pos int i = 0; elemType temp; /* 初始化 cp 和 ap 指针,使 cp 指向表头结点

32、,使ap 为空*/ struct sNode *cp = *hl; struct sNode *ap = NULL; 13 / 16 名师归纳总结 - - - - - - -第 13 页,共 16 页精选学习资料 - - - - - - - - - /* 单链表为空或个人收集整理仅供参考学习pos 值非法就停止运行*/ ifcp = NULL | pos next; /* 单链表中没有第pos 个结点*/ ifcp = NULL printfpos 值不正确,退出运行！; exit1; /* 如 pos 等于 1,就需要删除表头结点 */ ifpos = 1 *hl = *hl-next; /

33、* 或改为 *hl = cp-next; */ /* 否就删除非表头结点,此时cp 指向该结点, ap 指向前驱结点*/ else ap-next = cp-next; /* 暂存第 pos 个结点的值,以便返回 */ temp = cp-data; freecp; /* 回收被删除的第pos 个结点*/ */ return temp; /* 返回在 temp 中暂存的第pos 个结点的值 /* 16. 从单链表中删除值为x 的第一个结点,如删除胜利就返回1,否就返回 0 */ int deleteValueListstruct sNode* *hl, elemType x /* 初始化 cp

34、 和 ap 指针,使 cp 指向表头结点,使ap 为空*/ struct sNode *cp = *hl; struct sNode *ap = NULL; /* 从单链表中查找值为x 的结点,找到后由cp 指向该结点,由ap 指向其前驱结点*/ whilecp .= NULL ifcp-data = x break; 14 / 16 名师归纳总结 - - - - - - -第 14 页,共 16 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习ap = cp; cp = cp-next; /* 如查找失败,即该单链表中不存在值为x 的结点,就返回0 */ ifc

35、p = NULL return 0; /* 假如删除的是表头或非表头结点就分别进行处理 */ ifap = NULL *hl = *hl-next; /* 或改为 *hl= cp-next */ else ap-next = cp-next; freecp; /* 回收被删除的结点*/ */ return 1; /* 返回 1 表示删除胜利 /*/ int mainint argc, char* argv int aNN; int i; struct sNode *p, *h, *s; srandtimeNULL; initList&p; fori = 0; i NN; i+ ai = rand & MM