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

1、项目实训二项目名称 _家谱管理系统_姓名 班级学 号 指导教师 2018.1 问题描述：家谱用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料 管理系统，实现对一个家族所有的资料进行收集整理。实现对家庭成员 信息的建立、查找、插入、修改、增加、删除、更新、统计等等功能。目的和要求：目的：1、能根据具体问题的具体情况，结合数据结构课程中的基本理论和基本算 法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并 能设计出解决问题的有效算法。2、提高程序设计和调试能力。通过上机学习，验证自己设计的算法的正确 性。学会有效利用基本调试方法。3、初步掌握软件开发过程中问题分析、系统设计、

2、程序编码、测试等基本 方法和技能。4、培养根据选题需要选择学习书籍，查阅文献资料的自学能力。要求：用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料管理系统，实现对一个家族所有的资料进行收集整理。支持对家谱的增加， 删除，更新，统计等。软件环境:Microsoft Visual Studio 2010流程设计:FindChild 函数Case 9SaveToFile 函数FileToFamilyTree 函数CaselO模块划分：1、统计模块(1) 统计家族总人数、健在人数、几代人(2) 主要函数：int Ge neratio n(Node *root); /这个家族共有几代人int

3、NumberOfPeople( ); / 家族的总人数int LifeNum( ); /健在人数(3) 实现方法：静态成员变量(4) 实现结果：这个家族共有工代人陋个家族健在人数为：32、更新模块(1) 创建家谱、增加成员、删除成员、成员改名(2) 主要函数：Node* Creat( ); /构造函数调用voidAddNewPeople(Node *root,stringFatherName,stringNAme); /增加新的家族成员intDeletePeople(Node*root,stri ngFatherName,stri ngDeletepeople); /删除家族成员int Set

