数据结构课程设计报告
① 求一份数据结构课程设计报告
//class CNode.h
#ifndef __CNODE_H__
#define __CNODE_H__
#include <iostream>
using namespace std;
struct stData //出生年月结构
{
int m_nYear;
int m_nMonth;
int m_nDay;
};
struct stResult //五门课成绩结构
{
double m_dSubject_1; //自己改成绩的名称
double m_dSubject_2;
double m_dSubject_3;
double m_dSubject_4;
double m_dSubject_5;
};
struct stStudent //声明学生信息的结构
{
string m_strNumber; //学生学号
string m_strName; //姓名
char m_chSex; //性别
struct stData m_stData; //出生年月
string m_strAppearance; //政治面貌
struct stResult m_stResult; //五门课成绩
};
typedef class CNode
{
private:
struct stStudent m_stStudent;
CNode* m_Next;
public:
CNode(); //构造函数
~CNode(); //析构函数
void SetNodeData(); //设置结点内容的函数成员
stStudent GetNodeData(); //获取结点内容的函数成员
void SetNodeNext(CNode* _Next); //设置结点Next指针的函数成员
void ShowNodeData(); //输出结点内容的函数成员
CNode* GetNodeNext(); //获取结点Next指针的函数成员
}LinkNode;
#endif
//class CLinkList
#ifndef __CLINKLIST_H__
#define __CLINKLIST_H__
#include "CNode.h"
typedef class CLinkList
{
private:
LinkNode* m_Head; //链表的头指针
LinkNode m_Node; //链表的头结点
public:
CLinkList(); //构造函数
~CLinkList(); //析构函数
void CreateList(); //初始化链表的函数成员
LinkNode* GetListNode(int _nIndex); //按位置查找指定位结点的成员函数
void InsertList(int _nIndex); //插入结点的成员函数
void DeleteList(int _nIndex); //删除某一结点的成员函数
LinkNode* GetHeadList(); //获取头指针的成员函数
void SetListData(int _nIndex); //设置链表中某一结点的值的成员函数
void ShowListData(int _nIndex); //这个是现实链表中某一结点值的函数成员
void DestroyList(int _nIndex); //销毁某一位置以后链表的成员函数
void ShowList(); //显示链表的成员函数
}LinkList;
#endif
//class CLinkList
#include "CLinkList.h"
#include "CNode.h"
CLinkList::CLinkList()
{
cout << "这个是构造函数"<< endl;
m_Head = &m_Node; //链表的头指针指向头结点
m_Node.SetNodeNext(NULL); //将头结点的Next指针设置为NULL;
}
CLinkList::~CLinkList()
{
cout << "这个是析构函数" << endl;
}
void CLinkList::CreateList() //以向后追加的方式创建一个链表，输入0退出
{
int nTemp = 0; //定义一个临时变量用于标志程序结束
cout << "欢迎来创建链表 !" << endl;
CNode * pTemp = NULL; //定义一个临时结点指针，用来增加新结点用
CNode * pNode = m_Head; //定义一个标记指针，首先叫其指向头结点
while(1)
{
pTemp = new LinkNode;
cout << "请输入下一个结点的内容!" << endl;
pTemp->SetNodeData(); //设置链表中结点的内容
cout << "如果想继续输入下一个学生的信息请输入 1，否则输入 0" << endl;
cin >> nTemp;
if ('0' == nTemp)
{
break;
}
pNode->SetNodeNext(pTemp); //让链尾的Next指向新建的结点
pNode = pTemp; //将结尾元素向后移
}
cout << "创建链表结束" << endl;
}
LinkNode* CLinkList::GetListNode(int _nIndex)
{
cout << "这个是按位置查找指定位结点的成员函数" << endl;
LinkNode* pNode = m_Head->GetNodeNext(); //定义一个临时的结点指针,初始化指向头结点
int Temp = 0; //定义一个临时的变量，用来标记已检查结点的个数的
if(-1 == _nIndex) //返回头结点（即头指针）
{
return m_Head;
}
if(_nIndex < -1) //_nIndex控制条件
{
cout << "您输入的是错误的位置！" << endl;
return 0;
}
while(pNode != NULL)
{
if(_nIndex == Temp)
{
return pNode;
}
pNode = pNode->GetNodeNext(); //临时结点向后移动
++Temp;
}
return pNode; //没找到结点就返回NULL
}
void CLinkList::ShowListData(int _nIndex);
void CLinkList::InsertList(int _nIndex) //插入结点的函数成员
{
cout << "这个是插入结点的成员函数" << endl;
LinkNode* pNode = GetListNode(_nIndex - 1); //定义一个结点类的指针，指向的是要插入位置的前一指针
LinkNode* pTemp = new CNode; //定义一个临时结点指针，用来增加新结点用
pTemp->SetNodeData(); //设置插入结点的内容
pTemp->SetNodeNext(pNode->GetNodeNext());
pNode->SetNodeNext(pTemp);
}
void CLinkList::DeleteList(int _nIndex)
{
cout << "这个是删除某一结点的成员函数" << endl;
LinkNode* pNode = GetListNode(_nIndex - 1); //定义一个结点类的指针，指向的是要删除位置的前一指针
LinkNode* pTemp = NULL; //定义一个临时结点指针，用来指向要删除的结点
pTemp =pNode->GetNodeNext(); //把pTemp指向要删除的结点
pNode->SetNodeNext(pTemp->GetNodeNext()); //把pNode指向要删除的结点的后一个结点
delete pTemp; //删除结点
pTemp = NULL;
}
LinkNode* CLinkList::GetHeadList()
{
cout << "这个是获取头指针的成员函数" << endl;
return m_Head;
}
void CLinkList::SetListData(int _nIndex)
{
cout << "这个是设置链表中某一结点的值的成员函数" << endl;
CNode *pNode = GetListNode(_nIndex); //定义一个结点类的指针，指向的是要修改内容位置的结点
pNode->SetNodeData(); //修改内容
}
void CLinkList::ShowListData(int _nIndex)
{
cout << "这个是显示链表中某一结点值的成员函数" << endl;
CNode *pNode = GetListNode(_nIndex); //定义一个结点类的指针，指向的是要获取内容位置的结点
pNode->ShowNodeData(); //返回想要得到位置的结点内容
}
void CLinkList::DestroyList(int _nIndex)
{
cout << "这个是销毁某一位置以后链表的成员函数" << endl;
LinkNode* pTemp = GetListNode(_nIndex - 1); //定义一个结点指针，指向要销毁位置的前一结点
LinkNode* pNode = pTemp->GetNodeNext(); //定义一个结点指针，指向要销毁位置的结点
while(pTemp->GetNodeNext() != NULL) //销毁动作的结束条件或初始条件
{
pTemp->SetNodeNext(pNode->GetNodeNext()); //把需要销毁的位置的前结点的Next指向销毁位置的下一个结点
delete pNode; //销毁结点
pNode = pTemp->GetNodeNext(); //把pNode重新指向要销毁位置的结点
}
}
void CLinkList::ShowList()
{
cout << "这个是显示链表的成员函数" << endl;
int nTemp = 0; //定义一个临时的整形变量用来控制输入的个数
LinkNode* pTemp = m_Head->GetNodeNext(); //定义一个结点类指针，指向第0位的结点
if(NULL == pTemp)
{
cout << "这是个空链" << endl;
}
while(pTemp != NULL)
{
pTemp->ShowNodeData();
++nTemp;
if(0 == nTemp % 5 && nTemp != 0) //控制每行只能输出5个结点的内容
{
cout << endl;
}
pTemp = pTemp->GetNodeNext();
}
}
//class CNode
#include "CNode.h"
CNode::CNode() //构造函数
{
//m_stStudent = {0};
m_Next = NULL;
}
CNode::~CNode() //析构函数
{
}
void CNode::SetNodeData()
{
char* pNumber = new char[30]; //用来接收字符串的临时变量
char* pName = new char[30];
char* pAppearance = new char[30];
cout << "学生学号: " << endl;
cin >> pNumber;
m_stStudent.m_strNumber = pNumber;
cout << "姓名: " << endl;
cin >> pName;
m_stStudent.m_strName = pName;
cout << "性别: " << endl;
cin >> m_stStudent.m_chSex;
cout << "出生年月: " << endl;
cout << "m_stData.m_nYear" << endl;
cin >> m_stStudent.m_stData.m_nYear;
cout << "m_stData.m_nMonth" << endl;
cin >> m_stStudent.m_stData.m_nMonth;
cout << "m_stData.m_nDay" << endl;
cin >> m_stStudent.m_stData.m_nDay;
cout << "政治面貌: " << endl;
cin >> pAppearance;
m_stStudent.m_strAppearance = pAppearance;
cout << "五门课成绩: " << endl;
cout << "m_dSubject_1: " << endl;
cin >> m_stStudent.m_stResult.m_dSubject_1;
cout << "m_dSubject_2: " << endl;
cin >> m_stStudent.m_stResult.m_dSubject_2;
cout << "m_dSubject_3: " << endl;
cin >> m_stStudent.m_stResult.m_dSubject_3;
cout << "m_dSubject_4: " << endl;
cin >> m_stStudent.m_stResult.m_dSubject_4;
cout << "m_dSubject_5: " << endl;
cin >> m_stStudent.m_stResult.m_dSubject_5;
delete []pNumber; //释放内存
pNumber = NULL; //指针置空
delete []pName; //释放内存
pName = NULL;
delete []pAppearance; //释放内存
pAppearance = NULL;
}
stStudent CNode::GetNodeData() //返回结点内容（即学生信息）
{
return m_stStudent;
}
void CNode::SetNodeNext(CNode* _Next)
{
m_Next = _Next;
}
void CNode::ShowNodeData()
{
const char* pNumber = m_stStudent.m_strNumber.c_str(); //用来接收字符串的临时变量
const char* pName = m_stStudent.m_strNumber.c_str();
const char* pAppearance = m_stStudent.m_strAppearance.c_str();
cout << "学生学号: " << pNumber << '\t' << "姓名: " << pName << '\t' << "性别: " << m_stStudent.m_chSex;
cout << "出生年月: " << m_stStudent.m_stData.m_nYear << ',' << m_stStudent.m_stData.m_nMonth << ',' << m_stStudent.m_stData.m_nDay;
cout << "政治面貌: " << pAppearance << "五门课成绩: " << endl;
cout << "m_dSubject_1: "<< m_stStudent.m_stResult.m_dSubject_1<< endl;
cout << "m_dSubject_2: "<< m_stStudent.m_stResult.m_dSubject_2<< endl;
cout << "m_dSubject_3: "<< m_stStudent.m_stResult.m_dSubject_3<< endl;
cout << "m_dSubject_4: "<< m_stStudent.m_stResult.m_dSubject_4<< endl;
cout << "m_dSubject_5: "<< m_stStudent.m_stResult.m_dSubject_5<< endl;
}
CNode* CNode::GetNodeNext()
{
return m_Next;
}
#include "CLinkList.h"
#include "CNode.h"
void Text(); //测试函数声明
int main()
{
cout << "这是mian函数" << endl;
Text();
return 0;
}
void Text()
{
cout << "这个是测试函数" << endl;
LinkList* pList = new LinkList; //创建一个内存链表对象
cout << "------------------CreateList-----------------------------" << endl;
pList->CreateList(); //初始化链表的函数成员
pList->ShowList();
cout << endl;
cout << "------------------GetListNode-----------------------------" << endl;
LinkNode* pNode = NULL; //定义一个临时的结点类指针用于检测查找函数成员
pNode = pList->GetListNode(3); //按位置查找指定位结点的成员函数的测试
if(pNode)
{
cout << "用按位置查找的方法找到了指定位结点" << endl;
}
else
{
cout << "对不起，用按位置查找的方没有找到指定位结点" << endl;
}
cout << endl;
cout << "------------------InsertList-----------------------------" << endl;
pList->InsertList(0); //插入结点的成员函数的测试
pList->ShowList();
cout << endl;
cout << "------------------DeleteList-----------------------------" << endl;
pList->DeleteList(0); //删除某一结点的成员函数的测试
pList->ShowList();
cout << endl;
cout << "------------------GetHeadList-----------------------------" << endl;
pNode = NULL;
pNode = pList->GetHeadList(); //获取头指针的成员函数的测试
if(pNode)
{
cout << "已经返回了头指针" << endl;
}
else
{
cout << "对不起，头指针为空" << endl;
}
cout << endl;
cout << "------------------GetHeadList-----------------------------" << endl;
pList->SetListData(3); //设置链表中某一结点的值的成员函数的测试
pList->ShowList();
cout << endl;
cout << "------------------GetListData-----------------------------" << endl;
cout << "pList->ShowListData(3) =";
pList->ShowListData(3); //获取链中某一结点值的成员函数的测试
cout << endl;
cout << "------------------DestroyList(3)-----------------------------" << endl;
pList->DestroyList(3); //销毁第3位置以后链表的成员函数的测试
pList->ShowList();
cout << endl;
cout << "------------------DestroyList(0)-----------------------------" << endl;
pList->DestroyList(0); //销毁第0位置以后链表的成员函数的测试
pList->ShowList();
cout << endl;
delete pList; //释放内存
pList = NULL; //指针置空
}
你的要求太多 ， 没仔细看， 我把我给别人写的赋值给你吧 ， 我已经写的很全了，程序有问题可以给我留言
② 求一份数据结构课设报告（C语言）：个人课程表 设计要求：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;
}