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

(完整word)数据结构家谱管理系统(二叉链表)

《项目实训二》

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

2018.1
问题描述：
家谱用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料管理系统，实现对一个家族所有的资料进行收集整理。实现对家庭成员信息的建立、查找、插入、修改、增加、删除、更新、统计等等功能。

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

要求:
用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料管理系统,实现对一个家族所有的资料进行收集整理。支持对家谱的增加,删除，更新,统计等。

软件环境:
Microsoft Visual Studio 2010

流程设计:
开始
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