数据结构家谱综合管理系统二叉链表.doc

《项目实训二》

项目名称 __ 家谱管理系统__
　　　　 姓　　名　__ ___________
　 班　　级 __ _______________
　　　　 学　　号　__ ________________
　　　　 指导老师 __ __________ __

.1
问题描述：
家谱用于统计某家族历代家族组员情况和关系。现编制一个家谱资料管理系统，实现对一个家族全部资料进行搜集整理。实现对家庭组员信息建立、查找、插入、修改、增加、删除、更新、统计等等功效。

目标和要求：
目标：
1、 能依据具体问题具体情况，结合数据结构课程中基础理论和基础算法，分析并正确确定数据逻辑结构，合理地选择对应存放结构，并能设计出处理问题有效算法。
2、 提升程序设计和调试能力。经过上机学习,验证自己设计算法正确性。学会有效利用基础调试方法。
3、 初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基础方法和技能。
4、 培养依据选题需要选择学习书籍，查阅文件资料自学能力。

要求：
用于统计某家族历代家族组员情况和关系。现编制一个家谱资料管理系统，实现对一个家族全部资料进行搜集整理。支持对家谱增加，删除，更新，统计等。

软件环境：
Microsoft Visual Studio

步骤设计：
开始
Main函数
Menu函数
FamilyTree函数

Getroot函数

Case 1
Case 2
Case 3
Case 4
Case 5
Case 6
Case 7
Case 8
Case 9
Case10
defeault
结束
Creat函数
函数
递归调用
Menu函数
PreOrder函数
函数
InOrder函数
函数
PostOrder函数
函数
Generation函数
函数
NumberOfPeople函数
函数
LifeNum函数
函数
Message函数
函数
AddNewPeople函数数

DeletePeople函数

SetNewName函数

FindChild函数

SaveToFile函数

FileToFamilyTree函数

递归调用
递归调用
递归调用
PrintMessage函数
函数
SetNode函数
函数
函数
PreFindFather函数
函数
PreFindBrother函数
函数
PreFindFather函数
函数
PreFindBrother函数
函数
PrintMessage函数
函数

模块划分：
1、 统计模块
（1） 统计家族总人数、健在人数、几代人
（2） 关键函数：
int Generation(Node *root); //这个家族共有几代人
int NumberOfPeople( ); //家族总人数
int LifeNum( ); //健在人数
（3） 实现方法：静态组员变量
（4） 实现结果：

2、 更新模块
（1） 创建家谱、增加组员、删除组员、组员更名
（2） 关键函数：
Node* Creat( ); //结构函数调用
void AddNewPeople(Node *root,string FatherName,string NAme); //增加新家族组员
int DeletePeople(Node *root,string FatherName,string Deletepeople); //删除家族组员
int SetNewName(Node *root,string NAme,string NewName); //更改姓名
（3） 实现方法：创建家谱和组员更名关键经过递归调用；增加组员和删除组员关键经过栈非递归调用。
（4） 实现结果：

3、 查询模块
（1） 查询组员具体信息、查询组员孩子和孩子具体信息
（2） 关键函数：
int Message(Node *root,string Name); //显示该组员基础信息
int FindChild(Node *root,string NAme); //显示孩子信息
（3） 实现方法：经过递归调用，找到组员，输出对应信息
（4） 实现结果：

4、 显示模块
（1） 前序、中序、后序遍历家谱
（2） 关键函数：
void PreOrder(Node *root); //前序递归遍历输出家谱
void InOrder(Node *root); //中序递归遍历输出家谱
void PostOrder(Node *root); //后序递归遍历输出家谱
（3） 实现方法：递归遍历
（4） 实现结果：

5、 文件模块
（1） 保留到文件、从文件读取
（2） 关键函数：
void SaveToFile(Node *root); //保留到文件
void FileToFamilyTree( Node *root) ; //从文件中读取
（3） 实现方法：文件流
（4） 实现结果：

数据结构实现：
1、 生日结构体
struct BirthDay
{
int year;
int month;
int day;
friend istream& operator>>(istream &is,BirthDay &b);
friend ostream& operator<<(ostream &os,const BirthDay &b);
};

