数据结构
实验 家族族谱项目
一、家族族谱项目的问题分析
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<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<fstream>
#define MAXSIZE 100
using 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 2:
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<n-1;i++)
for(j=i+1;j<n;j++)
if(strcmp(bir[i],bir[j])>0)
{
strcpy(t,bir[i]);
strcpy(bir[i],bir[j]);
strcpy(bir[j],t);
}
for(i=0;i<n;i++)
{
p=search_birth(bt,bir[i]);
output(p);
}
puts("");
}
void menu()
{
printf("1.显示家谱图\n");
printf("2.层次遍历家谱图\n");
printf("3.显示第n代人的所有信息\n");
printf("4.按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）\n");
printf("5.按照出生日期查询成员名单\n");
printf("6.输入两人姓名，确定其关系\n");
printf("7.给某成员添加孩子\n");
printf("8.删除某成员（若其还有后代，则一并删除）\n");
printf("9.修改某成员信息\n");
printf("10.按出生日期对家谱中所有人排序\n");
printf("11.退出系统\n");
}
int main()
{
BiTree bt;
int wedding1,health1,i,j,n,x=0;
char bir[20][20],name1[20],birth1[20],add1[20],death_date1[20];
printf("欢迎来到家谱管理系统！\n");
bt=create();
LL1:menu();
printf("\n请输入你的选择:\n");
scanf("%d",&i);
switch(i)
{
case 1:show_family(bt);
goto LL1;
break;
case 2:
level(bt);
goto LL1;
break;
case 3:
printf("你想查找第几代的信息呀？\n");
scanf("%d",&n);
show_which_level(bt,n);
goto LL1;
break;
case 4:
search_3dai(bt);
goto LL1;
break;
case 5:
search_birthday(bt);
goto LL1;
break;
case 6:
ralationship(bt);
goto LL1;
break;
case 7:
add(bt);
show_family(bt);
level(bt);
goto LL1;
break;
case 8:
delete_name(bt);
show_family(bt);
level(bt);
goto LL1;
break;
case 9:
update(bt);
show_family(bt);
level(bt);
goto LL1;
break;
case 10:
transport(bt,bir,x);
sort_birth(bt,bir,x);
goto LL1;
break;
case 11:
printf("谢谢你的使用，再见啦！\n");
exit(0);
default:
printf("你的输入有误，请重新输入！\n");
goto LL1;
break;
}
}四、实验结果
文章出处登录后可见！
已经登录？立即刷新
