level 2
阳光的蛋壳
楼主
#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]
2014年12月08日 02点12分
1
#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]