2、 信息结构体（家族组员基础信息）
struct Information
{
string name; //姓名
string birthPlace; //出生地
BirthDay birthDay; //生日
string sex; //性别
string education; //学历
string job; //工作
string father; //父亲
string spouse; //配偶
char life; //是否健在
};

3、 二叉树结点结构体
struct Node
{
Information data; //个人信息
Node* child; //第一个孩子
Node* brother; //弟兄
};

4、 家谱类（二叉树结构、左孩子，右弟兄）
class FamilyTree
{
private:
Node* root;
Node* Creat( ); //结构函数调用
void Release(Node *root); //析构函数调用
static int Numberofpeople; //计算总人数，NumberOfPeople（）调用
static int LifePeopele; //计算健在人数，LifeNum（）调用
public:
FamilyTree(); //结构函数，初始化一棵树，其前序序列由键盘输入
~FamilyTree(); //析构函数，释放链表中各结点存放空间
void SetNode(Node *root); //设置结点信息
Node* Getroot(); //获取根结点
void PreOrder(Node *root); //前序递归遍历输出家谱
void InOrder(Node *root); //中序递归遍历输出家谱
void PostOrder(Node *root); //后序递归遍历输出家谱
int Generation(Node *root); //这个家族共有几代人
int NumberOfPeople( ); //家族总人数
int LifeNum( ); //健在人数
void PrintMessage(Node *root ); //输出基础信息
int Message(Node *root,string Name); //显示该组员基础信息
Node* PreFindFather(Node *root,string FatherName); //给定元素值查找父亲结点指针位置并返回其指针，此方法采取先序遍历
Node* PreFindBrother(Node *root,string FatherName); //给定元素值查找弟兄结点指针位置并返回其指针，此方法采取先序遍历
void AddNewPeople(Node *root,string FatherName,string NAme); //增加新家族组员
int DeletePeople(Node *root,string FatherName,string Deletepeople); //删除家族组员
int SetNewName(Node *root,string NAme,string NewName); //更改姓名
int FindChild(Node *root,string NAme); //显示孩子信息
void SaveToFile(Node *root); //保留到文件
void FileToFamilyTree( Node *root) ; //从文件中读取
};

调试分析：
1、 问题：在创建家谱时，问询用户是否需要继续添加组员，只要用户不输入”#”就继续添加。
处理方案：增加if语句判定条件，只要输入不是”Y”,”y”,”#”，就请用户重新输入。
2、 问题：计算总人数和健在人数，因为存在增加和删除函数，数次调用计算函数。
处理方案：在家谱类中使用静态组员变量
3、 问题：在输入和输出组员信息中生日，生日使用是生日结构体变量，输入输出包含年、月、日。
处理方案：使用友元输入输出重载
4、 问题：在输入生日时，输入数字程序正常运行，输入其它字符，程序会出现死循环。
处理方案：cin.fail()判定输入是否正确，cin.clear()为了使输入错误能重新输入，将错误标识符改为0，cin.sync()清空流。
5、 问题：在输入部分信息是，问询用户是否确定部分信息时，请用户输入‘y、‘n’，不过用户有时会输入大写。
处理方案：使用toupper()函数，将用户输入确实定信息转换成大写字母。
6、 问题：在增加孩子时，只能添加长子，添加第二个孩子、第三个等等，会出现错误。
处理方案：添加一个寻求弟兄指针函数，假如要添加孩子组员，已经有了孩子，则经过调用弟兄指针函数来增加孩子。
7、 问题：保留到文件和读取文件时，会出现输入路径错误情况。
处理方案：经过调用_access()函数，判定输入路径是否正确。
8、 问题：读取文件时，cin>>重载会跳过空白字符，包含回车符。
处理问题：使用cin.get()函数接收回车。
9、 问题：删除组员时，删除能够成功，但会出现空指针错误。
处理方案：在delete该组员时，需要将指向该组员指针置空。
10、 问题：在主函数中，经过请用户输入数字，来选择对应操作，当用户误输入为选择以外字符时,会结束程序运行。
处理方案：和处理方案4相同。

试验结果及分析
1、 创建家谱

2、 保留到文件

3、 读取文件

4、 增加组员

5、 基础信息

6、 查询组员信息

7、 组员更名

8、 遍历家谱

9、 查询孩子信息

10、 删除组员

