T4-线性表(双向链表和循环链表)_第1页
T4-线性表(双向链表和循环链表)_第2页
T4-线性表(双向链表和循环链表)_第3页
T4-线性表(双向链表和循环链表)_第4页
T4-线性表(双向链表和循环链表)_第5页
已阅读5页，还剩15页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

双向链表和循环链表第二章：线性表

主讲：周翔什么是双向链表什么是双向链表？什么是双向链表上一节学习了单链表，但是单链表有一个缺点，无法快速访问前驱结点，当查找到某一个元素时，如果想查找其前驱结点，需要再次从头遍历。因此，有人提出在结点中再添加一个指向前驱的指针，如此便构成了双向链表。什么是双向链表下图为一个双向链表，表中第一个结点的前驱指针pre指向了NULL，最后一个结点的后继结点next指向了NULL。在双向链表中，通过一个结点可以找到它的后继结点，也可以找到它的前驱结点。双向链表双向链表：在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双（向）链表（DoubleLinkedList）。双链表的结点结构后继指针域predatanext前驱指针域数据域双向链表双向链表的结构定义：ADTDNode{ //结点类型定义ElemTypedata //数据域Nodepre,next //指针域}ADTDNode,DoubleList双向链表结点指向p->prep->nextprenextp双向链表——基本运算前插操作算法描述：欲在双向链表第i个结点之前插入一个的新的结点，则指针的变化情况如图所示。pse......ab①②③④双向链表——基本运算删除操作算法描述：欲删除双向链表中的第i个结点，则指针的变化情况如图所示。abcp②①……什么是循环链表什么是循环链表？循环链表循环链表（CircularLinkedList）是首尾相接的一种链表，它尾结点的后继指针又指向链表的第一个结点，这样形成了一个环。对于循环链表，从表中的任何一个结点出发，能找到其它所有的结点。特点：将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点

La1……ai-1aianLa1……ai-1aianrear*(rear->next)*rear空链表带头结点的一般形式带尾结点的一般形式循环链表循环单链表假设链表长度为n在表头插入或删除，时间复杂性O(1)在表尾插入或删除，时间复杂性O(n)a1……ai-1aianL带头结点的一般形式循环单链表假设链表长度为n在表头插入或删除，时间复杂性O(1)在表尾插入或删除，时间复杂性O(1)a1……ai-1aianrear*(rear->next)*rear带尾结点的一般形式所以，在循环单链表中附设尾指针有时比附设头指针会使操作变得更简单循环单链表——查找查找成功查找不成功LL3131484815155757查找15

查找25

pppppppp循环链表中没有明显的尾端，如何避免死循环？循环单链表——查找循环条件：p的下一个指针指向表头从循环链表中的任何一个结点的位置都可以找到其他所有结点，而单链表做不到循环双链表循环双链表排序循环双链表总结相对于单链表来说，双向链表要复杂一些，因为它多了一个前驱指针，所以对应插入和删除

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论