版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、实验三 全线索链表应用问题定义及需求分析1.1课题目的和任务问题描述:对二叉树的二叉链表结点增加两个指针域,前驱指针prior和后继指针next。通过该结点构造全线索二叉链表。实验要求:设计一个全线索二叉链表的应用程序。1)创建全线索二叉树。2)完成全线索二叉树的主要基本操作。3)给出简单应用实例1.2数据形式输入数据形式:通过键盘输入数据输入值的范围:输入值的范围均为float型,范围为1.2e-38至3.4e+38。 输出数据形式:输出到显示器。1.3程序功能将全线索作用于二叉排序树中,通过对其进行中序遍历线索化,实现通过线索搜索某个节点的前驱和后继,并且利用线索,实现对整个树中数据的中序
2、线索输出,并且能够在删除树中某个节点后,实现对该树的重新线索化。1.4测试数据7 /树中元素的个数5 2 7 1 3 6 8 /依次输入的树中元素值3 /需要输出前驱和后继的元素值7 /删除的元素值8 /重新线索化后,需要输出前驱和后继的元素值1. 概要设计2.1抽象数据类型需要定义一个全线索二叉树,该树中含有数据,左右孩子,以及分别指向前驱和后继的指针。通过前驱和后继指针,将建立的二叉树中序线索化,从而实现对数据更方便和快速的获取。2.2主程序流程及各模块之间的调用关系2. 详细设计3.1存储结构实现typedef struct type/数据类型结构体声明 float num;type;t
3、ypedef struct bitnode/二叉树结构体声明 struct type data; struct bitnode* lchild,* rchild,* prior,* next;bitnode,*bitree;3.2负责模块的伪码算法(1)int visit(type e,bitree t)/找到相同元素并返回它的前驱和后继 if(t-data =e) return 1; else return 0;(2)const int inordertraverse_thr(bitree t,type e,int (*visit)(type e,bitree t),type& prior,
4、type& next)/中序遍历二叉排序线索树,并返回符合visit函数的元素的前驱和后继 b=t-next; while(b非空且不等于t) if(visit(e,b)/找到等于e的b结点值 if(b前驱等于t) next=b-next-data;/b只有后继 return 2; else if(b后继等于t) prior=b-prior-data;/b只有前驱 return 3; else/b前驱和后继都不等于t (prior,next)=(b-prior-data,b-next-data); return 1;/前驱和后继都存在 b=b-next; return 0;(3)const i
5、nt searchpn(bitree thrt,bitree t)/利用全线索查找所需元素的前驱和后继 cine;/输入要查找的元素m=inordertraverse_thr(thrt,e,(*visit),prior,next);/全线索中序查找某个元素的前驱和后继 if(m=1)输出前驱和后继 else if(m=2)前驱不存在,输出后继 else if(m=3)后继不存在,输出前驱 else查找失败,树中无该元素 return 1;3. 调试分析4.1问题分析与解决方法对于给定输入数,查找它的前驱和后继,需要考虑该数是否存在前驱和后继,如果没有前驱和后继,则需要输出不存在标志。利用线索指
6、针很容易进行判断,如果需要查找的元素的前驱是线索的头(线索的头是个空结点),那么该元素就不存在前驱,只存在后继;而如果需要查找的元素的后继是线索的头,那么它就不存在后继,只有前驱。因此通过if进行判断,就可以成功输出需要查询的元素的前驱和后继。4.2算法的时空分析在树中查找某个元素并输出该元素的前驱和后继的整个时间复杂度最多为,空间复杂度为。4.3算法的改进设想 全线索的应用主要是为了方便树的遍历,能够快速的访问某个节点的前驱和后继,因此可以考虑将线索应用于平衡二叉树上,从而进一步提高平衡二叉树获取数据的速度。4.4经验和体会 在整个程序的编写过程中,出现一个问题,如果是首次线索化,便可以通过
7、线索成功输出该树,但当删除某个节点后,再次进行线索化,然后利用线索输出该树就无法得到完整的树。后来经过调试发现,由于第一次的线索化,该树内的各个线索指针已被赋值,所以第二次线索化实际上是失败的,因此需要先对树进行去线索化操作(把线索指针指空)后,再对其进行线索化,这样才能输出正确的数据。 可见,程序各个模块之间的影响不容小觑,必须对程序各个模块的功能和影响有个整体的把握才不至于出现不合设想的错误。4. 使用说明按照操作提示,通过键盘输入数据即可。输入的节点数据可以为小数,但是数量数据必须为正整数。5. 测试结果(截屏)(1)前驱和后继都存在的数:(2)只存在前驱的数:(3)只存在后继的数:6.
8、 附录7.1个人负责模块的程序代码int visit(type e,bitree t)/找到相同元素并返回它的前驱和后继 if(t-data.num=e.num) return 1; else return 0;const int inordertraverse_thr(bitree t,type e,int (*visit)(type e,bitree t),type& prior,type& next)/中序遍历二叉排序线索树,并返回符合visit函数的元素的前驱和后继 bitree b=t-next; while(b!=null&b!=t) if(visit(e,b) if(b-prio
9、r=t)/该点的前驱为t,说明它无前驱 next.num=b-next-data.num; return 2; else if(b-next=t)/该点的后继为t,说明它无后继 prior.num=b-prior-data.num; return 3; else/该点既有前驱也有后继 prior.num=b-prior-data.num; next.num=b-next-data.num; return 1; b=b-next; return 0;const int searchpn(bitree thrt,bitree t)/利用全线索查找所需元素的前驱和后继 type e,prior,ne
10、xt; int m; coutplease input a number to be searched and print its prior and next:e.num; m=inordertraverse_thr(thrt,e,(*visit),prior,next);/全线索中序查找某个元素的前驱和后继 if(m=1)/前驱和后继均有的情形 coutthe prior of number e.num is prior.num,; coutand its next is next.num.endl; else if(m=2)/只有后继的情形 coutthe prior of number
11、 e.num is not existed,; coutand its next is next.num.endl; else if(m=3)/只有前驱的情形 coutthe prior of number e.num is prior.num,; coutand its next is not existed.endl; else/未找到该数的情形 coutthe number searched is not existedendl; return 1;7.2程序全部代码#include#includeusing namespace std;typedef struct type/数据类型结
12、构体声明 float num;type;typedef struct bitnode/二叉排序树结构体声明 struct type data; struct bitnode* lchild,* rchild,* prior,* next;bitnode,*bitree;int inittree(bitree& t,type e)/创建二叉排序树 t=(bitree)malloc(sizeof(bitnode); if(!t)return 0; t-data.num=e.num; t-lchild=t-rchild=null; t-prior=t-next=null; return 1;int
13、destroytree(bitree& t)/递归销毁二叉排序树 if(t=null) return 0; destroytree(t-lchild); destroytree(t-rchild); free(t); return 1;int searchtree(bitree t,type key,bitree& p)/非递归算法,搜索二叉排序树中元素 while(t) if(key.num=t-data.num)p=t;return 1; else if(key.numdata.num) p=t; t=t-lchild; else p=t; t=t-rchild; return 0;int
14、 inserttree(bitree& t, type e)/二叉排序树中元素插入 bitree p; if(!searchtree(t,e,p) bitree s; s=(bitree)malloc(sizeof(bitnode); s-data.num=e.num; s-lchild=s-rchild=null; s-prior=s-next=null; if(!p)t=s; else if(e.numdata.num) p-lchild=s; else p-rchild=s; return 1; coutthe number has been existed!data.num) dele
15、te(t); return 1; else if(e.numdata.num) deletetree(t-lchild,e); elsedeletetree(t-rchild,e); return 1;int delete(bitree& p)/结点删除算法 if(!p-lchild)/没有左孩子 bitree q; q=p; p=p-rchild; free(q); else if(!p-rchild)/没有右孩子 bitree q; q=p; p=p-lchild; free(q); else/两个孩子都有 bitree q,s; q=p; s=p-lchild; while(s-rchi
16、ld) q=s; s=s-rchild; p-data.num=s-data.num; if(q!=p) q-rchild=s-lchild; elseq-lchild=s-lchild; free(s); return 1;int visit(type e,bitree t)/找到相同元素并返回它的前驱和后继 if(t-data.num=e.num) return 1; else return 0;const int inordertraverse_thr(bitree t,type e,int (*visit)(type e,bitree t),type& prior,type& next
17、)/中序遍历二叉排序线索树,并返回符合visit函数的元素的前驱和后继 bitree b=t-next; while(b!=null&b!=t) if(visit(e,b) if(b-prior=t) next.num=b-next-data.num; return 2; else if(b-next=t) prior.num=b-prior-data.num; return 3; else prior.num=b-prior-data.num; next.num=b-next-data.num; return 1; b=b-next; return 0;int inorderthreadin
18、g(bitree& thrt,bitree& t)/中序遍历二叉排序树t,并将其线索化,头结点为thrt void inthreading(bitree& ,bitree& ); if(!t)return 0; else thrt=(bitree)malloc(sizeof(bitnode); thrt-next=thrt-prior=null; bitree pre; pre=thrt; inthreading(t,pre); pre-next=thrt; thrt-prior=pre; return 1;void inthreading(bitree& t,bitree& pre)/将结点
19、线索化 if(t) inthreading(t-lchild,pre); if(t-prior=null)t-prior=pre; if(pre-next=null)pre-next=t; pre=t; inthreading(t-rchild,pre); const int inorderthrprint(bitree thrt)/中序线索遍历输出树 if(!thrt) return 0; bitree b=thrt-next; while(b!=thrt) coutdata.numnext; coutendl; return 1;const int searchpn(bitree thrt
20、,bitree t)/利用全线索查找所需元素的前驱和后继 type e,prior,next; int m; coutplease input a number to be searched and print its prior and next:e.num; m=inordertraverse_thr(thrt,e,(*visit),prior,next);/全线索中序查找某个元素的前驱和后继 if(m=1) coutthe prior of number e.num is prior.num,; coutand its next is next.num.endl; else if(m=2) coutthe prior of number e.num is not existed,; coutand its next is next.num.endl; else if(m=3) coutthe prior of number e.num is prior.num,; coutand its next is not existed.endl; else coutthe number searched is not existednext=t-prior=null; removethr(t-lchild); removethr(t-rchild); r
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高中地理必修第二册《城乡内部空间结构》教学设计
- 九年级物理《电流 电流表》作业课教学设计
- 高中美术选修中国书画教学设计:方寸之间见精神-篆刻闲章与姓名印的文化解码与刀法实践
- 小学五年级音乐《卢沟谣》大单元整体教学设计:基于历史情境的家国情怀育人实践
- 初中科学酸碱盐综合应用教学设计
- 技术平权时代 2026年广东省AI大模型垂直应用内部创业孵化运营方案
- 双碳背景下:无人零售终端光伏自给与碳交易商业模式
- 山东省2027年春季高考语文全真冲刺模拟卷(三)
- 税务部门人员能力考核表
- 关于产品认证进展情况的确认函3篇范本
- (2026年)实施指南《DLT 1878-2018 燃煤电厂储煤场盘点导则》
- 双电源自动切换系统实验报告
- 初中语文阅读教学主问题设计:策略、实践与效能提升
- 《韧战》(2023年福建省中考满分作文15篇附审题指导)
- 艾灸治疗鼻炎
- 《相似植物如何区别》课件
- 驾驶员素质提升培训
- My family幼儿园家庭成员介绍手抄报
- 国家安全教育大学生读本-第一章完全准确领会总体国家安全观
- 《外科学》教案:第七章 麻醉
- 产后康复经络与腧穴
评论
0/150
提交评论