《攻克C语言链表学习资料》由会员分享，可在线阅读，更多相关《攻克C语言链表学习资料（51页珍藏版）》请在金锄头文库上搜索。
1、DataStructureUsingC,信息管理学院尹晓yx_,Chapter5LinkedLists,在本章中，我们将学到：认识链表的特性链表的三种类型单链表双链表循环链表稀疏矩阵利用链表对多项表达式进行加法计算,假设有一个单链表中存储了100000个数字，这些数字从第一个节点开始依次按升序排序。如果我们想以升序的方式显示这些数字，该怎么办呢？答案是：从第一个节点开始遍历列表。,假如我们又需要以降序的方式显示这些数字，如何解决此问题呢？单链表中每一个节点链接到序列中的下一个节点。这意味着我们只能以单向遍历列表。要以降序的方式显示数字，我们需要反转(reverse)这个链表。,链接列表,1,1
2、00000,2,Header,3,.,上述算法的存在什么问题？无论你什么时候访问下一节点，你都需要调整三个变量的所有链接。此方法的缺点：对长链表来说效率低且耗时。如何解决此问题？如果列表中每一个节点不仅包含序列中其下一个节点的地址，而且还包含其前一节点的地址，那么此问题就可以解决。,链接列表,考虑下面的单链表。我们可以在单链表的每个节点中引入一个额外的字段，它存储前一个节点的地址。这种类型的链表就是双链表(doublylinkedlist)。,链接列表,Header,15,19,21,23,25,32,Header,15,19,21,23,25,32,Doublylinkedlistsarea
3、lsocalledtwo-waylistortwo-waychain)。在双链表中，每个节点需要存储：数据下一个节点的地址前一个节点的地址定义双链表中节点的结构体类型structnodeintdata;structnode*Llink;structnode*Rlink;,链接列表（续）,5.5DoublyLinkedList,Adoublylinkedlistisalineardatastructureinwhicheachnodecanhaveanynumberofdatafieldsandtwolinkfieldswhichareusedtopointtothepreviousnodean
4、dthenextnode.(page184),链接列表（续）,5.5.1Definition,Theoperationsthatcanbeperformedonthedoublylinkedlistare：a)insertionb)deletionc)searchd)copye)mergef)traverseTheonlydifferencebetweenasinglylinkedlistanddoublylinkedlististhattwopointernodeshavetobemodified.(page184),链接列表（续）,5.5.2OpertationsonaDoublyLink
5、edList,25,10,15,createanewnode,theaddressisNew.ptr=Header-RlinkifNewisnotNULLNew-Llink=HeaderHeader-Rlink=NewNew-Rlink=ptrptr-Llink=NewNew-data=X,Header,在前端插入元素75,插入完成,75,a)Insertionoperationi)atthefrontii)attheendiii)atanypostion,75,25,10,15,在双链表的末尾插入一个节点ptr=Header-Rlinkwhileptr-RlinkisnotNULLptr=p
6、tr-Rlinkcreateanewnode,theaddressisNewifNewisnotNULLNew-Llink=ptrptr-Rlink=NewNew-Rlink=NULLNew-data=Xelseprint“createfail”,Header,在末尾插入元素75,插入完成,a)Insertionoperationi)atthefrontii)attheendiii)atanypostion,75,25,10,15,ptr=Header-Rlinkwhileptr-data!=XandptrisnotNULLptr=ptr-Rlinkcreateanewnode,theaddr
7、essisNewifptrisNULLprint“cantfindX”returnifptr-data=Xptr1=ptr-RlinkNew-Llink=ptrNew-Rlink=ptr1ptr-Rlink=Newptr1-Llink=NewNew-data=X,Header,在元素10后插入元素75,插入完成,a)Insertionoperationi)atthefrontii)attheendiii)atanypostion,25,10,ptr=Header-RlinkifptrisNULLprint“listempty”returnelseptr1=ptr-RlinkHeader-Rli
8、nk=ptr1ptr1-Llink=Headerfree(ptr),Header,在前端删除元素,删除完成,b)Deletionoperation：i)atthefrontii)attheendiii)atanypostion,10,ptr=Header-RlinkifptrisNULLprint“listempty”returnwhileptr-RlinkisnotNULLptr=ptr-Rlinkhere,ptrpointstothelastnodeptr1=ptr-Llinkptr1-Rlink=NULLfree(ptr),Header,在末尾删除元素,删除完成,b)Deletionop
9、eration：i)atthefrontii)attheendiii)atanypostion,ptr=Header-RlinkifptrisNULLprint“listempty”returnwhileptr-data!=XandptrisnotNULLptr=ptr-RlinkifptrisNULLprint“cantfindX”returnifptr-data=Xptr1=ptr-Llinkptr2=ptr-Rlinkptr1-Rlink=ptr2ptr2-Llink=ptr1free(ptr),Header,删除元素10,删除完成,15,25,b)Deletionoperation：i
10、)atthefrontii)attheendiii)atanypostion,c)searchoperationinadoublylinkedlist,ptr=Header-Rlinkwhileptr-data!=XandptrisnotNULLptr=ptr-RlinkifptrisNULLprint“cantfindX”returnifptr-data=Xreturnptr,returnptr,查找成功,查找元素10,15,25,Header,d)copyoperation,ptr1=Header-Rlinkcreateanewnode,theaddressisHeader1ptr2=He
11、ader1ptr2-data=NULLptr2-Llink=NULLwhileptr1isnotNULLcreateanewnode，theaddressisNewNew-data=ptr1-dataptr2-Rlink=NewNew-Llink=ptr2ptr1=ptr1-Rlinkptr2=Newptr2-Rlink=NULL,复制结束,15,25,10,Header,New,15,New,10,New,25,e)mergeoperationinadoublylinkedlist,ptr=Header1-Rlinkwhileptr-RlinkisnotNULLptr=ptr-Rlinkpt
12、r1=Header2-Rlinkptr1-Llink=ptrptr-Rlink=ptr1free(Header2),合并结束,15,25,10,Header1,27,35,18,f)traversingthedoublylinkedlist,ptr=Header1-RlinkwhileptrisnotNULLprintptr-dataptr=ptr-Rlink,15,25,10,Header1,15,10,25,遍历结束,假定你正在开发一款动作游戏，其中会给每个游戏者一套武器。在屏幕上依次显示每种武器。一旦显示第n个武器后，就会再次显示第一次出现的武器，并且这种顺序会跟前面一样继续。你将使用哪
13、种数据结构来存储武器的列表？,我们可以使用单链表。但是，武器需要以循环重复的次序显示。因此，一旦显示了所有武器，指针必须从列表中第一个武器重新开始。这需要在每次到达列表结尾时重新初始化指针。在此情况下，如果遍历最后一个武器对应的节点后指针能够自动移到列表中的第一个武器，那将会更加简单。使用循环链表(circularlinkedlist)可以实现这一点。,Acircularlinkedlistisalinkedlistwherethelastnodepointstotheheadernode.(page198)Incirclularlinkedlist,therearenoNULLlinks.C
14、ircularlinkedlistscanbeeitherofthetwotypes:singlylinkedcircularlistdoublylinkedcircularlist,链接列表（续）,5.6CircularLinkedList,15,9,11,23,5,12,15,9,11,23,5,12,5.6.2singlylinkedcircularlist,5.6.3doublylinkedcircularlist,Thereisadisadvantagethatifthereisnocareinprocessingthedataelementsinthenodes,aninfinit
15、eloopcanoccur.(page199),Toavoidthisproblem,aspecialnodecalledaheadernodecanbemaintainedwithoutthedataelement.,Theoperationsthatcanbeperformedoncircularlinkedlistare：a)insertionb)deletionc)traversingd)searchinge)mergingf)splittingg)copying,链接列表（续）,5.6.4OpertationsonaCircularLinkedList,traversingthecircularlinkedlist,ptr=Header-linkwhileptr!=Headerprintptr-dataptr=ptr-link,15,10,25,10,Header,15,10,25,遍历结束
