专业课程设计树的遍历.doc

.......

数据构造课程设计

树遍历

专业
计算机科学与技术
班级
xxxxx
学号
xxxxxx
学生姓名
xxxxxxxxx

目 录
1 设计题目 1
2 设计分析 2
3 设计实现 4
4.2 测试输入 13
4.3 对的输出 14
4.4 实际输出 16
5 分析与探讨 17
5.1 测试成果分析 17
5.2 探讨与改进 17
6 设计小结 17

1 设计题目
给出Unix下目录和文献信息，规定编程实现将其排列成一定缩进树。详细规定如下。
输入规定：
输入数据包括几种测试方案。每一种案例由几行构成，每一行都代表了目录树层次构造。第一行代表目录根节点。若是目录节点，那么它孩子节点将在第二行中被列出，同步用一对圆括号“()”界定。同样，如果这些孩子节点钟某一种也是目录话，那么这个目录所包括内容将在随后一行中列出，有一对圆括号将首位界定。目录输入格式为：*name size,文献输入格式为：name size，其中*代表当前节点目录，name代表文献或目录名称，由一串长度不不不大于10字符构成，并且name字符串中不能包具有‘(’,‘)’,‘[’,‘]’,‘*’。size是该文献/目录大小，为不不大于0整数。每一种案例中最多只能包括10层，每一层最多有10个文献/目录。
输出规定：
对每一种测试案例，输出时规定：第d层文献/目录名前面需要插入8*d个空格，兄弟节点之间要在同一列上。不要使用Tab(制表符)来统一输出缩进。每一种目录大小(size)是它包括所有子目录和文献大小以及它自身大小总和。
输入例子：
*/usr1
(*mark 1 *alex 1)
(hw.c3 *course 1)(hw.c 5)
(aa.txt 12)
*/usr 1
()
表达具有两个不同根目录，目录名都是/usr,第一种根目录/usr下包括mark和alex两个子目录，mark目录下包括大小为3文献hw.c和子目录course,alex目录下有一种大小为5文献hw.c，子目录course下包括文献aa.txt，其大小为12；第二个根目录/usr下为空。
输出例子：
|_*usr[24]
|_*mark[17]
| |_hw.c[3]
| |_*course[13]
| |_aa.txt[12]
|_*alex[6]
|_hw.c[5]
|_*/usr[1]

2 设计分析
目录构造是一种典型树形构造，为了以便对目录查找、遍历等操作，可以选取孩子兄弟双亲链表来存储树构造。程序中规定对目录大小进行重新计算，依照顾客输入来建立相应孩子兄弟双亲链表，最后输出树形构造。可以引用一种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[]下标变量，加入一种目录节点信息，rear就增长1；如果是文献类型目录，则需要按照Name和Size建立一种树节点，并和head所指父节点建立关联，但是不用放入treeArray[]中。
为进一步阐明这个树形链表构造构成，可参照图3-1。

treeArray[]

FirstChild

/usr

mark

alex

hw.c

course

hw.c

aa.txt

parent

NextSibling

parent

FirstChild

parent

parent

FirstChild
parent

NextSibling

图3-1通过parse()构建数据构造事例

它是依照如下详细输入例子所形成构造示意。
输入：
*/usr1
(*mark 1 *alex 1)
(hw.c3 *course 1)(hw.c 5)
(aa.txt 12)
形成数据构造如图2.5所示。
2.目录大小重新计算函数reSize()
输入数据中对目录大小初始值普通为1，而目录真正大小应当是自身大小和它包括所有文献及子目录大小之和。因而，在计算目录大小时候，需要遍历它下面所有文献和子目录，可以采用递归嵌套后序遍历方式。此外要注意，采用孩子兄弟双亲链表表达时，父目录下所有子目录和子文献都在该父目录左子树上（右子树第一种节点是该目录兄弟节点），因此白努力时候只需要遍历目录对左子树即可。
3.输出树形构造函数outPut()
输出是一种先序遍历过程。为完毕对树形输出，兄弟目录之间需要相似缩进，用‘|’上下相连，而父子目录或父目录和子文献之间需要设定对的缩进，子目录或子文献要比父目录向右缩进8个空格。设立一种标志数组flag[11](每个目录下最大层次数为10)，当前Tree*temp指针所指节点如果有兄弟节点，则置flag数组值为1，否则置为0；并由此节点重复查询它祖先节点状况，直到根节点为止。输出时，遇到flag[]=1时，屏幕输出“| ”，表白是兄弟节点；遇到flag[]=0则输出“ ”， 有相似缩进，而子节点总比父节点向右缩进8个空格。
4.消除输入中多余空格函数skipWhiteSpace(string &s,int *i)
从顾客输入数据中读入一行后，调用该函数来跳过s字符串中s[i]之后空格，以以便背面解决。
此外，关于读入目录名称、大小，以及将string类型Size值转换成int类型函数实现，相对比较简朴，此处不再赘述。
3 设计实现
运用visual c++，新建一种c++文献，将如下代码输入。
#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;
}