4、NewName(NodSroot,string NAme,string NewName); /更改姓名(3) 实现方法：创建家谱和成员改名主要通过递归调用；增加成员和删除成员主要通过栈的非递归调用。(4) 实现结果:鱷的序咤片右兄弟请體入家庭成员的基本信息苣-Q : lom出生地！ fujlan吿甲数字.年月日以空格或者回车间隔)：1997 3 1 性別* nan羊历；colleae匸作 vorK£杀首John已偶(有多任配偶则以"或者J ”间隔:wq!恵yJi 攵-E 亠一qn u 3kI!J丿 n f 算功的sunoAA1 .”地: MWI名牛历 喜改改姓羊名y 姓nn

5、的SUJaneFemale 2017-1-1 nono是:Tam :Sunnv言息一芒I: Sanny出生地；f u j in日(数字、年月日以空格或者回车间隔)f &ihaLb nonoTom佥霍(有多任配偶则以J "或者仁"no是占健在 *是，n r:y:2018间隔厂:n bb o 宀-tT 的亲 员父 人的 除员 要该功Suirinu3、查询模块(1) 查询成员详细信息、查询成员的孩子以及孩子的详细信息(2) 主要函数：int Message(Node *root,stri ng Name); /显示该成员的基本信息int Fin dChild(Node *

6、root,stri ng NAme); /显示孩子信息(3) 实现方法：通过递归调用，找到成员，输出相应的信息(4) 实现结果：名 姓 的人 勺 n e& 9 询Jiea 查-益11 要果h =co 入结-地: 轅名生历-J4-J-Aiie龛否健在：是询查;要M-亦看HaM 入结用査地禺ncs有牛历名 姓 的 员Ir «« 命生工 c 息 亠吕 细 详 的斷 子Ji 孩訂Sman201S-1-1no宙土士也I Fujian 詡5= afenale 2017-1-1 no是件别* An谎“ 生戸；1997-1-1 工作：vo i'k4、显示模块(1) 前序、中

7、序、后序遍历家谱(2) 主要函数：void PreOrder(Node *root); II前序递归遍历输出家谱 中序递归遍历输出家谱void In Order(Node *root); II后序递归遍历输出冢谱void PostOrder(Node *root); /(3) 实现方法：递归遍历(4) 实现结果：r前序遍历TonJan eMax中序遍历J-aneTonMax后底遍历kjaneMaxTom5、文件模块(1) 保存到文件、从文件读取(2) 主要函数：void SaveToFile(Node *root); / 保存到文件void FileToFamilyTree( Node *ro

8、ot) ; /从文件中读取(3) 实现方法：文件流(4) 实现结果：D - nniLy. txt已经保存全部信息。作文 型s' 入入務xf名在洁诂ID:|;4塞ITO另性肚配偶出生地生日学历工作父亲f u jian 199711 colleage uork Johnuni ly.txt -込事本刘牛:F)巒鲨鈕：。)空何存却出姓名性别配偶出主世主日学历工作TonrankkFujian1 collczi&=wukJohnv数据结构实现：1、生日结构体struct BirthDayint year;int mon th;int day;friend istream& ope

9、rator>>(istream &is,BirthDay &b);friend ostream& operator<<(ostream &os,c onst BirthDay &b);2、信息结构体(家族成员的基本信息)struct In formatio nstri ng n ame; /姓名stri ng birthPlace; /出生地BirthDay birthDay; /生日stri ng sex; /性另 Ustri ng educati on; /学历stri ng job; /工作stri ng father; /

10、父亲stri ng spouse; /配偶char life; /是否健在；3、二叉树结点结构体struct NodeIn formatio n data; / 个人信息Node* child; /第一个孩子Node* brother; / 兄弟；4、家谱类(二叉树结构、左孩子，右兄弟)class FamilyTree private:Node* root;Node* Creat( ); / 构造函数调用void Release(Node *root); /析构函数调用static int Numberofpeople; /计算总人数，NumberOfPeople ()调用static int

11、 LifePeopele; /计算健在人数，LifeNum ()调用public:FamilyTree(); /构造函数，初始化一棵树，其前序序列由键盘输入FamilyTree(); II 析构函数，释放链表中各结点的存储空间void SetNode(Node *root); II 设置结点信息Node* Getroot(); II获取根结点前序递归遍历输出家谱中序递归遍历输出家谱后序递归遍历输出家谱这个家族共有几代人void PreOrder(Node *root); II void In Order(Node *root); II void PostOrder(Node *root); I

12、I int Gen erati on(N ode *root); IIint NumberOfPeople( ); II家族的总人数int LifeNum( ); II健在人数void Prin tMessage(Node *root ); II输出基本信息int Message(Node *root,stri ng Name); II显示该成员的基本信息Node* PreFi ndFather(Node *root,stri ng FatherName); II给定元素值查找父亲结点指针位置并返回其指针，此方法采用的先序遍历Node* PreF in dBrother(Node *root,

13、stri ng FatherName); II给定元素值查找兄弟结点指针位置并返回其指针，此方法采用的先序遍历void AddNewPeople(Node *root,string FatherName,string NAme); II增加新的家族成员int DeletePeople(Node*root,stri ngFatherName,stri ngDeletepeople); II 删除家族成员int SetNewName(Node *root,stri ng NAme,stri ng NewName); II 更改姓名int Fi ndChild(Node *root,stri ng

14、NAme); II显示孩子信息void SaveToFile(Node *root); /保存到文件void FileToFamilyTree( Node *root) ; /从文件中读取；调试分析：1、问题：在创建家谱时，询问用户是否需要继续添加成员，只要用户不输 入” #”就继续添加。解决方案：增加if语句判断条件，只要输入的不是” Y” , ” y” , ” #”， 就请用户重新输入。2、问题：计算总人数和健在人数，因为存在增加和删除函数，多次调用计算函数。解决方案：在家谱类中使用静态成员变量3、问题：在输入和输出成员信息中的生日，生日使用的是生日结构体变量， 输入输出包括年、月、日。解

15、决方案：使用友元输入输出重载4、问题：在输入生日时，输入数字程序正常运行，输入其他字符，程序会 出现死循环。解决方案：cin .fail()判断输入是否正确，cin .clear() 为了使输入错误能重新输入，将错误标识符改为 0，cin.sync()清空流。5、问题：在输入一些信息是，询问用户是否确认一些信息时，请用户输入y、n'但是用户有时会输入大写。解决方案：使用toupper()函数，将用户输入的确认信息转换成大写字 母。6、问题：在增加孩子时，只能添加长子，添加第二个孩子、第三个等等， 会出现错误。解决方案：添加一个寻找兄弟指针的函数，如果要添加孩子的成员，已 经有了孩子，则

16、通过调用兄弟指针函数来增加孩子。7、问题：保存到文件和读取文件时，会出现输入路径错误的情况。解决方案：通过调用_access()函数，判断输入路径是否正确。8 问题：读取文件时，cin的重载会跳过空白字符，包括回车符。 解决问题：使用cin.get()函数接收回车。9、问题：删除成员时，删除能够成功，但会出现空指针错误。 解决方案：在delete该成员时，需要将指向该成员的指针置空。10、问题：在主函数中，通过请用户输入数字，来选择相应的操作，当用户 误输入的为选择以外的字符时，会结束程序运行。解决方案：与解决方案4相同。实验结果及分析1、创建家谱2、保存到文件famiiy.tKt -记事本文

17、蹴F）裳辑旧同O）玲輒H）姓名性别Tomman1配隅 kk岀生地fujian学历 工作 父亲 健在colieage work Johny3、读取文件4、增加成员olleage：161W驟ST:Xfanily.txt生名 性别 Bffi 出生地 om man kk f ujian1 cwo rk学历John工作或者仁”间隔）:o:I健在1 1S3 C:Wi nd ow£system 32cmid. exele肯青圭mT万 J e u n F生日名Ja建.息 八xwSB人人员ftn加加应庭專要家Ja菇fe IA入A;地斶. Hsu别nonoIon（有多任配偶则以J聿在（V是宀否）：5、基

18、本信息6、查询成员信息7、成员改名请渝入选择操乍笊序号汐为 名君鼠 改的！信 要新功的T n AAf U :JneI: feikale3 a 201R-1-1 E： no目匚因no: Ton是否催任：s8、遍历冢谱青揄入选择攧作的序号：2r前Ton Sunnsrn_-中 序遍历Sunn Ionk后序遍历ESwiny Ton9、查询孩子信息uinmy曰否査看孩子的详細信息£名 i Sunny 生地：fujiftn 历*I ! S 丿别琴 電生工否，n：y f enale 2318 11na«乗否 ix'是曰疋10、删除成员青输入选择操作的序号泊 曜阖缺盒g日恳成功收获

19、：本次实训在我们为期两周的时间里进行，通过自己的不断学习、请教和 老师的指导，完成了关于家谱资料管理的设计。前期主要是准备阶段，运用 哪些技术，中期实践阶段，通过几天的上机编写代码，然后完成，后期完善 阶段，对一些难点和重点再细化，和做一些数据输入时的异常处理。最后进 行答辩阶段。通过这次实训的互相帮助学习的过程，自己看书学习的经验， 以及从网上以及其他各种途径获得信息和知识的经验。理论与实际相结 合的设计，锻炼了我综合运用所学的基础知识，解决实际问题的能力，同时 也提高我查阅文献资料、对程序整体的把握等其他能力水平。而且通过对整 体的掌控，对局部的取舍，以及对细节的斟酌处理，都使我的能力得到

20、了锻 炼，我的各方面经验都得到了极大的丰富。附录全部代码Familytree.h#ifndef FAMIL YTREE_H #define FAMILYTREE_H #in clude <iostream> #in clude <stri ng> #in clude <cctype> #i nclude <io.h> #i nclude <ioma nip> #in clude <fstream>usi ngn amespacestd;structBirthDay intyear;intmon th;intday;frie

21、nd istream& operator >>(istream &is,BirthDay &b);friend ostream& operator <<(ostream &os, const BirthDay &b);struct In formati onstri ng n ame;stri ng birthPlace;BirthDay birthDay;stri ng sex;string education;stri ng job;string father;stri ng spouse;char life;stru

22、ct NodeIn formati on 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

23、);void PostOrder(Node *root);int Generation(Node *root);int NumberOfPeople();int LifeNum();void PrintMessage(Node *root );int Message(Node *root,string Name);Node* PreF in dFather(Node *root,stri ng FatherName);Node* PreF in dBrother(Node *root,stri ng FatherName);void AddNewPeople(Node *root,string

24、 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);；#en difFamilytree.cpp#i nclude "Familytree.h&qu

25、ot;int FamilyTree:Numberofpeople=O;int FamilyTree:LifePeopele=O;/生日结构体变量输入输出友元重载istrea m& operator>>(istream & is,BirthDay &b)is>>b.year>>b.m on th>>b.day;return is;ostream& operator<<(ostream &os,c onst BirthDay &b)os<vb.yearvv"-"vv

26、b.m on th<<"-"<<b.day;return os;FamilyTree:FamilyTree() /由键盘输入this->root=Creat();构造函数，初始化一棵树，其前序序列FamilyTree:FamilyTree() /析构函数，释放链表中各结点的存储空间Release(root);Node* FamilyTree:Getroot() /获取根结点return root;Node* FamilyTree:Creat()构造函数调用Node *root;stri ng ch;coutvv"请问是否创建（是：“

27、y” ,否：“#”）："；cin >>ch; /输入名字if(ch!="y")异常处理if(ch!=" Y")if(ch!="#")int t=1;docout<v"n输入不明确，请重新输入！ "<<endl;coutvv"请问是否创建(是：“ y” ,否：“#”):cin> >ch;if(ch="y")|(ch=' 'Y ")|(ch="#")t=0;while(t=1);if (ch=

28、"#") root = NULL;elseroot=n ew 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;voi

