家谱的实现与设计

1、 课 程 设 计 报 告课程设计名称：数据结构课程设计 系 ： 三系 学 生 姓 名 ： 朱强 班 级： 13软件 学 号： 20130311227 成 绩： 指 导 教 师： 刘杰 开 课 时 间：2014-2015学年一学期设计题目一：家谱的实现与设计一、 实习目的 通过学习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、编码集成以及调试分析，熟练掌握数据结构的选择、设计、实现、以及操作方法，为进一步的开发应用打好基础。二、 问题描述家谱的设计主要是实现对家庭成员信息的建立、查找、插入、修改、删除等功能。可。基本功能如下：（1）家谱祖先数据的录入（树的根结点）。（2）

2、家庭成员的添加：即添加某一人的儿女，儿女的数目由控制台端给出，然后输入相应的儿女姓名（此处儿女的姓名不能重名）。（3）家庭成员的修改：可以修改某一成员的姓名。（4）员的查询：查询某一成员在家族中的辈分（第几代），并能查询此成员的所有子女及这一辈的所有成员。（5）家庭成员的删除：删除此成员时，若其有后代，将删除其所有后代成员。三、 需求分析 该程序所做的工作是对家族成员的的管理，为家族成员对各代成员的姓名，性别及子女情况的记录、查询提供方便。此程序规定： 1.在姓名录入时，姓名为10个字母以内的字符串；性别以M/F表示； 2.程序的输出信息主要为：输出家族成员在家族中的辈分（第几代），并能查询此

3、成员的所有子女及这一辈的所有成员。3.程序的功能主要包括：家谱祖先数据的录入、家庭成员的添加、家庭成员的修改、员的查询、家庭成员的删除；四、 概要设计系统用到的数据有：char nameMAX; char sex; /int generation;1）typedef struct node /定义data存储结构2）typedef struct ft /创建结构体3）ft *search(ft *p,char ch) / 搜索指针函数4）ft *parent(ft *p,ft *q,int *flag) /通过parent函数得到双亲结点。用flag标志，-1为左孩子，1为右孩子 5）int

4、generation(ft *p,char ch) / 获得搜索到的成员的代目的返回值6）void saves(ft *p,char b,char c,int d) /建立家谱孩子结点 创建结点并对l赋值 保存7）void InitTree() /初始化8)void Add() /添加9)void Search() /查询10)void Change() /修改11)void Delete() /删除12)int main() /主函数各程序模块之间的调用关系：主函数12）可以调用7）至11）。五、 详细设计#include <stdio.h>#include <malloc

5、.h>#include <string>#include <stdlib.h>#define MAX 10 typedef struct node /定义data存储结构char nameMAX; /姓名char sex; /性别int generation;/代目node;typedef struct ft /创建结构体struct node l; /家谱中直系家属struct ft *lchild;/用来指向兄弟struct ft *rchild;/用来指向孩子ft;ft *root; /root是结构体ft的指针ft *search(ft *p,char c

6、h) / 搜索指针函数ft *q;if(p=NULL) return NULL;/没有家谱，头指针下为空if(strcmp(p->,ch)=0)return p;/家谱不为空，头指针下有这个人if(p->lchild)q=search(p->lchild,ch);/在兄弟中找if(q) return q;/找到if(p->rchild)q=search(p->rchild,ch); /在孩子中找if(q!=NULL) return q; return NULL;/没有找到ft *parent(ft *p,ft *q,int *flag) /通过pare

7、nt函数得到双亲结点。用flag标志，-1为左孩子，1为右孩子 if(p=NULL)return NULL; /没有家谱，头指针下为空if(p->rchild=NULL)*flag=0;return NULL;elseif(p->lchild=q)*flag=1;return p;else if(p->rchild=q)*flag=-1;return p;elseif(p->lchild!=NULL)parent(p->lchild,q,*&flag);if(p->rchild!=NULL)parent(p->rchild,q,*&fl

8、ag);int generation(ft *p,char ch) / 获得搜索到的成员的代目的返回值ft *q;if(p=NULL) return NULL;if(strcmpi(p->,ch)=0) return p->l.generation; /家谱不为空，头指针下有这个人if(p->lchild)q=search(p->lchild,ch); /在兄弟中找if(q) return q->l.generation; /找到if(p->rchild)q=search(p->rchild,ch); /在孩子中找if(q!=NULL) r

