人类族谱管理系统设计报告

软件学院综合训练项目报告书课程名称数据结构项目名称人类家谱管理系统专业班级软件13-3班组别第五组成员张伟竹王雨柔何惠民任课教师孙宁目录1.设计时间………………………………………………………………12.设计任务………………………………………………………………13.设计内容………………………………………………………………13.1问题分析…………………………………………………………….13.2程序设计……………………………………………………………33.3测试与分析………………………………………………………..103.3.1测试………………………………………………………..……103.3.2分析………………………………………………………..……143.4代码………………………………………………………………..144.总结与展望………………………………………………………….215.参考文献…………………………………………………………….2211设计时间2014年12月16日——2015年1月6日2设计任务树形结构是一种非常重要的非线性结构，它用于描述数据元素之间的层次关系，人类家谱是树形结构的典型体现，通过此项训练让学生掌握树形结构的知识；使学生重点掌握树与二叉树的转换，二叉树的存储和遍历；此项训练要求构造一棵家谱树，并完成任意成员的查找。3设计内容3.1问题分析1.程序所能达到的功能，见功能模块图（图3-1）。（1）输入家族始祖信息，初始化（或创建）一个家族族谱树。（2）输入要添加人信息，插入新的家族成员。（3）输入要查找人姓名，对家族成员进行查找。（4）输入要修改人姓名，修改某一个家族成员信息。2.输入的形式和输出的形式。输入和输出的姓名可以是中文也可以是英文，变量名为char类型，且最多不得多余20字符，对于某一个人所处代数为数字，变量名为int类型，对输入输出的性别，本设计要求是M或F表示，故必须是英文，为char类型的变量。3.存储结构设计思想。本项目设计采用孩子兄弟链表（二叉链表）方式存储信息，包含一个data域和两个指针域，其中data域又为一个结构体类型，存储某一个人的信息，而对于指针域，一个为child域，指向此人的孩子，另一个为brother域，指向此人的兄弟姐妹，形成如下存储结构，见图3-2。4.测试数据。首先，创建一个家谱，输入始祖的姓名及性别，然后根据菜单要求输入要选择的步骤，本次测试以三代人的家谱为例，输入三代人的姓名及性别，三代人各查找一次，修改某一代人姓名（或性别）后，查找修改人信息，以验证本程序是否正确，最后退出族谱管理系统。当家谱中成员存在时，显示初始化、添加、修改成功等信息。当家谱中不存在此成员2时，系统提示信息有误，要求重新输入所要添加、查找或修改人的信息。图3-1功能模块图图3-2存储结构图33.2程序设计1.本程序中用到的所有抽象数据类型的定义及实现。（1）定义一个data存储结构，存放个人信息。typedefstructnode{charname[MAX];//姓名charsex;//性别intgeneration;//代}node;（2）此处采用孩子兄弟链表法，定义一个结构体存放各代人信息。typedefstructtreenode{structnodel;//家谱中直系家属structtreenode*brother;//用来指向兄弟structtreenode*child;//用来指向孩子}treenode;（3）定义一个指针变量，为treenode类型，指向各代人信息。treenode*root;//root是指向结构体treenode的指针（4）主要函数列表及说明，见表3-1。表3-1主要函数列表及说明函数名及其类型函数功能参数及其类型参数功能InitTreevoid型，无返回值创建一个家族族谱charb[MAX],cinta数组参数b[MAX]存放姓名；参数c代表性别；参数a代表此人是第几代人Addvoid型，无返回值添加家谱新成员intaTreenode*m,*nTreenode*t参数a接收搜索到的代数；m，n，t为三个treenode类型的指针变量，将搜索到的个人信息赋给m，n，tSearchvoid型，无返回值查找家谱成员信息chard[MAX]treenode*n数组参数d[MAX]用于存放姓名；n为treenode类型的指针变量，将搜索到的个人信息赋给nChangevoid型，无返回值修改家谱成员信息chara[MAX],ccharr[MAX]treenode*ninti数组参数a[MAX]存放要修改人的姓名；数组参数r[MAX]存放修改后的姓名；c代表修改的性别；n为treenode类型的指针变量，将搜索到的个人信息赋给n42.主程序的流程图及函数的调用关系图。（1）主函数流程图，见图3-3。图3-3主函数流程图5（2）创建函数流程图，见图3-4。图3-4创建函数流程图（3）查找函数流程图，见图3-5。图3-5查找函数流程图6（4）添加函数流程图，见图3-6。图3-6添加函数流程图7（5）修改函数流程图，见图3-7。图3-7修改函数流程图(6)函数关系调用图，见图3-8。图3-8函数关系调用图83.主要函数伪码算法。（1）创建函数伪码。beginfree(root)root(treenode*)malloc(sizeof(treenode))print“输入始祖姓名及性别：”inputb,c1=aNULL=root-childNULL=root-brotherchildren(root,b,c,a)print“家谱初始化成功！”end（2）添加函数伪码。beginprint“请输入要添加子女的上一代人姓名：”inputdsearch(root,d)=ngeneration(root,d)=awhile(n==NULL){print“此人不存在，请重新输入！”inputdsearch(root,d)}if(n-child==NULL){print“输入孩子的姓名及性别：”inputb,ca+1=asearch(root,b)=mif(m!=NULL)print“出现重名，添加失败！”else{(treenode*)malloc(sizeof(treenode))=n-childNULL=n-child-brotherNULL=n-child-childchildren(n-child,b,c,a)print“家谱成员添加成功！”}else{n-child=n9while(n-brother!=NULL){n-brother=nprint“输入孩子的姓名及性别：”inputb,ca+1=asearch(root,b)=mif(m!=NULL)print“出现重名，添加失败！”else{(treenode*)malloc(sizeof(treenode))=tchildren(t,b,c,a)NULL=t-brotherNULL=t-childt=n-brotherprint“家谱成员添加成功！”}}}end（3）查找函数伪码。beginprint“输入要查找人姓名：”inputdsearch(root,d)=nwhile(n==NULL){print“此人不存在，请重新输入姓名：”inputdsearch(root,d)=n}output(n)end（4）修改函数伪码。beginprint“输入要修改人的姓名：”inputasearch(root,a)=nwhile(n==NULL){print“此人不存在，请重新输入姓名：”inputasearch(root,a)=n10}inputr,c0=iwhile(iMAX){r[i]=r-l.name[i]i+1=i}c=n-l.sexprint“家谱成员信息修改成功！”end3.3测试与分析3.3.1测试1.开始进入菜单选择界面2.运行过程（1）当输入信息正确时初始化（创建）一个家谱11添加家族成员查找家族成员信息12修改家族成员信息查找修改的成员信息（2）当输入错误信息时，系统做出提示，请求重新输入成员信息13添加输入错误信息时查找输入错误信息时修改输入错误信息时查找修改人原名，系统提示不存在3.结束14退出系统3.3.2分析从算法的设计、效率以及实用性上来说：总的来讲，设计不是很严谨，实际生活中的人类家族族谱是有配偶信息的，而且个人信息中不仅包含姓名、性别、双亲、子女，还应该有出生日期、死亡日期、籍贯等信息的。但是在本程序中，大部分信息没有记录族谱中，这是本设计的缺陷所在，故实用性并不高。但是，本设计也有其优点所在，就是有错误信息提示，不论是在添加成员信息，还是查找、修改成员信息时，当输入姓名不存在时，系统会给出错误信息提示，要求重新输入此人姓名。另外，本程序设计了指针搜索函数，便于搜索孩子和双亲信息从改进设想上：本程序设计的设计思想是很简单的，为了能够将家族成员信息记录全面，在存放个人信息的结构体中添加一部分信息，比如此人的出生日期、死亡日期、籍贯等，在存放各代人信息时，添加一个结构体类型的变量，用于存放配偶的信息，以便实现对此人配偶信息的存储，提高实用性。3.4代码#includestdio.h#includemalloc.h#includestring.h#includestdlib.h#defineMAX10typedefstructnode//定义data存储结构，存放个人信息{charname[MAX];//姓名charsex;//性别intgeneration;//代}node;15typedefstructtreenode//创建结构体{structnodel;//家谱中直系家属structtreenode*brother;//用来指向兄弟structtreenode*child;//用来指向孩子}treenode;treenode*root;//root是指向结构体treenode的指针treenode*search(treenode*p,charch[])//搜索指针函数，搜索需要修改和获得的结点，输入头指针，姓名{treenode*q;if(p==NULL)returnNULL;//没有家谱，头指针下为空if(strcmpi(p-l.name,ch)==0)//比较姓名，看是否重名或是否存在returnp;//家谱不为空，头指针下有这个人if(p-brother){q=search(p-brother,ch);//在兄弟中找if(q)returnq;//找到}if(p-child){q=search(p-child,ch);//在孩子中找if(q!=NULL)returnq;//找到}returnNULL;//没有找到}treenode*parent(treenode*p,treenode*q,int*flag)//搜索双亲的指针函数，通过parent函数得到双亲结点。用flag标志，-1为左孩子，1为右孩子{if(p==NULL)returnNULL;//没有家谱，头指针下为空if(p-child==NULL){flag=0;returnNULL;}else{if(p-brother==q){*flag=1;returnp;}16else{if(p-child==q){*flag=-1;returnp;}else{if(p-brother!=NULL){parent(p-brother,q,*&flag);}if(p-child!=NULL){parent(p-child,q,*&flag);}}}}returnp;}intgeneration(treenode*p,charch[])//获得搜索到的成员的代的返回值{treenode*q;if(p==NULL)return0;if(strcmpi(p-l.name,ch)==0)//比较姓名，看是