《攻克c语言链表》ppt课件

《《攻克c语言链表》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DataStructureUsingC信息管理学院尹晓yx_018@126.comChapter5LinkedLists在本章中，我们将学到：认识链表的特性链表的三种类型单链表双链表循环链表稀疏矩阵利用链表对多项表达式进行加法计算假设有一个单链表中存储了100000个数字，这些数字从第一个节点开始依次按升序排序。如果我们想以升序的方式显示这些数字，该怎么办呢？答案是：从第一个节点开始遍历列表。11000002Header3...假如我们又需要以降序的方式显示这些数字，如何解决此问题呢？单链表中每一个节点链接到序列中

2、的下一个节点。这意味着我们只能以单向遍历列表。要以降序的方式显示数字，我们需要反转(reverse)这个链表。链接列表11000002Header3...11000002Header3...反转单链表ptr1=Header->linkptr2=ptr1->linkptr3=ptr2->linkptr1->link=NULLwhileptr3不为空ptr2->link=ptr1ptr1=ptr2ptr2=ptr3ptr3=ptr3->linkptr2->link=ptr1Header->link=ptr2571022

3、Headerptr2ptr110ptr31015ptr1ptr2ptr3ptr1ptr2ptr3ptr1ptr2ptr3NULL反转结束上述算法的存在什么问题？无论你什么时候访问下一节点，你都需要调整三个变量的所有链接。此方法的缺点：对长链表来说效率低且耗时。如何解决此问题？如果列表中每一个节点不仅包含序列中其下一个节点的地址，而且还包含其前一节点的地址，那么此问题就可以解决。链接列表考虑下面的单链表。我们可以在单链表的每个节点中引入一个额外的字段，它存储前一个节点的地址。这种类型的链表就是双链表(doublyli

4、nkedlist)。链接列表Header151921232532Header151921232532Doublylinkedlistsarealsocalledtwo-waylistortwo-waychain)。在双链表中，每个节点需要存储：数据下一个节点的地址前一个节点的地址定义双链表中节点的结构体类型structnode{intdata;structnode*Llink;structnode*Rlink;}链接列表（续）5.5DoublyLinkedListDataRlinkNodeLlinkAdoub

5、lylinkedlistisalineardatastructureinwhicheachnodecanhaveanynumberofdatafieldsandtwolinkfieldswhichareusedtopointtothepreviousnodeandthenextnode.(page184)链接列表（续）5.5.1DefinitionTheoperationsthatcanbeperformedonthedoublylinkedlistare：a)insertionb)deletionc)search

6、d)copye)mergef)traverseTheonlydifferencebetweenasinglylinkedlistanddoublylinkedlististhattwopointernodeshavetobemodified.(page184)链接列表（续）5.5.2OpertationsonaDoublyLinkedList251015createanewnode,theaddressisNew.ptr=Header->RlinkifNewisnotNULLNew->Llink=HeaderHea

7、der->Rlink=NewNew->Rlink=ptrptr->Llink=NewNew->data=XHeader在前端插入元素75插入完成Newptr75a)Insertionoperationi)atthefrontii)attheendiii)atanypostionNew75251015在双链表的末尾插入一个节点ptr=Header->Rlinkwhileptr->RlinkisnotNULLptr=ptr->Rlinkcreateanewnode,theaddressisNewifNewisnotNU

8、LLNew->Llink=ptrptr->Rlink=NewNew->Rlink=NULLNew->data=Xelseprint“createfail”Header在末尾插入元素75插入完成ptrptra)Insertionoperationi)atthefrontii)attheendiii)atanypostionNew75251015ptr=Head