4测试办法
4.1测试目
为了测试程序对的性，需要分别测试它在正常状况和异常状况下体现状况。
正常状况下输入数据规定是：目录初始大小普通设为1，目录名中不能包括‘(’,‘)’,‘[’,‘]’和‘*’这些字符，加入多余空格不影响最后输出成果；同一父目录下兄弟节点用一对圆括号括起来；同一层上不同父节点下子节点均列在同一行中，但按照父节点不同永圆括号加以界定。
4.2 测试输入
*/usr 1
(*mark 1 *alex 1)
(hw.c 3 *course 1) (hw.c 5)
(aa.txt 12)
*/usr 1
()
*/usr000009 1
(*mark 1 *alex 1 *bill 1)
(*book 1 *course 1 junk.c 6) (junk.c 8) (*work 1 *course 1)
(ch1.r 3 ch2.r 2 ch3.r 4) (*cop3530 1) () (*cop3212 1)
(*fall96 1 *spr97 1 *sum97 1) (*fall96 1 *fall97 1)
(syl.r 1) (syl.r 5) (syl.r 2) (grades 3 prog1.r 4 prog2.r 1) (prog2.r 2 prog1.r 7 grades 9)
4.3 对的输出
The result is as follows:
|_*/usr[24]
|_*mark[17]
| |_hw.c[3]
| |_*course[13]
| |_aa.txt[12]
|_*alex[6]
|_hw.c[5]
|_*/usr[1]
|_*/usr000009[72]
|_*mark[30]
| |_*book[10]
| | |_ch1.r[3]
| | |_ch2.r[2]
| | |_ch3.r[4]
| |_*course[13]
| | |_*cop3530[12]
| | |_*fall96[2]
| | | |_syl.r[1]
| | |_*spr97[6]
| | | |_syl.r[5]
| | |_*sum97[3]
| | |_syl.r[2]
| |_junk.c[6]
|_*alex[9]
| |_junk.c[8]
|_*bill[32]
|_*work[1]
|_*course[30]
|_*cop3212[29]
|_*fall96[9]
| |_grades[3]
| |_prog1.r[4]
| |_prog2.r[1]
|_*fall97[19]
|_prog2.r[2]
|_prog1.r[7]
|_grades[9]
保存此文献，命名为“Tree”，在此文献夹中新建一种名为“input”文本文献，在此文献中键入“测试输入”代码，通过运营可以在“Tree”文献夹中找到一种名为“output”文本文献，详细成果如下图3-2所示。

图3-2

在output文献中即可显示程序输出成果。

4.4 实际输出
见图3-3

图3-3
5 分析与探讨
5.1 测试成果分析
输入数据
盼望输出成果
*/user001
（）
input error!-*user0
*a 1
(aa.txt 1 *b 1)
(*c 1)
(*d 1)
(*e 1)
(*f 1)
(*g 1)
(*h 1)
(*i 1)
(*j 1)
(*k 1)
(a.txt 10)
intput error!-directory contains more than 10 levels
*/user 1
(*mark 1 *alex 1)
([hw.c]3 *course 1)(hw.c 5)
(aa.txt 12)
input error!-[hw.c]
下表1-1为三组异常测试数据。
表1-1
5.2 探讨与改进
在输入测试构造分析中输入数据时，浮现了输出错误提示，由于目录和文献中不能浮现‘(’,‘)’,‘[’,‘]’,‘*’等符号，只需要将这些符号改掉，改为容许输入符号即可，因而，在得到对的输出成果中，对的输入是它前提。
6 设计小结
通过本次课程设计实验，我较好锻炼了理论联系实际，与详细项目、课题相结合程序设计能力。既让我懂得了如何把理论运用于实际，又让我懂得了在实践中遇到问题怎么样用理论去解决。我深刻体会到，学好《数据构造》这门课仅仅通过课堂教学或平时自学获取理论知识是远远不够，还必要加以恰当实践，亲自上机进行编辑，检查，调试，运营各种算法。课程设计能提高学生对所学知识综合运用能力，全面检查并掌握所学内容。为了充分运用时间，准时完毕课程设计任务，查阅资料和编写代码是运用剩余时间进行。在上机调试过程中，我也对数据构造这一门课所学知识有了更进一步掌握和理解，巩固了理论教学所学到知识，扩展了我编程思想。