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

1、软 件 学 院 综合训练项目报告书课程名称 数据结构 项目名称 人类家谱管理系统 专业班级 软件13-3班 组 别 第五组 成 员 张伟竹 王雨柔 何惠民 任课教师 孙宁 目 录设计时间1设计任务1设计内容13.1问题分析.13.2 程序设计33.3测试与分析.103.3.1测试.103.3.2分析.143.4代码.14总结与展望.21参考文献.22 1 设计时间 2014年12月16日2015年1月6日2 设计任务 树形结构是一种非常重要的非线性结构，它用于描述数据元素之间的层次关系，人类家谱是树形结构的典型体现，通过此项训练让学生掌握树形结构的知识；使学生重点掌握树与二叉树的转换，二叉树的

2、存储和遍历；此项训练要求构造一棵家谱树，并完成任意成员的查找。3 设计内容 3.1问题分析 程序所能达到的功能，见功能模块图（图3-1）。 （1）输入家族始祖信息，初始化（或创建）一个家族族谱树。 （2）输入要添加人信息，插入新的家族成员。 （3）输入要查找人姓名，对家族成员进行查找。（4）输入要修改人姓名，修改某一个家族成员信息。2.输入的形式和输出的形式。 输入和输出的姓名可以是中文也可以是英文，变量名为char类型，且最多不得多余20字符，对于某一个人所处代数为数字，变量名为int类型，对输入输出的性别，本设计要求是M或F表示，故必须是英文，为char类型的变量。3.存储结构设计思想。

3、本项目设计采用孩子兄弟链表（二叉链表）方式存储信息，包含一个data域和两个指针域，其中data域又为一个结构体类型，存储某一个人的信息，而对于指针域，一个为child域，指向此人的孩子，另一个为brother域，指向此人的兄弟姐妹，形成如下存储结构，见图3-2。4.测试数据。首先，创建一个家谱，输入始祖的姓名及性别，然后根据菜单要求输入要选择的步骤，本次测试以三代人的家谱为例，输入三代人的姓名及性别，三代人各查找一次，修改某一代人姓名（或性别）后，查找修改人信息，以验证本程序是否正确，最后退出族谱管理系统。当家谱中成员存在时，显示初始化、添加、修改成功等信息。当家谱中不存在此成员时，系统提示

4、信息有误，要求重新输入所要添加、查找或修改人的信息。图3-1 功能模块图 图3-2 存储结构图3.2程序设计 1.本程序中用到的所有抽象数据类型的定义及实现。（1）定义一个data存储结构，存放个人信息。 typedef struct node char nameMAX; /姓名 char sex;/性别 int generation;/代 node; （2）此处采用孩子兄弟链表法，定义一个结构体存放各代人信息。 typedef struct treenode struct node l; /家谱中直系家属 struct treenode *brother;/用来指向兄弟 struct tre

5、enode *child;/用来指向孩子 treenode; （3）定义一个指针变量，为treenode类型，指向各代人信息。 treenode *root; /root是指向结构体treenode的指针 （4）主要函数列表及说明，见表3-1。表3-1 主要函数列表及说明函数名及其类型函数功能参数及其类型 参数功能InitTree void型，无返回值创建一个家族族谱char bMAX,cint a数组参数bMAX存放姓名；参数c代表性别；参数a代表此人是第几代人Addvoid型，无返回值添加家谱新成员int aTreenode *m,*nTreenode *t参数a接收搜索到的代数；m，n，

6、t为三个treenode类型的指针变量，将搜索到的个人信息赋给m，n，tSearchvoid型，无返回值查找家谱成员信息char dMAXtreenode *n数组参数dMAX用于存放姓名；n为treenode类型的指针变量，将搜索到的个人信息赋给nChangevoid型，无返回值修改家谱成员信息char aMAX,cchar rMAXtreenode *nint i数组参数aMAX存放要修改人的姓名；数组参数rMAX存放修改后的姓名；c代表修改的性别；n为treenode类型的指针变量，将搜索到的个人信息赋给n 2.主程序的流程图及函数的调用关系图。主函数流程图，见图3-3。 图3-3 主函

