Question

数据结构课程设计报告 树的遍历:文件目录结构的显示

发我邮箱 993959784@qq.com

Answer 1

数据结构课程设计报告

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

专业 计算机科学与技术（软件工程）
学生姓名 施利华
班级 M计算机101
学号 0751401208
指导教师 吴 素 芹
起止日期 2012.1.7-2012.1.14

目 录
1 简介 1
2算法说明 2
3测试结果 3
4分析与探讨 6
5小结 8
参考文献 9
附录 10
附录1 源程序清单 10

树的遍历：文件目录结构的显示
1 简介
1． 树形结构
树形结构是一类十分重要的非线性结构，它可以很好地描述客观世界中广泛存在的具有分支关系或层次特性的对象，如操作系统的文件构成、人工智能搜索算法的模型表示以及数据库系统的信息组织形式等。

2．输入要求：
输入数据包含几个测试案例。每一个案例由几行组成，每一行都代表了目录树的层次结构。第一行代表了目录的根节点。若是目录节点，那么它的孩子节点将在第二行中被列出，同时用一对圆括号“（）”界定。同样，如果这些孩子节点中某一个也是目录的话，那么这个目录所包含的内容将在随后的一行中列出，由一对圆括号将首尾界定。目录的输入格式为：*name size,文件的输入格式为：name size，其中*代表当前节点是目录，表示文件或目录的名称，由一串长度不大于10的字符组成，并且name字符串中不能含有‘（’，‘），’[‘，’]‘和’*‘。size是该文件/目录的大小，为一个大于0的整数。每一个案例中最多只能包含10层，每一层最多有10个文件/目录。
3．输出要求：
对每一个测试案例，输出时要求：第d层的文件/目录名前需要插入8*d个空格，兄弟节点之间要在同一列上。不要使用Tab（制表符）来统一输出的缩进。每一个目录的大小（size）是它所包含的所有子目录和文件大小以及它自身大小的总和。
4．输入例子：
*/usr1
(*mark1*alex1)
(hw.c3*course1)(hw.c5)
(aa.txt12)
*/usr1
()
表示有两个不同的根目录，目录名都是/usr，第一个根目录/usr下包含mark和alex两个子目录，mark目录下包含大小为3的文件hw.c和子目录course，alex目录下有一个大小为5的文件hw.c，子目录course下包含文件aa.txt，其大小为12；第二个根目录/usr下为空。
5．输出例子：
|_*/usr[24]
|_*mark[17]
| |_hw.s[3]
| |_*course[13]
| |_aa.txt[12]
|_*alex[6]
|_hw.c[5]
|_*/usr[1]
2算法说明
typedef struct TreeNode{
int data;
TreeNode *left;
TreeNode *right;
}TreeNode,*Tree;
先序：
void first(Tree *root)
{
printf("%d ",root->data);
first(root->left);
first(root->right);
}
中序：
void mid(Tree *root)
{
mid(root->left);
printf("%d ",root->data);
mid(root->right);
}
后序：
void last(Tree *root)
{
last(root->left);
last(root->right);
printf("%d ",root->data);
}
3测试结果
将代码打入Microsoft Visual C++ 6.0软件中，改完相关错误后运行代码，开始不能出现正确的运行结果，在相关文件中新建文本文件，文件命名为”input.txt“。在文本文件中，打入输入数据，得出下列截图。

图3-1 输入数据
得出”input.txt”记事后，重新运行代码，在相关文件夹的“output.txt”会出现相关的正确的输出结果，此时得出下列两张截图。

图3-2 输出结果

图3-3 输出结果
输入正确的代码后运行程序，得出下列截图。

图3-4 运行结果

