本次项目题材选自数据结构与算法课程设计课程

项目源代码链接：https://pan.baidu.com/s/1NVlSJB6ti7Y5jhPCbdeGbg?pwd=uxzw
参考文章：http://t.csdnimg.cn/tar90

问题描述：

实现具有下列功能的家谱管理系统
(1) 输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容：
姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。
(2) 显示家谱。
(3) 显示第n 代所有人的信息。
(4) 按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。
(5) 按照出生日期查询成员名单。
(6) 输入两人姓名，确定其关系。
(7) 某成员添加孩子。
(8) 删除某成员（若其还有后代，则一并删除）。
(9) 修改某成员信息。
(10) 按出生日期对家谱中所有人排序。
【基本要求】
建立至少30个成员的数据，以较为直观的方式显示结果，并存储为文档。
界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
数据结构：建议树型结构。

题目分析：

题目要求实现一个家谱管理系统，该系统需要满足一系列的功能需求。首先，我们需要理解每个功能的具体要求，然后根据这些要求来设计数据结构和算法。

1. 读存文件：

   • 这一功能要求我们能够从文件中读取、保存家谱的成员信息。
   • 分析：可以使用树形结构，每个节点代表一个成员，节点中存储成员的详细信息。

2. 显示家谱：

   • 这一功能要求我们能够以某种形式（如树形图、表格等）展示整个家谱的结构。
   • 分析：使用命令行界面，以表格的形式打印家谱成员信息。

3. 显示第n代所有人：

   • 这一功能要求我们能够快速找到并显示特定代数下的所有成员。
   • 分析：通过递归树形结构，查询并输出对应层级的全部节点信息。

4. 按照姓名查询：

   • 需要快速查找到特定姓名的成员及其相关信息。
   • 分析：递归树形结构，查找姓名匹配的成员信息。

5. 按照出生日期查询：

   • 需要根据出生日期查找成员名单。
   • 分析：递归树形结构，查找出生日期匹配的成员信息。

6. 确定两人关系：

   • 根据两人姓名确定他们的家族关系（如父子、兄弟等）。
   • 分析：遍历家族树，找到两个成员的位置，并根据位置关系确定关系。

7. 添加孩子：

   • 在给定父亲姓名的情况下添加一个孩子。
   • 分析：找到父亲节点，并在其下创建一个子节点来表示孩子。

8. 删除成员：

   • 删除特定成员（如果还有后代，一并删除）。
   • 分析：遍历家族树，找到要删除的成员，并删除相关联的所有后代节点。

9. 修改成员信息：

   • 根据姓名修改特定成员的信息。
   • 分析：找到要修改的成员节点，更新其信息。

10. 按出生日期排序：

    • 对所有成员按照出生日期进行排序。
    • 数据结构建议：使用排序数组或有序集合来存储成员信息，以便进行排序操作。

部分代码讲解：

在选择数据结构的时候，一直在二叉树和二叉链表之间纠结。

对于父节点来说，可以拥有多个子节点。如果选择二叉树将会限制子节点的个数，不符合客观事实。

二叉链表更加符合客观事实，同时使用二叉链表的主要思路和二叉树一致

因此，为了简化、快速完成代码，本次项目使用了二叉树，便于理解。

数据结构：定义好节点信息和二叉树结构

typedef struct Infomation {//节点信息
    char name[20];//名字
    char birth[20];//出生日期
    char wedding[5];//婚否 
    char address[20];//地址
    char health[5];//健在否
    char death_date[20];//死亡日期
    char parentname[20];//父亲姓名
}Info;

typedef struct node //二叉树结构体
{
    Info person;//成员信息
    struct node* lchild, * rchild;//左右孩子
}Bnode, * tree;

全局变量

#define MAXSIZE 100
Info human[MAXSIZE];//用与读取、存储文件里的全部成员信息
char Birthday[MAXSIZE][10];// 定义一个二维数组，用于存储出生日期
int NumPeople = NumRows();//获取成员信息个数
int AddPeople = 0; //用以计算用户操作时候，成员的增量

1.读盘，构建二叉树

