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