4分析与探讨
目录结构是一种典型的树形结构，为了方便对目录的查找，遍历等操作，可以选择孩子兄弟双亲链表来存储数的结构。程序中要求对目录的大小进行重新计算，根据用户的输入来建立相应的孩子兄弟双亲链表，最后输入树形结构。可以引入一个Tree类，将树的构造，销毁，目录大小的重新计算（reSize），建立树形链表结构（parse），树形结构输出（outPut）等一系列操作都封装起来，同时对于每一个树的借点，它的私有变量除了名称（Name），大小（Size）和层数（Depth）之外，根据孩子兄弟双亲链表表示的需要，还要设置三个指针，即父指针（Tree*parent）,下一个兄弟指针（Tree*NextSibling）和第一个孩子指针（Tree*Firstchild）。下面是几个主要函数的实现。
1.建立树形链表结构的函数parse()
根据输入来确定树形关系是，首先读取根借点目录/文件名和大小值，并根据这些信息建立一个新的节点；然后读入后面的各行信息，对于同一括号中的内容，即具有相同父节点的那些节点建立兄弟关联。这个函数实际上是采用层数遍历建立树形链表结构。
定义一个Tree*类型的数组treeArray[ ]，用来存放目录的节点信息，并定义两个整型变量head和rear，head值用来标记当前节点的父节点位置，每处理完一对括号，head需要增加1,即下一对待处理括号的父节点在treeArray[ ]中要往后移一个位置。如果当前处理的节点是目录类型，则将它放在treeArray[ ]数组中，rear是treeArray[ ]的下标变量，加入一个树的节点，并和head所指的父节点建立关联，但是不用放入treeArray[ ]中。
2.目录大小重新计算函数reSize()
输入数据中对目录大小的初始化值一般为1，而目录的真正大小应该是自身的大小和它包含的所有文件及子目录的大小之和。因此，在计算目录大小的时候，需要遍历它下面所有的文件和子目录，可以采用递归嵌套的后序遍历方式。另外要注意，采用孩子兄弟双亲链表表示时，父目录下的所有子目录和子文件都在该父目录的左子树上（右字数第一个节点是该目录的兄弟节点），所以遍历的时候只需要遍历目录的左字数即可。
3.输出树形结构的函数outPut()
输出是一个线序遍历的过程。为完成对树形的输出，兄弟目录之前需要相同的缩进，用’|’上下相连，而斧子目录或父目录和子文件之间需要设定正确的缩进，子目录或子文件要比父目录向右缩进8个空格。设置一个标志数组flag[11]（每个目录下最大层次数为10），当前Tree*temp指针所指的节点如果有兄弟节点，则置flag数组值为1，否则置为0；并由此节点反复查询它的祖先节点的情况，知道根节点位置。输出时，遇到flag[ ]=1时，屏幕输出“| ”，表明是兄弟节点；遇到flag[ ]=0时则输出“ ”，这样就可以保证兄弟节点之间有相同的缩进，而子节点总比父节点享有缩进8个空格。

treeArray[]

4.消除输入总多余空格的函数skipwhiteSpace（string&s,int*i）
从用户输入数据中读入一行后，调用该函数来跳过s字符串中s[i]之后的空格，以方便后面的处理。
此外，关于读入目录名称，大小，以及将string类型的Size值转换成int类型的函数的实现，相对比较简单，此外不再赘述。

图4-1 数据异常测试案例

5小结

参考文献
[1] 刘振安,刘燕君.C程序设计课程设计[M].[北京]机械工业出版社,2004年9月
[2] 谭浩强.C程序设计（第三版）.清华大学出版社,2005年7月
[3] 严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社,1997年4月
[4]吴文虎.程序设计基础.清华大学出版社,2003年
[5]王立柱.C/C++与数据结构.清华大学出版社,2002年
[6]顾元刚.数据结构简明教程.东南大学出版社,2003年
[7]郭福顺,王晓芬,李莲治.数据结构（修订本）.大连理工大学出版社,1997年
[8]严蔚敏,陈文博.数据结构及应用算法教程.清华大学出版社,2004年

附录
附录1 源程序清单
#include <string>
#include <iostream>
#include <fstream>
using namespace std;

string s = "";
int startPos = 0;
ofstream outfile;
ifstream infile;