为确保每个家庭成员都能被正确链接到其父母，形成完整的家谱二叉树。通过while持续循环遍历成员信息数组（human[]），匹配成员的父亲姓名找到父节点并添加成员至二叉树。在循环可行性中，利用布尔数组added[]，标记此成员是否添加至二叉树，用以判断是否跳出单次循环。同时利用计数器，判断是否有未添加成功的成员以此来增加while循环次数，以此保证全部成员添加成功。

//读盘并且创建家族树 
tree creat()
{
    FILE* fp;
    int i;
    if ((fp = fopen("D:/family.txt", "r+")) == NULL)
        printf("不能打开家谱文件\n");
    printf("\n读盘成功！！家谱中一共有%d个成员\n",NumPeople);
    NumPeople = NumRows();//获取家谱中的成员数量 
    for (i = 0; i < NumPeople; i++)// 遍历文件中的每个家族成员，并将信息存储到human数组中  
        fscanf(fp, "%s %s %s %s %s %s %s", human[i].name, human[i].birth, human[i].wedding, human[i].address, human[i].health, human[i].death_date, human[i].parentname);
    fclose(fp);
    // 初始化二叉树的根节点 
    tree bt;
    bt = (tree)malloc(sizeof(Bnode));
    bt->person = human[0]; // 根节点指向第一个家族成员的信息
    bt->lchild = bt->rchild = NULL;
    bool added[MAXSIZE] = { false };// 记录哪些家族成员已经被添加到二叉树中 
    int count = 1;  // 计数器，用于控制循环的次数
    // 主循环，持续进行直到所有的家族成员都添加到了二叉树中 
    while (count) {
        for (int j = 1; j < NumPeople; j++) {// 遍历剩余的家族成员 
            if (added[j]) continue; // 如果这个家族成员已经被添加到二叉树中，跳过此次循环
            tree p = searchname(bt, human[j].parentname);
            if (p == NULL) {// 如果父节点不存在于二叉树中
                count++;//增加计数器，表示还有更多的家族成员需要添加到二叉树中
            }
            else// 如果父节点存在于二叉树中
            {
                if (p->lchild == NULL) {
                    newleft(p, human[j]);
                    added[j] = true; // 标记这个家族成员已经被添加到二叉树中
                }
                else if (p->rchild == NULL)
                {
                    newright(p, human[j]);
                    added[j] = true;
                }
                else
                {
                    //printf("该节点左右孩子已满");
                }
            }
        }
        count--;// 减少计数器，表示有一个家族成员已经被添加到了二叉树中
    }  
    return bt;
}

2.字符串匹配目标节点

//根据姓名匹配节点  （出生日期同理）
tree searchname(tree bt, char na[])
{
    tree lresult, rresult;// 声明左右子树结果，用于递归搜索左右子树 
    if (!bt)
    {
        return NULL; // 如果当前节点为空，表示已到树尾，返回NULL
    }
    if (strcmp(bt->person.name, na) == 0)
        return bt;// 如果当前节点的姓名与目标姓名匹配  返回目标节点
    else
    {
        lresult = searchname(bt->lchild, na);// 递归搜索左子树 
        rresult = searchname(bt->rchild, na); // 递归搜索右子树
        return lresult ? lresult : (rresult ? rresult : NULL);// 返回左右子树中第一个匹配的节点，如果没有匹配则返回NULL
    }
}

3.确认关系

在确认关系上，我们通过判断节点之间在数据结构上的关系以此来确认，例如节点高度差、是否为同一父亲等……

涉及函数   humannum()返回节点在human数组里的下标，若无返回-1

                 NodeHDiff()计算节点差