29、d FamilyTree:SetNode(Node *root) /设置结点信息Numberofpeople+;coutvv"请输入家庭成员的基本信息 "<<endl;coutvv"姓名："cin>> root->data .n ame;coutvv"出生地："cin>> root->data.birthPlace;coutvv"生日(数字、年月日以空格或者回车间隔)："；while(1)cin>> root->data.birthDay;if(ci

30、 n. fail()coutvv"输入有错！请重新输入生日(数字):"<<endl;cin. clear(); /输入错误则能重新输入cin.syn c();/ 清空流elsebreak;/isdigit异常处理生日输入，若参数c为阿拉伯数字09,则返回非0值，否则返回NULL/*i nt i;for(i=O;root->data.birthDayi!=O;+i)if(isdigit(root->data.birthDayi)=0)cout«"n输入不明确，请重新输入！ "<<endl;break;*/cou

31、tvv"性别："cin>> root->data.sex;coutvv"学历："；cin>> root->cati on;coutvv"工作："cin>> root->data.job;coutvv"父亲："cin>> root->data.father;coutvv"配偶(有多任配偶则以“，”或者“、”间隔) ："v<endl;cin>> root->data.spouse;cout

32、vv"是否健在(y是，n否):"cin>> root->dataife;if(toupper(root->dataife)!=' Y') /异常处理if(toupper(root->data.life)!='N')int t=1;docout«"n输入不明确，请重新输入！ coutvv"是否健在（y是，n否）:" cin>> root->dataife;！ "<<endl;if(toupper(root->data.life)=

33、' Y')|(toupper(root->dataife)='N')t=0;while(t=1);if(toupper(root->dataife)=' Y')LifePeopele+;void FamilyTree:PreOrder(Node *root) /前序递归遍历输出家谱if(root=NULL)return;elsecout<<root->data .n ame<<'t'PreOrder(root->child);PreOrder(root->brother);vo

34、id FamilyTree:l nO rder(Node *root) /中序递归遍历输出家谱if(root=NULL)return;elseInO rder(root->child);cout<<root->data .n ame<v't：InO rder(root->brother);void FamilyTree:PostOrder(Node *root) /后序递归遍历输出家谱if(root=NULL)return;elsePostOrder(root->child);PostOrder(root->brother);cout&l

35、t;<root->data .n ame<v't：int FamilyTree:Ge neratio n(Node *root) /这个家族共有几代人int l; /l 左孩子if(root=NULL) /这个家族为空，返回0return 0;elsel=Ge neratio n( root->child); /左孩子的return l+1;/int nu mberofpeople=0;int FamilyTree:NumberOfPeople( ) /家族的总人数if(root=NULL) /家族人数为 0return 0;/*elseif(root匸NULL

36、)nu mberofpeople+;NumberOfPeople(root->child); NumberOfPeople(root->brother);return nu mberofpeople;*/elsereturn Numberofpeople;int coun t=0;int FamilyTree:丄ifeNum( ) /健在人数if(root=NULL) /-1 表示这个家族不存在 return -1;/*elseif(toupper(root->data.life)=' Y')coun t+;LifeNum(root->child);Li

37、feNum(root->brother);retur n coun t;*/return LifePeopele;void FamilyTree:Pri ntMessage(Node *root ) /输出基本信息if(root=NULL)return ;elsecoutvv"姓名："<<root->;cout<v"tt 性别："v<root->data.sex;cout<<"tt酉己偶："vvroot->data.spousevvendl;coutvv&q

