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