void relationship(tree bt){
    char name1[20], name2[20];
    tree s1, s2, f1, f2;
    printf("请输入第一个人姓名：\n");
    scanf("%s", name1);
    printf("请输入第二个人姓名：\n");
    scanf("%s", name2);
    if (humannum(name1) == -1 || humannum(name2) == -1) {
        printf("查询失败!\n");
        if (humannum(name1) == -1) {
            printf("第一个人不存在家谱中!!!\n");
        }
        if (humannum(name2) == -1) {
            printf("第二个人不存在家谱中!!!\n");
        }
    }
    else
    {
        s1 = searchname(bt, name1);
        s2 = searchname(bt, name2);
        f1 = parent(bt, s1);
        f2 = parent(bt, s2);
        if (samefather(bt, s1, s2) == 1) {
            printf("他们是亲兄弟\n");
        }
        else if (samefather(bt, f1, f2) == 1) {
            printf("他们是堂兄弟\n");
        }
        else if (s1->lchild == s2 || s1->rchild == s2) {
            printf("%s是%s的孩子\n", s2->person.name, s1->person.name);
        }         
        else if (s2->lchild == s1 || s2->rchild == s1) {
            printf("%s是%s的孩子\n", s1->person.name, s2->person.name);
        }
        else if (searchname(s1, s2->person.name) != NULL) {
            if (NodeHDiff(s1, s2) == 2)
            {
                printf("%s是%s的爷爷\n", s1->person.name, s2->person.name);
            }
            else if (NodeHDiff(s1, s2) == 3)
            {
                printf("%s是%s的曾祖父\n", s1->person.name, s2->person.name);
            }
            else
                printf("两个人是亲戚\n");
        }
        else if (searchname(s2, s1->person.name) != NULL) {
            if (NodeHDiff(s1, s2) == 2)
            {
                printf("%s是%s的爷爷\n", s2->person.name, s1->person.name);
            }
            else if (NodeHDiff(s1, s2) == 3)
            {
                printf("%s是%s的曾祖父\n", s2->person.name, s1->person.name);
            }
            else
                printf("两个人是亲戚\n");
        }
        else
            printf("两个人是亲戚\n");
    }
}

4.增删改

主要思路就是找到匹配节点，修改二叉树，更新human数组

//添加成员
void add(tree* bt)
{
    char na[20];
    tree p;
    Info newchild;
    printf("请输入添加新成员的父亲的姓名:\n");
    scanf("%s", na);
    p = searchname(*bt, na);
    if (p==NULL)
    {
        printf("此人不在家谱中，添加失败\n");
    }
    else
    {
        if (p->lchild == NULL)
        {
            printf("请输入新成员的信息：（格式：名字 出生日期 婚否 地址 健在否 死亡日期）\n");
            AddPeople += 1;
            int i = AddPeople + NumRows()-1;
            printf("\n姓名：");
            scanf("%s",newchild.name);
            strcpy(human[i].name,newchild.name);

            printf("\n出生日期：（格式：20040101）");
            scanf("%s", newchild.birth);
            strcpy(human[i].birth, newchild.birth);//修改human数组

            //婚否、地址、健在否、死亡日期……

            newleft(p, newchild);//更新二叉树
            printf("\n添加成功！\n");
        }
        else if (p->rchild == NULL)
        {
            //思路同上
        }
        else
        {
            printf("添加失败！\n");
        }
    }    
}


//删除成员
void deletename(tree* bt){
    char na[20];
    tree p, f;
    printf("请输入想删除的人的姓名，删除之后他的后代也将一并删除！\n");
    scanf("%s", na);
    p = searchname(*bt, na);
    if (p == NULL)
    {
        printf("此人不在家谱中，添加失败\n");
    }
    else
    {
        f = parent(*bt, p);
        if (f!=NULL)
        {
            if (f->lchild == p)
                f->lchild = NULL;
            if (f->rchild == p)
                f->rchild = NULL;
            DeleteNode(p);//更新human数组，删除后继节点的信息
            free(p);
        }
        else
        {
            *bt = NULL;
        }
        printf("删除成功！\n");
    }   
}


