數(shù)據(jù)結(jié)構(gòu)

實驗 家族族譜項目

一、家族族譜項目的問題分析

1.設(shè)計制作自己的家族族譜，確認(rèn)問題；

?家譜記載了一個家族的世系繁衍及重要人物事跡。使用樹型結(jié)構(gòu)對家譜進行管理，實現(xiàn)查看祖先和子孫個人信息，插入家族成員，刪除家族成員的功能

2.分解問題，寫出問題陳述，即把問題分解為各個比較小的問題，區(qū)分出緊急、嚴(yán)重性或可能性等問題

（1）.顯示家譜圖
（2）.層次遍歷家譜圖
（3）.顯示第n代人的所有信息
（4）.按照姓名查詢，輸出成員信息(包括其本人、父親、孩子的信息)?
（5）.按照出生日期查詢成員名單
（6）.輸入兩人姓名，確定其關(guān)系
（7）.給某成員添加孩子
（8）.刪除某成員(若其還有后代，則-。并刪除)
（9）.修改某成員信息
（10）.按出生日期對家譜中所有人排序
（11）.退出系統(tǒng)

3. 分析選擇關(guān)鍵活動，按照問題優(yōu)先度排序，即制訂研究這些問題的先后程序。按照姓名查詢，輸出成員信息

4. 分析此類問題所需數(shù)據(jù)的類型、特點、關(guān)系等。

采用二叉樹來表示家譜。家譜可以看作是一顆樹。許多家庭看作一片森林。每個森林都有唯一對應(yīng)的二叉樹。且二叉樹非常方便操作和理解。

二、家族族譜項目的結(jié)構(gòu)設(shè)計

1.根據(jù)問題分析設(shè)計一款合適的數(shù)據(jù)結(jié)構(gòu)

2.選擇合適存儲結(jié)構(gòu)方案，寫出具體的結(jié)構(gòu)體定義

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{???//循環(huán)隊列的定義
????BiTree?queue[MAXSIZE];
????int?front,rear;
}Queue;

3.設(shè)計解決問題的基本功能/操作

1、初始化隊列，由void?InitQ()函數(shù)實現(xiàn)
2、入隊，由void?EnQueue()函數(shù)實現(xiàn)
3、出隊，由void?DeQueue()函數(shù)實現(xiàn)
4、判隊空，由int?QEmpty()函數(shù)實現(xiàn)
5、判隊滿，由int?QFull()函數(shù)實現(xiàn)
6、樹的左孩子，由void?new_left()函數(shù)實現(xiàn)
7、樹的右孩子，由void?new_right()函數(shù)實現(xiàn)
8、建立樹，由BiTree?create()函數(shù)實現(xiàn)
9、輸出某結(jié)點的信息，由void?output()?函數(shù)實現(xiàn)
10、層次遍歷家譜圖，由void?level()函數(shù)實現(xiàn)
11、層次遍歷家譜的第n層，由void?show_which_level()函數(shù)實現(xiàn)
12、找到結(jié)點p的雙親并返回，由BiTree?Parent()函數(shù)實現(xiàn)
13、通過名字找到結(jié)點并返回，由BiTree?search_name()函數(shù)實現(xiàn)
14、找到結(jié)點p的孩子存到指針數(shù)組child[]中，由void?search_child()函數(shù)實現(xiàn)
15、顯示三代的信息，由void?search_3dai()函數(shù)實現(xiàn)
16、通過生日找到結(jié)點并返回，由BiTree?search_birth()函數(shù)實現(xiàn)
17、輸出生日信息，由void?search_birthday()函數(shù)實現(xiàn)
18、判斷結(jié)點p和q是否是同一個爸爸，如果是返回1，否則返回0，由int?is_the_same_father()函數(shù)實現(xiàn)
19、判斷兩個人的關(guān)系，由void?ralationship()函數(shù)實現(xiàn)
20、讓一個結(jié)點擁有孩子，由void?add()函數(shù)實現(xiàn)
21、刪除一個結(jié)點和他的孩子們孫子們，由void?delete_name()函數(shù)實現(xiàn)
22、顯示家譜，由void?show_family()函數(shù)實現(xiàn)
23、修改家譜，由void?update()函數(shù)實現(xiàn)
24、把家譜中所有人的生日傳參給二維數(shù)組bir[][]，由void?transport()函數(shù)實現(xiàn)
25、將二維數(shù)組升序排序并輸出，由void?sort_birth()函數(shù)實現(xiàn)

三、代碼

#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{   //循環(huán)隊列的定義
    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)//輸出某結(jié)點的信息
{
    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)  //找到結(jié)點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[])  //通過名字找到結(jié)點并返回
{
    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[])  //找到結(jié)點p的孩子存到指針數(shù)組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("他的父親結(jié)點的信息為：\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[])  //通過生日找到結(jié)點并返回
{
    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)  //判斷結(jié)點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)   //判斷兩個人的關(guān)系
{
    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("他們是親兄弟關(guān)系\n");
    else if(is_the_same_father(bt,f1,f2)==1)
        printf("他們是堂兄弟關(guān)系\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("這兩個人關(guān)系太遠啦！\n");
}
void add(BiTree &bt)   //讓一個結(jié)點擁有孩子
{
    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("添加失??！人家已經(jīng)有左孩子了！\n");
                break;
            }
            else
            {
                printf("請輸入新孩子的姓名：\n");
                scanf("%s",new_child.name);
                printf("請輸入新孩子的出生日期：\n");
                scanf("%s",new_child.birth);
                printf("新孩子結(jié)婚了嗎，結(jié)婚請按1，沒有結(jié)婚請按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("添加失??！人家已經(jīng)有右孩子了！\n");
                break;
            }
            else
            {
                printf("請輸入新孩子的姓名：\n");
                scanf("%s",new_child.name);
                printf("請輸入新孩子的出生日期：\n");
                scanf("%s",new_child.birth);
                printf("新孩子結(jié)婚了嗎，結(jié)婚請按1，沒有結(jié)婚請按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) //刪除一個結(jié)點和他的孩子們孫子們
{
    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("請問修改過后的那個人結(jié)婚了嗎？結(jié)婚請輸入1,沒結(jié)婚請輸入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)  //把家譜中所有人的生日傳參給二維數(shù)組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)//將二維數(shù)組升序排序并輸出
{
    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.輸入兩人姓名，確定其關(guān)系\n");
    printf("7.給某成員添加孩子\n");
    printf("8.刪除某成員（若其還有后代，則一并刪除）\n");
    printf("9.修改某成員信息\n");
    printf("10.按出生日期對家譜中所有人排序\n");
    printf("11.退出系統(tǒng)\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("歡迎來到家譜管理系統(tǒng)！\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;
    }
}

四、實驗結(jié)果

文章來源地址http://www.zghlxwxcb.cn/news/detail-765408.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) 實驗 家族族譜項目的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！