《C程序设计C程序设计 (89).pdf》由会员分享，可在线阅读，更多相关《C程序设计C程序设计 (89).pdf（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、C C程序设计程序设计Programming in CProgramming in C链表运算链表运算1、遍历链表2、销毁链表3、查找结点4、链表逆序C C程序设计程序设计程序设计程序设计3 39.3 9.3 链表的运算链表的运算双链表与单链表的基本运算大多数是相同的，这里仅讨论单链表的情形。4 49.3.1 9.3.1 链表的遍历链表的遍历（1）链表遍历ListTraverse(L,visit()与数组不同，链表不是用下标而是用指针运算查找数据元素的。通过链表的头结点L可以访问开始结点p=L-next，令p=p-next，即p指向直接后继结点，如此循环可以访问整个链表中的全部结点，这就是链表
2、的遍历（traverse）。链表的输出、销毁、查找和逆序等运算都需要遍历链表。5 59.3.1 9.3.1 链表的遍历链表的遍历链表遍历算法的实现步骤为：令指针p指向L的开始结点。若p为0，表示已到链尾，遍历结束。令p指向直接后继结点，即p=p-next。重复步骤直至遍历结束。6 69.3.1 9.3.1 链表的遍历链表的遍历链表遍历的算法如下：其中visit是函数指针。当调用ListTraverse遍历结点时，通过调用visit()对每个结点完成定制的操作。1 voidvoid ListTraverseListTraverse(LinkList LLinkList L,voidvoid(*(
3、*visitvisit)()(ElemTypeElemType*)*)2 /遍历L中的每个元素且调用函数visit访问它/遍历L中的每个元素且调用函数visit访问它3 LinkList pLinkList p=L L-nextnext;/p指向开始结点/p指向开始结点4 whilewhile(p p!=!=NULLNULL)/若不是链尾继续/若不是链尾继续5 visitvisit(&(&(p p-datadata););/调用函数visit()访问结点/调用函数visit()访问结点6 p p=p p-nextnext;/p指向直接后继结点/p指向直接后继结点7 8 7 79.3.1 9.3
4、.1 链表的遍历链表的遍历（2）输出链表设计遍历结点时的visit函数：调用ListTraverse(L,visit)时扫描链表中的每个结点，并调用visit()输出结点的数据域。1 voidvoid visitvisit(ElemTypeElemType*epep)/实现链表遍历时结点访问的定制函数/实现链表遍历时结点访问的定制函数2 /在函数中对结点*ep实现定制的操作，例如输出/在函数中对结点*ep实现定制的操作，例如输出3 printfprintf(%d,*(%d,*epep););4 8 89.3.1 9.3.1 链表的遍历链表的遍历（3）计算链表长度ListLength(L)应用遍
5、历算法逐个统计链表结点个数的算法如下：1 intint ListLengthListLength(LinkList LLinkList L)/返回L中数据元素个数/返回L中数据元素个数2 3 intint cntcnt=0 0;4 LinkList pLinkList p=L L-nextnext;/p指向开始结点/p指向开始结点5 whilewhile(p p!=!=NULLNULL)/若不是链尾继续/若不是链尾继续6 cntcnt+;+;7 p p=p p-nextnext;/指向直接后继结点/指向直接后继结点8 9 returnreturn cntcnt;/返回0表示无数据结点/返回0表
6、示无数据结点10 9 99.3.1 9.3.1 链表的遍历链表的遍历（4）返回链表尾结点元素LastElem(L,&e)应用遍历算法移动到尾结点，返回尾结点元素的算法如下：1 intint LastElemLastElem(LinkList LLinkList L,ElemTypeElemType*e e)/用e返回尾结点元素/用e返回尾结点元素2 3 LinkList qLinkList q=NULLNULL,p p=L L;/指向头结点/指向头结点4 whilewhile(p p!=!=NULLNULL)/若不是链尾继续/若不是链尾继续5 q q=p p;6 p p=p p-nextnex
7、t;/指向直接后继结点/指向直接后继结点7 8 ifif(q q!=!=NULLNULL)9*e e=q q-datadata;10 returnreturn 1 1;/操作成功返回真（1）/操作成功返回真（1）11 12 returnreturn 0 0;/操作失败返回假（0）/操作失败返回假（0）13 10109.3.1 9.3.1 链表的遍历链表的遍历（5）检测是否为循环链表LinkRing(L)循环链表的特征是尾结点的next是头结点，所以应用遍历算法判断链表是否为循环链表的算法如下：1 intint LinkRingLinkRing(LinkList LLinkList L)/判断链
8、表是否为循环链表/判断链表是否为循环链表2 3 LinkList pLinkList p=L L;/指向头结点/指向头结点4 whilewhile(p p!=!=NULLNULL)/若是链尾结束/若是链尾结束5 p p=p p-nextnext;/指向直接后继结点/指向直接后继结点6 ifif(p p=L L)returnreturn 1 1;/是循环链表返回真（1）/是循环链表返回真（1）7 8 returnreturn 0 0;/不是循环链表返回假（0）/不是循环链表返回假（0）9 11119.3.1 9.3.1 链表的遍历链表的遍历（6）两个链表相连LinkContact(L1,*L2)
9、通过让链表L1的尾结点指向L2开始结点，将两个链表连接起来的算法如下：1 voidvoid LinkContactLinkContact(LinkList L1LinkList L1,LinkListLinkList*L2L2)/两个链表相连/两个链表相连2 3 LinkList qLinkList q=NULLNULL,p p=L1L1;/p指向链表1头结点/p指向链表1头结点4 whilewhile(p p!=!=NULLNULL)/若是链表1链尾结束/若是链表1链尾结束5 q q=p p;6 p p=p p-nextnext;/指向直接后继结点/指向直接后继结点7 8 ifif(q q!
10、=!=NULLNULL&(*&(*L2L2)!=)!=NULLNULL)9 q q-nextnext=(*=(*L2L2)-)-nextnext;/链表1尾结点指向链表2开始结点/链表1尾结点指向链表2开始结点10 freefree(*(*L2L2););/释放链表2头结点/释放链表2头结点11*L2L2=NULLNULL;12 13 12129.3.2 9.3.2 销毁链表销毁链表（1）销毁链表DestroyList(&L)按照动态内存的使用要求，当不再使用链表时或程序结束前，需要将创建链表时分配的所有结点的内存释放掉，即销毁链表。销毁链表的步骤如下：若*L为0，表示已到链尾，销毁链表结束。
11、令指针p指向结点*L的next，释放内存*L。*L置换为p，即*L指向直接后继结点，重复步骤直至销毁链表结束。13139.3.2 9.3.2 销毁链表销毁链表应用遍历算法销毁链表的算法如下：1 voidvoid DestroyListDestroyList(LinkListLinkList*L L)/销毁单链表L/销毁单链表L2 3 LinkList qLinkList q,p p=*=*L L;/p指向头结点/p指向头结点4 whilewhile(p p!=!=NULLNULL)/若不是链尾继续/若不是链尾继续5 q q=p p-nextnext;/指向直接后继结点/指向直接后继结点6 fr
12、eefree(p p););/释放结点存储空间/释放结点存储空间7 p p=q q;/直接后继结点/直接后继结点8 9*L L=NULLNULL;/置为空表/置为空表10 14149.3.2 9.3.2 销毁链表销毁链表（2）置空链表ClearList(&L)将一个链表重置为空表（即没有数据结点）的算法如下：1 voidvoid ClearListClearList(LinkListLinkList*L L)/将L重置为空表/将L重置为空表2 3 LinkList pLinkList p,q q;4 p p=(*=(*L L)-)-nextnext;/p指向开始结点/p指向开始结点5 whil
13、ewhile(p p!=!=NULLNULL)/若不是链尾继续/若不是链尾继续6 q q=p p-nextnext;/指向直接后继结点/指向直接后继结点7 freefree(p p););/释放结点存储空间/释放结点存储空间8 p p=q q;/直接后继结点/直接后继结点9 10(*(*L L)-)-nextnext=NULLNULL;/初始时为空表/初始时为空表11 15159.3.3 9.3.3 查找结点查找结点（1）用e返回链表中第i个数据元素GetElem(L,i,&e)应用遍历算法可以实现链表结点的查找，找出指定位置的元素。其步骤为：令指针p指向L。若p为0，表示已到链尾，查找结束，
14、未发现给定元素的结点。若计数器与给定i相同，查找结束，找到给定元素的结点。令p指向直接后继结点，即p=p-next。重复步骤直至查找结束。16169.3.3 9.3.3 查找结点查找结点应用遍历算法定位链表结点，返回第i个数据元素的算法如下：1 intint GetElemGetElem(LinkList LLinkList L,intint i i,ElemTypeElemType*e e)2 /用*e返回L中第i个数据元素/用*e返回L中第i个数据元素3 LinkList pLinkList p=L L;/p指向头结点/p指向头结点4 whilewhile(p p!=!=NULLNULL&
15、i i 0 0)5/顺指针向后查找直到p指向第i个元素或链尾结束/顺指针向后查找直到p指向第i个元素或链尾结束6 p p=p p-nextnext;/指向直接后继结点/指向直接后继结点7 i i-;-;8 9 ifif(p p=NULLNULL|p p=L L)returnreturn 0 0;/第i个元素不存在返回假（0）/第i个元素不存在返回假（0）10 ifif(e e!=!=NULLNULL)*)*e e=p p-datadata;/用*e返回第i个元素/用*e返回第i个元素11 returnreturn 1 1;/操作成功返回真（1）/操作成功返回真（1）12 17179.3.3 9
16、.3.3 查找结点查找结点（2）返回链表中满足指定数据元素的位序LocateElem(L,e,compare()应用遍历算法查找链表结点，返回第一个满足定制关系数据元素的位序的算法如下：18189.3.3 9.3.3 查找结点查找结点1 intint LocateElemLocateElem(LinkList LLinkList L,ElemType eElemType e,intint(*(*comparecompare)()(ElemTypeElemType*,*,ElemTypeElemType*)*)2 /返回L中第1个与e满足关系compare()的数据元素的位序/返回L中第1个与e
17、满足关系compare()的数据元素的位序3 intint i i=0 0;4 LinkList pLinkList p=L L-nextnext;/p指向开始结点/p指向开始结点5 whilewhile(p p!=!=NULLNULL)/若不是链尾继续/若不是链尾继续6 i i+;+;7/关系成立时找到指定元素的位序/关系成立时找到指定元素的位序8 ifif(comparecompare(&(&(p p-datadata),&),&e e)returnreturn i i;9 p p=p p-nextnext;/指向直接后继结点/指向直接后继结点10 11 returnreturn 0 0;
18、/关系不存在返回0/关系不存在返回012 19199.3.3 9.3.3 查找结点查找结点其中compare是函数指针。当调用LocateElem遍历结点时，通过调用compare()对每个结点与给定完成定制的关系比较，关系成立返回真，否则返回假。如相等比较为1/实现两个数据元素关系比较的定制函数/实现两个数据元素关系比较的定制函数2 intint comparecompare(ElemTypeElemType*ep1ep1,ElemTypeElemType*ep2ep2)3 /在函数中对数据元素进行定制的关系比较，如相等，大于或小于/在函数中对数据元素进行定制的关系比较，如相等，大于或小于4
19、 ifif(*(*ep1ep1=*=*ep2ep2)returnreturn 1 1;/满足相等关系返回真（1）/满足相等关系返回真（1）5 returnreturn 0 0;/不满足关系返回假（0）/不满足关系返回假（0）6 20209.3.3 9.3.3 查找结点查找结点（3）返回链表中指定元素的前驱元素PriorElem(L,cur_e,&pre_e)应用遍历算法查找链表结点，返回链表中指定元素的前驱元素的算法如下：21219.3.3 9.3.3 查找结点查找结点1 intint PriorElemPriorElem(LinkList LLinkList L,ElemType cur_e
20、ElemType cur_e,ElemTypeElemType*pre_epre_e)2 /用pre_e返回cur_e元素的前驱/用pre_e返回cur_e元素的前驱3 LinkList qLinkList q,p p=L L-nextnext;/p指向开始结点/p指向开始结点4 whilewhile(p p!=!=NULLNULL)/若不是链尾继续/若不是链尾继续5 q q=p p-nextnext;/q为p的直接后继结点/q为p的直接后继结点6 ifif(q q!=!=NULLNULL&q q-datadata=cur_ecur_e&pre_epre_e!=!=NULLNULL)7*pre
21、_epre_e=p p-datadata;/*pre_e返回前驱元素/*pre_e返回前驱元素8 returnreturn 1 1;/操作成功返回真（1）/操作成功返回真（1）9 10 p p=q q;/p指向直接后继结点/p指向直接后继结点11 12 returnreturn 0 0;/不存在cur_e返回假（0）/不存在cur_e返回假（0）13 22229.3.3 9.3.3 查找结点查找结点（4）返回链表中指定元素的后继元素NextElem(L,cur_e,&next_e)应用遍历算法查找链表结点，返回链表中指定元素的后继元素的算法如下：23239.3.3 9.3.3 查找结点查找结点
22、1 intint NextElemNextElem(LinkList LLinkList L,ElemType cur_eElemType cur_e,ElemTypeElemType*next_enext_e)2 /用next_e返回cur_e元素的后继/用next_e返回cur_e元素的后继3 LinkList pLinkList p=L L-nextnext;/p指向开始结点/p指向开始结点4 whilewhile(p p!=!=NULLNULL)/若不是链尾继续/若不是链尾继续5 ifif(p p-datadata=cur_ecur_e)6 ifif(p p-nextnext!=!=N
23、ULLNULL&next_enext_e!=!=NULLNULL)7*next_enext_e=p p-nextnext-datadata;/*next_e返回后继元素/*next_e返回后继元素8 returnreturn 1 1;/操作成功返回真（1）/操作成功返回真（1）9 10 p p=p p-nextnext;/p指向直接后继结点/p指向直接后继结点11 12 returnreturn 0 0;/不存在cur_e返回假（0）/不存在cur_e返回假（0）13 24249.3.4 9.3.4 链表的逆序链表的逆序链表的逆序是指将原始链表中开始结点变为尾结点，尾结点变为开始结点。逆序的实现是从链表开始结点建立前向链p，移动前向链判断是否到链尾，移动中建立后向链q，最后修改头结点指向后向链。如果是循环链表，则逆序实现起来要方便一些。25259.3.4 9.3.4 链表的逆序链表的逆序图9.7 链表逆序示意结束结束