课程设计--树的遍历.doc

《课程设计--树的遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计——树的遍历：文件目录结构的显示.......数据结构课程设计树的遍历专业计算机科学与技术班级xxxxx学号xxxxxx学生姓名xxxxxxxxx1数据结构课程设计——树的遍历：文件目录结构的显示目录1设计题目12设计分析23设计实现44.2测试输入134.3正确输出144.4实际输出165分析与探讨175.1测试结果分析175.2探讨与改进176设计小结171数据结构课程设计——树的遍历：文件目录结构的显示1设计题目给出Unix下目录和文件信息，要求编程实现将其排列成一定缩进的树。具体要求如下。输入要求：输入数据包含几个测

2、试方案。每一个案例由几行组成，每一行都代表了目录树的层次结构。第一行代表目录的根节点。若是目录节点，那么它的孩子节点将在第二行中被列出，同时用一对圆括号“()”界定。同样，如果这些孩子节点钟某一个也是目录的话，那么这个目录所包含的内容将在随后的一行中列出，有一对圆括号将首位界定。目录的输入格式为：*namesize,文件的输入格式为：namesize，其中*代表当前节点的目录，name代表文件或目录的名称，由一串长度不大于10的字符组成，并且name字符串中不能包含有‘(’,‘)’,‘[’,‘]’,‘*’。size是该文件/目录的大小，为大

3、于0的整数。每一个案例中最多只能包含10层，每一层最多有10个文件/目录。输出要求：对每一个测试案例，输出时要求：第d层的文件/目录名前面需要插入8*d个空格，兄弟节点之间要在同一列上。不要使用Tab(制表符)来统一输出的缩进。每一个目录的大小(size)是它包含的所有子目录和文件大小以及它自身大小的总和。输入例子：*/usr1(*mark1*alex1)(hw.c3*course1)(hw.c5)(aa.txt12)*/usr1()表示含有两个不同的根目录，目录名都是/usr,第一个根目录/usr下包含mark和alex两个子目录，mar

4、k目录下包含大小为3的文件hw.c和子目录course,alex目录下有一个大小为5的文件hw.c，子目录course下包含文件aa.txt，其大小为12；第二个根目录/usr下为空。输出例子：

5、_*usr[24]

6、_*mark[17]

7、

8、_hw.c[3]

9、

10、_*course[13]17数据结构课程设计——树的遍历：文件目录结构的显示

11、

12、_aa.txt[12]

13、_*alex[6]

14、_hw.c[5]

15、_*/usr[1]2设计分析目录结构是一种典型的树形结构，为了方便对目录的查找、遍历等操作，可以选择孩子兄弟双亲链表来存储树的结构。程序中要求对

16、目录的大小进行重新计算，根据用户的输入来建立相应的孩子兄弟双亲链表，最后输出树形结构。可以引用一个Tree类，将树的构造、销毁、目录的大小重新计算(reSize)、建立树形链表结构(parse)、树形结构输出(outPut)等一系列操作都封装起来，同时对于每一个树的节点，它的私有变量除了名称(Name)、大小(Size)和层数(Depth)之外，根据孩子兄弟双亲链表表示的需要，还要设置三个指针，即父指针(Tree*parent)、下一个兄弟指针(Tree*NextSibling)和第一个孩子指针(Tree*FirstChild)。1.建立树

17、形链表结构的函数parse()根据输入来确定树形关系时，首先读取根节点目录/文件名和大小值，并根据这些信息建立一个新的节点；然后读入后面各行信息，对于同一括号中的内容，即具有相同父节点的那些节点建立兄弟关联。这个函数实际上是采取遍历建立树形链表结构。定义一个Tree*类型的数组treeArray[]，用来存放目录的节点信息，并定义两个整型变量head和rear，head值用来标记当前节点的父节点位置，每处理完一对括号，head需要增加1，即下一对待处理括号的父节点在treeArray[]中要往后移一个位置。如果当前处理的节点是目录类型，则将

18、它放在treeArray[]数组中，rear是treeArray[]的下标变量，加入一个目录节点信息，rear就增加1；如果是文件类型的目录，则需要按照Name和Size建立一个树的节点，并和head所指的父节点建立关联，但是不用放入treeArray[]中。为进一步说明这个树形链表结构的构成，可参考图3-1。17数据结构课程设计——树的遍历：文件目录结构的显示treeArray[]FirstChild/usrmarkalexhw.ccoursehw.caa.txtparentNextSiblingparentFirstChildparen

19、tparentFirstChildparentNextSibling图3-1通过parse()构建的数据结构事例它是根据如下的具体输入例子所形成的结构示意。输入：*/usr1(*