/**构造Tree类**/
class Tree{
string Name; /* 树的根结点名称 */
int Size; /* 树的大小，用于统计这棵树本身及其包含的所以子树大小的总和*/
Tree* FirstChild; /* 指向它的第一个孩子结点 */
Tree* NextSibling; /* 指向它的下一个兄弟结点 */
Tree* parent; /* 指向双亲结点 */

public:
Tree(string Name = "", int Size = 0);/* 构造函数 */
void parse(); /* 根据输入数据来建立树形结构 */
void reSize(); /* 重新统计树结点的大小 */
void outPut(); /* 输出树形结构 */
~Tree(); /* 析构函数 */
};

/*** 树结点数组treeArray[],以及用来标注双亲结点位置的head和目录结点的rear***/
Tree* treeArray[100];
int head = 0, rear = 0;

/*** 建立只有一个结点的树，其三个指针域均为空 ***/
Tree::Tree(string Name, int Size){
this->Name = Name;
this->Size = Size;
FirstChild = NULL;
NextSibling = NULL;
parent = NULL;
}

/*** 析构函数，删除同一根结点下的各个子结点，释放空间 ***/
Tree::~Tree()
{
Tree* temp;
Tree* temp1;
temp = FirstChild;
while(temp != NULL)
{
temp1 = temp;
temp = temp->NextSibling;
delete temp1;
}
}

/* 先序遍历根结点下的所有结点，将每一个结点的Size值都加到根结点的Size中去**/
void Tree::reSize()
{
Tree* temp = this;

/*** 如果当前的结点没有孩子结点，则它的Size值不变，即为输入时候的值 ***/
if(temp->FirstChild != 0){
temp = temp->FirstChild;
while(temp != 0){
temp->reSize();
Size += temp->Size;
temp = temp->NextSibling;
}
}
}

/***检查Name中有无非法字符**************/
bool checkName(string s)
{
if(s[0]!='*' && s.length() > 10)
return false;
if(s[0]=='*' && s.length() > 11)
return false;
if(s[0]!='*' && (s[0]=='(' || s[0]==')' || s[0]=='[' || s[0]==']'))
return false;
for(int i=1;i<s.length();i++){
if(s[i]=='*' || s[i]=='(' || s[i]==')' || s[i]=='[' || s[i]==']')
return false;
}
return true;
}

/*** 按照先序遍历的方式有缩进地来输出树形结构 ***/
void Tree::outPut()
{
Tree* temp; /*用来指向当前结点的祖先结点*/
Tree* temp1;
bool flag[11];/*用来标志输出缩进、层次情况的数组*/
int i;

outfile.open("output.txt",ios::app);
if(!outfile){
cout<<"cannot append the output file.\n";
exit(0);
}
if(!checkName(Name)){
cout<<"input error!--"<<Name<<endl;
exit(0);
}
outfile<<"|_"<<Name<<"["<<Size<<"]\n";
outfile.close();

/* 输出当前的结点信息 */
temp1= FirstChild;/* 用来指向当前结点的子结点 */

while(temp1 != NULL)
{
outfile.open("output.txt",ios::app);
if(!outfile){
cout<<"cannot append the output file.\n";
exit(0);
}

i = 0;
temp = temp1;
while(temp->parent != NULL)
{
/*当前temp指针所指的结点如果有兄弟结点，则置flag数组值为1，否则置为0；并由此结点反复查询它的祖先结点的情况，直到根结点为止*/
if(i>=10){
//检查当前的父目录包含的子文件(或目录数)是否大于10；
cout<<"input error!--dictionary contains more than 10 levels."<<endl;
exit(0);
}
temp = temp->parent;
if(temp->NextSibling != NULL)
flag[i++] = true;
else
flag[i++] = false;
}
/*兄弟结点之间有相同的缩进，子结点比父结点向右缩进8个空格*/
while(i--)
{
if(flag[i] == true)
outfile<<"| ";
else
outfile<<" ";
}
outfile.close();
temp1->outPut();
temp1 = temp1->NextSibling;
}
}