9、eturn q->l.generation;return NULL;void saves(ft *p,char b,char c,int d) /建立家谱孩子结点 创建结点并对l赋值 保存 for(int i=0;i<MAX;i+)p->i=bi; p->l.sex=c;p->l.generation=d;void disp(ft *n) /搜索到数据的输出ft *t=NULL;printf("此人姓名:%s 性别%c 为第%d代n",n->,n->l.sex,n->l.generation); pri

10、ntf("n");printf("此人的子女:"); /子女输出if(n->rchild=NULL)printf("此人无子女!");else if(n->rchild->lchild=NULL)printf("姓名:%s 性别:%ct",n->rchild->,n->rchild->l.sex); else printf("姓名:%s 性别:%ct",n->rchild->,n->rchild->l.se

11、x); t=n->rchild->lchild; while(t!=NULL) printf("姓名:%s 性别:%ct",t->,t->l.sex); t=t->lchild; printf("n"); printf("n"); printf("此人的同辈成员:"); /同辈输出if(n->lchild=NULL)printf("此人无同辈成员!");else if(n->lchild->lchild=NULL)printf(&quo

12、t;姓名:%s 性别:%ct",n->lchild->,n->lchild->l.sex); else printf("姓名:%s 性别:%ct",n->lchild->,n->lchild->l.sex); t=n->lchild->lchild; while(t!=NULL) printf("姓名:%s 性别:%ct",t->,t->l.sex); t=t->lchild; printf("n");void

13、InitTree() /初始化char bMAX,c;int a;printf(" 请输入始祖的姓名 性别:n"); printf("输入姓名(不超过10个字符)n");printf("性别：M/F（男/女) n");printf("格式：XX M(姓名为XX性别男)n");free(root); /释放root （ft） 空间root=(ft *)malloc(sizeof(ft); / 创建一个ft结构体大小的空间 然后强制转换为ft *类型的指针 然后赋值给root ,这时 root指向一个struct di

14、ctree结构体大小的新空间 scanf("%s %c",&b,&c);a=1; /输入姓名，性别root->rchild=NULL; /清空左右孩子root->lchild=NULL; saves(root,b,c,a); /存入结构printf("家谱重构成功!n");void Manu()printf(" *n");printf(" * 请选择对家谱的操作: *n");printf(" * 0.退出 *n");printf(" * 1.添加 *n&qu

15、ot;);printf(" * 2.查找 *n");printf(" * 3.修改 *n");printf(" * 4.删除 *n");printf(" * 5.重构 *n");printf(" *n");void Add() /添加ft *n,*m,*t=NULL; char bMAX,c,dMAX;int i;printf("请输入要添加子女的上一辈的姓名:n"); /判断是否有重名scanf("%s",&d);n=search(root,d)

16、;int a=generation(root,d);while(n=NULL)printf("此人不在家谱内,请重新输入姓名:n");scanf("%s",&d);n=search(root,d); /孩子信息添加if(n->rchild=NULL) printf("孩子姓名与性别输入:n");scanf("%s %c",&b,&c);a+;m=search(root,b);if(m!=NULL)printf("出现重名，添加失败!n");else n->rc

17、hild=(ft *)malloc(sizeof(ft); n->rchild->lchild=NULL;n->rchild->rchild=NULL;saves(n->rchild,b,c,a); printf("添加成功!n");elsen=n->rchild;while(n->lchild!=NULL)n=n->lchild;printf("孩子姓名与性别输入:n");scanf("%s %c",&b,&c);a+;m=search(root,b);if(m!=NU

18、LL) printf("出现重名，添加失败!n");else t=(ft *)malloc(sizeof(ft);saves(t,b,c,a);t->lchild=NULL;t->rchild=NULL;n->lchild=t; printf("添加成功!n"); void Search() /查询ft *n;char dMAX;printf("输入姓名，查找相关信息:n");scanf("%s",&d);n=search(root,d);while(n=NULL)printf("

19、;此人不存在，请再次输入:n");scanf("%s",&d);n=search(root,d);disp(n);void Change() /修改char aMAX,rMAX,c;ft *n;printf("请输入要修改人的姓名:");scanf("%s",&a);n=search(root,a);while(n=NULL)printf("此人不存在,请重新输入姓名:n"); scanf("%s",&a);n=search(root,a);printf(&qu

20、ot;此人存在，请输入新信息:");scanf("%s %c",&r,&c);for(int i=0;i<MAX;i+)n->i=ri;n->l.sex=c;printf("修改成功!n");void Delete() /删除ft *n,*m;int flag;char dMAX,aMAX;printf("请输入要删除人的姓名:");scanf("%s",a);n=search(root,a);while(n=NULL)printf("此人不存在,请

21、重新输入姓名:n");scanf("%s",&a);n=search(root,a); printf("n"); printf("此人已找到!n"); printf("n");m=parent(root,n,&flag);if(flag>0)m->lchild=n->lchild; printf("删除成功!n");else if(flag<0)m->rchild=n->lchild; printf("删除成功!n"

22、;);else if (flag = 0)root->l.generation = NULL;root->l.sex = NULL;strcpy(root->, "");printf("删除成功!n");int main()system("color 5a");InitTree();for(;)system("pause");system("cls");Manu();int choice; scanf("%d",&choice);swit

23、ch(choice)case 0:exit(0); break;/退出case 1:Add(); break;/添加case 2:Search(); break;/查找case 3:Change(); break;/修改case 4:Delete(); break;/删除case 5:InitTree(); break;/初始化return 0;六、 测试分析建立一个家谱，输入第一代人的姓名与性别以上为，在第一代aa下添加子女：bb、cc、dd，在第二代bb下添加子女ee、ff，在cc下添加子女gg修改bb为hh，修改gg为ii，查找一下，发现已修改成功删除ee、hh，查找一下，aa子女hh、

24、bb子女ee本身及其子代已被删除重构家谱，子女信息消除七、 使用说明 首先运行程序，包括六个选项：0.退出家谱系统. 1.家族成员的添加 2. 家族成员的查找3.家族人员姓名及性别修改4.删除家族成员信息. 5.重新建立新的家谱图 然后可以根据不同的需要选择不同的选项进行操作最后退出程序。八、 运行程序过程中产生的问题及采取的措施在调试时，遇到的几个问题如下：（1）建立树时，由于新申请结点的孩子指针、兄弟指针、及双亲指针均未赋空值。而在以后的函数中对树进行递归操作时均以这些指针值中的一个或几个是否为空作为递归结束条件。从而导致调用这些函数时出现系统保护异常（使用了不安全的指针）。（2）刚开始删

25、除结点时，只考虑到删除其本身结点的情况，而删除其孩子结点的情况未考虑到，故在删除某些结点时使树出现了“断链”现象。故在程序代码中对删除某一结点进行操作时，首先要判断此结点是否有孩子及兄弟，然后进行相应操作。（3）刚开始进行程序概要设计时，曾考虑到用控制台下的文本方式作为程序界面，实际操作后发现并不理想。一方面字符形式的界面友好性较差，另一方面显示整个家谱树的信息时不方便。故考虑用VC+中MFC 类自带的树型控件显示家谱层次，而用列表控件显示家谱中的信息。用后效果不错。九、 总结和展望转眼课程设计已经结束，从选择任务到上网查找资料，到源代码的完成，再到真正的代码运行出来，我对数据结构课程设计有了更深的了解、对以前学过的知识进行了巩固和提高。数据结构是计算机程序设计的重要理论技术基础。这次课程设计运用C语言作为描述语言，对二叉树和查找进行描述，这次任务提高了我们对实际问题的解决能力，即运用所学知识对问题进行分析：了解问题的基本要求，怎样将实际问题转化成学科问题的