家谱的实现与设计说明.docx

家谱的实现与设计说明.docx

《家谱的实现与设计说明.docx》由会员分享，可在线阅读，更多相关《家谱的实现与设计说明.docx（29页珍藏版）》请在冰点文库上搜索。

家谱的实现与设计说明

课程设计报告

课程设计名称：

数据结构课程设计

系：

三系

学生姓名：

朱强

班级：

13软件

学号：

20130311227

成绩：

指导教师：

刘杰

开课时间：

2014-2015学年一学期

设计题目一：

家谱的实现与设计

一、实习目的

通过学习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、编码集成以及调试分析，熟练掌握数据结构的选择、设计、实现、以及操作方法，为进一步的开发应用打好基础。

二、问题描述

家谱的设计主要是实现对家庭成员信息的建立、查找、插入、修改、删除等功能。

可。

基本功能如下：

（1）家谱祖先数据的录入（树的根结点）。

（2）家庭成员的添加：

即添加某一人的儿女，儿女的数目由控制台端给出，然后输入相应的儿女姓名（此处儿女的姓名不能重名）。

（3）家庭成员的修改：

可以修改某一成员的姓名。

（4）员的查询：

查询某一成员在家族中的辈分（第几代），并能查询此成员的所有子女及这一辈的所有成员。

（5）家庭成员的删除：

删除此成员时，若其有后代，将删除其所有后代成员。

三、需求分析

该程序所做的工作是对家族成员的的管理，为家族成员对各代成员的姓名，性别及子女情况的记录、查询提供方便。

此程序规定：

1.在姓名录入时，姓名为10个字母以内的字符串；性别以M/F表示；

2.程序的输出信息主要为：

输出家族成员在家族中的辈分（第几代），并能查询此成员的所有子女及这一辈的所有成员。

3.程序的功能主要包括：

家谱祖先数据的录入、家庭成员的添加、家庭成员的修改、员的查询、家庭成员的删除；

四、概要设计

系统用到的数据有：

charname[MAX];

charsex;/

intgeneration;

1）typedefstructnode{}//定义data存储结构

2）typedefstructft{}//创建结构体

3）ft*search（ft*p,charch[]）//搜索指针函数

4）ft*parent（ft*p,ft*q,int*flag）//通过parent函数得到双亲结点。

用flag标志，-1为左孩子，1为右孩子

5）intgeneration（ft*p,charch[]）//获得搜索到的成员的代目的返回值

6）voidsaves（ft*p,charb[],charc,intd）//建立家谱孩子结点创建结点并对l赋值保存

7）voidInitTree（）//初始化

8）voidAdd（）//添加

9）voidSearch（）//查询

10）voidChange（）//修改

11）voidDelete（）//删除

12）intmain（）//主函数

各程序模块之间的调用关系：

主函数12）可以调用7）至11）。

五、详细设计

#include

#include

#include

#include

#defineMAX10

typedefstructnode{//定义data存储结构

charname[MAX];//姓名

charsex;//性别

intgeneration;//代目

}node;

typedefstructft{//创建结构体

structnodel;//家谱中直系家属

structft*lchild;//用来指向兄弟

structft*rchild;//用来指向孩子

}ft;

ft*root;//root是结构体ft的指针

ft*search（ft*p,charch[]）//搜索指针函数

{

ft*q;

if（p==NULL）

returnNULL;//没有家谱，头指针下为空

if（strcmp（p->l.name,ch）==0）

returnp;//家谱不为空，头指针下有这个人

if（p->lchild）

{

q=search（p->lchild,ch）;//在兄弟中找

if（q）

returnq;//找到

}

if（p->rchild）

{

q=search（p->rchild,ch）;//在孩子中找

if（q!

=NULL）

returnq;

}

returnNULL;//没有找到

}

ft*parent（ft*p,ft*q,int*flag）//通过parent函数得到双亲结点。

用flag标志，-1为左孩子，1为右孩子