7、数流程图创建函数流程图，见图3-4。 图3-4 创建函数流程图查找函数流程图，见图3-5。 图3-5 查找函数流程图添加函数流程图，见图3-6。图3-6 添加函数流程图修改函数流程图，见图3-7。 图3-7 修改函数流程图函数关系调用图，见图3-8。 图3-8 函数关系调用图主要函数伪码算法。（1）创建函数伪码。 begin free(root) root(treenode *)malloc(sizeof(treenode) print “输入始祖姓名及性别：” input b,c 1=a NULL=root-child NULL=root-brother children(root,b,c,

8、a) print “家谱初始化成功！” end添加函数伪码。 begin print “请输入要添加子女的上一代人姓名：” input d search(root,d)=ngeneration(root,d)=a while(n=NULL) print “此人不存在，请重新输入！” input d search(root,d)if(n-child=NULL) print “输入孩子的姓名及性别：” input b,c a+1=a search(root,b)=m if(m!=NULL) print “出现重名，添加失败！” else (treenode *)malloc(sizeof(tree

9、node)=n-child NULL=n-child-brother NULL=n-child-child children(n-child,b,c,a) print “家谱成员添加成功！” else n-child=n while(n-brother!=NULL) n-brother=n print “输入孩子的姓名及性别：” input b,c a+1=a search(root,b)=m if(m!=NULL) print “出现重名，添加失败！” else (treenode *)malloc(sizeof(treenode)=t children(t,b,c,a) NULL=t-br

10、other NULL=t-child t=n-brother print “家谱成员添加成功！” end（3）查找函数伪码。 begin print “输入要查找人姓名：” input d search(root,d)=n while(n=NULL) print “此人不存在，请重新输入姓名：” input d search(root,d)=n output(n) end修改函数伪码。 begin print “输入要修改人的姓名：” input a search(root,a)=n while(n=NULL) print “此人不存在，请重新输入姓名：” input a search(roo

11、t,a)=n input r,c 0=i while(i i+1=i c=n-l.sex print “家谱成员信息修改成功！” end3.3测试与分析3.3.1测试 1. 开始进入菜单选择界面2. 运行过程（1） 当输入信息正确时初始化（创建）一个家谱添加家族成员查找家族成员信息修改家族成员信息查找修改的成员信息当输入错误信息时，系统做出提示，请求重新输入成员信息 添加输入错误信息时查找输入错误信息时修改输入错误信息时查找修改人原名，系统提示不存在3. 结束退出系统3.3.2分析 从算法的设计、效率以及实用性上来说：总的来讲，设计不是很严谨，实际生活中的人类家族族谱是有配偶

12、信息的，而且个人信息中不仅包含姓名、性别、双亲、子女，还应该有出生日期、死亡日期、籍贯等信息的。但是在本程序中，大部分信息没有记录族谱中，这是本设计的缺陷所在，故实用性并不高。但是，本设计也有其优点所在，就是有错误信息提示，不论是在添加成员信息，还是查找、修改成员信息时，当输入姓名不存在时，系统会给出错误信息提示，要求重新输入此人姓名。另外，本程序设计了指针搜索函数，便于搜索孩子和双亲信息从改进设想上：本程序设计的设计思想是很简单的，为了能够将家族成员信息记录全面，在存放个人信息的结构体中添加一部分信息，比如此人的出生日期、死亡日期、籍贯等，在存放各代人信息时，添加一个结构体类型的变量，用于存

13、放配偶的信息，以便实现对此人配偶信息的存储，提高实用性。3.4 代码#include #include #include #include #define MAX 10 typedef struct node/定义data存储结构，存放个人信息 char nameMAX; /姓名 char sex;/性别 int generation;/代node; typedef struct treenode/创建结构体 struct node l; /家谱中直系家属 struct treenode *brother;/用来指向兄弟 struct treenode *child;/用来指向孩子treeno

14、de; treenode *root; /root是指向结构体treenode的指针treenode *search(treenode *p,char ch) / 搜索指针函数，搜索需要修改和获得的结点，输入头指针，姓名 treenode *q; if(p=NULL) return NULL;/没有家谱，头指针下为空 if(strcmpi(,ch)=0)/比较姓名，看是否重名或是否存在 return p;/家谱不为空，头指针下有这个人 if(p-brother) q=search(p-brother,ch);/在兄弟中找 if(q) return q;/找到 if(p-chil

15、d) q=search(p-child,ch);/在孩子中找 if(q!=NULL) return q; /找到 return NULL;/没有找到 treenode *parent(treenode *p,treenode *q,int *flag) /搜索双亲的指针函数，通过parent函数得到双亲结点。用flag标志，-1为左孩子，1为右孩子 if(p=NULL) return NULL;/没有家谱，头指针下为空 if(p-child=NULL) flag=0; return NULL; else if(p-brother=q) *flag=1; return p; else if(p-

16、child=q) *flag=-1; return p; else if(p-brother!=NULL) parent(p-brother,q,*&flag); if(p-child!=NULL) parent(p-child,q,*&flag); return p;int generation(treenode *p,char ch) /获得搜索到的成员的代的返回值 treenode *q; if(p=NULL) return 0; if(strcmpi(,ch)=0) /比较姓名，看是否重名或是否存在 return p-l.generation;/家谱不为空，头指针下有这

17、个人 if(p-brother) q=search(p-brother,ch);/在兄弟中找 if(q) return q-l.generation;/找到 if(p-child) q=search(p-child,ch);/在孩子中找 if(q!=NULL) return q-l.generation; /找到 return 0; void children(treenode *p,char b,char c,int d)/建立家谱孩子结点，创建结点并对l赋值保存 int i; for(i=0;i=bi; p-l.sex=c; p-l.generation=d; void ou

18、tput(treenode *n) /搜索到数据的输出 treenode *t=NULL; printf(此人姓名:%s 性别%c 为第%d代n,,n-l.sex,n-l.generation); printf(n); printf(此人的子女:); /子女输出 if(n-child=NULL) printf(此人无子女!); else if(n-child-brother=NULL) printf(姓名:%s 性别:%ct,,n-child-l.sex); else printf(姓名:%s 性别:%ct,,n-chil

19、d-l.sex); t=n-child-brother; while(t!=NULL) printf(姓名:%s 性别:%ct,,t-l.sex); t=t-brother; printf(n); printf(此人的同辈成员:); /同辈输出 if(n-brother=NULL) printf(此人无同辈成员!); else if(n-brother-brother=NULL) printf(姓名:%s 性别:%ct,,n-brother-l.sex); else printf(姓名:%s 性别:%ct,,n-b

20、rother-l.sex); t=n-brother-brother; while(t!=NULL) printf(姓名:%s 性别:%ct,,t-l.sex); t=t-brother; void InitTree() /初始化（创建） char bMAX,c; int a; printf( 请输入始祖的姓名性别:); free(root);/释放root （ft）空间 root=(treenode *)malloc(sizeof(treenode); / 创建一个treenode结构体大小的空间 /然后强制转换为treenode *类型的指针然后赋值给root scanf(

21、%s %c,&b,&c);/输入姓名，性别 a=1; root-child=NULL; /清空左右孩子 root-brother=NULL; children(root,b,c,a);/存入结构 printf(家谱初始化成功!n); void Add() /添加 treenode *n,*m,*t=NULL; char bMAX,c,dMAX; int a; printf(请输入要添加子女的上一辈的姓名:); scanf(%s,&d); n=search(root,d); a=generation(root,d); while(n=NULL) /判断是否有重名 printf(此人不在家谱内,请

22、重新输入姓名:); scanf(%s,&d); n=search(root,d); if(n-child=NULL)/孩子信息添加 printf(孩子姓名与性别输入:); scanf(%s %c,&b,&c); a+; m=search(root,b); if(m!=NULL) printf(出现重名，添加失败!n); else n-child=(treenode *)malloc(sizeof(treenode); n-child-brother=NULL; n-child-child=NULL; children(n-child,b,c,a); printf(添加成功!n); else n

23、=n-child; while(n-brother!=NULL) /添加另一个孩子 n=n-brother; printf(孩子姓名与性别输入:); scanf(%s %c,&b,&c); a+; m=search(root,b); if(m!=NULL) printf(出现重名，添加失败!n); else t=(treenode *)malloc(sizeof(treenode); children(t,b,c,a); t-brother=NULL; t-child=NULL; n-brother=t; printf(添加成功!n); void Search() /查找 treenode *

24、n; char dMAX; printf(输入姓名，查找相关信息:); scanf(%s,&d); n=search(root,d); while(n=NULL) printf(此人不存在，请再次输入:); scanf(%s,&d); n=search(root,d); output(n); printf(n); void Change() /修改 char aMAX,rMAX,c; treenode *n; int i; printf(请输入要修改人的姓名:); scanf(%s,&a); n=search(root,a); while(n=NULL) printf(此人不存在,请重新输入姓

25、名:); scanf(%s,&a); n=search(root,a); printf(此人存在，请输入新信息:); scanf(%s %c,&r,&c); for(i=0;i=ri; n-l.sex=c; printf(修改成功!n); int main() int choice; for(;) system(pause); printf(请选择对家谱的操作:n); printf(1.初始化（创建）n); printf(2.添加n); printf(3.查找n); printf(4.修改n); printf(5.退出n); scanf(%d,&choice); switch(choice) case 1:InitTree(); break;/初始化 case 2:Add(); break;/添加 case 3:Search(); break;/查找 case 4:Change(); break;/修改 case 5:exit(0