全线索二叉链表实验报告_中学教育-中学实验.pdf
( 4.5 )《全线索二叉链表实验报告_中学教育-中学实验.pdf》由会员分享，可在线阅读，更多相关《全线索二叉链表实验报告_中学教育-中学实验.pdf（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、w.资 料.全 线 索 链 表 应 用 w.资 料.报告提交人：郭超峰 班级：计算机 1404 学号：20143678 一：问题定义及需求分析 二：概要设计 分析五使用说明六测试结果截屏七组个人设计部分八附录带源代码资料一问题定义及需求分析课题全线索链表应用课题描述对二叉树的二叉链表结点增加两个指针域前驱指针和后继指针通过该结点构造全线索二叉链表课题要求设计 形式本实验中全线索二叉树元素均为整形程序功能创建二叉树对二叉树中序遍历进行全线索化求树中任意元素的前驱后继左孩子右孩子对二叉树进行元素的插入和删除对二叉树的清空操作资料测试数据测试的二叉树为如下资料二概 后继求左孩子求右孩子插入元素删除元
2、素将二叉树清空主函数调用上述函数求解相应问题资料三详细设计各模块的算法如下初始化栈判断栈空入栈资料出栈二叉树的构建存储分配失败递归构建左子树递归构建右子树资料返回头节点w.资 料.三：详细设计 四：调试分析 五：使用说明 六:测试结果（截屏）七：组个人设计部分 八：附录（带源代码）分析五使用说明六测试结果截屏七组个人设计部分八附录带源代码资料一问题定义及需求分析课题全线索链表应用课题描述对二叉树的二叉链表结点增加两个指针域前驱指针和后继指针通过该结点构造全线索二叉链表课题要求设计 形式本实验中全线索二叉树元素均为整形程序功能创建二叉树对二叉树中序遍历进行全线索化求树中任意元素的前驱后继左孩子右
3、孩子对二叉树进行元素的插入和删除对二叉树的清空操作资料测试数据测试的二叉树为如下资料二概 后继求左孩子求右孩子插入元素删除元素将二叉树清空主函数调用上述函数求解相应问题资料三详细设计各模块的算法如下初始化栈判断栈空入栈资料出栈二叉树的构建存储分配失败递归构建左子树递归构建右子树资料返回头节点w.资 料.一：问题定义及需求分析 课题：全线索链表应用 课题描述：对二叉树的二叉链表结点增加两个指针域，前驱指针 prior 和后继指 针 next。通过该结点构造全线索二叉链表。课题要求：设计一个全线索二叉链表的应用程序。1)创建全线索二叉树。2)完成全线索二叉树的主要基本操作。3)给出简单应用实例。输
4、入输出形式：本实验中全线索二叉树元素均为整形（int）。程序功能：1：创建二叉树。2：对二叉树中序遍历进行全线索化。3：求树中任意元素的前驱、后继、左孩子、右孩子。4：对二叉树进行元素的插入和删除。5：对二叉树的清空操作。分析五使用说明六测试结果截屏七组个人设计部分八附录带源代码资料一问题定义及需求分析课题全线索链表应用课题描述对二叉树的二叉链表结点增加两个指针域前驱指针和后继指针通过该结点构造全线索二叉链表课题要求设计 形式本实验中全线索二叉树元素均为整形程序功能创建二叉树对二叉树中序遍历进行全线索化求树中任意元素的前驱后继左孩子右孩子对二叉树进行元素的插入和删除对二叉树的清空操作资料测试数
5、据测试的二叉树为如下资料二概 后继求左孩子求右孩子插入元素删除元素将二叉树清空主函数调用上述函数求解相应问题资料三详细设计各模块的算法如下初始化栈判断栈空入栈资料出栈二叉树的构建存储分配失败递归构建左子树递归构建右子树资料返回头节点w.资 料.测试数据：测试的二叉树为如下 1 2 3 4 5 6 7 8 分析五使用说明六测试结果截屏七组个人设计部分八附录带源代码资料一问题定义及需求分析课题全线索链表应用课题描述对二叉树的二叉链表结点增加两个指针域前驱指针和后继指针通过该结点构造全线索二叉链表课题要求设计 形式本实验中全线索二叉树元素均为整形程序功能创建二叉树对二叉树中序遍历进行全线索化求树中任
6、意元素的前驱后继左孩子右孩子对二叉树进行元素的插入和删除对二叉树的清空操作资料测试数据测试的二叉树为如下资料二概 后继求左孩子求右孩子插入元素删除元素将二叉树清空主函数调用上述函数求解相应问题资料三详细设计各模块的算法如下初始化栈判断栈空入栈资料出栈二叉树的构建存储分配失败递归构建左子树递归构建右子树资料返回头节点w.资 料.二：概要设计 typedef struct BiThrNode int data;struct BiThrNode*lchild,*rchild,*prior,*next;BiThrNode,*BiThrTree;/抽象数据类型 BiThrNode typedef str
7、uct ElemType data100;int Stacksize;SqStack;/抽象数据类型 SqStack void*InitStack(SqStack*p);/初始化栈 int StackEmpty(SqStack*S);/判断栈空 int Push(SqStack*S,ElemType e);/入栈 ElemType Pop(SqStack*S,ElemType e);/出栈 分析五使用说明六测试结果截屏七组个人设计部分八附录带源代码资料一问题定义及需求分析课题全线索链表应用课题描述对二叉树的二叉链表结点增加两个指针域前驱指针和后继指针通过该结点构造全线索二叉链表课题要求设计 形
8、式本实验中全线索二叉树元素均为整形程序功能创建二叉树对二叉树中序遍历进行全线索化求树中任意元素的前驱后继左孩子右孩子对二叉树进行元素的插入和删除对二叉树的清空操作资料测试数据测试的二叉树为如下资料二概 后继求左孩子求右孩子插入元素删除元素将二叉树清空主函数调用上述函数求解相应问题资料三详细设计各模块的算法如下初始化栈判断栈空入栈资料出栈二叉树的构建存储分配失败递归构建左子树递归构建右子树资料返回头节点w.资 料.BiThrTree CreatBiTree(BiThrTree p);/二叉树的构建 BiThrTree InOrderThreading(BiThrTree p);/中序线索化 in
9、t InOrder(BiThrTree p);/求中序序列 int qianqu(BiThrTree p);/求前驱 int houji(BiThrTree p);/求后继 int zuohai(BiThrTree p);/求左孩子 int youhai(BiThrTree p);/求右孩子 int Insert(BiThrTree p);/插入元素 int Delete(BiThrTree p);/删除元素 int Clear(BiThrTree p);/将二叉树清空 Int main()/主函数调用上述函数求解相应问题 分析五使用说明六测试结果截屏七组个人设计部分八附录带源代码资料一问题定
10、义及需求分析课题全线索链表应用课题描述对二叉树的二叉链表结点增加两个指针域前驱指针和后继指针通过该结点构造全线索二叉链表课题要求设计 形式本实验中全线索二叉树元素均为整形程序功能创建二叉树对二叉树中序遍历进行全线索化求树中任意元素的前驱后继左孩子右孩子对二叉树进行元素的插入和删除对二叉树的清空操作资料测试数据测试的二叉树为如下资料二概 后继求左孩子求右孩子插入元素删除元素将二叉树清空主函数调用上述函数求解相应问题资料三详细设计各模块的算法如下初始化栈判断栈空入栈资料出栈二叉树的构建存储分配失败递归构建左子树递归构建右子树资料返回头节点w.资 料.三：详细设计 各模块的算法如下：Status I
11、nitStack(SqStack*p)/初始化栈 p.Stacksize=-1;return OK;Status StackEmpty(SqStack*S)/判断栈空 if(p-Stacksize=-1)return TURE;else return FALSE;Status Push(SqStack*S,ElemType e)/入栈 P-Stacksize=p-Stacksize+1;P-datap-Stacksize=e;return OK;分析五使用说明六测试结果截屏七组个人设计部分八附录带源代码资料一问题定义及需求分析课题全线索链表应用课题描述对二叉树的二叉链表结点增加两个指针域前驱指
12、针和后继指针通过该结点构造全线索二叉链表课题要求设计 形式本实验中全线索二叉树元素均为整形程序功能创建二叉树对二叉树中序遍历进行全线索化求树中任意元素的前驱后继左孩子右孩子对二叉树进行元素的插入和删除对二叉树的清空操作资料测试数据测试的二叉树为如下资料二概 后继求左孩子求右孩子插入元素删除元素将二叉树清空主函数调用上述函数求解相应问题资料三详细设计各模块的算法如下初始化栈判断栈空入栈资料出栈二叉树的构建存储分配失败递归构建左子树递归构建右子树资料返回头节点w.资 料.Status Pop(SqStack*S,ElemType e)/出栈 e=p-datap-Stacksize;P-Stacks
13、ize=p-Stacksize-1;return e;Status CreatBiTree(BiThrTree p)/二叉树的构建 scanf(&m);if(m=0)p=NULL;else if(!(p=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);/存储分配失败 else p-data=m;p-prior=NULL;p-next=NULL;p-lchild=NULL;p-rchild=NULL;p-lchild=CreatBiTree(p-lchild);/递归构建左子树 p-rchild=CreatBiTree(p-rchild);/递
14、归构建右子树 分析五使用说明六测试结果截屏七组个人设计部分八附录带源代码资料一问题定义及需求分析课题全线索链表应用课题描述对二叉树的二叉链表结点增加两个指针域前驱指针和后继指针通过该结点构造全线索二叉链表课题要求设计 形式本实验中全线索二叉树元素均为整形程序功能创建二叉树对二叉树中序遍历进行全线索化求树中任意元素的前驱后继左孩子右孩子对二叉树进行元素的插入和删除对二叉树的清空操作资料测试数据测试的二叉树为如下资料二概 后继求左孩子求右孩子插入元素删除元素将二叉树清空主函数调用上述函数求解相应问题资料三详细设计各模块的算法如下初始化栈判断栈空入栈资料出栈二叉树的构建存储分配失败递归构建左子树递归
15、构建右子树资料返回头节点w.资 料.return p;/返回头节点 Status InOrderThreading(BiThrTree p)/中序线索化 InitStack(&S);if(!(Thr=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);/存储分配失败 Thr-data=0;Thr-lchild=p;/Thr 为头节点 Thr-rchild=NULL;p1=p;pre=Thr;/pre 为全局变量，指向 p1 的前一个节点 while(p1|!StackEmpty(&S)if(p1)Push(&S,p1);p1=p1-lchild;
16、/进栈 else p1=Pop(&S,p1);/出栈 pre-next=p1;p1-prior=pre;/中序线索化 分析五使用说明六测试结果截屏七组个人设计部分八附录带源代码资料一问题定义及需求分析课题全线索链表应用课题描述对二叉树的二叉链表结点增加两个指针域前驱指针和后继指针通过该结点构造全线索二叉链表课题要求设计 形式本实验中全线索二叉树元素均为整形程序功能创建二叉树对二叉树中序遍历进行全线索化求树中任意元素的前驱后继左孩子右孩子对二叉树进行元素的插入和删除对二叉树的清空操作资料测试数据测试的二叉树为如下资料二概 后继求左孩子求右孩子插入元素删除元素将二叉树清空主函数调用上述函数求解相应
17、问题资料三详细设计各模块的算法如下初始化栈判断栈空入栈资料出栈二叉树的构建存储分配失败递归构建左子树递归构建右子树资料返回头节点w.资 料.pre=p1;p1=p1-rchild;pre-next=Thr;/最后一个节点线索化 Thr-prior=pre;return Thr;/返回头节点 Status InOrder(BiThrTree p)/求中序序列 for(p1=p-next;p1!=p;p1=p1-next)printf(p1-data);/输出节点值 求前驱、后继、左孩子、右孩子思路差距不大，下面以求前驱为例：Status qianqu(BiThrTree p)/求前驱 scanf
18、(&e);/输入要查找元素 for(p2=p-next;p2-data!=0;p2=p2-next)/逐个检查树中元素 if(p2-data=e)p3=p2-prior;分析五使用说明六测试结果截屏七组个人设计部分八附录带源代码资料一问题定义及需求分析课题全线索链表应用课题描述对二叉树的二叉链表结点增加两个指针域前驱指针和后继指针通过该结点构造全线索二叉链表课题要求设计 形式本实验中全线索二叉树元素均为整形程序功能创建二叉树对二叉树中序遍历进行全线索化求树中任意元素的前驱后继左孩子右孩子对二叉树进行元素的插入和删除对二叉树的清空操作资料测试数据测试的二叉树为如下资料二概 后继求左孩子求右孩子插
19、入元素删除元素将二叉树清空主函数调用上述函数求解相应问题资料三详细设计各模块的算法如下初始化栈判断栈空入栈资料出栈二叉树的构建存储分配失败递归构建左子树递归构建右子树资料返回头节点w.资 料.if(p3-data=0)Printf(“该点不存在中序前驱！”)；break;else printf(该点的中序前驱为：);printf(p3-data);/输出 e 的前驱 break;Status Insert(BiThrTree p)/插入元素 p2=(BiThrTree)malloc(sizeof(BiThrNode);printf(输入所要插入的节点：);scanf(&a);printf(输入
20、所要查找的节点：);scanf(&b);for(p1=p-next;p1!=p;p1=p1-next)/逐个检查树中元素 if(p1-data=b)break;if(p1=p)printf(该节点不存在！n);else switch(j)case 1:/插入元素作为左孩子 p2-data=a;p2-lchild=NULL;p2-rchild=NULL;p2-next=p1;p2-prior=p1-prior;p1-prior-next=p2;p1-prior=p2;p1-lchild=p2;break;分析五使用说明六测试结果截屏七组个人设计部分八附录带源代码资料一问题定义及需求分析课题全线索
21、链表应用课题描述对二叉树的二叉链表结点增加两个指针域前驱指针和后继指针通过该结点构造全线索二叉链表课题要求设计 形式本实验中全线索二叉树元素均为整形程序功能创建二叉树对二叉树中序遍历进行全线索化求树中任意元素的前驱后继左孩子右孩子对二叉树进行元素的插入和删除对二叉树的清空操作资料测试数据测试的二叉树为如下资料二概 后继求左孩子求右孩子插入元素删除元素将二叉树清空主函数调用上述函数求解相应问题资料三详细设计各模块的算法如下初始化栈判断栈空入栈资料出栈二叉树的构建存储分配失败递归构建左子树递归构建右子树资料返回头节点w.资 料.case 2:/插入元素作为右孩子 p2-data=a;p2-lchi
22、ld=NULL;p2-rchild=NULL;p2-prior=p1;p2-next=p1-next;p1-next-prior=p2;p1-next=p2;p1-rchild=p2;break;default:exit(0);/switch/else Status Delete(BiThrTree p)/删除元素 scanf(&a);/输入要删除的元素 for(p1=p-next;p1!=p;p1=p1-next)/逐个检查树中是否有此元素 if(p1-data=a)break;if(p1=p)printf(该树中无此节点！);else if(p1=p1-prior-rchild)/元素作为
23、右孩子 p1-prior-next=p1-next;p1-next-prior=p1-prior;p1-prior-rchild=NULL;free(p1);/释放 P1 if(p1=p1-next-lchild)/元素作为左孩子 p1-prior-next=p1-next;p1-next-prior=p1-prior;p1-next-lchild=NULL;free(p1);/释放 p1/else/Delete Status Clear(BiThrTree p)/将二叉树清空 for(p1=p-next;p2!=p;)分析五使用说明六测试结果截屏七组个人设计部分八附录带源代码资料一问题定义及
24、需求分析课题全线索链表应用课题描述对二叉树的二叉链表结点增加两个指针域前驱指针和后继指针通过该结点构造全线索二叉链表课题要求设计 形式本实验中全线索二叉树元素均为整形程序功能创建二叉树对二叉树中序遍历进行全线索化求树中任意元素的前驱后继左孩子右孩子对二叉树进行元素的插入和删除对二叉树的清空操作资料测试数据测试的二叉树为如下资料二概 后继求左孩子求右孩子插入元素删除元素将二叉树清空主函数调用上述函数求解相应问题资料三详细设计各模块的算法如下初始化栈判断栈空入栈资料出栈二叉树的构建存储分配失败递归构建左子树递归构建右子树资料返回头节点w.资 料.p2=p1-next;free(p1);/释放节点
25、p1 p1=p2;free(p);/释放头节点 四：调试分析 1：对所遇到问题的解决方法及分析 1）建立二叉树时遇到问题：输入时未使用 0 来表明无左右孩子，导致递归 无法结束，原因是为理解递归建立二叉树的过程。2）建立二叉树后进行相应问题的求解后，无法进行多次求解，经分析后采用子函数相互调用的方法顺利解决。3）其余一些程序语法 及逻辑错误，经组成员严谨排查顺利解决 2：算法的时空分析及改进设想 1）算法时空分析：相应算法的时间复杂度均为 O（n）2）改进设想：1）可以使用函数指针来使用求前驱、后继、左孩子、右孩子 等子函数。2）或许可以使用一子函数代替程序中实现多次求解的代码，简化程序。分析
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 线索 二叉 实验 报告 中学 教育
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内