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

1、郑州轻工业学院课程设计任务书题目专业、班级 软件外包11-01 学号541107080145 姓名 周朱莉主要内容、基本要求、主要参考资料等： 主要内容：建立家族关系数据库，实现对家族成员关系的相关查询基本要求：（1）建立家族关系并能存储到文件中；（2）实现家族成员的添加。（3）可以查询家族成员的双亲、祖先、兄弟、孩子和后代等信息。课程设计按照教学要求需要一周时间完成，总共要上机调试程序10小时。对每个题目要有需求分析，在需求分析中，将题目中要求的功能进行叙述分析， 并且设计解决此问题的数据存储结构，设计或叙述解决此问题的算法，描述算法 建议使用流程图，进行算法分析指明关键语句的时间复杂度。

2、给出实现功能的一 组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来。源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量， 重点功能部分要加上清晰的程序注释。程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环；主要参考资料：数据结构（C语言版），在网上查询的相关资料及部 分代码完成期限：2013618-2013620指导教师签名：课程负责人签名：2013 年 6 月 18 日郑州轻工业学院本科数据结构课程设计总结报告设计题目 ：家族关系查询系统 学生姓名 ：周朱莉 系 别：计算机与通信工程 专 业：软件外包 班 级： 11-01 学 号： 54110

3、7080145 指导教师 ：卢冰2013 年 6 月 20 日一、设计题目（任选其一）家族关系查询系统二、运行环境（软、硬件环境）电脑及 Visual C+6.0三、算法设计的思想随着社会发展，人们使用纸质的家谱已经非常不方便 而且不利于在家谱里进行添加和修改。而用算法设计一个 家族关系查询系统则可以解决这个问题。数据结构的二叉 树刚好满足家谱的基本结构。首先建立一个文件作为家谱，然后在文件中输入字符 串，实现了在文件中按照数据的逻辑关系进进输入便可建 立相应的三叉链表。然后就是进行数据的存储、删除及查 找工作。四、算法的流程图家谱的创建:7 / 29开始结束载入家谱:开始输入家谱名家谱打开失

4、败结束修改家谱:开始选择删除成员添加成员返回上一级输入成员姓名成员是否存在?删除成功成员查询:开始输入成员名成员是否存在?I是输出成员信息结束五、算法设计分析本次设计研究的是建立家族关系，实现对家族成员关 系相关查询的问题。在设计中使用的数据结构为树状结构， 树状结构采用三叉链表实现。我们在建立好家族关系后将 其存储在文件中，在文件中家族关系是以树的形式存储， 运用树的操作使家族关系得以准确建立。家族关系查询系 统可分为六大模块，分别是创建、修改、查询、保存、退 出等。建立家族关系模块，建立家族关系并存入文件。建 立时首先输入家族关系的名称，以此名称为名建立文本文 件。接下来按层输入成员姓名，

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

6、 弟，一个成员的兄弟为其父亲除了该结点以外的所有孩子。 对于要操作的结点， 先判断它是否是根结点， 若是根结点， 则无兄弟；若不是根结点，则找到该结点的父亲。接着判 断父亲的兄弟是否都存在，如果都不存在，则无兄弟；如 果都存在，对父亲的孩子操作。六、源代码#include <stdio.h>#include <stdlib.h>#include <string.h>#include<conio.h>typedef char TElemType;typedef int status;typedef struct BiTPNodeTElemType

