数据结构课程设计总结报告

郑州轻工业学院 课 程 设 计 任 务 书

题目家族关系查询系统

专业、班级 软件外包11-01学号541107080145 姓名周朱莉 主要内容、基本要求、主要参考资料等： 主要内容：

建立家族关系数据库，实现对家族成员关系的相关查询。

基本要求：

（1）建立家族关系并能存储到文件中； （2）实现家族成员的添加。

（3）可以查询家族成员的双亲、祖先、兄弟、孩子和后代等信息。 课程设计按照教学要求需要一周时间完成，总共要上机调试程序10小时。对每个题目要有需求分析， 在需求分析中，将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，设计或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来。

源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。 程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环；

主要参考资料：数据结构（C语言版），在网上查询的相关资料及部分代码

完 成 期 限：2013.6.18-2013.6.20 指导教师签名： 课程负责人签名：

2013年 6 月 18 日

郑州轻工业学院本科

数据结构课程设计总结报告

设计题目：家族关系查询系统 学生姓名：周朱莉 系别：计算机与通信工程 专业：软件外包 班级：11-01 学号：541107080145 指导教师：卢冰

2013年6月20日

一、 设计题目（任选其一）

家族关系查询系统

二、 运行环境（软、硬件环境）

电脑及Visual C++ 6.0 三、 算法设计的思想

随着社会发展，人们使用纸质的家谱已经非常不方便而且不利于在家谱里进行添加和修改。而用算法设计一个家族关系查询系统则可以解决这个问题。数据结构的二叉树刚好满足家谱的基本结构。

首先建立一个文件作为家谱，然后在文件中输入字符串，实现了在文件中按照数据的逻辑关系进进输入便可建立相应的三叉链表。然后就是进行数据的存储、删除及查找工作。 四、 算法的流程图 家谱的创建：

输入家族成员 输入家谱名称 开始

结束 载入家谱：

结束 家谱是否存在？ 是 载入成功 开始 输入家谱名 否 家谱打开失败 修改家谱：

输入成员姓名 添加成员 返回上一级 删除成员 选择 开始 输入成员姓名 否 成员是否存在？ 是 删除成功 请重新输入

结束 成员查询：

否 输入成员名 开始

成员是否存在？ 是 输出成员信息 不在家谱中，请重新输入 结束 五、 算法设计分析

本次设计研究的是建立家族关系，实现对家族成员关系相关查询的问题。在设计中使用的数据结构为树状结构，树状结构采用三叉链表实现。我们在建立好家族关系后将其存储在文件中，在文件中家族关系是以树的形式存储，运用树的操作使家族关系得以准确建立。家族关系查询系统可分为六大模块，分别是创建、修改、查询、保存、退出等。建立家族关系模块，建立家族关系并存入文件。建立时首先输入家族关系的名称，以此名称为名建立文本文件。接下来按层输入成员姓名，输入一个在文件中写入一

个字符串，以回车键结束。打开一个家族关系。在界面输入选项名，以家族关系名为文件名打开文件，如果家族关系不存在，返回空；如果存在，打开文件，读取文件。向家族中添加一个新成员，添加的新成员要根据其父亲确定其在家族中的位置。首先判断该父亲是否在此家族关系中，若存在，则查找其父亲，将新节点插入其父亲的最后一个孩子之后；若没有孩子，直接作为左孩子插入。以写入的方式打开文件，更新数组中的信息，然后将数组中的信息写入文件保存，关闭文件。查找功能模块，查找一个成员的所有祖先及其兄弟，查找一个成员的所有祖先路径，需要从它的父亲一直向上查找带根结点。查找一个成员的兄弟，一个成员的兄弟为其父亲除了该结点以外的所有孩子。对于要操作的结点，先判断它是否是根结点，若是根结点，则无兄弟；若不是根结点，则找到该结点的父亲。接着判断父亲的兄弟是否都存在，如果都不存在，则无兄弟；如果都存在，对父亲的孩子操作。

六、源代码

#include #include #include #include typedef char TElemType;

typedefint status; typedefstructBiTPNode{ TElemTypedata[10];

structBiTPNode *parent,*lchild,*rchild; //父亲及左右孩子指针

}BiTPNode,*BiPTree; BiPTree P; BiPTree T;

//家谱的创建 intCre() {

