数据结构课程设计家族关系

1、课程名称：数据结构课程设计 课程设计题目：家族关系查询系统 姓名：周楠院系：计算机学院专业：软件工程年级: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、理论知识和方法独立分析和解决问题的能力 ;2. 需求分析 随着社会发展，人们使用纸质的家谱已经非常不方便而且不利于在家谱里进行 添加和修改。而用算法设计一个家族关系查询系统则可以解决这个问题。数据 结构的二叉树刚好满足家谱的基本结构。首先建立一个文件作为家谱，然后在 文件中输入字符串，实现了在文件中按照数据的逻辑关系进进输入便可建立相 应的三叉链表。然后就是进行数据的存储、删除及查找工作。3. 算法分析 本次设计研究的是建立家族关系，实现对家族成员关系相关查询的问题。在设 计中使用的数据结构为树状结构，树状结构采用三叉链表实现。我们在建立好 家族关系后将其存储在文件中，在文件中家族关系是以树的

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

4、子，直接作为左孩子插入。以写入的方式打开文件，更 新数组中的信息，然后将数组中的信息写入文件保存，关闭文件。查找功能模 块，查找一个成员的所有祖先及其兄弟，查找一个成员的所有祖先路径，需要 从它的父亲一直向上查找带根结点。查找一个成员的兄弟，一个成员的兄弟为 其父亲除了该结点以外的所有孩子。对于要操作的结点，先判断它是否是根结 点，若是根结点，则无兄弟；若不是根结点，则找到该结点的父亲。接着判断 父亲的兄弟是否都存在，如果都不存在，则无兄弟；如果都存在，对父亲的孩 子操作。4. 源程序#include <stdio.h>#include <stdlib.h>#inclu

5、de <string.h> #include<conio.h> typedef char TElemType; typedef int status;typedef struct BiTPNodeTElemType data10;父亲及左右孩子指针struct BiTPNode *parent,*lchild,*rchild; / BiTPNode,*BiPTree;BiPTree P;BiPTree T;/ 家谱的创建int Cre()system("cls");FILE *fp; /声明指向文件的指针char 40,str10;printf(&q

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

7、); /关闭文件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;elsereturn 0;/ 构造二叉树status inittree(BiPTree &T)T=(BiTPNode

8、*)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 40,name10; system("cls"); / 清屏 R=(BiTPNode *)malloc(sizeof(BiTPNode); / M=(BiTPNode *)malloc(sizeof(BiTPNode); N=(

9、BiTPNode *)malloc(sizeof(BiTPNode); printf(" 请输入家谱名 :"); getchar(); gets();while(0=NULL)printf(" 家谱名不能为空 , 请重新输入 :"); gets(); if(fp=fopen(,"r")=NULL)家谱打开失败 !n",); printf("%s return 0;inittree(T);fscanf(fp,"%s",name); / 从文件读入姓名 strcpy(T->data,name)

10、;T->lchild=NULL;T->rchild=NULL;T->parent=NULL;fclose(fp);if(fp=fopen(,"r")=NULL)printf("% 家谱打开失败 !n",);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-

11、>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,"%s",name

12、);printf(" 信息载入成功 ,按任一键继续 !"); getch();return 1;/ 添加成员status in(BiPTree &T)char father10,name10;BiPTree Q,M;system("cls");printf(" 请输入要添加到该家谱中的人的父亲姓名 :"); getchar();gets(father);while(!loc(T,P,father)printf("%s 不在该家谱中 ! 请重新输入 :",father); gets(father);print

13、f(" 请输入要添加到该家谱中的人的姓名 :"); 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

14、->parent=M;printf(" 成员添加成功 , 按任一键继续 !");getch();return 1;/ 删除成员 status de(BiPTree &T)char name10; system("cls");printf(" 请输入要删除的人的姓名 :"); getchar();gets(name); while(!loc(T,P,name)printf("%s 不在该家谱中 ! 请重新输入 :",name);gets(name);if(!P->rchild)if(P->p

15、arent->lchild=P)P->parent->lchild=NULL;elseP->parent->rchild=NULL;free(P);else if(P->rchild)if(P->parent->lchild=P)P->parent->lchild=P->rchild;elseP->parent->rchild=P->rchild;free(P);printf(" 成员删除成功 , 按任一键继续 !");getch();return 1;status Show(TElemTy

16、pe 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->rchild,visit) return 1; return 0;else return 1;/ 家族成员查询 status Sea(BiPTree T) char name10; BiPTree N;N=(BiTPNode *)malloc(sizeof(B

17、iTPNode); 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 的父亲

18、是 :%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("%s没有兄弟 !n",P->data);else printf("%s的兄弟有 :n",name);while(N->rchild)printf("%s ",N->rchild->d

19、ata);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);elseprintf("%s的祖先是 :%sn",name,T->data);N=P;if(!P->lchild)printf("%s没有孩子 !n",name);pri

20、ntf("%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

21、("n");printf(" 按任一键继续 !");getch();return 1;/ 文件的创建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->

22、rchild;fprintf(fp,"n"); / 输出 fclose(fp);return 1;40)status prewrite(BiPTree T,status(*visit)(BiPTree,char40),char 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);数据结

23、构课程设计家族关系printf(" getch(); return 1;无此选项,请重新选择 !( 按任一键继续 !)");/ 家谱的存储 status Sav(BiPTree T)FILE *fp;char 40; system("cls");printf(" 请输入新的文件名 :"); getchar();gets(); while(0=NULL)printf(" 家谱名不能为空 , 请重新输入 :"); gets();prewrite(T,write,);printf("%s 家谱保存成功 , 按任

24、一键继续 !",); getch();return 1;/ 修改家谱 status Upd() 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);s