7、data10;struct BiTPNode *parent,*lchild,*rchild;/父亲及左右孩子指针BiTPNode,*BiPTree;BiPTree P;BiPTree T;/家谱的创建int Cre()system("cls");FILE *fp; / 声明指向文件的指针char 40,str10;printf(" 请输入家谱名称 :");getchar();gets(); / 输入家谱名称while(0=NULL)printf(" 家谱名不能为空 ,请重新输入 :");gets();9/ 29if(fp=fopen

8、(,"w")=NULL)printf("%s 家谱创建失败 !n",);return 0;printf(" 请输入家谱内容 :n");while (strlen(gets(str)>0)fputs(str,fp); / 向文件写入字符串putc('n',fp);fclose(fp); / 关闭文件printf(" 按任一键继续 !");getch();return 1; status loc(BiPTree T,BiPTree &P,TElemType name10)if(T)P=T;

9、/字符串的比较if(!strcmp(name,T ->data) return 1;if(loc(T ->lchild,P,name) return 1;if(loc(T ->rchild,P,name) return 1;else return 0;/构造二叉树status inittree(BiPTree &T)T=(BiTPNode *)malloc(sizeof(BiTPNode); if(T)return 0;T->lchild=NULL;T->rchild=NULL;T ->parent=NULL; return 1;/载入家谱 stat

10、us Crt(BiPTree &T)FILE *fp;BiPTree Q,R,M,N;char 40,name10;system("cls"); / 清屏/分配存R=(BiTPNode *)malloc(sizeof(BiTPNode); 储空间M=(BiTPNode *)malloc(sizeof(BiTPNode);N=(BiTPNode *)malloc(sizeof(BiTPNode);printf(" 请输入家谱名 :"); getchar();gets();while(0=NULL)printf(" 家谱名不能为空 ,请重新

11、输入 :")gets();if(fp=fopen(,"r")=NULL)printf("%s 家谱打开失败 !n",);return 0; inittree(T); fscanf(fp,"%s",name); / 从文件读入姓名 strcpy(T ->data,name); T->lchild=NULL; T->rchild=NULL;T ->parent=NULL;fclose(fp);if(fp=fopen(,"r")=NULL)printf("% 家谱打开失败 !n

12、",); return 0; 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;else if(!loc(T,P,name)Q=(BiTPNode *)mallo

13、c(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();return 1;/添加成员 status in(BiPTree &T)char father10,name10;

14、BiPTree Q,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

15、(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 name10; s

16、ystem("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;elseP->parent->rchild=NULL;free(P);else if(P->rchild)if(

17、P ->parent ->lchild=P)P->parent->lchild=P ->rchild;elseP->parent->rchild=P ->rchild;free(P);printf(" 成员删除成功 ,按任一键继续 !");getch();return 1; status Show(TElemType e10) printf("%s ",e); return 1;/二叉树的遍历status pre(BiPTree T,status(*visit)(TElemType10)if(T) if (

18、*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 name10;BiPTree N;N=(BiTPNode *)malloc(sizeof(BiTPNode);system("cls");printf(" 请输入要查寻的人的姓名 :");getchar();gets(name);while(!loc(T,P,name)pri

19、ntf("%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 的 父 亲是:sn",P ->data,N->parent->data);N=P;if(P=T)printf("%s 没有兄弟 !n",P ->data);

20、else if(!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

21、->data);N=N ->parent;printf("n");if(P=T)printf("%s 的 祖 先 在 该 家 谱 中 没 有 记 载!n ”, name);elseprintf("%s 的祖先是 :%sn",name,T ->data); N=P;if(!P ->lchild)printf("%s 没有孩子 !n",name);printf("%s 没有后代 n",name); else printf("%s 的孩子有 :n",name);pri

22、ntf("%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();return 1;/文件的

23、创建status write(BiPTree T,char 40)FILE *fp;if(fp=fopen(,"a+")=NULL)printf("%s 文件创建失败 !n",);return 0;fprintf(fp,"%s ",T ->data);T=T ->lchild; while(T)fprintf(fp,"%s ",T ->data);T=T ->rchild; fprintf(fp,"n"); / 输出 fclose(fp);return 1; status

24、 prewrite(BiPTreeT,status(*visit)(BiPTree,char40),char 40)if(T) if (T ->lchild)(*visit)(T,);prewrite(T ->lchild,visit,);prewrite(T ->rchild,visit,);return 1;else return 1;status wrong()char a;scanf("%c",&a);printf(" 无此选项 ,请重新选择 !( 按任一键继 续!)");getch();return 1;/家谱的存储s

25、tatus Sav(BiPTree T)FILE *fp;char 40;system("cls");printf(" 请输入新的文件名 :");getchar();gets();while(0=NULL)printf(" 家谱名不能为空 ,请重新输入 :"); gets();prewrite(T,write,);printf("%s 家谱保存成功 ,按任一键继续 !",); getch();return 1; /修改家谱status Upd() system("cls");int xz;whi

26、le(1) system("cls");printf("nnnn");prin tf("(*A A*) 家族成员的添加与删除操作(*A A*)n");prin tf("(*AA*)请选择(*A A*)n");printf("(*AA*)1.添加成员 .(*A A*)n");printf("(*AA*)2.删除成员 .(*A A*)n");29 / 29prin tf(" (*A八*)3.返回上一级 . A*printf("请选择 :");scan

27、f("%d",&xz);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);int xz;while(1)system("cls"); printf("nnnn");prin tf("(*AA*)家族关系查询系统(*A A*)n");prin tf("(*AA*)具体操作如下(*A A*)n");printf("(*AA*)1.创建家谱 .(*A A*)n");printf("(*AA*)2.载入家谱 .(*A A*)n");printf("(*AA*)3.修改家谱 .(*A A*)n");printf("(*AA*)4.查寻成员