system(\

FILE *fp; //声明指向文件的指针 char filename[40],str[10]; printf(\请输入家谱名称:\ getchar();

gets(filename); //输入家谱名称 while(filename[0]==NULL) {

printf(\家谱名不能为空,请重新输入:\ gets(filename);

}

if((fp=fopen(filename,\ {

printf(\家谱创建失败!\\n\ return 0; }

printf(\请输入家谱内容:\\n\ while (strlen(gets(str))>0) {

fputs(str,fp); //向文件写入字符串 putc('\\n',fp); }

fclose(fp); //关闭文件 printf(\按任一键继续!\ getch(); return 1; }

statusloc(BiPTreeT,BiPTree&P,TElemType name[10]){ if(T)

{

P=T; //字符串的比较

if(!strcmp(name,T->data)) return 1; if(loc(T->lchild,P,name)) return 1; if(loc(T->rchild,P,name)) return 1; }

else }

//构造二叉树

statusinittree(BiPTree&T){

T=(BiTPNode *)malloc(sizeof(BiTPNode)); if(T)

return 0;

return 0;

T->lchild=NULL; T->rchild=NULL; T->parent=NULL; return 1; }

//载入家谱

statusCrt(BiPTree&T){ FILE *fp; BiPTree Q,R,M,N;

char filename[40],name[10]; system(\清屏

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,\ {

printf(\家谱打开失败!\\n\

return 0; } inittree(T);

fscanf(fp,\从文件读入姓名 strcpy(T->data,name); T->lchild=NULL; T->rchild=NULL; T->parent=NULL; fclose(fp);

if((fp=fopen(filename,\ {

printf(\家谱打开失败!\\n\ return 0; }

fscanf(fp,\ while(!feof(fp)){ if(loc(T,P,name)){ fscanf(fp,\

Q=(BiTPNode *)malloc(sizeof(BiTPNode)); strcpy(Q->data,name);

P->lchild=Q; //构建孩子 Q->parent=P;

Q->lchild=NULL; Q->rchild=NULL; N=P; } else if(!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,\ }

printf(\信息载入成功,按任一键继续!\ getch(); return 1; }

//添加成员

status in(BiPTree&T){ char father[10],name[10]; BiPTree Q,M; system(\

printf(\请输入要添加到该家谱中的人的父亲姓名:\ getchar(); gets(father);

while(!loc(T,P,father)){

printf(\不在该家谱中!请重新输入:\ 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(); return 1; }

//删除成员

status de(BiPTree&T){ char name[10]; system(\

printf(\请输入要删除的人的姓名:\ getchar(); gets(name);

while(!loc(T,P,name)){

printf(\不在该家谱中!请重新输入:\ gets(name);} if(!P->rchild){

if(P->parent->lchild==P)

P->parent->lchild=NULL; else

P->parent->rchild=NULL; free(P);} else if(P->rchild){ if(P->parent->lchild==P)

P->parent->lchild=P->rchild; else

P->parent->rchild=P->rchild; free(P);}

printf(\成员删除成功,按任一键继续!\ getch(); return 1; }

status Show(TElemType e[10]){

printf(\ \ return 1; }

//二叉树的遍历

status pre(BiPTreeT,status(*visit)(TElemType[10])){ if(T) {

if ((*visit)(T->data)) if (pre(T->lchild,visit))

if (pre(T->rchild,visit)) return 1; return 0; }

else return 1; }

//家族成员查询 status Sea(BiPTree T){ char name[10]; BiPTree N;

N=(BiTPNode *)malloc(sizeof(BiTPNode));

system(\

printf(\请输入要查寻的人的姓名:\ getchar(); gets(name);

while(!loc(T,P,name)){

printf(\不在该家谱中!请重新输入:\ gets(name);} N=P; if(P==T)

printf(\的父亲在该家谱中没有记载!\\n\ else {

while(N->parent->rchild==N) N=N->parent;

printf(\的父亲是:%s\\n\ N=P; if(P==T)

printf(\没有兄弟!\\n\ else if(!P->rchild&&P->parent->rchild!=P) printf(\没有兄弟!\\n\ else {

printf(\的兄弟有:\\n\ while(N->rchild){

printf(\ N=N->rchild;} N=P;

while(N->parent->rchild==N){ printf(\ N=N->parent;} printf(\ } if(P==T)

printf(\的祖先在该家谱中没有记载!\\n\ else

printf(\的祖先是:%s\\n\ N=P; if(!P->lchild){

printf(\没有孩子!\\n\ printf(\没有后代\\n\ else {

printf(\的孩子有:\\n\ printf(\ N=N->lchild; while(N->rchild){

printf(\

N=N->rchild;} printf(\

printf(\的后代有:\\n\ pre(P->lchild,Show); printf(\ }

printf(\按任一键继续!\ getch(); return 1; }

//文件的创建

status write(BiPTreeT,char filename[40]){ FILE *fp;

if((fp=fopen(filename,\ {

printf(\文件创建失败!\\n\ return 0; }

fprintf(fp,\ T=T->lchild; while(T){

fprintf(fp,\ T=T->rchild;} fprintf(fp,\输出 fclose(fp); return 1; } status

prewrite(BiPTreeT,status(*visit)(BiPTree,char[40]),char filename[40]){ if(T) { if (T->lchild)

(*visit)(T,filename); prewrite(T->lchild,visit,filename); prewrite(T->rchild,visit,filename); return 1;} else return 1; }

status wrong() { char a;

scanf(\

printf(\无此选项,请重新选择!(按任一键继续!)\ getch(); return 1; }

//家谱的存储

statusSav(BiPTree T){ FILE *fp; char filename[40]; system(\

printf(\请输入新的文件名:\ getchar(); gets(filename);

while(filename[0]==NULL) {

printf(\家谱名不能为空,请重新输入:\ gets(filename);

}

prewrite(T,write,filename);

printf(\家谱保存成功,按任一键继续!\ getch(); return 1; }

//修改家谱 statusUpd(){ system(\ intxz; while(1) { system(\ printf(\

printf(\◎^*)家族成员的添加与删除操作(*^◎^*) \\n\printf(\◎^*)请选择 (*^◎^*)\\n\printf(\◎^*) 1.添加成员. (*^◎^*)\\n\ printf(\◎^*) 2.删除成员. (*^◎^*)\\n\

printf(\◎^*) 3.返回上一级. (*^◎^*)\\n\ printf(\ 请选择:\ scanf(\

switch(xz) {

case 1 : in(T);break; case 2 : de(T);break; case 3 : return 0; default : wrong();

break;

} } } main() {

P=(BiTPNode *)malloc(sizeof(BiTPNode)); intxz; while(1) { system(\ printf(\

printf(\◎^*) 家族关系查询系统 (*^◎^*) \\n\

printf(\◎^*) 具体操作如下 (*^◎^*) \\n\ printf(\◎^*) 1.创建家谱. (*^◎^*) \\n\ printf(\◎^*) 2.载入家谱. (*^◎^*) \\n\ printf(\◎^*) 3.修改家谱. (*^◎^*) \\n\ printf(\◎^*) 4.查寻成员. (*^◎^*) \\n\ printf(\◎^*) 5.保存家谱. printf(\◎^*) 6.退出程序. printf(\ 请选择操作:\

scanf(\ switch(xz) { case 1 : Cre();

break;

case 2 : Crt(T);

break;

case 3 : Upd();

break;

case 4 :

Sea(T);

(*^◎^*) (*^◎^*) \\n\ \\n\ break;

case 5 :

Sav(T); break;

case 6 :

return 0;

default :

wrong(); break;

} } }

六、 运行结果分析 主界面及其操作选项：

输入家谱名称及家谱内容：

载入已建立家谱：

家族成员的添加及删除主选项：

家族成员的添加：

家族成员的删除：

家族成员的查询操作：

七、 收获及体会

转眼课程设计已经结束，从选择任务到上网查找资料，

到源代码的完成，到代码真正的运行出来。我通过本次数据结构课程设计对数据结构的算法有了更深的了解、对以前学过的知识进行了巩固和提高。

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

次课程设计运用C语言作为数据结构和算法的描述语言对数

据的存储结构和算法进行描述。这次任务提高了我们对实际问题的解决能力，即运用所学的知识对问题进行分析：了解问题的基本要求，怎样将实际问题转化成学科语言的输入输出，要用到什么知识来存储信息。

虽然这次的课程设计有点困难，在网上借鉴了部分代

码的情况下做的还是不够完美，有很多的基本算法思想还不是很理解，但是我没有放弃，让我学会怎样在遇到困难的时候去解决问题，去坚持。同时也让我感受到了数据结构的乐趣，坚定了我学习数据结构的决心。

本文来源：https://www.bwwdw.com/article/a3z3.html