38、uot;出生地："vvroot->data.birthPlace;coutvv"tt生日"vvroot->data.birthDay;/;vvroot->data.birthDay.yearvv"-"vvroo t->data.birthDay. mon thvv"-"vvroot->data.birthDay.dayvve ndl;coutvv"tt 父亲："vvroot->data.fathervvendl;coutvv"学历："vvroot-&

39、gt;cation;cout<v"tt 工作："<<root->data.job;coutvv"tt是否健在："if(toupper(root->data.life)=' Y')coutvv"是"<<endl;elsecoutvv"否"vvendl;int message=0; /判断是否查找成功int FamilyTree:Message(Node *root,stri ngName) /显示该成员的基本信息if(root=NULL)ret

40、ur n message;elseif(root->data. name=Name)message=1;Prin tMessage(root );elseMessage(root->child,Name);Message(root->brother,Name);retur n message;Node* FamilyTree:PreFindFather(Node *root,string FatherName)/给定元素值查找父亲结点指针位置并返回其指针，此方法采用的先序遍历if(root=NULL)throw"错误"Node *p;Node *tree2

41、0;int top=0;while(root!=NULL|top!=O)while(root!=NULL)if(root->data .n ame=FatherName) p=root;top+；treetop=root;root=root->child;if(top!=0)root=treetop->brother;top-;return p;Node* FamilyTree:PreFi ndBrother(Node*root,stri ng FatherName)/给定元素值查找兄弟结点指针位置并返回其指针，此方法采用的先序 遍历if(root=NULL)throw&qu

