数据结构课程设计（家族关系查询系统）

家族关系查询系统

1 课程设计介绍

1.1课程设计项目简介

家谱是一种以表谱形式，记载一个以血缘关系为主体的家族世

系繁衍和重要人物事迹的特殊图书载体。家谱是中国特有的文化遗产，是中华民族的三大文献之一，属珍贵的人文资料，对于历史学，民俗学，人口学，社会学和经济学的深入研究，均有不可替代的重要功能。本项目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息 、插入家族成员等功能。

1.2课设题目分析

本程序的实质是完成对家谱成员信息的建立、查找、插入等功能。可以首先定义家族成员的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。 本程序包含以下几个模块 （1）建立家族关系树。此模块将构建一个家族关系，对数据初始化，构造关系树并录入数据一遍后续程序使用。 （2）添加新成员。此模块将添加一个新成员，实现对家族关系的修改。

（3）家族关系的查询。此模块将实现对家族不同关系的查询 （4）主程序模块。此模块实现整个程序的进入和进出，以及各种初始化处理。 （5）

1.3课程题目原理与数据结构

因为家族的成员之间存在一个对多个的层次结构关系，所以不能用线性表来表示和实现。家谱从形状上看像一颗倒长的树，所以用树结构来表示比较合适。树形结构是一类非常重要的非线性数据结构，直观看来树是以分支关系定义的层次结构。

因此本课程设计可以采用的数据结构有树状结构和队列。树状结构采用三叉链表来实现，队列采用链式队列实现。

1

家族关系查询系统

1.4功能分析说明图 家族关系查询系统 建 查

2

立一个家族关系打开一个家族关系添加一个家庭成员员按关系查找各个家庭成退出系统找一个成员的祖先查找成员祖先路径查找成员是第几代查找一个成员双亲查找一个成员的兄弟查找成员的堂兄弟查找一个成员的孩子查找成员的子孙后代 家族关系查询系统

2 分析与实现

2.1 基本数据结构和栈队的操作

2.1.1 结点基本数据结构和链队的定义

/*家族关系树实现*/ #include #include #include #include #include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1

#define ERROR -1

#define INFEASIBLE -1 typedef char DataType; #define MAXNUM 20

typedef struct TriTNode/* 树的三叉链表存储结构*/ {

DataType data[MAXNUM];

struct TriTNode *parent;/* 双亲*/ struct TriTNode *lchild;/* 左孩子*/ struct TriTNode *rchild;/* 右孩子*/ }TriTree;

typedef struct Node/* 队列的结点结构*/ {

TriTree *info; struct Node *next; }Node;

typedef struct/* 链接队列类型定义*/ {

struct Node *front; /* 头指针*/

3

家族关系查询系统

struct Node *rear; /* 尾指针*/ }LinkQueue;

DataType fname[MAXNUM],family[50][MAXNUM];/* 全局变量*/

2.1.2 链队的基本操作

LinkQueue *LQueueCreateEmpty( )/* 建立一个空队列*/ {

LinkQueue *plqu=(LinkQueue *)malloc(sizeof(LinkQueue)); if (plqu!=NULL)

plqu->front=plqu->rear=NULL; else { printf(\内存不足！\\n\); return NULL; }

return plqu; }

int LQueueIsEmpty(LinkQueue *plqu)/* 判断链接表示队列是否为空队列*/ {

return(plqu->front==NULL); }

void LQueueEnQueue(LinkQueue *plqu,TriTree *x)/* 进队列*/ {

Node *p=(Node *)malloc(sizeof(Node)); if(p==NULL)

printf(\内存分配失败！\\n\); else {

p->info=x;

p->next=NULL;

if(plqu->front==NULL)/* 原来为空队*/ plqu->front=p; else

plqu->rear->next=p; plqu->rear=p;

4

家族关系查询系统

} }

int LQueueDeQueue(LinkQueue *plqu,TriTree *x)/* 出队列*/ {

Node *p;

if(plqu->front==NULL) { printf(\队列空！\\n\); return ERROR; } else {

p=plqu->front; x=p->info;

plqu->front=plqu->front->next; free(p); return OK; } }