收获：
此次实训在我们为期两周时间里进行，经过自己不停学习、请教和老师指导，完成了相关家谱资料管理设计。前期关键是准备阶段，利用哪些技术，中期实践阶段，经过几天上机编写代码，然后完成，后期完善阶段，对部分难点和关键再细化，和做部分数据输入时异常处理。最终进行答辩阶段。经过这次实训相互帮助学习过程，自己看书学习经验，和从网上和其它多种路径取得信息和知识经验。理论和实际相结
合设计，锻炼了我综合利用所学基础知识，处理实际问题能力，同时也提升我查阅文件资料、对程序整体把握等其它能力水平。而且经过对整体掌控，对局部取舍，和对细节斟酌处理，全部使我能力得到了锻炼，我各方面经验全部得到了极大丰富。

附录 全部代码
Familytree.h
#ifndef FAMILYTREE_H
#define FAMILYTREE_H
#include <iostream>
#include <string>
#include <cctype>
#include <io.h>
#include <iomanip>
#include <fstream>
using namespace std;
struct BirthDay {
int year;
int month;
int day;
friend istream& operator>>(istream &is,BirthDay &b);
friend ostream& operator<<(ostream &os,const BirthDay &b);
};

struct Information
{
string name;
string birthPlace;
BirthDay birthDay;
string sex;
string education;
string job;
string father;
string spouse;
char life;
};
struct Node
{
Information data;
Node* child;
Node* brother;
};
class FamilyTree
{
private:
Node* root;
Node* Creat( );
void Release(Node *root);
static int Numberofpeople;
static int LifePeopele;
public:
FamilyTree();
~FamilyTree();
void SetNode(Node *root);
Node* Getroot();
void PreOrder(Node *root);
void InOrder(Node *root);
void PostOrder(Node *root);
int Generation(Node *root);
int NumberOfPeople( );
int LifeNum( );
void PrintMessage(Node *root );
int Message(Node *root,string Name);
Node* PreFindFather(Node *root,string FatherName);
Node* PreFindBrother(Node *root,string FatherName);
void AddNewPeople(Node *root,string FatherName,string NAme);
int DeletePeople(Node *root,string FatherName,string Deletepeople);
int SetNewName(Node *root,string NAme,string NewName);
int FindChild(Node *root,string NAme);
void SaveToFile(Node *root);
void FileToFamilyTree( Node *root) ;
};
#endif

Familytree.cpp

#include "Familytree.h"
int FamilyTree::Numberofpeople=0;
int FamilyTree::LifePeopele=0;

//生日结构体变量输入输出友元重载
istream& operator>>(istream &is,BirthDay &b)
{
is>>b.year>>b.month>>b.day;
return is;
}
ostream& operator<<(ostream &os,const BirthDay &b)
{
os<<b.year<<"-"<<b.month<<"-"<<b.day;
return os;
}

FamilyTree::FamilyTree() //结构函数，初始化一棵树，其前序序列由键盘输入
{
this->root=Creat();
}

FamilyTree::~FamilyTree() //析构函数，释放链表中各结点存放空间
{
Release(root);
}

Node* FamilyTree::Getroot() //获取根结点
{
return root;
}

Node* FamilyTree::Creat()//结构函数调用
{
Node *root;
string ch;
cout<<"请问是否创建（是：“y”,否:“#”）：";
cin>>ch; //输入名字
if(ch!="y")//异常处理
{
if(ch!="Y")
if(ch!="#")
{
int t=1;
do
{
cout<<"\n输入不明确，请重新输入！！"<<endl;
cout<<"请问是否创建（是：“y”,否:“#”）：";
cin>>ch;
if((ch=="y")||(ch=="Y")||(ch=="#"))
t=0;
}while(t==1);
}
}
if (ch=="#") root = NULL;
else
{
root=new Node; //申请结点内存空间
SetNode(root); //设置结点内容
root->child=Creat( ); //该结点孩子
root->brother=Creat( ); //该结点弟兄
}
return root; //返回结点
}

void FamilyTree::Release(Node *root) //析构函数调用
{
if(root!=NULL)
{
Release(root->child); //释放左孩子
Release(root->brother); //释放右弟兄
delete root;
}
}