42、ot;错误"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;voidFamilyTree:AddNewPeople(Node*root,stri ngFatherName,stri ng NAme) /增加新的家族成员if(root=N

43、ULL)如果这个家族为空，直接把该结点置为根结点Creat();elseNode *p=new Node;p->data .n ame=NAme;p->child=NULL;p->brother=NULL;Node *Brother=PreFi ndBrother(root,FatherName); /兄弟结点if(root->data.father=FatherName) /如果与祖先(根结点)同一个父亲，则置为根结点的右兄弟Node *q=root;while(q->brother!=NULL) /寻找根结点的右兄弟结点为空的结点q=q->brother

44、;if(q->brother=NULL)q->brother=p;SetNode(p);Node *Father=PreF in dFather(root,FatherName); /父亲结点/Node *Brother=PreFindBrother(root,FatherName);/ 兄弟结占八、if(Father->child=NULL) /如果父亲结点的孩子结点为空Father->child=p;SetNode(p);else /如果父亲结点的孩子结点不为空if(Brother->brother=NULL) /最后一个兄弟结点Brother->bro

45、ther=p;SetNode(p);intFamilyTree:DeletePeople(Node*root,stri ngFatherName,stri ng 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=PreFi ndF

46、ather(root,FatherName);Node *Brother=PreFi ndBrother(root,FatherName); /兄弟结点Node *p;Node *tree20;int top=0;while(root!=NULL|top!=O)while(root!=NULL)if(root->data .n ame=Deletepeople)p=root;/break;top+;treetop=root;root=root->child;if(top!=0)root=treetop->brother;top-;if(toupper(p->dataif

47、e)=' Y') /健在人数减一LifePeopele-;if(Father->child->data .n ame=p->data .n ame)/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,stri ngNAme,stri ngNewName) /更改姓名

48、if(root=NULL)retur n flag;elseif(root->data. name=NAme)flag=1;root->data. name=NewName;elseSetNewName(root->child,NAme,NewName);SetNewName(root->brother,NAme,NewName);retur n flag;int FamilyTree:FindChild(Node*root,stringNAme) / 显示孩子信息int flag=O;if(root=NULL)retur n flag ;elseif(root->

49、;data. name=NAme)if(root->child=NULL)retur n flag;elseflag=1;cout<<root->child->data .n ame<<""Node *p;Node *tree20;p=root->child;tree0=p;int top=0;while(p->brother!=NULL)p=p->brother;top+；treetop=p;cout«p->data .n ame<<""coutvv"n是

50、否查看孩子的详细信息(是：y,否：n):"char ch;cin> >ch;if(toupper(ch)=' Y')Node *q=treetop;while(top>-1) Prin tMessage(q);cout<<"n"<<e ndl;top-; q=treetop;retur n flag;void FamilyTree:SaveToFile(Node *root) /保存到文件if(root=NULL)coutvv"家谱为空"<<endl;return ;ofst

51、ream ofile;cout << "请输入要保存文件的路径："<< en dl;char c = ci n.get(); II接收回车char dir40;cin. getl in e(dir, 40);ofile.ope n( dir,ios:app);if (_access(dir, 0) = -1) II系统自带功能判断路径是否有效cout << "输入路径不存在！" << endl;return;elsed:test.txt"cout vv "已经保存全部信息。"v

52、v endl;ofile vv " 姓名"vv setw(10) vv " 性别"vv setw(10) vv " 配偶"vv setw(10) vv " 出生地"vv setw(10) vvIV生日"vv setw(10) vv父亲"vvsetw vv "vvroot->data.spouse<v"学历"vv setw(7) vv " 工作"vvsetw(7) vv "健在"<< endl;Node *tree20;int top=0;while(root!=NULL|top!=0)while(root!=NULL)ofi