树的遍历：文件目录结构的显示

《树的遍历：文件目录结构的显示》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、程序实践报告（2010）数据结构课程设计报告树的遍历：文件目录结构的显示专业计算机科学与技术学生姓名杜攀班级BM计算机091学号0951401108指导教师吴素芹1程序实践报告（2010）起止日期2011.1.10-2011.1.141程序实践报告（2010）目录1简介12算法说明43测试结果54分析与探讨65小结8参考文献9附录10附录1源程序清单101程序实践报告（2010）树的遍历：文件目录结构的显示1简介1．树形结构树形结构是一类十分重要的非线性结构，它可以很好地描述客观世界中广泛存在的具体分支关系或层次特性的对象，如操作系统的文件构成、人工智能搜

2、索算法的模型表示以及数据库系统的信息组织形式等。树的一种参考定义为：树是n(n>0)个节点的有穷集合，满足以下条件：（1）有且仅有一个称为根(Root)的节点。（2）其余节点分为m(m≥0)个互不相交的非空集合T1,T2,…,Tm，而这些集合本身都是一棵树，称为根的子树(SubTree)。例如在图2.2中，总共有11个节点，其中A是根节点，B，C，D分别A下面的子树，B子树包含子集{E，F，G}，C子树包含{H}，D子树包含{I，J，K}。B、C、D有共同的父节点A，因此称为兄弟节点。BGFECDIHJKA图2.2树的示例2．树的存储结构和树的遍历（1）三

3、种常用的树的存储结构。双亲表示法：双亲表示的存储方法利用了每个节点都只有唯一的双亲（父节点）的性质（除根节点以外）。在双亲表示法下，每个存储点由两个域组成：数据域——用语存储树上节点中的数据元素；指针域——用于指示本节点所在的存储节点。其形式如下：Typedefstruct{ElemTypedata;Intparent;}TreeNode;17程序实践报告（2010）在存储整棵树的时候，可以利用一维数组，同时设置两个参数，用来表示根的位置和节点数，其形式如下：Typedefstruct{TreeNodenodes[MAX_SIZE];Introot,num

4、;}Tree;例如，表2.2表示的是双亲表示的图2.2中树的存储结构。表2.2图2.2中树的双亲表示存储结构数组下标节点名称对应的双亲节点下标0A-11B02C03D04E15F16G17H28I39J310K8孩子链表表示法：树的双亲表示方法在求节点的孩子时需要遍历整个结构，而孩子链表表示法则便于设计对孩子节点的操作。它的实现方法是：把每个节点的孩子节点排列起来，看成是一个线性表，且以单链表作为存储结构，那么n个节点的树将有n个孩子链表；而n个头指针又组成一个线性表，线性表可以采用顺序存储结构。图2.3表示的是图2.2中树的孩子链表表示。typedefs

5、tructChildNode{intchild;structChildNode*next;}*ChildPtr;typedefstruct{ElemTypedata;ChildPtrfirstchildr;}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;}CTree;17程序实践报告（2010）孩子兄弟双链表表示法：孩子兄弟双亲表示方法中，链表中节点的三个指针域分别指向该节点的父亲点、第一孩子节点和下一兄弟节点，分别命名为Parent域，FirstChild域和NextSibling域。图2.4表

6、示的是图2.2中树的孩子兄弟双亲链表表示。TypedefstructTreeNode{ElemTypedata;structTreeNode*FirstChild,*NextSibling,*Parent;}TreeNode,*Tree;孩子双亲链表的节点形式：*FirstChilddata*NextSibling*Parent图2.4图2.2中树的孩子兄弟双亲链表表示A^^B^EC^F^H^D^^G^I^K^^J^2算法说明输入要求：17程序实践报告（2010）输入数据包含几个测试案例。每一个案例有几行组成，每一行都代表了目录树的层次结构。第一行代表目录

7、的根节点。若是目录节点，那么它的孩子节点将在第二行中被列出，同时用一对圆括号“（）”界定。同时，如果这些孩子节点中某一个也是目录的话，那么这个目录所包含的内容将在随后的一行中列出，有一堆圆括号将首位界定。目录的输入格式为：*namesize，文件的输入格式为：namesize，其中*代表当前节点是目录，name表示文件或目录的名称，由一串长度不大于10的字符组成，并且name字符串中不能含有’(’,’)’,’[’,’]’和’*’。size是该文件/目录的大小，为一个大于0的整数。每一个案例中最多只能包含10层，每一层最多有10个文件/目录。输出要求：对每一

8、个测试案例，输出时要求：第d层的文件/目录名前面需要插入8*d个空