{

if（p==NULL）

returnNULL;//没有家谱，头指针下为空

if（p->rchild==NULL）

{

*flag=0;

returnNULL;

}

else

{

if（p->lchild==q）

{

*flag=1;

returnp;

}

else

{

if（p->rchild==q）

{

*flag=-1;

returnp;

}

else

{

if（p->lchild!

=NULL）

{

parent（p->lchild,q,*&flag）;

}

if（p->rchild!

=NULL）

{

parent（p->rchild,q,*&flag）;

}

}

}

}

}

intgeneration（ft*p,charch[]）//获得搜索到的成员的代目的返回值

{

ft*q;

if（p==NULL）

returnNULL;

if（strcmpi（p->l.name,ch）==0）

returnp->l.generation;//家谱不为空，头指针下有这个人

if（p->lchild）

{

q=search（p->lchild,ch）;//在兄弟中找

if（q）returnq->l.generation;//找到

}

if（p->rchild）

{

q=search（p->rchild,ch）;//在孩子中找

if（q!

=NULL）

returnq->l.generation;

}

returnNULL;

}

voidsaves（ft*p,charb[],charc,intd）//建立家谱孩子结点创建结点并对l赋值保存

{

for（inti=0;i

p->l.name[i]=b[i];

p->l.sex=c;

p->l.generation=d;

}

voiddisp（ft*n）//搜索到数据的输出

{

ft*t=NULL;

printf（"此人姓名:

%s性别%c为第%d代\n",n->l.name,n->l.sex,n->l.generation）;

printf（"\n"）;

printf（"此人的子女:

"）;//子女输出

if（n->rchild==NULL）

{

printf（"此人无子女!

"）;

}

else

{

if（n->rchild->lchild==NULL）

{printf（"姓名:

%s性别:

%c\t",n->rchild->l.name,n->rchild->l.sex）;}

else

{

printf（"姓名:

%s性别:

%c\t",n->rchild->l.name,n->rchild->l.sex）;

t=n->rchild->lchild;

while（t!

=NULL）

{

printf（"姓名:

%s性别:

%c\t",t->l.name,t->l.sex）;

t=t->lchild;

}

}

}

printf（"\n"）;

printf（"\n"）;

printf（"此人的同辈成员:

"）;//同辈输出

if（n->lchild==NULL）

{

printf（"此人无同辈成员!

"）;

}

else

{

if（n->lchild->lchild==NULL）

{printf（"姓名:

%s性别:

%c\t",n->lchild->l.name,n->lchild->l.sex）;}

else

{

printf（"姓名:

%s性别:

%c\t",n->lchild->l.name,n->lchild->l.sex）;

t=n->lchild->lchild;

while（t!

=NULL）

{

printf（"姓名:

%s性别:

%c\t",t->l.name,t->l.sex）;

t=t->lchild;

}

}

}

printf（"\n"）;

}

voidInitTree（）//初始化

{

charb[MAX],c;

inta;

printf（"请输入始祖的姓名性别:

\n"）;

printf（"输入姓名（不超过10个字符）\n"）;

printf（"性别：

[M/F（男/女）]\n"）;

printf（"格式：

XXM（姓名为XX性别男）\n"）;

free（root）;//释放root（ft）空间

root=（ft*）malloc（sizeof（ft））;//创建一个ft结构体大小的空间然后强制转换为ft*类型的指针然后赋值给root,这时root指向一个structdictree结构体大小的新空间

scanf（"%s%c",&b,&c）;a=1;//输入姓名，性别

root->rchild=NULL;//清空左右孩子

root->lchild=NULL;

saves（root,b,c,a）;//存入结构

printf（"家谱重构成功!

\n"）;

}

voidManu（）

{

printf（"*********************************************\n"）;

printf（"*****请选择对家谱的操作:

　　　　*****\n"）;

printf（"*****0.退出　*****\n"）;

printf（"*****　1.添加　*****\n"）;

printf（"*****2.查找　*****\n"）;

printf（"*****3.修改　*****\n"）;

printf（"*****4.删除　*****\n"）;

printf（"*****5.重构*****\n"）;

printf（"*********************************************\n"）;

}

voidAdd（）//添加

{

ft*n,*m,*t=NULL;

charb[MAX],c,d[MAX];

inti;

printf（"请输入要添加子女的上一辈的姓名:

\n"）;//判断是否有重名

scanf（"%s",&d）;

n=search（root,d）;

inta=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->rchild=（ft*）malloc（sizeof（ft））;

n->rchild->lchild=NULL;

n->rchild->rchild=NULL;

saves（n->rchild,b,c,a）;

printf（"添加成功!

\n"）;

}

}

else

{

n=n->rchild;

while（n->lchild!

=NULL）

n=n->lchild;

printf（"孩子姓名与性别输入:

\n"）;

scanf（"%s%c",&b,&c）;

a++;

m=search（root,b）;

if（m!

=NULL）

printf（"出现重名，添加失败!

\n"）;

else

{

t=（ft*）malloc（sizeof（ft））;

saves（t,b,c,a）;

t->lchild=NULL;

t->rchild=NULL;

n->lchild=t;

printf（"添加成功!

\n"）;

}

}

}

