1、 数据结构课程设计实验数据结构课程设计实验 树的遍历，文件目录结构的显示树的遍历，文件目录结构的显示 实验报告实验报告 一、一、简介简介 树型结构是一类十分重要的非线性结构，它可以很好地描述客观世界中广泛 存在的具有分支关系或层次特性的对象，如操作系统的文件构成、人工智能搜索 算法的模型表示以及数据库系统的信息组织形式等。 文件的目录结构是树型结构在计算机操作系统的典型应用。通过树型结构可 以直观且清晰的表明操作系统中的文件组织结构。用户可通过树型结构显示的文 件目录列表找到自己想访问的内容。 本实验的要求在给出 Unix 下目录和文件信息的前提下，编程实现将其排列成 一棵具有一定缩进的树。具
2、体要求如下： 输入要求 输入数据包含几个测试案例。每一个案例由几行组成，每以行都代表了目录 树的层次结构。第一行代表目录的根节点。若是目录节点，那么它的孩子节点将 在第二行中被输出，同时用一对圆括号“ （） ”界定。同样，如果这些孩子节点中 某一个也是目录的话，那么这个目录所包含的内容将在随后的一行中列出，由一 对圆括号将首尾界定。 目录的输入格式为： *nams size， 文件的输入格式为： name size，其中*代表当前节点是目录，name 代表文件或目录的名称，由一串长度不 大于 10 的字符组成，并且 name 字符串中不能含有(，)，和*。size 是该 文件/目录的大小，为一
3、个大于 0 的整数。每一个案例中最多只能包含 10 层，每 一层最多有 10 个文件/目录。 输出要求 对每一个测试案例，输出时要求：第 d 层的文件/目录名前面需要插入 8*d 个 空格，兄弟节点之间要在同一列上。不要使用 Tab（制表符）来统一输出的缩进。 每一个目录的大小（size）是它所包含的所有子目录和文件大小以及它自身大小 的总和。 有输入/输出样例如下： 输入样例： */usr 1 (*mark 1 *alex 1) (hw.c 3 *course 1)(hw.c 5) 树的遍历，文件目录结构的显示 1 (aa.txt 12) */usr 1 () 输出样例： |_*/usr24
4、 |_*mark17 | |_hw.c3 | |_*course13 |_aa.txt12 |_*alex6 |_hw.c5 |_*usr1 因此，实验任务如下： （1）读入给定的 Unix 目录和文件信息。 （2）建立树型链表以表示目录和文件结构，同时重新计算目录大小 （3）以树型结构输出文件信息。 二、设计说明二、设计说明 2.1、数据结构实现 目录结构是一种典型的树形结构，可以选择孩子兄弟双亲链表来储存树的结 构。 孩子兄弟双亲链表是一种典型的树的存储结构。在该表示方法中，链表中节 点的三个指针域分别指向该节点的父亲、第一个孩子节点和下一个兄弟节点，分 别命名为 Parent 域，Fir
5、stChild 域和 NextSibling 域。 在孩子兄弟双亲链表表示法中，节点形式统一，节点间的联系比较简洁。同 时，在这种存储结构上容易实现树数据结构的大多数运算。因此，孩子兄弟双亲 链表表示是树的一种实用的储存结构。其节点形式如下： 本题中采用面向对象的方式实现树型结构。构建 Tree 类,将所有的目录作为 Tree 类的对象。Tree 类定义如下： class Tree string Name; /树的根节点名称 int Size; /树的大小，用于统计树本身及其子数大小的总和 Tree* FirstChild; /指向他的第一个孩子节点 Tree* NextSibling; /指
6、向下一个兄弟节点 Tree* Parent; /指向父节点 *FirstChild data *NextSibling *Parent 数据结构课程设计 2 public: Tree (string Name=”,int Size=0); /构造函数 void parse(); /根据输入数据建立树型结构 void reSize(); /重新统计树节点的大小 void outPut(); /输出函数 Tree(); /析构函数 ； 2.2、主要函数的实现 在 Tree 类中共定义了 5 个函数， 即构造树 （Tree()构造函数） ， 销毁树 （Tree() 析构函数） ，目录大小计算（reSize()函数） ，建立树型链表结构（parse()函数）和 树型结构输出（outPut()函数） 。下面分别说明如下： 2.2.1 构造函数 构造函数的作用是建立一个只有一个节点的树，其三个指针域均为空，以方 便接下来目录结构的读入和树型链表的构建。 函数实现如下： Tree:Tree(st