TriTree *LQueueGetFront(LinkQueue *plqu)/* 在非空队列中求队头元素*/ {

return(plqu->front->info); }

2.2建立家族关系

2.2.1 建立家族关系并存入文件

基本思想：首先输入家族关系的名称，以此名称为文件

名，建立文本文件接下来按层次输入结点信息，输入一个在文件中写入一行同时将输入的信息保存

到二位字符数组family中。字符数组family是全局变量，存储临时信息 . 注意，输入时每个结点信息占一行，一个结点有多个

5

家族关系查询系统

}

}

family[i][j]='\\0'; /* 字符串结束标志*/ i++; /* family数组行下标后移*/ j=0; /* family数组列下标归零*/ } ch=fgetc(fp); /* 继续读取文件信息*/ }

fclose(fp); /* 关闭文件*/

t=TriTreeCreate(family); /* 调用函数建立三叉链表*/ printf(\家族关系已成功打开！\\n\); return t;

2.4在家族关系中查找一个成员是否存在

用递归算法实现。如果树空，返回NULL。如果根节点就是要查找的成员，返回根节点；否则，递归查找它的左右子树。

/* 查找一个成员是否存在*/

TriTree *Search(TriTree *t,DataType str[]) {

TriTree *temp;

if(t==NULL) /* 如果树空则返回NULL */ return NULL;

else if(strcmp(t->data,str)==0) /* 如果找到返回该成员指针*/ return t;

else /* 如果没找到遍历左右子树进行查找*/ { temp=Search(t->lchild,str); /* 递归查找*/ if(temp) /* 结点不空则查找*/ return(Search(t->lchild,str)); else return(Search(t->rchild,str)); } }

2.5 向家族中添加一个新成员

11

家族关系查询系统

基本思想：添加的新成员要根据其双亲确定其在家族中的位置。首先判断该双亲是否在此家族关系中，若存在则查找其双亲，将新结点插入其双亲的最后一个孩子之后；若没有孩子，则直接作为左孩子插入。以写入的方式打开文件，如果成功打开，则更新family数组中的信息，并查找新成员的双亲所在位置和其对应的“@”个数，如果“@”个数小于双亲位置，则添加“@”实质相等，新成员不插入到最后“@”之前。最后将family数组中信息写入文件保存，关闭文件。