voidSearch（）//查询

{

ft*n;

chard[MAX];

printf（"输入姓名，查找相关信息:

\n"）;

scanf（"%s",&d）;

n=search（root,d）;

while（n==NULL）

{

printf（"此人不存在，请再次输入:

\n"）;

scanf（"%s",&d）;

n=search（root,d）;

}

disp（n）;

}

voidChange（）//修改

{

chara[MAX],r[MAX],c;

ft*n;

printf（"请输入要修改人的姓名:

"）;

scanf（"%s",&a）;

n=search（root,a）;

while（n==NULL）

{

printf（"此人不存在,请重新输入姓名:

\n"）;

scanf（"%s",&a）;

n=search（root,a）;

}

printf（"此人存在，请输入新信息:

"）;

scanf（"%s%c",&r,&c）;

for（inti=0;i

n->l.name[i]=r[i];

n->l.sex=c;

printf（"修改成功!

\n"）;

}

voidDelete（）//删除

{

ft*n,*m;

intflag;

chard[MAX],a[MAX];

printf（"请输入要删除人的姓名:

"）;

scanf（"%s",a）;

n=search（root,a）;

while（n==NULL）

{

printf（"此人不存在,请重新输入姓名:

\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"）;

}

elseif（flag<0）

{m->rchild=n->lchild;

printf（"删除成功!

\n"）;

}

elseif（flag==0）

{

root->l.generation=NULL;

root->l.sex=NULL;

strcpy（root->l.name,""）;

printf（"删除成功!

\n"）;

}

}

intmain（）

{

system（"color5a"）;

InitTree（）;

for（;;）

{

system（"pause"）;

system（"cls"）;

Manu（）;

intchoice;

scanf（"%d",&choice）;

switch（choice）

{

case0:

exit（0）;break;//退出

case1:

Add（）;break;//添加

case2:

Search（）;break;//查找

case3:

Change（）;break;//修改

case4:

Delete（）;break;//删除

case5:

InitTree（）;break;//初始化

}

}

return0;

}

六、测试分析

建立一个家谱，输入第一代人的姓名与性别

以上为，在第一代aa下添加子女：

bb、cc、dd，在第二代bb下添加子女ee、ff，在cc下添加子女gg

修改bb为hh，修改gg为ii，查找一下，发现已修改成功

删除ee、hh，查找一下，aa子女hh、bb子女ee本身及其子代已被删除

重构家谱，子女信息消除

七、使用说明

首先运行程序，包括六个选项：

0.退出家谱系统.

1.家族成员的添加

2..家族成员的查找

3.家族人员姓名及性别修改

4.删除家族成员信息.

5.重新建立新的家谱图

