




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
《数据结构》实验报告◎实验题目:二叉树的建立与遍历◎实验目的:1、掌握使用VisualC++6.0上机调试程序的基本方法;2、掌握二叉树的存储结构和非递归遍历操作的实现方法。3、提高自己分析问题和解决问题的能力,在实践中理解教材上的理论。◎实验内容:利用链式存储结构建立二叉树,然后先序输出该二叉树的结点序列,在在本实验中不使用递归的方法,而是用一个栈存储结点的指针,以此完成实验要求。一、需求分析1、输入的形式和输入值的范围:根据提示,输入二叉树的括号表示形式,按回车结束。2、输出的形式:输出结果为先序遍历二叉树所得到的结点序列。3、程序所能达到的功能:输入二叉树后,该程序可以建立二叉树的链式存储结构,之后按照一定的顺序访问结点并输出相应的值,从而完成二叉树的先序遍历。4、测试数据:输入二叉树的括号表示形式:A(B(D(,G)),C(E,F))先序遍历结果为:ABDGCEF是否继续?(是,输入1;否,输入0):1输入二叉树的括号表示形式:二叉树未建立是否继续?(是,输入1;否,输入0):0Pressanykeytocontinue二概要设计1、二叉树的链式存储结构是用一个链表来存储一棵二叉树,二叉树中每一个结点用链表中的一个链结点来存储。每个结点的形式如下图所示。1childdatarchild其中data表示值域,用于存储对应的数据元素,lchild和rchild分别表示左指针域和右指针域,用于分别存储左孩子结点和右孩子结点的存储位置。2、二叉树的建立本程序中利用数组存储所输入的二叉树,然后从头到尾扫描数组中的每一个字符根据字符的不同分别执行不同的操作,并用一个存储结点指针的栈辅助完成。在扫描前先申请一个结点作为根结点,也是当前指针所指结点,在二叉树的建立的过程中,每次申请一个新结点,需对其进行初始化,即令lchild域和rchild域为空。按照本程序的思路,二叉树A(B(D(,G)),C(E,F))的链式存储结构如下图所示。二叉树建立的具体过程见详细设计部分。3、二叉树的先序遍历在二叉树的先序遍历过程中也需利用一个存储结点指针的栈辅助完成,初始时栈为空,二叉树遍历结束后栈也为空,所以在开始时将头结点入栈,之后根据当前指针所指结点的特性的不同执行不同的操作,以栈空作为二叉树遍历的结束条件。二叉树先序遍历的具体过程见详细设计部分。
4、本程序的基本操作和模块:建立二叉树的函数:voidCreate(BiTNode*B,SeqStack&K,chars[])遍历二叉树的函数:voidPreorder(BiTNode*B,SeqStack&K)主函数:main()函数的调用关系如下图所示:三详细设计(一)元素类型、结点类型
1、二叉树结点的类型描述/*二叉树结点的类型描述*//*data用于存储二叉树中的字母*//*lchild为指向该结点左孩子的指针*//*rchild为指向该结点下一层的指针*/typedefstructnode{chardata;structnode*lchild;structnode*rchild;}BiTNode;/*二叉树结点的类型描述*//*data用于存储二叉树中的字母*//*lchild为指向该结点左孩子的指针*//*rchild为指向该结点下一层的指针*//*顺序栈的类型描述*//*指针数组,用于存储广义表结点指针*//*栈顶指针*/2、顺序栈的类型描述typedefstruct{BiTNode*pin[40];inttop;}SeqStack;/*顺序栈的类型描述*//*指针数组,用于存储广义表结点指针*//*栈顶指针*/(二)每个模块的分析1、主程序模块main(){定义数组,存储输入的字符串定义并申请根结点初始化顺序栈while(1){调用建立二叉树的函数,建立二叉树的链式存储结构调用遍历二叉树的函数,输出所建立的二叉树的结点选择是否继续,若是,则重新执行循环中的操作;若否,则退出循环}}2、建立二叉树的函数voidCreate(BiTNode*B,SeqStack&K,chars[]){定义表示当前结点的指针p,和表示新申请结点的指针q令p指向根结点,根结点的lchild域和rchild域为空。输入二叉树从头到尾扫描输入的字符,进入以下循环,当遇到空字符时结束循环for(j=0;s[j]!='\0';j++){◎若字符为'(',执行以下操作{若'('的下一个字符为',',当前结点p的lchild域为空若'('的下一个字符不为','则执行以下的操作:{申请新结点q,并令新结点q的lchild域和rchild域为空令当前结点p的Ichild域指向新申请的结点q将新申请的结点q作为新的当前结点p}}◎若字符为',',执行以下操作{令当前结点p为栈顶元素,但不退栈申请新结点q,并令新结点q的Ichild域和rchild域为空令当前结点p的rchild域指向新申请的结点q将新申请的结点q作为新的当前结点p}◎若字符为')',执行以下操作{出栈,令当前结点p为栈顶元素}◎若字符为字母,执行以下操作{令当前结点p的data域为该字母若该字母的下一个字符为'('则令当前结点指针p进栈}}}3、遍历二叉树的函数voidDisplay(GLNode*G,SeqStack&K){定义表示当前结点的指针p,并令p指根结点。指向根结点的指针p入栈,使栈不空'。当栈不空时执行以下操作while(K.top!=-1){出栈,栈顶元素所指的结点作为当前结点p,输出当前结点p中的字母若当前结点p的右孩子不为空,则令当前结点p的右孩子进栈若当前结点p的左孩子不为空,则令当前结点p的左孩子进栈}}四使用说明、测试分析及结果1、程序使用说明:本程序运行环境为VisualC++6.0;根据界面提示进行操作,注意输入的字符为西文字符2、测试结果与分析:页面提示“输入二叉树的括号表示形式:”输入“A(B(D(,G)),C(E,F))”,按回车确定,页面显示如下:“先序遍历结果为:ABDGCEF是否继续?(是,输入1;否,输入0):”输入序号“1”,按回车确定,表示继续操作。页面提示“输入二叉树的括号表示形式:”不输入二叉树,直接按回车确定,则页面显示如下:“二叉树未建立是否继续?(是,输入1;否,输入0):”输入序号“0”,按回车确定,表示结束操作,页面显示如下:“Pressanykeytocontinue”由上测试结果分析得,该程序功能满足题目要求。3、调试过程中遇到的问题及解决方法当代码编写完成后,编译过程出现了很多小错误,比如语句末尾漏掉分号,使用了某些变量却未定义,但这些问题很快发现并及时纠正。总的来说,因为本次实验和广义表的建立和输出有相似之处,所以避免了很多问题,比较顺利。4、运行界面五、实验总结本次实验提前作了预习,在编写程序上花费的时间不算太多,我在11月1日下午完成代码的编写并修改正确。因为本次实验和广义表的建立和输出有相似之处,所以大的问题基本没有出现,一些小的问题也及时发现并纠正。本次实验,我很感谢老师和同学对我的指点。通过本次实验,对二叉树的存储结构有了更深的认识,对一些细节更加理解,收获了很多。教师评语:
指导教师签名:批阅日期:指导教师签名:批阅日期:代码:include<stdio.h>include<stdlib.h>//typedefstructnode〃二叉树结点的类型描述(chardata;//data用于存储二叉树中的字母structnode*lchild;//lchild为指向该结点左孩子的指针structnode*rchild;//rchild为指向该结点下一层的指针}BiTNode;//typedefstruct〃顺序栈的类型描述(BiTNode*pin[40];〃指针数组,用于存储广义表结点指针inttop;〃栈顶指针}SeqStack;//voidCreate(BiTNode*B,SeqStack&K,chars[])〃建立二叉树的函数(BiTNode*p,*q;//p指针指向当前结点,q指针指向新申请的结点intj;//j用于标记输入的字符在数组中的位置printf("输入二叉树的括号表示形式:");〃提示输入二叉树gets(s);p=B;p->lchild=NULL;p->rchild=NULL;for(j=0;s[j]!='\0';j++)〃当前结点为根结点〃根结点的lchild域和p=B;p->lchild=NULL;p->rchild=NULL;for(j=0;s[j]!='\0';j++)〃当前结点为根结点〃根结点的lchild域和rchild域为空〃进入循环,建立二叉树(
if(s[j+1]==',')〃若'('的下一个字符为',',当前结点p的lchild域为空p->lchild=NULL;else〃若'('的下一个字符不为',’(q=(BiTNode*)malloc(sizeof(BiTNode));〃申请新结点qq->lchild=NULL;q->rchild=NULL;〃令新结点q的lchild域和rchild域为空p->lchild=q;〃令当前结点p的lchild域指向新申请的结点q
p=q;〃将新申请的结点q作为新的当前结)elseif(s[j]==',')(p=K.pin[K.top];q=(BiTNode*)malloc(sizeof(BiTNode));q->lchild=NULL;q->rchild=NULL;〃若字符为',',执行以下操作〃令当前结点p为栈顶元素,但不退栈//申请新结点q〃令新结点q的lchild域和rchild域为空〃令当前结点p的lchild域指向新申请的结点〃将新申请的结点q作为新的当前结//若字符为')',执行以下操作〃出栈,令当前结点p为栈顶元素〃若字符为'字母',执行以下操作〃令当前结点p的data〃令当前结点p的lchild域指向新申请的结点〃将新申请的结点q作为新的当前结//若字符为')',执行以下操作〃出栈,令当前结点p为栈顶元素〃若字符为'字母',执行以下操作〃令当前结点p的data域为该字母〃若该字母的下一个字符为'('则令当前结点指针p进栈)printf("\n");)//voidPreorder(BiTNode*B,SeqStack&K)(printf(-先序遍历结果为:");BiTNode*p;p=B;K.top++;K.pin[K.top]=p;while(K.top!=-1)〃遍历二叉树函数〃提示以下结果为先序遍历结果//p指针指向当前结点〃当前结点为根结点〃令当前结点指针p进栈〃当栈不为空时执行以下操作(〃出栈,栈顶元素所指的结点作为当前结点p〃输出当前结点p中的字母〃若当前结点p的右孩子不为空,则令当前结点p的右孩子进栈〃若当前结点p的左孩子不为空,则令当前结点p的左孩子进栈〃出栈,栈顶元素所指的结点作为当前结点p〃输出当前结点p中的字母〃若当前结点p的右孩子不为空,则令当前结点p的右孩子进栈〃若当前结点p的左孩子不为空,则令当前结点p的左孩子进栈)printf("\n");)//intmain()(chars[40];〃定义数组,存储输入的字符串inti;BiTNode*B;〃定义根结点,并申请存储空间B=(BiTNode*)malloc(sizeof(BiTNode));SeqStackK;〃定义栈并初始化栈K.t
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 农业生产技术交流与合作意向书
- 2025年心理发展与教育策略的实务能力测试题及答案
- 2025年网络应用与网站建设考试题及答案
- 2025年临床医学专业实践技能考试试题及答案
- 2025年家庭教育指导师职业能力测试试卷及答案
- 2025年海洋生态保护相关知识考试试卷及答案
- 2025年甘肃省特岗教师招聘2261人笔试参考题库及完整答案详解1套
- 2025年甘肃省民航机场集团校园招聘45人笔试备考试题参考答案详解
- 特教学校安全管理制度
- 特殊医用耗材管理制度
- 幼儿园病媒生物防制培训方案
- “影子教育”之全球扩张教育公平、质量、发展中的利弊谈
- JB T 8925-2008滚动轴承汽车万向节十字轴总成技术条件
- (word版)2024年成人高考语文试题及答案
- MOOC Spark编程基础-厦门大学 中国大学慕课答案
- 大易通用能力测评题库
- 联邦学习技术在人工智能中的应用与发展前景
- 地块控制性详细规划说明书
- 工程招标代理服务投标方案(技术方案)
- 【博物馆文创营销方案2600字】
- 分体空调施工方案及分体空调施工组织设计
评论
0/150
提交评论