专业课程设计树的遍历.doc
《专业课程设计树的遍历.doc》由会员分享,可在线阅读,更多相关《专业课程设计树的遍历.doc(24页珍藏版)》请在咨信网上搜索。
1、.数据构造课程设计树遍历专业计算机科学与技术班级xxxxx学号xxxxxx学生姓名xxxxxxxxx目 录1 设计题目12 设计分析23 设计实现44.2 测试输入134.3 对的输出144.4 实际输出165 分析与探讨175.1 测试成果分析175.2 探讨与改进176 设计小结171 设计题目 给出Unix下目录和文献信息,规定编程实现将其排列成一定缩进树。详细规定如下。输入规定:输入数据包括几种测试方案。每一种案例由几行构成,每一行都代表了目录树层次构造。第一行代表目录根节点。若是目录节点,那么它孩子节点将在第二行中被列出,同步用一对圆括号“()”界定。同样,如果这些孩子节点钟某一种也
2、是目录话,那么这个目录所包括内容将在随后一行中列出,有一对圆括号将首位界定。目录输入格式为:*name size,文献输入格式为:name size,其中*代表当前节点目录,name代表文献或目录名称,由一串长度不不不大于10字符构成,并且name字符串中不能包具有(,),*。size是该文献/目录大小,为不不大于0整数。每一种案例中最多只能包括10层,每一层最多有10个文献/目录。输出规定:对每一种测试案例,输出时规定:第d层文献/目录名前面需要插入8*d个空格,兄弟节点之间要在同一列上。不要使用Tab(制表符)来统一输出缩进。每一种目录大小(size)是它包括所有子目录和文献大小以及它自身
3、大小总和。输入例子:*/usr1(*mark 1 *alex 1)(hw.c3 *course 1)(hw.c 5)(aa.txt 12)*/usr 1()表达具有两个不同根目录,目录名都是/usr,第一种根目录/usr下包括mark和alex两个子目录,mark目录下包括大小为3文献hw.c和子目录course,alex目录下有一种大小为5文献hw.c,子目录course下包括文献aa.txt,其大小为12;第二个根目录/usr下为空。输出例子:|_*usr24 |_*mark17| |_hw.c3| |_*course13| |_aa.txt12|_*alex6 |_hw.c5 |_*/u
4、sr12 设计分析目录构造是一种典型树形构造,为了以便对目录查找、遍历等操作,可以选取孩子兄弟双亲链表来存储树构造。程序中规定对目录大小进行重新计算,依照顾客输入来建立相应孩子兄弟双亲链表,最后输出树形构造。可以引用一种Tree类,将树构造、销毁、目录大小重新计算(reSize)、建立树形链表构造(parse)、树形构造输出(outPut)等一系列操作都封装起来,同步对于每一种树节点,它私有变量除了名称(Name)、大小(Size)和层数(Depth)之外,依照孩子兄弟双亲链表表达需要,还要设立三个指针,即父指针(Tree*parent)、下一种兄弟指针(Tree*NextSibling)和第
5、一种孩子指针(Tree*FirstChild)。1.建立树形链表构造函数parse()依照输入来拟定树形关系时,一方面读取根节点目录/文献名和大小值,并依照这些信息建立一种新节点;然后读入背面各行信息,对于同一括号中内容,即具备相似父节点那些节点建立兄弟关联。这个函数事实上是采用遍历建立树形链表构造。定义一种Tree*类型数组treeArray,用来存储目录节点信息,并定义两个整型变量head和rear,head值用来标记当前节点父节点位置,每解决完一对括号,head需要增长1,即下一对待解决括号父节点在treeArray中要往后移一种位置。如果当前解决节点是目录类型,则将它放在treeArr
6、ay数组中,rear是treeArray下标变量,加入一种目录节点信息,rear就增长1;如果是文献类型目录,则需要按照Name和Size建立一种树节点,并和head所指父节点建立关联,但是不用放入treeArray中。为进一步阐明这个树形链表构造构成,可参照图3-1。treeArrayFirstChild/usrmarkalexhw.ccoursehw.caa.txtparentNextSiblingparentFirstChildparentparentFirstChildparentNextSibling图3-1通过parse()构建数据构造事例它是依照如下详细输入例子所形成构造示意。输
7、入:*/usr1(*mark 1 *alex 1)(hw.c3 *course 1)(hw.c 5)(aa.txt 12)形成数据构造如图2.5所示。2.目录大小重新计算函数reSize()输入数据中对目录大小初始值普通为1,而目录真正大小应当是自身大小和它包括所有文献及子目录大小之和。因而,在计算目录大小时候,需要遍历它下面所有文献和子目录,可以采用递归嵌套后序遍历方式。此外要注意,采用孩子兄弟双亲链表表达时,父目录下所有子目录和子文献都在该父目录左子树上(右子树第一种节点是该目录兄弟节点),因此白努力时候只需要遍历目录对左子树即可。3.输出树形构造函数outPut()输出是一种先序遍历过程
8、。为完毕对树形输出,兄弟目录之间需要相似缩进,用|上下相连,而父子目录或父目录和子文献之间需要设定对的缩进,子目录或子文献要比父目录向右缩进8个空格。设立一种标志数组flag11(每个目录下最大层次数为10),当前Tree*temp指针所指节点如果有兄弟节点,则置flag数组值为1,否则置为0;并由此节点重复查询它祖先节点状况,直到根节点为止。输出时,遇到flag=1时,屏幕输出“| ”,表白是兄弟节点;遇到flag=0则输出“ ”, 有相似缩进,而子节点总比父节点向右缩进8个空格。4.消除输入中多余空格函数skipWhiteSpace(string &s,int *i)从顾客输入数据中读入一
9、行后,调用该函数来跳过s字符串中si之后空格,以以便背面解决。此外,关于读入目录名称、大小,以及将string类型Size值转换成int类型函数实现,相对比较简朴,此处不再赘述。3 设计实现运用visual c+,新建一种c+文献,将如下代码输入。#include #include #include using namespace std;string s = ;int startPos = 0;ofstream outfile;ifstream infile;/*构造Tree类*/class Treestring Name; /* 树根结点名称 */int Size; /* 树大小,用于记录
10、这棵树自身及其包括因此子树大小总和*/Tree* FirstChild; /* 指向它第一种孩子结点 */Tree* NextSibling;/* 指向它下一种兄弟结点 */Tree* parent; /* 指向双亲结点 */public:Tree(string Name = ,int Size = 0);/* 构造函数 */void parse(); /* 依照输入数据来建立树形构造 */void reSize(); /* 重新记录树结点大小 */void outPut();/* 输出树形构造 */Tree(); /* 析构函数 */;/* 树结点数组treeArray,以及用来标注双亲结点
11、位置head和目录结点rear*/Tree* treeArray100;int head = 0,rear = 0;/* 建立只有一种结点树,其三个指针域均为空 */Tree:Tree(string Name,int Size)this-Name = Name;this-Size = Size;FirstChild = NULL;NextSibling = NULL;parent = NULL;/* 析构函数,删除同一根结点下各个子结点,释放空间 */Tree:Tree()Tree* temp;Tree* temp1;temp = FirstChild;while(temp != NULL)t
12、emp1 = temp;temp = temp-NextSibling;delete temp1;/* 先序遍历根结点下所有结点,将每一种结点Size值都加到根结点Size中去*/void Tree:reSize()Tree* temp = this; /* 如果当前结点没有孩子结点,则它Size值不变,即为输入时候值 */if(temp-FirstChild != 0)temp = temp-FirstChild;while(temp != 0)temp-reSize();Size += temp-Size;temp = temp-NextSibling;/*检查Name中有无非法字符*/b
13、ool checkName(string s)if(s0!=* & s.length() 10)return false;if(s0=* & s.length() 11)return false;if(s0!=* & (s0=( | s0=) | s0= | s0=)return false;for(int i=1;is.length();i+)if(si=* | si=( | si=) | si= | si=)return false;return true;/* 按照先序遍历方式有缩进地来输出树形构造 */void Tree:outPut()Tree* temp;/*用来指向当前结点祖先结
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 专业课程 设计 遍历
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。