然后可以根据不同的需要选择不同的选项进行操作最后退出程序。

八、运行程序过程中产生的问题及采取的措施

在调试时，遇到的几个问题如下：

（1）建立树时，由于新申请结点的孩子指针、兄弟指针、及双亲指针均未赋空值。

而在以后的函数中对树进行递归操作时均以这些指针值中的一个或几个是否为空作为递归结束条件。

从而导致调用这些函数时出现系统保护异常（使用了不安全的指针）。

（2）刚开始删除结点时，只考虑到删除其本身结点的情况，而删除其孩子结点的情况未考虑到，故在删除某些结点时使树出现了“断链”现象。

故在程序代码中对删除某一结点进行操作时，首先要判断此结点是否有孩子及兄弟，然后进行相应操作。

（3）刚开始进行程序概要设计时，曾考虑到用控制台下的文本方式作为程序界面，实际操作后发现并不理想。

一方面字符形式的界面友好性较差，另一方面显示整个家谱树的信息时不方便。

故考虑用VC++中MFC类自带的树型控件显示家谱层次，而用列表控件显示家谱中的信息。

用后效果不错。

九、总结和展望

转眼课程设计已经结束，从选择任务到上网查找资料，到源代码的完成，再到真正的代

码运行出来，我对数据结构课程设计有了更深的了解、对以前学过的知识进行了巩固和提高。

数据结构是计算机程序设计的重要理论技术基础。

这次课程设计运用C语言作为描述语言，对二叉树和查找进行描述，这次任务提高了我们对实际问题的解决能力，即运用所学知识对问题进行分析：

了解问题的基本要求，怎样将实际问题转化成学科问题的输入输出，要运用到什么知识来存储信息。

虽然这次的课程设计有点困难，在网上借鉴了部分代码的情况下做的还是不够完美，有很多的基本算法思想还不是很理解，但是我没有放弃，让我学会怎样在遇到困难的时候去解决问题，去坚持。

同时也让我感受到了数据结构的乐趣，坚定了我学习数据结构的决心。

通过这次课程设计，体会很深刻，将一直以来学到的东西都运用到实际上来，学以致用，对所学知识有了更深刻的理解，同时还发现了许多平时在书本上没有遇见过的问题，促进了自己对知识的渴望，遇见了问题，就希望能够通过查找课外书来解决它们。

刚接触题目的时候，自己就觉得程序很难，但到了自己真正开始编程的时候却发现比想象中更难，很多细节的问题没有预想到，很多关系的处理想得过于简单，以至于实施起来遇到了很大的困难，花了大量的时间。

同时还有一个比较深刻的体会就是要尽量多在源码上作注释，以前编一些功能简单的程序，总能很清楚每个函数和每个变量的作用，但到了做这个课程设计，由于分开了各个功能板块去实现，很多时候是做了后面就忘了前面，后来意识到这个问题，便开始在编程时加入注释，而且是越详细越好，这样做了以后，很多时候需要查看自己原来写的源代码，也能够很方便地了解了，跟上了思路，也方便以后的维护。

关于这个程序的缺点方面，由于自己花的时间不是很多，再加上知识有限，编写出来的界面不够友好,在功能上还是有不完善的地方，譬如说各项数据的统计还没有弄，数据的存储还不够理想等等。

总的来说，通过这次课程设计，收获还是挺多的，也发现了不少的问题，并给自己以后的学习指引了方向，知道自己缺少哪方面的知识，需要补充哪些知识等等。

自己将会以这次作业为契机，看更多编程方面的书籍，不断充实自己的知识库。

参考文献

《数据结构（C语言版）》——清华大学出版社——严蔚敏、吴伟民编著

《PrimerPlus（第五版·中文版）》——人民邮电出版社出版社——StephenPrata编著

《数据结构算法实现及解析》——西安电子科技大学出版社——高一凡编著

《数据结构教程（第四版）》——清华大学出版社——李春葆编著