文件目录结构的显示.doc

兄弟双亲链表

二叉树先序遍历

后序遍历

目录结构

需积分: 10 52 下载量 161 浏览量更新于2023-07-19 收藏 139KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

26页

本设计采用孩子兄弟双亲链表的存储结构，引入了一个Tree类，将树的构造、销毁、目录大小的重新计算（reSize）、建立树形链表结构（parse）、树形机构输出（outPut）等一系列操作都封装起来，另设置了三个指针，即父指针（Tree* parent）、下一个兄弟指针（Tree* NextSibling）和第一个孩子指针（Tree* FirstChild）。运用二叉树的后序遍历算法将每一个节点的size值都加到根节点的size中去，如果当前的节点没有孩子节点，则它的size值即为输入时的值；运用二叉树的先序遍历算法将输入的字符串有缩进的输出，在此基础之上完成系统设计，实现了文件目录结构的显示。此文中还具体给出Linux下目录和文件信息，并在Visual Studio C++ 6.0环境里面实现将其排列成一棵有一定缩进的树。

资源详情

资源推荐

文件目录结构的显示

relife

摘要：本设计采用孩子兄弟双亲链表的存储结构，引入了一个 Tree 类，将树的

构造、销毁、目录大小的重新计算（reSize）、建立树形链表结构（parse）、树形

机构输出（outPut）等一系列操作都封装起来，另设置了三个指针，即父指针

（Tree* parent）、下一个兄弟指针（Tree* NextSibling）和第一个孩子指针

（Tree* FirstChild）。运用二叉树的后序遍历算法将每一个节点的 size 值都加到

根节点的 size 中去，如果当前的节点没有孩子节点，则它的 size 值即为输入时

的值；运用二叉树的先序遍历算法将输入的字符串有缩进的输出，在此基础之

上完成系统设计，实现了文件目录结构的显示。此文中还具体给出 Linux 下目

录和文件信息，并在 Visual Studio C++ 6.0 环境里面实现将其排列成一棵有一定

缩进的树。

关键词：兄弟双亲链表；二叉树先序遍历；后序遍历；目录结构

目 录
操作系统为 Windows XP，编程环境为 VC++6.0。...............12
目录的输入格式为：*name size,文件的输入格式为：name
size,其中*代表当前节点是目录,name 表示文件或目录的名称，
由一窜长度不大于 10 的字符组成，并且 name 字符串中不能
含有‘（‘，’）’，‘[‘，’ ]’和‘*’。Size 是该文件/目录的大小，
为一个大于 0 的整数。每一个案例中最多只能包含 10 层。
每一层最多有 10 个文件/目录。.............................................12
输入例子：................................................................................12
*/usr1......................................................................................... 12
(*mark 1 *alex 1).......................................................................12
(hw.c 3 *course 1)(hw.c 5).........................................................12
(aa.txt 12)...................................................................................12
*/usr 1........................................................................................12
()................................................................................................. 12
表示有两个不同的根目录，目录名都是/usr，第一个根目录/
usr 下包含 mark 和 alex 两个子目录，mark 目录下包含大小为
3 的文件 hw.c 和子目录 course,alex 目录下有一个大小为 5 的
文件 hw.c，子目录 course 下包含文件 aa.txt，其大小为 12；
第二个根目录/usr 下为空。.....................................................12
第 d 层的文件/目录名前面需要插入 8*d 个空格，兄弟节点之
2

间要在同一列上。不要使用 Tab（制表符）来统一输出的缩
进。每一个目录的大小（size）是它包含的所有目录和文件
大小以及它自身大小的总和。................................................12
输出例子：................................................................................12
|_*/usr[24]..................................................................................12
|_*mark[17]................................................................................12
| |_hw.c[3]................................................................................... 13
 | |_*course[13]...........................................................................13
 | |_aa.txt[12]............................................................................... 13
 |_*alex[6]..................................................................................13
 |_hw.c[5].................................................................................... 13
|_*/usr[1]....................................................................................13
树形结构是一类十分重要的非线性结构，它可以很好地描述客
观世界中广泛存在的具有分支关系或层次特性的对象，如操作
系统的文件构成、人工智能搜索算法的模型表示以及数据库系
统的信息组织形式等。.................................................................13
树的一种参考定义为：树是 n（n>0）个节点的有穷集合，满足
以下条件：..................................................................................... 13
（1）有且仅有一个称为根（Root）的节点。............................13
（2）有余节点分为 m（m>=0）个互不相交的非空集合 T1,T2,
…,Tm ， 而 这 些 集 合 本 身 都 是 一 颗 树 ， 称 为 根 的 子 树
（SubTree）。例如在图 1.1 中，总共有 11 个节点，其中 A 是
3

根节点，B、C、D 分别是 A 下面的子树，B 子树包含子集
{E,F,G}，C 子树包含{H}，D 子树包含{I,J,K}。B、C、D 有共
同的父节点 A，因此称为兄弟节点。..........................................13
下面是一些树结构中基本术语：..................................................13
直接前驱：A 为 B 的父节点（Parent），则节点 A 是 B 的直接
前驱。............................................................................................. 13
根节点（Root）：没有直接前驱的节点。 ................................13
节点的度（Degree）：树上任一节点所拥有的子树的数目。 .13
叶子或终端节点（Leaf）：度为 0 的节点。.............................13
分支点或非终端节点：度大于 0 的节点。..................................13
树的度：一颗树中所有节点的度的最大值。..............................13
兄弟节点（Sibling）：父节点相同的节点。 ............................13
节点的层数（Level）：根的层数为 1，其余节点的层数为其父
节点的层数加 1..............................................................................13
树的高度或深度：一颗树中所有节点层数的最大值。..............14
图 1.1 树的示例..............................................................................14
Typedef{ /*结构*/................................................................14
ElemType data;.....................................................................14
int Parent; /*父节点位置*/...................................................14
}TreeNode;...........................................................................14
在存储整棵树的时候，可以利用一维数组，同时设置两
个参数，用来表示根的位置和节点数，其形式如下:......14
4

 typedef struct{ /*树结构*/..................................................14
 TreeNode nodes[MAX_SIZE];............................................14
 int root,num; /*根的位置和节点数*/.................................14
 }Tree;...................................................................................14
树的双亲表示方法在求节点的孩子时需要遍历整个结构，
而孩子链表表示法则便于设计对孩子节点的操作。其实
现方法是：把每个节点的孩子节点排列起来，看成是一
个线性表，且以单链表作为存储结构，那么 n 个节点的
树将有 n 个孩子链表；而 n 个头指针又组成一个线性表，
线性表可以采用顺序存储结构。树的孩子链表表示如下：
.............................................................................................. 15
 typedef struct ChildNode{...................................................15
 Int child;..............................................................................15
 Struct ChildNode* next;......................................................15
 } *ChildPtr;.........................................................................15
 typedef struct{.....................................................................15
 ElemType data;....................................................................15
 ChildPtr firstchildr;..............................................................15
 } CTBox;.............................................................................15
 typedef struct{.....................................................................15
 CIBox nodes[MAX_TREE_SIZE];.....................................15
 int n,r;..................................................................................15
5