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

项目实训二 项目名称 _ 家谱管理系统_ 姓名_ _ 班级 _ _学号_ _指导教师 _ _ _ 2018.1问题描述：家谱用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料管理系统，实现对一个家族所有的资料进行收集整理。实现对家庭成员信息的建立、查找、插入、修改、增加、删除、更新、统计等等功能。目的和要求：目的：1、 能根据具体问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2、 提高程序设计和调试能力。通过上机学习,验证自己设计的算法的正确性。学会有效利用基本调试方法。3、 初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。4、 培养根据选题需要选择学习书籍，查阅文献资料的自学能力。要求： 用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料管理系统，实现对一个家族所有的资料进行收集整理。支持对家谱的增加，删除，更新，统计等。软件环境：Microsoft Visual Studio 2010流程设计：开始Main函数Menu函数FamilyTree函数Getroot函数Case 1Case 2Case 3Case 4Case 5Case 6Case 7Case 8Case 9Case10defeault结束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 Informationstring name; /姓名string birthPlace; /出生地BirthDay birthDay; /生日string sex; /性别string education; /学历string job; /工作string father; /父亲string spouse; /配偶char life; /是否健在;3、 二叉树结点结构体struct NodeInformation data; /个人信息Node* child; /第一个孩子Node* brother; /兄弟;4、 家谱类（二叉树结构、左孩子，右兄弟）class FamilyTreeprivate: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 Informationstring name;string birthPlace;BirthDay birthDay;string sex; string education; string job;string father;string spouse;char life; ;struct NodeInformation data;Node* child; Node* brother; ;class FamilyTreeprivate: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) ; ;#endifFamilytree.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;docout<<"n输入不明确，请重新输入！"<<endl;cout<<"请问是否创建（是：“y”,否:“#”）："cin>>ch;if(ch="y")|(ch="Y")|(ch="#")t=0;while(t=1);if (ch="#") root = NULL;elseroot=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(); /清空流 elsebreak;/isdigit异常处理生日输入,若参数c为阿拉伯数字09，则返回非0值，否则返回NULL。/*int i;for(i=0;root->data.birthDayi!=0;+i)if(isdigit(root->data.birthDayi)=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;docout<<"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;elsecout<<root->data.name<<'t'PreOrder(root->child);PreOrder(root->brother);void FamilyTree:InOrder(Node *root) /中序递归遍历输出家谱if(root=NULL) return;elseInOrder(root->child);cout<<root->data.name<<'t'InOrder(root->brother);void FamilyTree:PostOrder(Node *root) /后序递归遍历输出家谱if(root=NULL)return;elsePostOrder(root->child);PostOrder(root->brother);cout<<root->data.name<<'t'int FamilyTree:Generation(Node *root) /这个家族共有几代人int l; /l左孩子 if(root=NULL) /这个家族为空,返回0return 0; elsel=Generation(root->child); /左孩子的return l+1;/int numberofpeople=0;int FamilyTree:NumberOfPeople( ) /家族的总人数if(root=NULL) /家族人数为0return 0;/*elseif(root!=NULL)numberofpeople+;NumberOfPeople(root->child);NumberOfPeople(root->brother);return numberofpeople;*/elsereturn Numberofpeople;/int count=0;int FamilyTree:LifeNum( ) /健在人数if(root=NULL) /-1表示这个家族不存在return -1; /*elseif(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 ;elsecout<<"姓名："<<root->data.name;cout<<"tt性别："<<root->data.sex;cout<<"tt配偶："<<root->data.spouse<<endl;cout<<"出生地："<<root->data.birthPlace;cout<<"tt生日："<<root->data.birthDay;/;<<root->data.birthDay.year<<"-"<<root->data.birthDay.month<<"-"<<root->data.birthDay.day<<endl;cout<<"tt父亲："<<root->data.father<<endl;cout<<"学历："<<root->data.education;cout<<"tt工作："<<root->data.job;cout<<"tt是否健在："if(toupper(root->data.life)='Y')cout<<"是"<<endl;elsecout<<"否"<<endl; int message=0; /判断是否查找成功int FamilyTree:Message(Node *root,string Name) /显示该成员的基本信息if(root=NULL)return message;elseif(root->data.name=Name)message=1;PrintMessage(root );elseMessage(root->child,Name);Message(root->brother,Name);return message;Node* FamilyTree:PreFindFather(Node *root,string FatherName) /给定元素值查找父亲结点指针位置并返回其指针，此方法采用的先序遍历 if(root=NULL)throw"错误"Node *p;Node *tree20;int top=0;while(root!=NULL|top!=0)while(root!=NULL)if(root->data.name=FatherName)p=root;top+;treetop=root;root=root->child;if(top!=0)root=treetop->brother;top-;return p;Node* FamilyTree:PreFindBrother(Node *root,string FatherName) /给定元素值查找兄弟结点指针位置并返回其指针，此方法采用的先序遍历 if(root=NULL)throw"错误"Node *p;Node *tree20;int top=0;while(root!=NULL|top!=0)while(root!=NULL)if(root->data.father=FatherName)p=root;top+;treetop=root;root=root->child;if(top!=0)root=treetop->brother;top-;return p;void FamilyTree:AddNewPeople(Node *root,string FatherName,string NAme) /增加新的家族成员if(root=NULL)/如果这个家族为空，直接把该结点置为根结点Creat( ) ;elseNode *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;elseif(root->data.name=Deletepeople) /如果要删除的为祖先，则调用Release()函数t=1;root->brother=NULL;root->child=NULL;Release(root);elseNode *Father=PreFindFather(root,FatherName);Node *Brother=PreFindBrother(root,FatherName); /兄弟结点Node *p;Node *tree20;int top=0;while(root!=NULL|top!=0)while(root!=NULL)if(root->data.name=Deletepeople)p=root;/break;top+;treetop=root;root=root->child;if(top!=0)root=treetop->brother;top-;if(toupper(p->data.life)='Y') /健在人数减一LifePeopele-;if(Father->child->data.name=p->data.name)/Deletepeople)Father->child=NULL;elseBrother->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;elseif(root->data.name=NAme)flag=1;root->data.name=NewName;elseSetNewName(root->child,NAme,NewName);SetNewName(root->brother,NAme,NewName);