树的遍历课程设计.doc

....... 数据结构课程设计 树的遍历：文件目录结构的显示 专业 计算机科学与技术 班级 ........ 学号 ................ 学生姓名 ................... 目 录 1 设计题目 1 2 设计分析 2 3 设计实现 4 4.2 测试输入 13 4.3 正确输出 14 4.4 实际输出 16 5 分析与探讨 17 5.1 测试结果分析 17 5.2 探讨与改进 17 6 设计小结 17 1 设计题目 给出Unix下目录和文件信息，要求编程实现将其排列成一定缩进的树。具体要求如下。 输入要求： 输入数据包含几个测试方案。每一个案例由几行组成，每一行都代表了目录树的层次结构。第一行代表目录的根节点。若是目录节点，那么它的孩子节点将在第二行中被列出，同时用一对圆括号“()”界定。同样，如果这些孩子节点钟某一个也是目录的话，那么这个目录所包含的内容将在随后的一行中列出，有一对圆括号将首位界定。目录的输入格式为：*name size,文件的输入格式为：name size，其中*代表当前节点的目录，name代表文件或目录的名称，由一串长度不大于10的字符组成，并且name字符串中不能包含有‘(’,‘)’,‘[’,‘]’,‘*’。size是该文件/目录的大小，为大于0的整数。每一个案例中最多只能包含10层，每一层最多有10个文件/目录。 输出要求： 对每一个测试案例，输出时要求：第d层的文件/目录名前面需要插入8*d个空格，兄弟节点之间要在同一列上。不要使用Tab(制表符)来统一输出的缩进。每一个目录的大小(size)是它包含的所有子目录和文件大小以及它自身大小的总和。 输入例子： */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下为空。 输出例子： |_*usr[24] |_*mark[17] | |_hw.c[3] | |_*course[13] | |_aa.txt[12] |_*alex[6] |_hw.c[5] |_*/usr[1] 2 设计分析 目录结构是一种典型的树形结构，为了方便对目录的查找、遍历等操作，可以选择孩子兄弟双亲链表来存储树的结构。程序中要求对目录的大小进行重新计算，根据用户的输入来建立相应的孩子兄弟双亲链表，最后输出树形结构。可以引用一个Tree类，将树的构造、销毁、目录的大小重新计算(reSize)、建立树形链表结构(parse)、树形结构输出(outPut)等一系列操作都封装起来，同时对于每一个树的节点，它的私有变量除了名称(Name)、大小(Size)和层数(Depth)之外，根据孩子兄弟双亲链表表示的需要，还要设置三个指针，即父指针(Tree*parent)、下一个兄弟指针(Tree*NextSibling)和第一个孩子指针(Tree*FirstChild)。 1.建立树形链表结构的函数parse() 根据输入来确定树形关系时，首先读取根节点目录/文件名和大小值，并根据这些信息建立一个新的节点；然后读入后面各行信息，对于同一括号中的内容，即具有相同父节点的那些节点建立兄弟关联。这个函数实际上是采取遍历建立树形链表结构。 定义一个Tree*类型的数组treeArray[]，用来存放目录的节点信息，并定义两个整型变量head和rear，head值用来标记当前节点的父节点位置，每处理完一对括号，head需要增加1，即下一对待处理括号的父节点在treeArray[]中要往后移一个位置。如果当前处理的节点是目录类型，则将它放在treeArray[]数组中，rear是treeArray[]的下标变量，加入一个目录节点信息，rear就增加1；如果是文件类型的目录，则需要按照Name和Size建立一个树的节点，并和head所指的父节点建立关联，但是不用放入treeArray[]中。 为进一步说明这个树形链表结构的构成，可参考图3-1。 treeArray[] 图3-1通过parse()构建的数据结构事例 它是根据如下的具体输入例子所形成的结构示意。 输入： */usr1 (*mark 1 *alex 1) (hw.c3 *course 1)(hw.c 5) (aa.txt 12)