家谱管理系统

1、武汉工商学院信息工程学院项目名称： 家谱管理系统 学生姓名： 周光波 学 号： 14401034 班 级： 14计科本1 指导教师： 刘莹 2015年6月23日目录1引言12 系统需求分析22.1 系统功能概述22.2 系统模块23 系统存储结构说明33.1 系统存储信息说明33.2 系统存储结构设计34 系统功能设计及实现44.1 输入家庭成员信息44.2 输出所有成员44.3 查找某人的所有孩子54.4 查找某人的双亲64.5 查找某人的所有祖先74.6 查找某人的所有兄弟85系统测试95.1 主菜单95.2 录入家庭成员信息95.3 输出家谱中的所有成员95.4 查找相应的家族成员106

2、 体会13参考文献14附录：代码15数据结构课程设计1引言树形结构是区别于线性结构的另一大类数据结构，它具有分支性和层次性，在计算机科学的许多领域和日程生活中都具有十分广泛的应用，是数据表示、信息组织和程序设计的基础和有力工具，下面我们将通过树与二叉树的转换来制作家谱管理系统。2 系统需求分析2.1 系统功能概述家谱管理系统将树形结构转换为二叉树结构，通过二叉树链表储存家谱信息，需要初始录入家谱信息，然后即可显示出全面的人员关系，还可查找某人的双亲、孩子、祖先、兄弟。充分利用二叉树的方便性和简洁性。2.2 系统模块图2-1 系统功能模块图（1）录入家庭信息模块用来初次输入家庭成员姓名，按照提示

3、的亲缘关系来输入相应的人的姓名，没有对应的成员就会提示输入#，输入的家庭成员信息将保存在二叉树链表中，输入完所有信息后将返回主菜单，让用户选择下一步操作。（2）输出所有家庭成员进入此功能后会将家谱姓名按代数关系和亲子关系罗列出来，方便用户全面观察整个家谱。（3）查找相应的家庭成员进入要查找的成员类型，按提示输入成员姓名，查找到对应亲属会罗列出来，如果没查找到会有相应的提示，然后返回主菜单。如果没有用户输入的那个人，将提示输入错误，返回主菜单。3 系统存储结构说明3.1 系统存储信息说明系统采用二叉链表来保存家庭成员姓名信息。将树形成员关系转化为二叉树结构保存。用队列辅助暂时储存一些家庭成员。3

4、.2 系统存储结构设计typedef char datatype;typedef struct node /定义二叉树结构datatype data10;struct node *lchild,*rchild;bintnode;typedef bintnode *bintree; /定义二叉树指针typedef struct /队列定义bintree aMAXSIZE;int front;int rear;int n; /队列元素个数int depth; /家谱代数queue;4 系统功能设计及实现4.1 输入家庭成员信息先在调用此函数前给出提示先输入根节点，保存在变量ch中，然后在函数中输入

5、姓名，如果姓名为#则执行t=NULL,否则建立空节点t，将ch的值赋给t->data,然后提示输入ch的孩子，并执行t->lchild=input()来递归调用此函数，调用完成后下一步操作为给出提示输入ch的兄弟，并执行t->rchild=input()来递归调用，调用完成后就完成了else语句，最后返回节点指针t。图4-1 录入家谱成员信息4.2 输出所有成员先输出提示显示出下面输出的是第一代人，然后调用postorder()函数输出第一代的成员,并将它们入队，然后定义两个控制循环的变量i,然后进入for(int x=2;x<=sq->depth;x+)循环中，

6、循环完成后结束函数，循环中先输出格式划分语句“第x代”，然后让i=sq->n,再进入while(i!=0)循环，循环结束回到for循环中，循环中先定义一个节点指针变量a并初始化为出队节点，判断a->lchild是否存在，存在就调用postorder()函数输出a节点的所有孩子，并将这些孩子入队，判断完成后让i-。图4-2 输出全部家谱成员4.3 查找某人的所有孩子先判断节点t是否存在，如果存在再判断t->data是否等于x，等于的话判断t->lchild是否为空，空的话输出“没有孩子”，不为空就调用getbrother(t->lchild,x)函数输出所有孩子。如

7、果t->data!=x就递归调用遍历左指针和右指针。根节点不存在就结束函数。图4-3 查找孩子4.4 查找某人的双亲先判断根节点是否存在，不存在就函数结束，存在就再判断t->data=x?满足条件就m=NULL，否则判断t->lchild!=NULL&&strcmp(t->lchild->data,x)=0满足条件就m=t，否则就再判断t->rchild!=NULL&&strcmp(t->rchild->data,x)=0，满足就getparent(a,a,t->data)来查找双亲的双亲，不满足就遍历左指针

