数据结构课程设计家族关系.docx
《数据结构课程设计家族关系.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计家族关系.docx（22页珍藏版）》请在冰点文库上搜索。
数据结构课程设计家族关系
课程名称:
《数据结构》课程设计
课程设计题目:
家族关系查询系统
姓名:
周楠
院系:
计算机学院
专业:
软件工程
年级:
2011
学号:
E01114323
指导教师:
王爱平
2013年9月25日
1课程设计的目的…………………………
2需求分析…………………………………
3课程设计报告内容………………………
3.1概要设计…………………………………
3.2详细设计…………………………………
3.3调试分析…………………………………
3.4用户手册………………………………
3.5测试结果…………………………………
3.6程序清单………………………………
4小结………………………………………
5参考文献…………………………………
1.课程设计的目的
（1）熟练使用C语言编写程序，解决实际问题;
（2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;
（3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;
（4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力;
2.需求分析
随着社会发展，人们使用纸质的家谱已经非常不方便而且不利于在家谱里进行添加和修改。
而用算法设计一个家族关系查询系统则可以解决这个问题。
数据结构的二叉树刚好满足家谱的基本结构。
首先建立一个文件作为家谱，然后在文件中输入字符串，实现了在文件中按照数据的逻辑关系进进输入便可建立相应的三叉链表。
然后就是进行数据的存储、删除及查找工作。
3.算法分析
本次设计研究的是建立家族关系，实现对家族成员关系相关查询的问题。
在设计中使用的数据结构为树状结构，树状结构采用三叉链表实现。
我们在建立好家族关系后将其存储在文件中，在文件中家族关系是以树的形式存储，运用树的操作使家族关系得以准确建立。
家族关系查询系统可分为六大模块，分别是创建、修改、查询、保存、退出等。
建立家族关系模块，建立家族关系并存入文件。
建立时首先输入家族关系的名称，以此名称为名建立文本文件。
接下来按层输入成员姓名，输入一个在文件中写入一个字符串，以回车键结束。
打开一个家族关系。
在界面输入选项名，以家族关系名为文件名打开文件，如果家族关系不存在，返回空；如果存在，打开文件，读取文件。
向家族中添加一个新成员，添加的新成员要根据其父亲确定其在家族中的位置。
首先判断该父亲是否在此家族关系中，若存在，则查找其父亲，将新节点插入其父亲的最后一个孩子之后；若没有孩子，直接作为左孩子插入。
以写入的方式打开文件，更新数组中的信息，然后将数组中的信息写入文件保存，关闭文件。
查找功能模块，查找一个成员的所有祖先及其兄弟，查找一个成员的所有祖先路径，需要从它的父亲一直向上查找带根结点。
查找一个成员的兄弟，一个成员的兄弟为其父亲除了该结点以外的所有孩子。
对于要操作的结点，先判断它是否是根结点，若是根结点，则无兄弟；若不是根结点，则找到该结点的父亲。
接着判断父亲的兄弟是否都存在，如果都不存在，则无兄弟；如果都存在，对父亲的孩子操作。
4.源程序
#include
#include
#include
#include
typedefcharTElemType;
typedefintstatus;
typedefstructBiTPNode{
TElemTypedata[10];
structBiTPNode*parent,*lchild,*rchild;//父亲及左右孩子指针
}BiTPNode,*BiPTree;
BiPTreeP;
BiPTreeT;
//家谱的创建
intCre（）
{
system（"cls"）;
FILE*fp;//声明指向文件的指针
charfilename[40],str[10];
printf（"请输入家谱名称:
"）;
getchar（）;
gets（filename）;//输入家谱名称
while（filename[0]==NULL）
{
printf（"家谱名不能为空,请重新输入:
"）;
gets（filename）;
}
if（（fp=fopen（filename,"w"））==NULL）
{
printf（"%s家谱创建失败!
\n",filename）;
return0;
}
printf（"请输入家谱内容:
\n"）;
while（strlen（gets（str））>0）
{
fputs（str,fp）;//向文件写入字符串
putc（'\n',fp）;
}
fclose（fp）;//关闭文件
printf（"按任一键继续!
"）;
getch（）;
return1;
}
statusloc（BiPTreeT,BiPTree&P,TElemTypename[10]）{
if（T）
{
P=T;
//字符串的比较
if（!
strcmp（name,T->data））return1;
if（loc（T->lchild,P,name））return1;
if（loc（T->rchild,P,name））return1;
}
else
return0;
}
//构造二叉树
statusinittree（BiPTree&T）{
T=（BiTPNode*）malloc（sizeof（BiTPNode））;
if（T）
return0;
T->lchild=NULL;
T->rchild=NULL;
T->parent=NULL;
return1;
}
//载入家谱
statusCrt（BiPTree&T）{
FILE*fp;
BiPTreeQ,R,M,N;
charfilename[40],name[10];
system（"cls"）;//清屏
R=（BiTPNode*）malloc（sizeof（BiTPNode））;//分配存储空间
M=（BiTPNode*）malloc（sizeof（BiTPNode））;
N=（BiTPNode*）malloc（sizeof（BiTPNode））;
printf（"请输入家谱名:
"）;
getchar（）;
gets（filename）;
while（filename[0]==NULL）
{
printf（"家谱名不能为空,请重新输入:
"）;
gets（filename）;
}
if（（fp=fopen（filename,"r"））==NULL）
{
printf（"%s家谱打开失败!
\n",filename）;
return0;
}
inittree（T）;
fscanf（fp,"%s",name）;//从文件读入姓名
strcpy（T->data,name）;
T->lchild=NULL;
T->rchild=NULL;
T->parent=NULL;
fclose（fp）;
if（（fp=fopen（filename,"r"））==NULL）
{
printf（"%家谱打开失败!
\n",filename）;
return0;
}
fscanf（fp,"%s",name）;
while（!
feof（fp））{
if（loc（T,P,name））{
fscanf（fp,"%s",name）;
Q=（BiTPNode*）malloc（sizeof（BiTPNode））;
strcpy（Q->data,name）;
P->lchild=Q;//构建孩子
Q->parent=P;
Q->lchild=NULL;
Q->rchild=NULL;
N=P;
}
elseif（!
loc（T,P,name））{
Q=（BiTPNode*）malloc（sizeof（BiTPNode））;
R=N;
R=R->lchild;
while（R）{
M=R;
R=R->rchild;}
strcpy（Q->data,name）;
M->rchild=Q;
Q->parent=M;
Q->lchild=NULL;
Q->rchild=NULL;}
fscanf（fp,"%s",name）;
}
printf（"信息载入成功,按任一键继续!
"）;
getch（）;
return1;
}
//添加成员
statusin（BiPTree&T）{
charfather[10],name[10];
BiPTreeQ,M;
system（"cls"）;
printf（"请输入要添加到该家谱中的人的父亲姓名:
"）;
getchar（）;
gets（father）;
while（!
loc（T,P,father））{
printf（"%s不在该家谱中!
请重新输入:
",father）;
gets（father）;}
printf（"请输入要添加到该家谱中的人的姓名:
"）;
gets（name）;
Q=（BiTPNode*）malloc（sizeof（BiTPNode））;
M=（BiTPNode*）malloc（sizeof（BiTPNode））;
strcpy（Q->data,name）;
Q->lchild=NULL;
Q->rchild=NULL;
if（!
P->lchild）{
P->lchild=Q;
Q->parent=P;}
else{
P=P->lchild;
while（P）{
M=P;
P=P->rchild;}
M->rchild=Q;
Q->parent=M;
}
printf（"成员添加成功,按任一键继续!
"）;
getch（）;
return1;
}
//删除成员
statusde（BiPTree&T）{
charname[10];
system（"cls"）;
printf（"请输入要删除的人的姓名:
"）;
getchar（）;
gets（name）;
while（!
loc（T,P,name））{
printf（"%s不在该家谱中!
请重新输入:
",name）;
gets（name）;}
if（!
P->rchild）{
if（P->parent->lchild==P）
P->parent->lchild=NULL;
else
P->parent->rchild=NULL;
free（P）;}
elseif（P->rchild）{
if（P->parent->lchild==P）
P->parent->lchild=P->rchild;
else
P->parent->rchild=P->rchild;
free（P）;}
printf（"成员删除成功,按任一键继续!
"）;
getch（）;
return1;
}
statusShow（TElemTypee[10]）{
printf（"%s",e）;
return1;
}
//二叉树的遍历
statuspre（BiPTreeT,status（*visit）（TElemType[10]））{
if（T）{
if（（*visit）（T->data））
if（pre（T->lchild,visit））
if（pre（T->rchild,visit））return1;
return0;
}
elsereturn1;
}
//家族成员查询
statusSea（BiPTreeT）{
charname[10];
BiPTreeN;
N=（BiTPNode*）malloc（sizeof（BiTPNode））;
system（"cls"）;
printf（"请输入要查寻的人的姓名:
"）;
getchar（）;
gets（name）;
while（!
loc（T,P,name））{
printf（"%s不在该家谱中!
请重新输入:
",name）;
gets（name）;}
N=P;
if（P==T）
printf（"%s的父亲在该家谱中没有记载!
\n",P->data）;
else{
while（N->parent->rchild==N）
N=N->parent;
printf（"%s的父亲是:
%s\n",P->data,N->parent->data）;}
N=P;
if（P==T）
printf（"%s没有兄弟!
\n",P->data）;
elseif（!
P->rchild&&P->parent->rchild!
=P）
printf（"%s没有兄弟!
\n",P->data）;
else{
printf（"%s的兄弟有:
\n",name）;
while（N->rchild）{
printf（"%s",N->rchild->data）;
N=N->rchild;}
N=P;
while（N->parent->rchild==N）{
printf（"%s",N->parent->data）;
N=N->parent;}
printf（"\n"）;
}
if（P==T）
printf（"%s的祖先在该家谱中没有记载!
\n",name）;
else
printf（"%s的祖先是:
%s\n",name,T->data）;
N=P;
if（!
P->lchild）{
printf（"%s没有孩子!
\n",name）;
printf（"%s没有后代\n",name）;}
else{
printf（"%s的孩子有:
\n",name）;
printf（"%s",P->lchild->data）;
N=N->lchild;
while（N->rchild）{
printf（"%s",N->rchild->data）;
N=N->rchild;}
printf（"\n"）;
printf（"%s的后代有:
\n",name）;
pre（P->lchild,Show）;
printf（"\n"）;
}
printf（"按任一键继续!
"）;
getch（）;
return1;
}
//文件的创建
statuswrite（BiPTreeT,charfilename[40]）{
FILE*fp;
if（（fp=fopen（filename,"a+"））==NULL）
{
printf（"%s文件创建失败!
\n",filename）;
return0;
}
fprintf（fp,"%s",T->data）;
T=T->lchild;
while（T）{
fprintf（fp,"%s",T->data）;
T=T->rchild;}
fprintf（fp,"\n"）;//输出
fclose（fp）;
return1;
}
statusprewrite（BiPTreeT,status（*visit）（BiPTree,char[40]）,charfilename[40]）{
if（T）{
if（T->lchild）
（*visit）（T,filename）;
prewrite（T->lchild,visit,filename）;
prewrite（T->rchild,visit,filename）;
return1;}
elsereturn1;
}
statuswrong（）
{
chara;
scanf（"%c",&a）;
printf（"无此选项,请重新选择!
（按任一键继续!
）"）;
getch（）;
return1;
}
//家谱的存储
statusSav（BiPTreeT）{
FILE*fp;
charfilename[40];
system（"cls"）;
printf（"请输入新的文件名:
"）;
getchar（）;
gets（filename）;
while（filename[0]==NULL）
{
printf（"家谱名不能为空,请重新输入:
"）;
gets（filename）;
}
prewrite（T,write,filename）;
printf（"%s家谱保存成功,按任一键继续!
",filename）;
getch（）;
return1;
}
//修改家谱
statusUpd（）{
system（"cls"）;
intxz;
while
（1）
{
system（"cls"）;
printf（"\n\n\n\n"）;
printf（"家族成员的添加与删除操作\n"）;
printf（"请选择\n"）;
printf（"1.添加成员.\n"）;
printf（"2.删除成员.\n"）;
printf（"3.返回上一级.\n"）;
printf（"请选择:
"）;
scanf（"%d",&xz）;
switch（xz）
{
case1:
in（T）;break;
case2:
de（T）;break;
case3:
return0;
default:
wrong（）;
break;
}
}
}
main（）
{
P=（BiTPNode*）malloc（sizeof（BiTPNode））;
intxz;
while
（1）
{
system（"cls"）;
printf（"\n\n\n\n"）;
printf（"家族关系查询系统\n"）;
printf（"具体操作如下\n"）;
printf（"1.创建家谱.\n"）;
printf（"2.载入家谱.\n"）;
printf（"3.修改家谱.\n"）;
printf（"4.查寻成员.\n"）;
printf（"5.保存家谱.\n"）;
printf（"6.退出程序.\n"）;
printf（"请选择操作:
"）;
scanf（"%d",&xz）;
switch（xz）
{
case1:
Cre（）;
break;
case2:
Crt（T）;
break;
case3:
Upd（）;
break;
case4:
Sea（T）;
break;
case5:
Sav（T）;
break;
case6:
return0;
default:
wrong（）;
break;
}
}
}
5运行截图：
升级会员 