没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
试读
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 环境里面实现将其排列成一棵有一定
缩进的树。
关键词:兄弟双亲链表;二叉树先序遍历;后序遍历;目录结构
1
目 录
操作系统为 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
剩余25页未读,继续阅读
资源评论
kaoyanbibi
- 粉丝: 4
- 资源: 8
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功