行业知识
数据结构 实验 家族族谱项目
2026-10-21 19:03:09
来源：互联网转载
数据结构
实验 家族族谱项目
一、家族族谱项目的问题分析
1.��计制作自己的家族族谱，确认问题；
家谱记载了一个家族的世系繁衍及重要人物事迹。使用树型结构对家谱进行管理，实现查看祖先和子孙个人信息，插入家族成员，删除家族成员的功能
2.分解问题，写出问题陈述，即把问题分解为各个比较小的问题，区分出紧急、严重性或可能性等问题
（1）.显示家谱图
（2）.层次遍历家谱图
（3）.显示第n代人的所有信息
（4）.按照姓名查询，输出成员信息(包括其本人、父亲、孩子的信息)
（5）.按照出生日期查询成员名单
（6）.输入两人姓名，确定其关系
（7）.给某成员添加孩子
（8）.删除某成员(若其还有后代，则-。并删除)
（9）.修改某成员信息
（10）.按出生日期对家谱中所有人排序
（11）.退出系统
3. 分析选择关键活动，按照问题优先度排序，即制订研究这些问题的先后程序。按照姓名查询，输出成员信息
4. 分析此类问题所需数据的类型、特点、关系等。
采用二叉树来表示家谱。家谱可以看作是一颗树。许多家庭看作一片森林。每个森林都有唯一对应的二叉树。且二叉树非常方便操作和理解。
二、家族族谱项目的结构设计
1.根据问题分析设计一款合适的数据结构
2.选择合适存储结构方案，写出具体的结构体定义
typedef struct Infomation{
char name[20];
char birth[20];
int wedding;
char add[20];
int health;
char death_date[20];
}Info;
typedef struct bnode{
Info person;
struct bnode *lchild,*rchild;
}BNode,*BiTree;
typedef struct{ //循环队列的定义
BiTree queue[MAXSIZE];
int front,rear;
}Queue;
3.设计解决问题的基本功能/操作
1、初始化队列，由void InitQ()函数实现
2、入队，由void EnQueue()函数实现
3、出队，由void DeQueue()函数实现
4、判队空，由int QEmpty()函数实现
5、判队满，由int QFull()函数实现
6、树的左孩子，由void new_left()函数实现
7、树的右孩子，由void new_right()函数实现
8、建立树，由BiTree create()函数实现
9、输出某结点的信息，由void output() 函数实现
10、层次遍历家谱图，由void level()函数实现
11、层次遍历家谱的第n层，由void show_which_level()函数实现
12、找到结点p的双亲并返回，由BiTree Parent()函数实现
13、通过名字找到结点并返回，由BiTree search_name()函数实现
14、找到结点p的孩子存到指针数组child[]中，由void search_child()函数实现
15、显示三代的信息，由void search_3dai()函数实现
16、通过生日找到结点并返回，由BiTree search_birth()函数实现
17、输出生日信息，由void search_birthday()函数实现
18、判断结点p和q是否是同一个爸爸，如果是返回1，否则返回0，由int is_the_same_father()函数实现
19、判断两个人的关系，由void ralationship()函数实现
20、让一个结点拥有孩子，由void add()函数实现
21、删除一个结点和他的孩子们孙子们，由void delete_name()函数实现
22、显示家谱，由void show_family()函数实现
23、修改家谱，由void update()函数实现
24、把家谱中所有人的生日传参给二维数组bir[][]，由void transport()函数实现
25、将二维数组升序排序并输出，由void sort_birth()函数实现
三、代码
#include#include#include#include#include#include#define MAXSIZE 100using namespace std;typedef struct Infomation{ char name[20]; char birth[20]; int wedding; char add[20]; int health; char death_date[20];}Info;typedef struct bnode{ Info person; struct bnode *lchild,*rchild;}BNode,*BiTree; typedef struct{ //循环队列的定义 BiTree queue[MAXSIZE]; int front,rear;}Queue;void InitQ(Queue &Q) //初始化{ Q.front=Q.rear=0;} void EnQueue(Queue &Q,BiTree e) //入队{ Q.rear=(Q.rear+1)%MAXSIZE; Q.queue[Q.rear]=e;} void DeQueue(Queue &Q,BiTree &e) //出队{ Q.front=(Q.front+1)%MAXSIZE; e=Q.queue[Q.front];} int QEmpty(Queue Q) //判队空{ return Q.front==Q.rear;} int QFull(Queue Q) //判队满{ if((Q.rear+1)%MAXSIZE==Q.front) return 1; return 0;}void new_left(BiTree p,Info info){ BiTree q=(BiTree)malloc(sizeof(BNode)); q->person=info; q->lchild=q->rchild=NULL; p->lchild=q;}void new_right(BiTree p,Info info){ BiTree q=(BiTree)malloc(sizeof(BNode)); q->person=info; q->lchild=q->rchild=NULL; p->rchild=q;}BiTree create(){ struct Infomation human[11]={{"John","19000511",1,"nefu",0,"19800401"}, {"Jack","19200721",1,"hit",0,"19900402"}, {"Mary","19230526",1,"mit",0,"19981221"}, {"Tom","19440501",1,"bit",0,"20080419"}, {"Lily","19480711",0,"nefu",0,"20010201"}, {"Ben","19480505",1,"hit",0,"20070401"}, {"June","19490541",1,"baidu",0,"20141111"}, {"Mark","19600430",0,"nefu",1,"I am alive!"}, {"Lucy","19760301",0,"jingdong",1,"I am alive!"}, {"Steven","19770519",1,"alibaba",1,"I am alive!"}, {"Ann","20000101",0,"nefu",1,"I am alive!"}}; BiTree bt; bt=(BiTree)malloc(sizeof(BNode)); bt->person=human[0]; bt->lchild=bt->rchild=NULL; new_left(bt,human[1]); new_right(bt,human[2]); new_left(bt->lchild,human[3]); new_right(bt->lchild,human[4]); new_left(bt->rchild,human[5]); new_right(bt->rchild,human[6]); new_left(bt->lchild->lchild,human[7]); new_right(bt->lchild->lchild,human[8]); new_left(bt->rchild->rchild,human[9]); new_right(bt->rchild->rchild->lchild,human[10]); return bt;}void output(BiTree p)//输出某结点的信息{ printf("%-7s%-7s%7d%12s%10d%17s\n",p->person.name,p->person.birth,p->person.wedding,p->person.add,p->person.health,p->person.death_date);}void level(BiTree t) //层次遍历家谱图{ BiTree q[20],p; int front,rear; front=rear=0; printf("姓名 出生日期 婚否 地址 健在否 ***亡日期\n"); if(t) { rear++; q[rear]=t; while(front!=rear) { front=(front+1)%20; p=q[front]; output(p); if((rear+1)%20!=front&&p->lchild!=NULL) { rear=(rear+1)%20; q[rear]=p->lchild; } if((rear+1)%20!=front&&p->rchild!=NULL) { rear=(rear+1)%20; q[rear]=p->rchild; } } }}void show_which_level(BiTree p,int n) //层次遍历家谱的第n层{ static int depth=0; depth++; if(p) { if(depth==n) { output(p); } show_which_level(p->lchild,n); show_which_level(p->rchild,n); } depth--;}BiTree Parent(BiTree bt,BiTree p) //找到结点p的双亲并返回{ BiTree l_result,r_result; if (!bt||bt==p) return NULL; if (bt->lchild==p||bt->rchild==p) return bt; else { l_result=Parent(bt->lchild,p); r_result=Parent(bt->rchild,p); return l_result?l_result:(r_result?r_result:NULL); }}BiTree search_name(BiTree bt,char na[]) //通过名字找到结点并返回{ BiTree l_result,r_result; if(!bt) return NULL; if(strcmp(bt->person.name,na)==0) return bt; else { l_result=search_name(bt->lchild,na); r_result=search_name(bt->rchild,na); return l_result?l_result:(r_result?r_result:NULL); }}void search_child(BiTree p,BiTree child[]) //找到结点p的孩子存到指针数组child[]中{ child[0]=child[1]=NULL; if(p->lchild!=NULL) child[0]=p->lchild; if(p->rchild!=NULL) child[1]=p->rchild;}void search_3dai(BiTree bt) //显示三代的信息{ char na[20]; BiTree parent,node,child[2]; printf("请输入你想查找的那个人的姓名：\n"); scanf("%s",na); node=search_name(bt,na); parent=Parent(bt,node); search_child(node,child); printf("你查找的这个人的信息为:\n\n"); printf("姓名 出生日期 婚否 地址 健在否 ***亡日期\n"); output(node); printf("他的父亲结点的信息为：\n"); output(parent); if(child[0]!=NULL) { printf("他的左孩子的信息为：\n"); output(child[0]); } if(child[1]!=NULL) { printf("他的右孩子的信息为：\n"); output(child[1]); }}BiTree search_birth(BiTree bt,char bir[]) //通过生日找到结点并返回{ BiTree l_result,r_result; if(!bt) return NULL; if(strcmp(bt->person.birth,bir)==0) return bt; else { l_result=search_birth(bt->lchild,bir); r_result=search_birth(bt->rchild,bir); return l_result?l_result:(r_result?r_result:NULL); }}void search_birthday(BiTree bt) //输出生日信息{ BiTree p; char bir[20]; printf("请输入你想查找的那个人的生日：\n"); scanf("%s",bir); p=search_birth(bt,bir); printf("你想查找的那个人的信息为：\n"); printf("姓名 出生日期 婚否 地址 健在否 ***亡日期\n"); output(p);} int is_the_same_father(BiTree bt,BiTree p,BiTree q) //判断结点p和q是否是同一个爸爸，如果是返回1，否则返回0{ BiTree f1,f2; f1=Parent(bt,p); f2=Parent(bt,q); if(f1==f2) return 1; else return 0;}void ralationship(BiTree bt) //判断两个人的关系{ char name1[20],name2[20]; BiTree s1,s2,f1,f2; printf("请输入第一个人的姓名：\n"); scanf("%s",name1); printf("请输入第二个人的姓名：\n"); scanf("%s",name2); s1=search_name(bt,name1); s2=search_name(bt,name2); f1=Parent(bt,s1); f2=Parent(bt,s2); if(is_the_same_father(bt,s1,s2)==1) printf("他们是亲兄弟关系\n"); else if(is_the_same_father(bt,f1,f2)==1) printf("他们是堂兄弟关系\n"); else if(s1->lchild==s2) printf("%s是%s的左孩子\n",s2->person.name,s1->person.name); else if(s1->rchild==s2) printf("%s是%s右孩子\n",s2->person.name,s1->person.name); else if(s2->lchild==s1) printf("%s是%s的左孩子\n",s1->person.name,s2->person.name); else if(s2->rchild==s1) printf("%s是%s的右孩子\n",s1->person.name,s2->person.name); else printf("这两个人关系太远啦！\n");}void add(BiTree &bt) //让一个结点拥有孩子{ char na[20]; int i; BiTree p; Info new_child; printf("请输入你想让其拥有孩子的那个人的名字：\n"); scanf("%s",na); p=search_name(bt,na); printf("你是想让他有左孩子呀，还是右孩子呀？左孩子请按1,右孩子请按0：\n"); scanf("%d",&i); switch(i) { case 1: if(p->lchild!=NULL) { printf("添加失败！人家已经有左孩子了！\n"); break; } else { printf("请输入新孩子的姓名：\n"); scanf("%s",new_child.name); printf("请输入新孩子的出生日期：\n"); scanf("%s",new_child.birth); printf("新孩子结婚了吗，结婚请按1，没有结婚请按0：\n"); scanf("%d",&new_child.wedding); printf("请输入新孩子的地址：\n"); scanf("%s",new_child.add); printf("新孩子健在吗？健在请按1，***了请按0：\n");\ scanf("%d",&new_child.health); printf("如果新孩子***了，请输入***亡日期，不然请输入-1：\n"); scanf("%s",new_child.death_date); if(strcmp(new_child.death_date,"-1")==0) strcpy(new_child.death_date,"I am alive!"); new_left(p,new_child); } break; case 0: if(p->rchild!=NULL) { printf("添加失败！人家已经有右孩子了！\n"); break; } else { printf("请输入新孩子的姓名：\n"); scanf("%s",new_child.name); printf("请输入新孩子的出生日期：\n"); scanf("%s",new_child.birth); printf("新孩子结婚了吗，结婚请按1，没有结婚请按0：\n"); scanf("%d",&new_child.wedding); printf("请输入新孩子的地址：\n"); scanf("%s",new_child.add); printf("新孩子健在吗？健在请按1，***了请按0：\n");\ scanf("%d",&new_child.health); printf("如果新孩子***了，请输入***亡日期，不然请输入-1：\n"); printf("%s",new_child.death_date); if(strcmp(new_child.death_date,"-1")==0) strcpy(new_child.death_date,"I am alive!"); new_right(p,new_child); } break; default: printf("你的输入有误！\n"); break; }}void delete_name(BiTree &bt) //删除一个结点和他的孩子们孙子们{ char na[20]; BiTree p,f; printf("请输入你想删除的那个人的姓名，删除之后他的孩子孙子们也将一并删除！\n"); scanf("%s",na); p=search_name(bt,na); f=Parent(bt,p); if(f!=NULL) { if(f->lchild==p) { f->lchild=NULL; free(p); } if(f->rchild==p) { f->rchild=NULL; free(p); } } else { bt=NULL; }} void show_family(BiTree bt) //显示家谱{ Queue Q1,Q2; int i=0; BiTree e; InitQ(Q1); InitQ(Q2); if(bt!=NULL) { EnQueue(Q1,bt); while(!QEmpty(Q1)) { while(!QEmpty(Q1)) { DeQueue(Q1,e); EnQueue(Q2,e); } i++; if(i==1) printf("第%d代： ",i); if(i==2) printf("第%d代： ",i); if(i==3) printf("第%d代： ",i); if(i==4) printf("第%d代：",i); if(i==5) printf("第%d代： ",i); while(!QEmpty(Q2)) { DeQueue(Q2,e); printf("%s ",e->person.name); if(!QFull(Q1)&&e->lchild!=NULL) EnQueue(Q1,e->lchild); if(!QFull(Q1)&&e->rchild!=NULL) EnQueue(Q1,e->rchild); } puts(""); } }} void update(BiTree bt){ char na[20]; BiTree p; printf("请输入你想修改孩子的姓名：\n"); scanf("%s",na); p=search_name(bt,na); printf("请输入修改过后的姓名：\n"); scanf("%s",p->person.name); printf("请输入修改过后的出生日期：\n"); scanf("%s",p->person.birth); printf("请问修改过后的那个人结婚了吗？结婚请输入1,没结婚请输入0：\n"); scanf("%d",&p->person.wedding); printf("请输入修改过后的住址：\n"); scanf("%s",p->person.add); printf("请问修改过后的那个人健在吗？健在请输入1，***了请输入0：\n"); scanf("%d",&p->person.health); printf("如果修改过后那个人***了，请输入***亡日期，否则请输入-1：\n"); scanf("%s",p->person.death_date); if(strcmp(p->person.death_date,"-1")==0) strcpy(p->person.death_date,"I am alive!");} void transport(BiTree bt,char bir[][20],int &x) //把家谱中所有人的生日传参给二维数组bir[][]{ if(bt) { strcpy(bir[x++],bt->person.birth); transport(bt->lchild,bir,x); transport(bt->rchild,bir,x); }} void sort_birth(BiTree bt,char bir[][20],int n)//将二维数组升序排序并输出{ char t[20]; int i,j; BiTree p; for(i=0;i
上一篇：怎么把服务器共享到本地?
下一篇：服务器怎么挂机?
