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

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

2、图，进行算法分析指明关键语句的时间复杂度。给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来 。  源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。  程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环； 主要参考资料：数据结构（C语言版），在网上查询的相关资料及部分代码完 成 期 限： 2013.6.18-2013.6.20 指导教师签名： 课程负责人签名： 2013年 6 月 18 日郑州轻工业学院本科数据结构课程设计总结报告设计题目：家族关系查询系统学

3、生姓名：周朱莉系 别：计算机与通信工程专 业：软件外包班 级：11-01学 号：541107080145指导教师：卢冰 2013年 6 月 20 日一、 设计题目（任选其一） 家族关系查询系统二、 运行环境（软、硬件环境）电脑 及Visual C+ 6.0三、 算法设计的思想随着社会发展，人们使用纸质的家谱已经非常不方便而且不利于在家谱里进行添加和修改。而用算法设计一个家族关系查询系统则可以解决这个问题。数据结构的二叉树刚好满足家谱的基本结构。首先建立一个文件作为家谱，然后在文件中输入字符串，实现了在文件中按照数据的逻辑关系进进输入便可建立相应的三叉链表。然后就是进行数据的存储、删除及查找工作

4、。四、 算法的流程图家谱的创建：开始 输入家谱名称 输入家族成员结束开始载入家谱： 输入家谱名否 家谱打开失败家谱是否存在？是 载入成功结束修改家谱：开始 选择 删除成员返回上一级添加成员 输入成员姓名输入成员姓名 否请重新输入成员是否存在？是删除成功结束成员查询：开始 输入成员名否 不在家谱中，请重新输入成员是否存在？是 输出成员信息结束五、 算法设计分析本次设计研究的是建立家族关系，实现对家族成员关系相关查询的问题。在设计中使用的数据结构为树状结构，树状结构采用三叉链表实现。我们在建立好家族关系后将其存储在文件中，在文件中家族关系是以树的形式存储，运用树的操作使家族关系得以准确建立。 家族

5、关系查询系统可分为六大模块，分别是创建、修改、查询、保存、退出等。建立家族关系模块，建立家族关系并存入文件。建立时首先输入家族关系的名称，以此名称为名建立文本文件。接下来按层输入成员姓名，输入一个在文件中写入一个字符串，以回车键结束。打开一个家族关系。在界面输入选项名，以家族关系名为文件名打开文件，如果家族关系不存在，返回空；如果存在，打开文件，读取文件。向家族中添加一个新成员，添加的新成员要根据其父亲确定其在家族中的位置。首先判断该父亲是否在此家族关系中，若存在，则查找其父亲，将新节点插入其父亲的最后一个孩子之后；若没有孩子，直接作为左孩子插入。以写入的方式打开文件，更新数组中的信息，然后将

6、数组中的信息写入文件保存，关闭文件。查找功能模块，查找一个成员的所有祖先及其兄弟，查找一个成员的所有祖先路径，需要从它的父亲一直向上查找带根结点。查找一个成员的兄弟，一个成员的兄弟为其父亲除了该结点以外的所有孩子。对于要操作的结点，先判断它是否是根结点，若是根结点，则无兄弟；若不是根结点，则找到该结点的父亲。接着判断父亲的兄弟是否都存在，如果都不存在，则无兄弟；如果都存在，对父亲的孩子操作。六、源代码#include <stdio.h> #include <stdlib.h> #include <string.h> #include<conio.h&g

7、t; typedef char TElemType; typedef int status; typedef struct BiTPNode TElemType data10; struct BiTPNode *parent,*lchild,*rchild; /父亲及左右孩子指针BiTPNode,*BiPTree; BiPTree P; BiPTree T; /家谱的创建int Cre() system("cls"); FILE *fp; /声明指向文件的指针 char filename40,str10; printf("请输入家谱名称:"); getc

8、har(); gets(filename); /输入家谱名称 while(filename0=NULL) printf("家谱名不能为空,请重新输入:"); gets(filename); if(fp=fopen(filename,"w")=NULL) printf("%s家谱创建失败!n",filename); return 0; printf("请输入家谱内容:n"); while (strlen(gets(str)>0) fputs(str,fp); /向文件写入字符串 putc('n'

9、,fp); fclose(fp); /关闭文件 printf("按任一键继续!"); getch(); return 1; status loc(BiPTree T,BiPTree &P,TElemType name10) 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 return 0; /构造二叉树status inittree(BiPTr

10、ee &T) T=(BiTPNode *)malloc(sizeof(BiTPNode); if(T) return 0; T->lchild=NULL; T->rchild=NULL; T->parent=NULL; return 1; /载入家谱status Crt(BiPTree &T) FILE *fp; BiPTree Q,R,M,N; char filename40,name10; system("cls"); /清屏 R=(BiTPNode *)malloc(sizeof(BiTPNode); /分配存储空间 M=(BiTPN

11、ode *)malloc(sizeof(BiTPNode); N=(BiTPNode *)malloc(sizeof(BiTPNode); printf("请输入家谱名:"); getchar(); gets(filename); while(filename0=NULL) printf("家谱名不能为空,请重新输入:"); gets(filename); if(fp=fopen(filename,"r")=NULL) printf("%s家谱打开失败!n",filename); return 0; inittre

12、e(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); return 0; fscanf(fp,"%s",name); while(!feof(fp) if(loc(T,P,name) fs

13、canf(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 *)malloc(sizeof(BiTPNode); R=N; R=R->lchild; while(R) M=R; R=R->rchild; strcpy(Q->

14、;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; BiPTree Q,M; system("cls"); printf("请输入要添加到该家谱中的人的父亲姓名:")

15、; 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;

16、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; system("cls"); printf("请输入要删除的人的姓名:"); getchar()

17、; 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); else if(P->rchild) if(P->parent->lchild=P) P->parent->lchild=P->rchild;

18、 else P->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 (*visit)(T->data) if (pre(T->lchild,visit) if (pre(T->

19、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) printf("%s不在该家谱中!请重新输入:",name); gets(name); N=

20、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); else if(!P->rchild&&P->parent->rchild!=P) printf(&

21、quot;%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("

22、;%s的祖先在该家谱中没有记载!n",name); else printf("%s的祖先是:%sn",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) p

23、rintf("%s ",N->rchild->data); N=N->rchild; printf("n"); printf("%s的后代有:n",name); pre(P->lchild,Show); printf("n"); printf("按任一键继续!"); getch(); return 1; /文件的创建status write(BiPTree T,char filename40) FILE *fp; if(fp=fopen(filename,"a+

24、")=NULL) printf("%s文件创建失败!n",filename); 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 prewrite(BiPTree T,status(*visit)(BiPTree,char40),char

25、 filename40) 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("%c",&a); printf("无此选项,请重新选择!(按任一键继续!)"); getch(); return 1; /家谱的存储status Sav(BiPTree

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

27、system("cls"); int xz; while(1) system("cls"); printf("nnnn");printf("(*)家族成员的添加与删除操作(*) n");printf("(*) 请选择 (*)n"); printf("(*) 1.添加成员. (*)n"); printf("(*) 2.删除成员. (*)n"); printf(" (*) 3.返回上一级. (*)n"); printf(" 请选择:"); scanf("%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"); printf("(*) 家族关系查询系统 (*) n"); pri