/* 添加一个新成员*/ void Append(TriTree *t) {

int i=0,j,parpos=1,curpos,num,end=0,count=-1;

DataType chi[MAXNUM],par[MAXNUM];/* 存储输入的孩子和其双亲结点*/

TriTree *tpar,*temp; FILE *fp;

printf(\请输入要添加的成员和其父亲，以回车分隔！\\n. \); gets(chi);

printf(\); /* 以点提示符提示继续输入*/ gets(par);

tpar=Search(t,par); /* 查找双亲结点是否存在*/ if(!tpar) printf(\该成员不存在！\\n\);

else /* 存在则添加其孩子*/ { temp=(TriTree *)malloc(sizeof(TriTree));/* 申请空间*/ temp->parent=tpar; strcpy(temp->data,chi); temp->lchild=NULL; /* 新结点左右孩子置空*/ temp->rchild=NULL; if(tpar->lchild) /* 成员存在左孩子*/ { tpar=tpar->lchild; /* 遍历当前成员左孩子的右子树*/ while(tpar->rchild) /* 当前结点右孩子存在*/ tpar=tpar->rchild; /* 继续遍历右孩子*/ tpar->rchild=temp; /* 将新结点添

12

家族关系查询系统

加到所有孩子之后*/ } else /* 没有孩子则直接添加*/ tpar->lchild=temp; fp=fopen(fname,\); /* 以写入方式打开文件*/ if(fp) { while(strcmp(par,family[i])!=0&&family[i][0]!='#') { if(family[i][0]!='@') /* 查找双亲在数组中位置*/ parpos++; /* parpos计数*/ i++; /* family数组行下标后移*/ } i=0; /* family数组行下标归*/ while(family[i][0]!='#') { if(family[i][0]=='@') /* 查找“@”的个数，第一个不计*/ count++; /* count累加个数*/ if(count==parpos) /* 说明此“@”与其前一个“@”之前为par的孩子*/ curpos=i; /* curpos计当前位置*/ i++; /* family数组行下标后移*/ } if(count

13

家族关系查询系统

{ for(j=i;j>=curpos;j--) /* 当前位置到数组最后的全部信息后移一行*/ strcpy(family[j+1],family[j]); strcpy(family[curpos],chi); /* 将新结点存储到“@”的前一行*/ } if(end==1) /* 若end为，则数组末尾下标后移num位*/ i=i+num; for(j=0;j<=i+1;j++) /* 将数组所有信息写入文件*/ { fputs(family[j],fp); fputc('\\n',fp); /* 一个信息存一行*/ } fclose(fp); /* 关闭文件*/ printf(\添加新成员成功！\\n\); } else printf(\添加新成员失败！\\n\); } }

2.6 家族成员关系的相关查询

2.6.1 查找一个家族的鼻祖

判断输入的姓名是否在该家族中存在，如果存在，则返回该家族的根节点信息。

/* 查找一个家族的祖先*/

void Ancesstor(TriTree *t) /* 返回树的根结点信息*/ {

printf(\该家族的祖先为%s\\n\,t->data); }

14

家族关系查询系统

2.6.2 查找一个成员的所有祖先路径

查找一个成员的所有祖先路径，需要从它的双亲一直向上查找到根结点。

基本思想：对与结点t，先判断它是否是根结点（根节点的双亲是NULL），如果是根结点，直接输出它本身；如果不是，查找它的双亲指针指向的结点，将双亲信息输出。继续查找，直到找到根结点。

/* 查找一个成员的所有祖先*/ void AncesstorPath(TriTree *t) {

if(t->parent==NULL) /* 若该成员为祖先，则直接输出*/ printf(\无祖先！\\n\,t->data);

else /* 否则继续查找祖先*/ { printf(\所有祖先路径：%s\,t->data,t->data); while(t->parent!=NULL)/* 若当前成员的双亲不是祖先，则继续查找*/ { printf(\,t->parent->data); /* 访问当前成员的双亲*/ t=t->parent; /* 继续循环查找*/ } printf(\); } }

2.6.3 查找一个成员的双亲

基本思想：先判断结点t是否是根结点，过不是根结点，

直接输出该结点双亲指针的结点信息；若是根结点，输出提示信息，结点无双亲。

15

家族关系查询系统

/* 查找一个成员的双亲*/ void Parent(TriTree *t) {

if(t->parent!=NULL) /* 若该成员为祖先，则无双亲*/ printf(\的双亲为%s\\n\,t->data,t->parent->data); else printf(\无双亲！\\n\,t->data); }

2.6.4 确定一个成员是第几代

确定一个成员是第几代，只要知道从它本身到根结点包括的祖先个数就可。因而对于跟结点t，从它本身开始一直向上查找到根结点，查找的过程中用变量count（初值为1）计数，最后输出 count。

/* 确定一个成员是第几代*/ void Generation(TriTree *t) {

int count=1; /* 计数*/ DataType str[MAXNUM];

strcpy(str,t->data); /* 存储当前信息*/ while(t->parent!=NULL)/* 查找其双亲*/ {

count++; /* 累加计数*/ t=t->parent; }

printf(\是第%d 代！\\n\,str,count); }

2.6.5 查找一个成员的兄弟

一个成员的为其双亲除了该成员以外的所有孩子。 基本思想：对于结点t，先判断它是否是跟结点，若是根结点，则无兄弟；若不是根结点，则找到结点t的双亲。接着判断双亲的左孩子和左孩子的兄弟是否都存在（若只有左孩子，左孩子就是要查找的这个成员），如果都不存在，则无兄弟；如果

16

家族关系查询系统

都存在，对双亲的左孩子操作。若左孩子不是要查找的这个成员，则将结点信息输出。接下来查找左孩子的右兄弟，判断当前结点是否是要查找的这个成员，若不是，则将结点信息输出，继续查找当前结点的右兄弟，直到NULL为止。

/* 查找一个成员的兄弟*/

void Brothers(TriTree *t,DataType str[]) /* 查找兄弟*/ {

if(t->parent!=NULL) /* 若该结点是祖先，则无兄弟*/ { t=t->parent; /* 该结点的兄弟即为其双亲除该成员以外的所有孩子*/ if(t->lchild&&t->lchild->rchild) /* 当前结点的左孩子及其右孩子都存在*/ { printf(\的所有兄弟有：\,str); t=t->lchild; while(t) /* 遍历当前成员左孩子的右子树*/ { if(strcmp(t->data,str)!=0) /* 遍历右子树，选择输出*/ printf(\ \,t->data); /* 访问当前结点*/ t=t->rchild; } printf(\); } else printf(\无兄弟！\\n\,str); } else printf(\无兄弟！\\n\,str); }

2.6.6 查找一个成员的堂兄弟

一个成员的堂兄弟为其双亲的双亲结点的所有孩子的孩子（该成员除外）.

17

家族关系查询系统

基本思想：如果结点t的双亲和双亲的双亲（爷爷）都存在，首先考虑爷爷的左孩子。如果爷爷的左孩子不是结点t的双亲，那么爷爷还有其他孩子。现对爷爷的左孩子的左孩子访问，如果不是结点t就输出。同样，对爷爷左孩子的左孩子的右孩子、右孩子的右孩子一直访问下去，直到无右孩子为止。如果爷爷还有其他孩子，那么就对爷爷的左孩子的右孩子、爷爷的左孩子的右孩子的右孩子------即对爷爷的其他孩子做相同的处理。

/* 查找一个成员的堂兄弟*/ void Consin(TriTree *t) {

int flag=0; TriTree *ch=t; TriTree *temp;

if(t->parent&&t->parent->parent)/* 当前结点的双亲及其双亲都存在*/ { t=t->parent->parent->lchild;/* 当前结点等于其祖先的第一个孩子*/ while(t) /* 存在则继续查找*/ { if(strcmp(t->data,ch->parent->data)!=0)/* 不是同一结点*/ { if(t->lchild) /* 当前结点存在左孩子*/ { temp=t->lchild; while(temp) /* 遍历当前结点左孩子的右子树*/ { if(strcmp(temp->data,ch->data)!=0) { if(!flag) /* 第一次输入时先输出下句*/ printf(\的所有堂兄弟有：\,ch->data); printf(\ \,temp->data);/* 访问当

18

家族关系查询系统

前成员*/ flag=1; } temp=temp->rchild; /* 继续遍历右孩子*/ } } } t=t->rchild; /* 继续遍历右孩子*/ } printf(\); }

if(!flag) /* 标志没有输出结点*/ printf(\无堂兄弟！\\n\,ch->data); }

2.6.7 查找一个成员的所有孩子

一个成员的所有孩子包括左孩子和左孩子的右孩子、左孩子的右孩子的右孩子----直到右孩子为空为止。

基本思想：首先判断结点t是否有左孩子，如果没有，输出没有孩子；如果有左孩子，输出左孩子的信息，然后判断左孩子的右孩子是否为空，若不为空（存在右孩子），输出左孩子的右孩子的信息，接着循环判断结点是否有右孩子，有就输出，直到右孩子为空。

/* 查找一个成员的所有孩子*/

void Children(TriTree *t) /* 遍历左孩子*/ {

if(t->lchild) /* 当前结点存在左孩子*/ { printf(\的所有孩子有：\,t->data); t=t->lchild; /* 遍历当前成员左孩子的右子树*/ while(t) /* 不空*/ { printf(\ \,t->data);/* 访问当前成员*/ t=t->rchild; }

19

家族关系查询系统

printf(\); } else printf(\无孩子！\\n\,t->data); }

/* 中序遍历一棵树*/

void InOrder(TriTree *t) {

if(t) /* 二叉树存在*/ { InOrder(t->lchild); /* 中序遍历左子树*/ printf(\ \,t->data);/* 访问成员*/ InOrder(t->rchild); /* 中序遍历右子树*/ } }

2.6.8 查找一个成员的子孙后代

一个成员的子孙后代就是其左子树上的所有结点，所以对其左子树进行中序遍历即可。

/* 查找一个成员的子孙后代*/

void Descendants(TriTree *t) /* 遍历左孩子*/ {

if(t->lchild) /* 当前结点存在左孩子*/ { printf(\的所有子孙后代有：\,t->data); InOrder(t->lchild); /* 中序遍历当前结点的左右子树*/ printf(\); } else printf(\无后代！\\n\,t->data); }

2.7 各软件之间的调用方式

该软件各个模块的调用主要是通过声明函数，和定义函数

20

家族关系查询系统

再通过主函数调用实现的。 主函数：

/* 主控函数*/

int main(int argc,char* argv[]) {

DataType str[MAXNUM]=\,input[40]; int i,j,flag,start=0,pos,tag1,tag2; TriTree *temp,*tree=NULL; while(1) { printf(\欢迎使用家族关系查询系统！\\n\); printf(\请输入与之匹配的函数和参数，如parent(C)\\n\); printf(\新建一个家庭关系： Create(familyname) 参数为字符串\\n\); printf(\打开一个家庭关系： Open(familyname) 参数为字符串\\n\); printf(\添加新成员的信息： Append() 无参数\\n\); printf(\查找一个成员的祖先： Ancesstor(name) 参数为字符串\\n\); printf(\查找一个成员的祖先路径：AncesstorPath(name) 参数为字符串\\n\); printf(\确定一个成员是第几代： Generation(name) 参数为字符串\\n\); printf(\查找一个成员的双亲： Parent(name) 参数为字符串\\n\); printf(\查找一个成员的兄弟： Brothers(name) 参数为字符串\\n\); printf(\查找一个成员的堂兄弟： Consin(name) 参数为字符串\\n\); printf(\查找一个成员的孩子： Children(name) 参数为字符串\\n\);

printf(\查找一个成员的子孙后代：Descendants(name) 参数为字符串\\n\); printf(\退出系统： Exit() 无参数\\n? \);

21

家族关系查询系统

gets(input); /* input数组存放输入的函数和参数*/ j=0,tag1=0,tag2=0; for(i=0;i

22

家族关系查询系统

else if(strcmp(input,\)==0) flag=7; else if(strcmp(input,\)==0) flag=8; else if(strcmp(input,\)==0) flag=9; else if(strcmp(input,\)==0) flag=10; else if(strcmp(input,\)==0) flag=11; else if(strcmp(input,\)==0) flag=12; else /* 无匹配则重新输入*/ { printf(\无匹配的函数，请重新输入！\\n\); continue; } if(!(flag==1||flag==2||flag==12)&&start==0) { /* 如果第一次输入函数不是建立、打开或退出，则重新输入*/ printf(\请先建立或打开一个家族关系！\\n\); continue; } start=1; /* 标记不是第一次输入input */ if(flag>=4&&flag<=11) /* 函数需要字符串型参数name */ { temp=Search(tree,str);/* 若存在则返回结点*/ if(!temp) /* 若不存在则返回*/ { printf(\该成员不存在！\\n\); continue; } } switch(flag) /* 根据flag标记调用函数*/ { case 1: tree=Create(str);

23

家族关系查询系统

}

break; case 2: tree=Open(str); break; case 3: Append(tree); break; case 4: Ancesstor(tree); break; case 5: AncesstorPath(temp); break; case 6: Parent(temp); break; case 7: Generation(temp); break; case 8: Brothers(temp,str); break; case 9: Consin(temp); break; case 10: Children(temp); break; case 11: Descendants(temp); break; case 12: exit(OK); } }

return 0;

24

家族关系查询系统

3 调试结果

调试运行后，显示主界面

1) 新建一个家族关系

25

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