//修改成员
void update(tree* bt)
{
    char na[20];
    tree p;
    printf("请输入你想修改的成员信息的姓名：\n");
    scanf("%s", na);
    p = searchname(*bt, na);
    if (p == NULL)
    {
        printf("此人不在家谱中，修改失败\n");
    }
    else
    {
        int i;
        int num = humannum(na);
        tree c[2];
        int cnum = 0;
        char u[20];
        while (1)
        {
            printf("请选择你要修改的选项\n");
            printf("1.姓名\n");
            printf("2.出生日期\n");
            printf("3.婚否\n");
            printf("4.地址\n");
            printf("5.健在否\n");
            printf("6.死亡日期\n");
            scanf("%d", &i);
            switch (i)
            {
            case 1:
                printf("\n修改姓名：");
                scanf("%s", u);
                strcpy(human[num].name, u);
                strcpy(p->person.name, u);
                searchchild(p, c);
                if (c[1]!=NULL)
                {
                    cnum = humannum(c[0]->person.name);
                    strcpy(human[cnum].parentname, u);
                }
                if (c[2]!=NULL)
                {
                    cnum = humannum(c[1]->person.name);
                    strcpy(human[cnum].parentname, u);
                }

                break;
            //case……思路同上
            }
            printf("继续？（y/n)\n");
            char ch = getch();
            if (ch=='y'||ch=='Y')
                continue;
            else if (ch == 'n' || ch == 'N')
                break;
            else
            {
                printf("输入有误,请重新输入\n");
                continue;
            }
            
        }
        
    }


}

5.出生日期排序

通过遍历提取全体成员出生日期至数组，利用strcmp()函数返回比较结果作为出生日期比较规则，最终用qsort()函数对数组进行整体排序

char Birthday[MAXSIZE][10];// 定义一个二维字符数组，用于存储生日日期

//Birth比较
int compare_dates(const void* a, const void* b) {// 比较函数，用于qsort排序 
    return strcmp((char*)a, (char*)b);// 使用strcmp函数比较字符串，返回它们的字典顺序差值
}

//生日排序
void BirthSort(tree bt) {
    int len = NumRows() + AddPeople;//成员总人数
    for (int i = 0; i < len; i++)
        strcpy(Birthday[i], human[i].birth);
    
    qsort(Birthday, len, sizeof(Birthday[0]), compare_dates);//排序
    printf("\n排序结果如下：\n");
    printf("姓名         出生日期      婚否    地址        健在否    死亡日期\n");
    for (int i = 0; i < len; i++)
    {
        tree p = searchbirth(bt, Birthday[i]);
        output(p);
    }
}

family.txt 姓名 出生日期 婚否 地址 健在否 死亡日期 父亲姓名

chenjia 19000511 yes chongqing no 19800401 NULL
chenshen 19200721 yes chongqing no 19900402 chenjia
chenxiaofan 19230526 yes beijing no 19981221 chenjia
nanfeng 19440501 yes nanning no 20080419 chenshen
nanzhi 19480711 yes nanning no 20010201 chenshen
wuxie 19480505 yes tianjing no 20070401 chenxiaofan
wuxing 19490541 yes tianjing no 20141111 chenxiaofan
nanpan 19640815 yes nanning yes living nanfeng
xunuo 19650430 no taiwan yes living nanfeng
nanlian 19640624 yes jiling yes living nanzhi
nandong 19680301 yes taiwan yes living nanzhi
xiatian 19761226 yes fujian yes living wuxie
xiazhuo 19770519 yes fujian yes living wuxie
wuyan 19781231 yes xinjiang yes living wuxing
wuqi 19820728 yes xinjiang yes living wuxing
zhengping 19840831 yes USA yes living nanpan
xiaoming 19850525 yes taiwan yes living nanpan
nanyang 19860625 yes jiling yes living nanlian
nannan 19880427 yes jiling yes living nanlian
liuliu 19880318 yes shanghai yes living nandong
liufang 19940728 yes guangdong yes living nandong
xiahao 19970425 yes USA yes living xiatian
xialingling 19920624 yes gansu yes living xiazhuo
xiazhon 19890828 yes hunan no 20150301 xiazhuo
lifang 19900725 yes hubei yes living wuyan
liqiang 19940728 no hubei no 20230531 wuyan
yongming 20020731 no guangdong yes living wuqi
yongxiu 20040815 no guangdong yes living wuqi
fangliang 20200425 no USA yes living xiahao
k 20230321 yes USA yes living xiahao