一、引言（简要说明设计题目的目的、意义、内容、主要任务等） （一）问题描述 家谱用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料管理系统，实现对一个家族所有的资料进行收集整理。实现对家庭成员信息的建立、查找、插入、修改、增加、删除、更新、统计等等功能。 （二）目的和要求 1、目的 （1）能根据具体问题的具体情况， 结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 （2）提高程序设计和调试能力。通过上机学习 , 验证自己设计的算法的正确性。学会有效利用基本调试方法。 （3）初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。 （4） 培养根据选题需要选择学习书籍，查阅文献资料的自学能力。 2、要求 用于记录某家族历代家族成员的情况与关系。 现编制一个家谱资料管理系统，实现对一个家族所有的资料进行收集整理。支持对家谱的增加，删除，更新，统计等。 二、正文（课程设计的主要内容，包括实验与观测方法和结果、仪器设备、计算方法、编程原理、数据处理、设计说明与依据、加工整理和图表、形成的论点和导出的结论等。正文内容必须实事求是、客观真切、准确完备、合乎逻辑、层次分明、语言流畅、结构严谨，符合各学科、专业的有关要求。） 算法思想:本程序是一个管理家谱的系统，通过这个系统可以对家族成员进行创建、显示、查找 、修改、以及保存家谱和读取家谱功能。该系统分为以下几个模块，分别是：创建家谱，显示家谱、按姓名和生日查找家庭成员、修改家谱、存盘、读盘以及退出系统。本程序用到的存储形式为多叉树，因为家谱中每个人既有父母又有孩子，而且孩子的个数并不确定，所以用多叉树来存储最为合适。用多叉树来存储，就用用到多叉树的递归创建及递归遍历。因为是多叉树，所以遍历时用广度优先搜索合适。本函数最主要的思想就是递归调用，每个子函数中都会用到递归。定义结构体时给定指针数组的最大容量，来规定家谱中最多可以存多少人。定义一个家族树的指针变量用来当每个子函数的参数，从而将其返回到主函数中。 （一）流程设计 （二）模块划分 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); //保存到文件 11 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 #include #include #include #include #include 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 \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<root=Creat(); } FamilyTree::~FamilyTree() // 析构函数，释放链表中各结点的存储空间 { Release(root); } Node* FamilyTree::Getroot() //获取根结点 { return root; } Node* FamilyTree::Creat()// 构造函数调用 { Node *root; string ch; cout<<\请问是否创建（是： “y”, 否: “#）”：\cin>>ch; //输入名字 if(ch!=\异常处理 { if(ch!=\if(ch!=\{ int t=1; do { cout<<\输入不明确，请重新输入！ ！\cout<<\请问是否创建（是： “y”, 否: “#）”：\cin>>ch; if((ch==\t=0; }while(t==1); } } if (ch==\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<<\请输入家庭成员的基本信息 \cout<<\姓名： \cin>>root->data.name; cout<<\出生地： \cin>>root->data.birthPlace; cout<<\生日 (数字、年月日以空格或者回车间隔） ：\while(1) { cin>>root->data.birthDay; if(cin.fail()) { cout<<\输入有错！！请重新输入生日 (数字）：\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<<\输入不明确，请重新输入！ ！\break; } }*/ cout<<\性别： \cin>>root->data.sex; cout<<\学历： \cin>>root->data.education; cout<<\工作： \cin>>root->data.job; cout<<\父亲： \cin>>root->data.father; cout<<\配偶（有多任配偶则以 “，”或者 “、”间隔）：\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<<\输入不明确，请重新输入！ ！\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<data.name<<'\\t'; PreOrder(root->child); PreOrder(root->brother); } } void FamilyTree::InOrder(Node *root) // 中序递归遍历输出家谱 { if(root==NULL) return; else { InOrder(root->child); cout<data.name<<'\\t'; InOrder(root->brother); } } void FamilyTree::PostOrder(Node *root) // 后序递归遍历输出家谱 { if(root==NULL) return; else { PostOrder(root->child); PostOrder(root->brother); cout<data.name<<'\\t'; } 29 30 } 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<<\姓名： \cout<<\性别： \cout<<\配偶： \cout<<\出生地： \cout<<\生 日 ： \hDay.month<<\cout<<\父亲： \cout<<\学历： \cout<<\工作： \cout<<\是否健在： \if(toupper(root->data.life)=='Y') cout<<\是\else cout<<\否\} } 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) //显示孩子信息 { int flag=0; if(root==NULL) return flag ; else { if(root->data.name==NAme) { if(root->child==NULL) return flag; else { flag=1; cout<child->data.name<<\Node *p; Node *tree[20]; p=root->child; tree[0]=p; int top=0; while(p->brother!=NULL) { p=p->brother; top++; tree[top]=p; cout<data.name<<\} cout<<\是否查看孩子的详细信息 (是： y,否： n):\char ch; cin>>ch; if(toupper(ch)=='Y') { Node *q=tree[top]; while(top>-1) { PrintMessage(q); cout<<\top--; q=tree[top]; } } } } } return flag; } void FamilyTree::SaveToFile(Node *root) //保存到文件 { if(root==NULL) { cout<<\家谱为空 \return ; } ofstream ofile; cout << \请输入要保存文件的路径： \char c = cin.get(); //接收回车 char dir[40]; cin.getline(dir, 40); ofile.open(dir,ios::app); if (_access(dir, 0) == -1) //系统自带功能判断路径是否有效 { cout << \输入路径不存在！ \return; } else { //d:\\test.txt\cout << \已经保存全部信息。 \ofile << \姓名 \性别 \配偶 \setw(10) << \出生地 \生日 \学历 \setw(7) << \工作 \父亲 \健在 \Node *tree[20]; int top=0; while(root!=NULL||top!=0) { while(root!=NULL) { ofile<data.name<data.sex<data.spouse<< setw(10)<data.birthPlace<data.birthDay<data.education<data.job<data.father<data.life<child; } if(top!=0) { root=tree[top]->brother; top--; } } ofile.close(); } } void FamilyTree::FileToFamilyTree(Node *root ) //从文件中读取47 { cout << \请输入要读取文件的路径： \ifstream ifile; char c = cin.get(); //读入任意一个字符，包括回车符 char dir[40]; //因为 cin 的>>重载会跳过空白字符， 包括回车字符，所以无法使用 >>直接读入回车符 cin.get()，该成员函数功能为， 从 cin 读入一个字符，并返回 cin.getline(dir, 40); // cin.get()，该成员函数功能为， 从 cin 读入一个字符，并返回 ifile.open(dir); // if (_access(dir, 0) == -1) { cout << \输入路径不存在！ \return; } string ch; getline(ifile, ch); cout << ch << endl; Node *tree[20]; int i=0; while (!ifile.eof()) //eof 文件末尾 {// 姓名 性别 配偶 出生地 生日 学历4 工作 父亲 健在 ifile>>root->data.name>>root->data.sex>>root->data.spouse>>root->dat a.birthPlace>>root->data.birthDay>>root->data.education>>root->data.job> >root->data.father>>root->data.life; tree[i]=root; i++; } i--; for(int j=0;jdata.name<<\\\\\\\\\} Family.cpp #include #include #include \#include using namespace std; void Menu(); int main() { Menu(); cout<<\创建家谱，输入顺序为前序序列，左孩子，右兄弟 \FamilyTree ft; system(\Menu(); Node *root=ft.Getroot(); while(1) { int select; cout<<\请输入选择操作的序号 :\//cin>>select; while(1) { cin>>select; if(cin.fail()) { cout<<\输入有错！！请重新输入选择 (数字）：\cin.clear(); //输入错误则能重新输入 将错误标识符改为 0 cin.sync(); //清空数据流 } else break; } switch(select) { case 1:system(\case 2: { cout<<\前序遍历 -----------\cout<<\中序遍历 -----------\cout<<\后序遍历 -----------\cout<>Name; cout<<\查找结果： \int message=ft.Message(root,Name); if(message==0) cout<<\查找失败！！\}break; case 5: { cout<<\请输入要增加人员的父亲姓名： \string FatherName; cin>>FatherName; cout<<\请输入要增加人员的姓名： \string NAme; cin>>NAme; ft.AddNewPeople(root,FatherName,NAme); }break; case 6: { cout<<\请输入要删除人员的姓名： \string Deletepeople; cin>>Deletepeople; cout<<\请输入该成员的父亲： \string Fname; cin>>Fname; int DelName=ft.DeletePeople(root,Fname,Deletepeople); if(DelName==0) cout<<\删除失败，请重新选择 \else cout<<\删除成功 \52 }break; case 7: { cout<<\请输入要改名人员的姓名： \string Name; cin>>Name; cout<<\请输入新的名字： \string NewName; cin>>NewName; int a=ft.SetNewName(root,Name,NewName); if(a==1) { cout<<\改名成功！！\\n 改名后的信息为： \ft.Message(root,NewName); } else cout<<\改名失败！！\}break; case 8: { cout<<\请输入要查询人员的姓名： \string NAMe; cin>>NAMe; cout<<\查找结果： \int fc=ft.FindChild(root,NAMe); if(fc==0) cout<<\该成员无孩子 \}break; case 9: { ft.SaveToFile(root); }break; case 10: { ft.FileToFamilyTree(root); }break; default: { cout<<\欢迎使用 ---------------\} break; } } return 0; } void Menu() { cout<<'\\n'<