8、和右指针。最后输出m->data。图4-4 查找双亲4.5 查找某人的所有祖先先判断根节点是否存在不存在就函数运行完成，存在就再判断节点的左孩子是否存在并且就是关键字，如果满足就输出双亲，并递归调用这个函数，将关键字换成这时后的双亲（即再查找双亲的双亲），否则就判断节点的右孩子是否存在并且是关键字，如果满足就把t->data作为关键字递归调用这个函数继续查找，如果不满足就遍历左孩子和右孩子。图4-5 查找祖先4.6 查找某人的所有兄弟调用查找双亲函数（图4-4）来将双亲节点保存在节点指针m中，然后调用找兄弟函数getbrother(m->lchild,x)来输出除了关键字以外

9、的所有兄弟。5系统测试5.1 主菜单直接选择要进入的下级菜单，输入其他的将提示输入错误重新选择，并清屏重新输出主菜单。图5-1 主菜单5.2 录入家庭成员信息先输入根节点然后根据提示输入相应的家庭关系成员（注：输入兄弟的时候输入前面没有输入过的其他兄弟），没有就输入#，全部输入完成后按任意键返回到主菜单。图5-2 录入家庭成员信息5.3 输出家谱中的所有成员进入后将按代数和亲子关系罗列出说有已经录入的家庭成员。图5-3 查看家庭成员5.4 查找相应的家族成员进入后按提示输入姓名，系统将检测该姓名是否存在，如果不存在则提示用户没有此人并返回主菜单，如果存在就按要求查找相应的家庭成员，如果有满足要

10、求的成员就全部输出，没有就给出提示“没有相应亲属关系的成员”，然后按任意键即可返回主菜单。图5-4 查找某人所有孩子图5-5 查找双亲图5-6 查找祖先图5-7 查找所有兄弟下面给出其他输入的界面：图5-8 输入家谱里面没有的姓名图5-9 d的孩子不存在6 体会通过写这家谱运算的代码，通过树与二叉树之间的灵活转变来实现了对复杂关系的树形家谱运用二叉树链表来保存，克服了树形结构的不方便查找的特性。用队列辅助暂时保存链表节点来灵活处理，运用递归算法用简洁的代码实现那些复杂重复的树变成二叉树遵循左孩子右兄弟的原则。找孩子：左孩子和左孩子的右孩子以及再右孩子是根节点的孩子。找双亲：如果根节点的左孩子是

11、关键字，根节点即为关键字的双亲，如果根节点的右孩子是关键字则说明根节点是关键字的兄弟，需要再查找根节点的双亲，直到找到双亲为止。找祖先：先找到双亲，再把双亲当关键字找双亲的双亲，直到找到根节点所有祖先都找全。找兄弟：先找到关键字的双亲，再找双亲的孩子去除自己就找到兄弟了。22参考文献1 Weiss MA.数据结构与算法分析M.北京：机械工业出版社, 2009:124-126.2 Stephen Prata. C Primer Plus（第五版）中文版M.北京：人民邮电出版社，2005:51-623 Kyle Loudon.算法精解M.北京：机械工业出版社，2012:156-165.4 陈正冲.

12、C语言深度解剖(第2版)M.北京：北京航空航天大学出版社，2012:34-42.5 王道论团组.2016年数据结构联合复习指导M.北京：电子工业出版社，2015:56-78.6 塞奇威克. 算法：C语言实现M.北京：机械工业出版社,2009:213-225.7 维斯 数据结构与算法分析：C语言描述M.北京：机械工业出版社，2010:192-200.8 乔兹德克. C+数据结构与算法(第4版) M.北京: 清华大学出版社，2014:32-56.9 里斯. 深入理解C指针M.北京：人民邮电出版社，2014:103-122.10 汉森. C语言接口与实现M.北京：人民邮电出版社,2011:234-2

13、54.附录：代码#include <iostream>#include <iomanip>using namespace std;#include <string.h>#include <malloc.h>#include <stdlib.h>#define MAXSIZE 100typedef char datatype;typedef struct node /定义二叉树结构datatype data10;struct node *lchild,*rchild;bintnode;typedef bintnode *bintree;

14、 /定义二叉树指针 bintree m; /保存双亲节点typedef struct /队列定义bintree aMAXSIZE;int front;int rear;int n; /队列元素个数int depth; /代数queue;void into(queue *sq) /初始化sq->front=sq->rear=0;sq->n=0;void insert(queue *sq,bintree x) /入队函数if(sq->rear=MAXSIZE)cout<<"顺序表已满！"elsesq->asq->rear=x;sq

