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

程序实践报告（2010） 数据结构课程设计报告树的遍历 文件目录结构的显示专业计算机科学与技术学生姓名杜攀班级BM计算机091学号0951401108指导教师吴 素 芹起止日期2011.1.10-2011.1.141目 录1 简介12算法说明33测试结果54分析与探讨65小结8参考文献9附 录10附录1 源程序清单101树的遍历文件目录结构的显示1 简介 1树形结构树形结构是一类十分重要的非线性结构，它可以很好地描述客观世界中广泛存在的具体分支关系或层次特性的对象，如操作系统的文件构成、人工智能搜索算法的模型表示以及数据库系统的信息组织形式等。树的一种参考定义为树是nn0个节点的有穷集合，满足以下条件（1） 有且仅有一个称为根Root的节点。（2） 其余节点分为mm0个互不相交的非空集合T1,T2Tm，而这些集合本身都是一棵树，称为根的子树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）三种常用的树的存储结构。双亲表示法双亲表示的存储方法利用了每个节点都只有唯一的双亲（父节点）的性质（除根节点以外）。在双亲表示法下，每个存储点由两个域组成数据域用语存储树上节点中的数据元素；指针域用于指示本节点所在的存储节点。其形式如下Typedef structElemType data;Int parent;TreeNode;在存储整棵树的时候，可以利用一维数组，同时设置两个参数，用来表示根的位置和节点数，其形式如下Typedef structTreeNode nodesMAX_SIZE;Int root,num;Tree;例如，表2.2表示的是双亲表示的图2.2中树的存储结构。表2.2 图2.2中树的双亲表示存储结构数组下标节点名称对应的双亲节点下标0A-11B02C03D04E15F16G17H28I39J310K8孩子链表表示法树的双亲表示方法在求节点的孩子时需要遍历整个结构，而孩子链表表示法则便于设计对孩子节点的操作。它的实现方法是把每个节点的孩子节点排列起来，看成是一个线性表，且以单链表作为存储结构，那么n个节点的树将有n个孩子链表；而n个头指针又组成一个线性表，线性表可以采用顺序存储结构。图2.3表示的是图2.2中树的孩子链表表示。typedef struct ChildNodeint child;struct ChildNode*next;*ChildPtr;typedef structElemType data;ChildPtr firstchildr;CTBox;typedef structCTBox nodesMAX_TREE_SIZE;int n,r;CTree;孩子兄弟双链表表示法孩子兄弟双亲表示方法中，链表中节点的三个指针域分别指向该节点的父亲点、第一孩子节点和下一兄弟节点，分别命名为Parent域，FirstChild域和NextSibling域。图2.4表示的是图2.2中树的孩子兄弟双亲链表表示。Typedef struct TreeNode ElemType data; struct TreeNode*FirstChild,*NextSibling,*Parent;TreeNode,*Tree;孩子双亲链表的节点形式*FirstChilddata*NextSibling*Parent图2.4 图2.2中树的孩子兄弟双亲链表表示 A B E C F H D G I K J 2算法说明输入要求输入数据包含几个测试案例。每一个案例有几行组成，每一行都代表了目录树的层次结构。第一行代表目录的根节点。若是目录节点，那么它的孩子节点将在第二行中被列出，同时用一对圆括号“（）”界定。同时，如果这些孩子节点中某一个也是目录的话，那么这个目录所包含的内容将在随后的一行中列出，有一堆圆括号将首位界定。目录的输入格式为*name size，文件的输入格式为name size， 其中*代表当前节点是目录，name表示文件或目录的名称，由一串长度不大于10的字符组成，并且name字符串中不能含有,和*。size是该文件/目录的大小，为一个大于0的整数。每一个案例中最多只能包含10层，每一层最多有10个文件/目录。输出要求对每一个测试案例，输出时要求第d层的文件/目录名前面需要插入8*d个空格，兄弟节点之间要在同一列上。不要使用Tab（制表符）来统一输出的缩进。每一个目录的大小（size）是它包含的所有子目录和文件大小以及它自身大小的总和。 1. 先序遍历 Void preorderBinaryTreePtr t Ift Visitt; /*访问根节点*/ preordert-LeftChild; /*先序遍历左子树*/ preordert-RightChild; /*先序遍历右子树*/ 2. 中序遍历 Void InorderBinaryTreePtr t Ift Inordert-LeftChild; /*中序遍历左子树*/ Visitt; /*访问根节点*/ Inordert-RightChild; /*中序遍历右子树*/ 3.后序遍历 Void PostorderBinaryTreePtr t Ift Postordert-LeftChild; /*后序遍历左子树*/ Postordert-RightChild; /*后序遍历右子树*/ Visitt; /*访问根节点*/ 3测试结果4分析与探讨目录结构是一种典型的树形结构，为了方便对目录的查找、遍历等操作，可以选择孩子兄弟双亲链表来存储树的结构。程序中要求对目录的大小进行重新计算，根据用户的输入来建立相应的孩子兄弟双亲链表，最后输出树形结构。可以引用一个Tree类，将树的构造、销毁、目录大小的重新计算（reSize）、建立树形连标结构（parse）、树形结构输出（outPut）等一系列操作都封装起来，同时对于每一个树的节点，它的私有变量除了名称（Name）、大小（Size）和层数（Depth）之外，根据孩子兄弟双亲链表表示的需要，还要设置三个指针，即父指针Tree * parent、下一个兄弟指针Tree * Nextsibling和第一个孩子指针Tree * FirstChild.1.建立树形链表结构的函数parse（）根据输入来确定树形关系时，首先读取根节点目录/文件名和大小值，并根据这些信息建立一个新的节点；然后读入后面各行信息，对于同一括号中的内容，即具有相同父节点的那些节点建立兄弟关联。这个函数实际上采用层次遍历建立树形链表结构。为进一步说明这个树形链表结构的构成，可参考图2.5，它是根据如下的具体输入例子所形成的结构示意。输入*/usr 1* mark 1*alex1hw.c3 * course 1hw.c5aa.txt.12 treeArray/usrparentmarkNextsiblingFirstChildFirstChildparent Hw.cNextsiblingFirstChildparent.parentFirstChildalexHw.caa.txtcourseparent 图2.5通过parse（）构建的数据结构示例2目录大小重新计算函数reSize（） 输入数据对目录大小的初始化值一般为1，而目录的真正大小应该是自身的大小和它包含的所有文件及子目录的大小之和。因此，在计算机目录大小的时候，需要遍历它下面所有的文件及子目录，可以采用递归嵌套的后序遍历方式。另外要注意，采用孩子兄弟双亲链表表示时，父目录下的所有子目录和子文件都在该父目录的左子（右子树第一个节点是该目录的兄弟节点），所以遍历的时候只需要遍历目录的左子树即可。 3.输出树形结构的函数outOut（） 输出是一个先序遍历的过程。为完成对树形的输出，兄弟目录之间需要相同的缩进，用|上下连接，而父子目录或父目录和子文件之间需要设定正确的缩进，子目录或子文件要比父目录向右缩进8个空格。设置一个标志数组flag11每个目录下最大的层次数为10，当前Tree * temp指针所指的节点如果没有兄弟节点，则置flag数组为1。否则置为0，并由此节点反复查询它的祖先节点的情况，直到根节点为止。输出时，遇到flag1时，屏幕输出“| ”，表明是兄弟节点；遇到flag0则输出“ ”，这样就可以保证兄弟节点之间有相同的缩进，而子节点总比父节点向右缩进8个空格。4消除输入中多余空格的函数skipWhiteSpace（string string s;int startPos0;ofstream outfile;ifstream infile;class Treestring Name;int Size;Tree*FirstChildTree*NextSibling;Tree*parent;publicTreestring Name,int Size0;void parse;void reSize;void outPut;TreeTree*treeArray100;int head0,rear0;TreeTreestring Name,int Sizethis-NameName;this-SizeSize;FirstChildNULL;NextSiblingNULL;parentNULL;TreeTree Tree*temp; Tree*temp1; tempFirstChild; whiletempNULL temp1temp; temptemp-NextSibling; delete temp1; void TreereSize Tree*tempthis; iftemp-FirstChild0 temptemp-FirstChild; whiletemp0 temp-reSize; Sizetemp-Size; temptemp-NextSibling; bool checkNamestring s ifs.length10 return false; ifs0*s0*s0s0s0s0 return false; forint i1;is.length;i ifsi*sisisisi return false; return true; void TreeoutPut Tree*temp; Tree*temp1; boll flag11; int i; outfile.openoutput.txt,iosapp; ifoutfile coutcannot append the output file.n; exit0; ifcheckNameName cout errorNameendl; exit0; outfile|_NameSizen; outfile.close; temp1FirstChild; whiletemplNULL outfile.openoutput.txt,iosapp; ifoutfile coutcannot append the output file.n; exit0; i0; temptemp1; whiletemp-parentNULL 4 ifi10 cout errordirectory contains more than 10 levels.endl; exit0; temptemp-parent; iftemp-NextSiblingNULL flagitrue; else flagifalse; whilei ifflagitrue outfile| ; else outfile ; outfile.close templ-outPut; templtempl-NextSibling; void skipWhiteSpacestring string getsubDirstring skipWhiteSpaceline,startPos; whileline*startPos resline* stratPOs; resline* stratPOs; skipWhileSpaceline,startPos; return res; int stringToNumstring s int num0; unsigned int i0; whileis,length num*10; numsi-0; return num; string getNamestring whiles*i s*it names*i; return name; int getSizestring whileunsigned int*is.length s*i s*it s*i sizes*i; return stringToNumsize; void Treeparse tree*temp; string line; string name; int size; whilegetlineinfile,line,n startPos0; while1 sgetSubDirline, int i1; skipWhiteSpaces, ifsi skipWhiteSpaces, namegetnames, skipWhiteSpaces, sizegetSizes, temptreeArrayhead100-FirstChildnew Treename,size; temp-parenttreeArrayhead100; ifname0* treeArrayrear100temp; skipWhiteSpaces, whilesi skipWhiteSpaces, namegetNames, skipWhiteSpaces, sizegetSizes, temp-NextSiblingnew Treename,size; skipWhileSpaces, temp-parenttreeArrayhead100; ifname0* treeArrayrear100temp; head; ifunsigned intstartPosline.length break; ifheadrear break; int main Tree*fileTree; string s; string name; int size; outfile.openoutput.txt; ifoutfile coutcannot open the output filen; exit0; outfilethe result is as followsn;outfile.close; infile.open.txt,iosout;if infilecoutcannot open the file.n;exit0;whilegetlineinfile,s,nnint i0;skipWhitSpaces,namegetNames,skipWhiteSpaces,sizegetSizes,fileTreenew Treename,size;ifname0*treeArrayrearfileTree;fileTree-parse;fileTree-reSize;fileTree-outPut;delete fileTree;infile.close;return 0;17