void FamilyTree::SetNode(Node *root) //设置结点信息
{
Numberofpeople++;
cout<<"请输入家庭组员基础信息"<<endl;
cout<<"姓名：";
cin>>root->data.name;
cout<<"出生地：";
cin>>root->data.birthPlace;
cout<<"生日(数字、年月日以空格或回车间隔）：";
while(1)
{
cin>>root->data.birthDay;
if(cin.fail())
{
cout<<"输入有错！！请重新输入生日(数字）："<<endl;
cin.clear(); //输入错误则能重新输入
cin.sync(); //清空流
}
else
break;
}
//isdigit异常处理生日输入,若参数c为阿拉伯数字0~9，则返回非0值，不然返回NULL。
/*int i;
for(i=0;root->data.birthDay[i]!=0;++i)
{
if(isdigit(root->data.birthDay[i])==0)
{
cout<<"\n输入不明确，请重新输入！！"<<endl;
break;
}
}*/
cout<<"性别：";
cin>>root->data.sex;
cout<<"学历：";
cin>>root->data.education;
cout<<"工作：";
cin>>root->data.job;
cout<<"父亲：";
cin>>root->data.father;
cout<<"配偶（有多任配偶则以“，”或“、”间隔）："<<endl;
cin>>root->data.spouse;
cout<<"是否健在（y 是，n 否）：";
cin>>root->data.life;
if(toupper(root->data.life)!='Y') //异常处理
{
if(toupper(root->data.life)!='N'){
int t=1;
do
{
cout<<"\n输入不明确，请重新输入！！"<<endl;
cout<<"是否健在（y 是，n 否）：";
cin>>root->data.life;
if((toupper(root->data.life)=='Y')||(toupper(root->data.life)=='N'))
t=0;
}while(t==1);
}
}
if(toupper(root->data.life)=='Y')
LifePeopele++;
}

void FamilyTree::PreOrder(Node *root) //前序递归遍历输出家谱
{
if(root==NULL)
return;
else
{
cout<<root->data.name<<'\t';
PreOrder(root->child);
PreOrder(root->brother);
}
}

void FamilyTree::InOrder(Node *root) //中序递归遍历输出家谱
{
if(root==NULL)
return;
else
{
InOrder(root->child);
cout<<root->data.name<<'\t';
InOrder(root->brother);
}
}

void FamilyTree::PostOrder(Node *root) //后序递归遍历输出家谱
{
if(root==NULL)
return;
else
{
PostOrder(root->child);
PostOrder(root->brother);
cout<<root->data.name<<'\t';
}
}

int FamilyTree::Generation(Node *root) //这个家族共有几代人
{
int l; //l左孩子
if(root==NULL) //这个家族为空,返回0
return 0;
else
{
l=Generation(root->child); //左孩子
return l+1;
}
}

//int numberofpeople=0;
int FamilyTree::NumberOfPeople( ) //家族总人数
{
if(root==NULL) //家族人数为0
return 0;
/*else
{
if(root!=NULL)
numberofpeople++;
NumberOfPeople(root->child);
NumberOfPeople(root->brother);
}
return numberofpeople;*/
else
return Numberofpeople;
}

//int count=0;
int FamilyTree::LifeNum( ) //健在人数
{
if(root==NULL) //-1表示这个家族不存在
return -1;
/*else
{
if(toupper(root->data.life)=='Y')
count++;
LifeNum(root->child);
LifeNum(root->brother);
}
return count;*/
return LifePeopele;
}

void FamilyTree::PrintMessage(Node *root ) //输出基础信息
{
if(root==NULL)
return ;
else
{
cout<<"姓名："<<root->data.name;
cout<<"\t\t性别："<<root->data.sex;
cout<<"\t\t配偶："<<root->data.spouse<<endl;
cout<<"出生地："<<root->data.birthPlace;
cout<<"\t\t生日："<<root->data.birthDay;//;<<root->data.birthDay.year<<"-"<<root->data.birthDay.month<<"-"<<root->data.birthDay.day<<endl;
cout<<"\t\t父亲："<<root->data.father<<endl;
cout<<"学历："<<root->data.education;
cout<<"\t\t工作："<<root->data.job;
cout<<"\t\t是否健在：";
if(toupper(root->data.life)=='Y')
cout<<"是"<<endl;
else
cout<<"否"<<endl;
}
}