15、->rear+;sq->n+;bintree get(queue *sq) /出队函数if(sq->front=sq->rear)return NULL;elsesq->front+;sq->n-;return sq->asq->front-1;bintree input() /录入家族信息datatype ch10;cin>>ch;bintree t;if(strcmp(ch,"#")=0)t=NULL;elset=(bintnode *)malloc(sizeof(bintnode);strcpy(t->

16、data,ch);cout<<"请输入"<<ch<<"的孩子（没有孩子输入#）："t->lchild=input();cout<<"请输入"<<ch<<"的兄弟（没有兄弟输入#）："t->rchild=input();return t;void postorder(bintree t,queue *sq) /输出兄弟并入队if(t)cout<<t->data<<" "insert(s

17、q,t);postorder(t->rchild,sq);void getbrother(bintree t,datatype x) /输出t的所有孩子，不包含xif(t)if(strcmp(t->data,x)!=0)cout<<t->data<<" "getbrother(t->rchild,x); /*利用队列来保存输出的家庭成员，然后在输出下一代时出队用于给出提示出队元素的孩子是谁。外层while循环来判断正在输出第几代成员，内层循环来输出上一代每个人的孩子，并将这些孩子再入队 */void output(bintre

18、e t,queue *sq) /输出家谱cout<<"*第1代*"<<endl;postorder(t,sq);cout<<endl<<endl;int i;for(int x=2;x<=sq->depth;x+)cout<<"*第"<<x<<"代*"<<endl;i=sq->n; /此时n等于一代人的个数while(i!=0) /上一代的依次出队，输出每个人的孩子，并将孩子再入队，上一代人全部出队结束循环 bintree

19、 a=get(sq);if(a->lchild) /判断是否有孩子cout<<a->data<<"的孩子："postorder(a->lchild,sq);cout<<endl;i-;cout<<endl;int depth(bintree t) /求成员代数int h,lh,rh;if(t=NULL)h=0;elseif(t->lchild!=NULL&&t->rchild=NULL)h=1+depth(t->lchild);else if(t->lchild=NUL

20、L&&t->rchild!=NULL)h=depth(t->rchild);else if(t->lchild!=NULL&&t->rchild!=NULL)lh=1+depth(t->lchild);rh=depth(t->lchild);if(lh>=rh)h=lh;elseh=rh;elseh=1;return h;bintree locate(bintree t,datatype x) /查找bintree p;if(t=NULL)return NULL;elseif(strcmp(t->data,x)=0

21、)return t;elsep=locate(t->lchild,x);if(p)return p;elsereturn locate(t->rchild,x);void getchild(bintree t,datatype x) /输出x的孩子if(t)if(strcmp(t->data,x)=0) /查找xif(t->lchild=NULL)cout<<t->data<<"没有孩子"<<endl;elsecout<<t->data<<"的所有孩子为："g

22、etbrother(t->lchild,x);elsegetchild(t->lchild,x);getchild(t->rchild,x);void getparent(bintree t,bintree a,datatype x) /输出x的双亲if(t)if(strcmp(t->data,x)=0) /如果是头节点就没有双亲m=NULL;elseif(t->lchild!=NULL&&strcmp(t->lchild->data,x)=0)m=t; /保存双亲节点else if(t->rchild!=NULL&&am

23、p;strcmp(t->rchild->data,x)=0) /当x在右子树上时找他根节点（兄弟）的双亲getparent(a,a,t->data);elsegetparent(t->lchild,a,x);getparent(t->rchild,a,x);void getparents(bintree t,bintree a,datatype x) /输出x的所有祖先if(t)if(t->lchild!=NULL&&strcmp(t->lchild->data,x)=0)cout<<t->data<<

24、;" " /输出双亲getparents(a,a,t->data); /把双亲作为关键字递归输出双亲的双亲else if(t->rchild!=NULL&&strcmp(t->rchild->data,x)=0) /当x在右子树上时找他根节点（兄弟）的双亲getparents(a,a,t->data);elsegetparents(t->lchild,a,x);getparents(t->rchild,a,x);void getbrothers(bintree t,bintree a,datatype x) /输出x

25、的所有兄弟getparent(a,a,x); /先找出x的双亲getbrother(m->lchild,x); /根据双亲找出x的兄弟void menu()cout<<endl<<endl;cout<<"tt *"<<"欢迎进入家谱管理系统"<<"*"<<endl;cout<<endl;cout<<"ttt"<<"1、输入家庭成员"<<endl;cout<<&

26、quot;ttt"<<"2、输出家谱中所有成员"<<endl;cout<<"ttt"<<"3、查找某人的所有孩子"<<endl;cout<<"ttt"<<"4、查找某人的双亲"<<endl;cout<<"ttt"<<"5、查找某人的所有祖先"<<endl;cout<<"ttt"<

27、<"6、查找某人的所有兄弟"<<endl;cout<<"ttt"<<"0、退出"<<endl;void main()bintree tree; /定义二叉树变量queue q; /定义队列变量into(&q); /队列初始化int choice;dosystem("cls");menu();cout<<endl<<"请输入您的选择："cin>>choice;switch(choice)case 1:

28、system("cls");cout<<"请输入第一代人："tree=input();q.depth=depth(tree);system("pause");break;case 2:system("cls");output(tree,&q);cout<<endl;system("pause");break;case 3:system("cls");cout<<"请输入此人姓名："datatype a10;cin>>a;if(locate(tree,a)=NULL)cout<<"没有此人"<<endl;elsegetchild(tree,a);cout<<endl<<endl;system("pause");break;case 4:system("cls");cout<<"请输入此人姓名："dat