/*** 跳过字符串s中，第(*i)个之后多余的空格 ***/
void skipWhiteSpace(string& s, int* i)
{
while(s[*i] == '\t' || s[*i] == ' ')
(*i)++;
}

/*** 获取输入行中一对'()'之间的字符串，即为同一双亲结点下的子结点 ***/
string getSubDir(string& line, int* startPos)
{
string res = "";
skipWhiteSpace(line,startPos);
while(line[*startPos] != ')')
res += line[(*startPos)++];
res += line[(*startPos)++];
skipWhiteSpace(line, startPos);
return res;
}

/*** 由于用户输入时候目录的大小Size值为String类型，因此需要将它转变成integer类型***/
int stringToNum(string s)
{
int num = 0;
unsigned int i = 0;
while(i < s.length())
{
num *= 10;
num += s[i++] - '0';
}

return num;
}

/*** 提取目录/文件的名称 ***/
string getName(string& s, int* i)
{
string name = "";
while(s[*i] != ' ' && s[*i] != '\t')
name += s[(*i)++];
return name;
}

/*** 提取目录/文件的大小，然后将string类型转换成integer类型 ***/
int getSize(string&s, int* i)
{
string size = "";
while((unsigned int)(*i) < s.length() && s[*i] != ' ' && s[*i] != '\t' && s [*i] != ')')
size += s[(*i)++];
return stringToNum(size);
}

/*** 根据用户的输入字符串来构建树的结构 ***/
void Tree::parse()
{
Tree* temp;
string line;
string name;
int size;

/***head值用来标记当前结点的双亲结点位置；如果当前处理的结点是目录类型，则将它放在treeArray[]数组中，下标用rear来记录；如果是文件类型的目录，只需要按照name和size建立一个树的结点，但是不用放入treeArray[]中 ***/
while(getline(infile,line,'\n'))
{
startPos = 0;
while(1)
{
s = getSubDir(line, &startPos);
int i = 1;
skipWhiteSpace(s, &i);
if(s[i] != ')')
{
skipWhiteSpace(s,&i);
name = getName(s,&i);
skipWhiteSpace(s,&i);
size = getSize(s,&i);
temp = treeArray[head%100]->FirstChild = new Tree(name,size);
temp->parent = treeArray[head%100];
if(name[0] == '*')
treeArray[(rear++)%100] = temp;
skipWhiteSpace(s,&i);
}
while(s[i] != ')')
{
skipWhiteSpace(s,&i);
name = getName(s,&i);
skipWhiteSpace(s,&i);
size = getSize(s,&i);
temp->NextSibling = new Tree(name,size);
skipWhiteSpace(s,&i);
temp = temp->NextSibling;
temp->parent = treeArray[head%100];
if(name[0] == '*')
treeArray[(rear++)%100] = temp;
}
head ++;
/***测试是否一行扫描完毕***/
if((unsigned int)startPos >= line.length())
break;
}
/***只有一个根结点的情况***/
if(head == rear)
break;
}
}

///////////////////////////////////////////////////////////
//**** 主测试文件main.cpp******/////
//////////////////////////////////////////////////////////
int main()
{
Tree* fileTree;
string s;
string name;
int size;

outfile.open("output.txt");
if(!outfile){
cout<<"cannot open the output file!\n";
exit(0);
}

outfile<<"The result is as follows:\n";
outfile.close();

infile.open("input.txt",ios::out);
if(!infile){
cout<<"cannot open the input file!\n";
exit(0);
}

while(getline(infile,s,'\n'))
{
int i = 0;
skipWhiteSpace(s, &i);
name = getName(s,&i);
skipWhiteSpace(s,&i);
size = getSize(s,&i);
fileTree = new Tree(name, size);
if(name[0] == '*')
{
treeArray[rear++] = fileTree;
fileTree->parse();
}
fileTree->reSize();
fileTree->outPut();
delete fileTree;
}
infile.close();
return 0;
}