int message=0; //判定是否查找成功
int FamilyTree::Message(Node *root,string Name) //显示该组员基础信息
{
if(root==NULL)
return message;
else
{
if(root->data.name==Name)
{
message=1;
PrintMessage(root );
}
else
{
Message(root->child,Name);
Message(root->brother,Name);
}
}
return message;
}

Node* FamilyTree::PreFindFather(Node *root,string FatherName) //给定元素值查找父亲结点指针位置并返回其指针，此方法采取先序遍历
{
if(root==NULL)
throw"错误";
Node *p;
Node *tree[20];
int top=0;
while(root!=NULL||top!=0)
{
while(root!=NULL)
{
if(root->data.name==FatherName)
p=root;
top++;
tree[top]=root;
root=root->child;
}
if(top!=0)
{
root=tree[top]->brother;
top--;
}
}
return p;
}

Node* FamilyTree::PreFindBrother(Node *root,string FatherName) //给定元素值查找弟兄结点指针位置并返回其指针，此方法采取先序遍历
{
if(root==NULL)
throw"错误";
Node *p;
Node *tree[20];
int top=0;
while(root!=NULL||top!=0)
{
while(root!=NULL)
{
if(root->data.father==FatherName)
p=root;
top++;
tree[top]=root;
root=root->child;
}
if(top!=0)
{
root=tree[top]->brother;
top--;
}
}
return p;
}

void FamilyTree::AddNewPeople(Node *root,string FatherName,string NAme) //增加新家族组员
{
if(root==NULL)//假如这个家族为空，直接把该结点置为根结点
{
Creat( ) ;
}
else{
Node *p=new Node;
p->data.name=NAme;
p->child=NULL;
p->brother=NULL;
Node *Brother=PreFindBrother(root,FatherName); //弟兄结点
if(root->data.father==FatherName) //假如和祖先（根结点）同一个父亲，则置为根结点右弟兄
{
Node *q=root;
while(q->brother!=NULL) //寻求根结点右弟兄结点为空结点
{
q=q->brother;
}
if(q->brother==NULL)
{
q->brother=p;
SetNode(p);
}
}
Node *Father=PreFindFather(root,FatherName); //父亲结点
//Node *Brother=PreFindBrother(root,FatherName); //弟兄结点
if(Father->child==NULL) //假如父亲结点孩子结点为空
{
Father->child=p;
SetNode(p);
}
else //假如父亲结点孩子结点不为空
{
if(Brother->brother==NULL) //最终一个弟兄结点
{
Brother->brother=p;
SetNode(p);
}
}
}
}

int FamilyTree::DeletePeople(Node *root,string FatherName,string Deletepeople) //删除家族组员
{
int t=0;
Numberofpeople--;
if(root==NULL)
return t;
else
{

if(root->data.name==Deletepeople) //假如要删除为祖先，则调用Release()函数
{
t=1;
root->brother=NULL;
root->child=NULL;
Release(root);
}
else
{
Node *Father=PreFindFather(root,FatherName);
Node *Brother=PreFindBrother(root,FatherName); //弟兄结点
Node *p;
Node *tree[20];
int top=0;
while(root!=NULL||top!=0)
{
while(root!=NULL)
{
if(root->data.name==Deletepeople)
{
p=root;
//break;
}
top++;
tree[top]=root;
root=root->child;
}
if(top!=0)
{
root=tree[top]->brother;
top--;
}
}
if(toupper(p->data.life)=='Y') //健在人数减一
LifePeopele--;
if(Father->child->data.name==p->data.name)//Deletepeople)
Father->child=NULL;
else
Brother->brother=NULL;
//p->brother=NULL;
//p->child=NULL;
t=1;
delete p;
}
}
return t;
}

int flag=0; //标识
int FamilyTree::SetNewName(Node *root,string NAme,string NewName) //更改姓名
{
if(root==NULL)
return flag;
else
{
if(root->data.name==NAme)
{
flag=1;
root->data.name=NewName;
}
else
{
SetNewName(root->child,NAme,NewName);
SetNewName(root->brother,NAme,NewName);
}
}
return flag;
}

int FamilyTree::FindChild(Node *root,string NAme) //显示孩子信