- 1、本文档共85页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
2. 双向链表(Double Linked List) 类型描述 typedef struct DuLNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode, *DuLinkList; 双向循环链表 p-next-prior = p-prior-next; p 双向链表的前(后)插入操作 ①s-prior = p-prior; ②p-prior-next = s; ③ s-next = p; ④p-prior = s; q ①s-next = q-next; ②q-next-prior= s; ③s-prior = q; ④q-next = s; ③ ④ ② ① 双向链表的删除操作 ①p-prior-next = p-next; ②p-next-prior = p-prior; 删除*p的直接后继结点的语句序列 q = p-next; p-next = p-next-next; p-next-prior = p; free(q); 删除*p的直接前驱结点的语句序列 q = p-prior; p-prior = p-prior-prior; p- prior-next = p; free(q); 作业: 2.8 2.9 循环链表算法举例 (1) 假设一个单循环链表,其结点含有三个域pre、data、link。其中data为数据域;pre为指针域,它的值为空指针(null);link为指针域,它指向后继结点。请设计算法,将此表改成双向循环链表。 void SToDouble(DuLinkList la) // la是结点含有pre,data,link三个域的单循环链表。其中data为数据域; pre为空指针域,link是指向后继的指针域。本算法将其改造成双向循环链表。 {while(la-link-pre==null) {la-link-pre=la//将结点la后继的pre指针指向la la=la-link; //la指针后移 } } //算法结束 循环链表算法举例(2) 已知一双向循环链表,从第二个结点至表尾递增有序,(设a1xan)如下图。试编写程序,将第一个结点删除并插入表中适当位置,使整个链表递增有序 x a1 a2 an L void DInsert(DuLinkList L) ∥L是无头结点的双向循环链表,自第二结点起递增有序。本算法将第一结点(a1xan)插入到链表中,使整个链表递增有序 {s=L; ∥s暂存第一结点的指针 t=L-prior; // t暂存尾结点指针 p=L-next; ∥将第一结点从链表上摘下 p-prior=L-prior;p-prior-next=p; x=s-data; while(p-datax) p=p-next; ∥查插入位置 s-next=p;s-prior=p-prior;∥插入原第一结点s p-prior-next=s;p-prior=s; L=t-next; }∥算法结束 例 编写出判断带头结点的双向循环链表L是否对称相等的算法。 解:p从左向右扫描L,q从右向左扫描L,若对应数据结点的data域不相等,则退出循环,否则继续比较,直到p与q相等或p的下一个结点为*q为止。对应算法如下: 循环链表算法举例(3) int Equal(DuLinkList L) { int same=1; DuLinkList p=L-next; /*p指向第一个数据结点*/ DuLinkList q=L-prior; /*q指向最后数据结点*/ while (same==1) if (p-data!=q-data) same=0; else { if (p==q) break; /*数据结点为奇数的情况*/ q=q-prior; if (p==q) break; /*数据结点为偶数的情况*/ p=p-next; } ret
您可能关注的文档
最近下载
- 泌尿科内镜随访制度.docx
- 大学英语综合教程(高级)(华中农业大学)中国大学MOOC(慕课)章节测验试题(答案).pdf
- 江苏海洋大学2023-2024学年第1学期《高等数学(上)》期末考试试卷(B卷)附参考答案.pdf
- 初中物理-内能知识点.doc VIP
- 《语文新课程改革研究》课程考试题库文学类专业(2023年)完整版.doc VIP
- 2023年新版征信报告详细版征信报告模板-Word-可编辑-有水印.docx VIP
- 餐饮店长个人年终工作总结.pptx
- 西门子azl52.00b1中文说明书.pdf
- 泌尿外科内镜技术的风险评估与应急预案.doc
- 《仪器分析》练习题及参考答案(按章节).pdf
文档评论(0)