C语言使用树设计族谱

C语言使用树设计族谱

完整代码地址: Github

本项目可使用vscode 打开并编译,详情请参考环境搭建教程:教程链接

问题描述

家属关系查询系统

  1. 问题描述：用树结构表示你所在家族的家谱关系，实现家族信息的管理与查询。
  2. 具体要求：此系统应实现如下功能。
    1. 建立(打开)家族关系树。
    2. 添加(删除)家属成员。
    3. 家属关系查询，例如查找某人的祖先、双亲、兄弟、孩子、堂兄弟、后代子孙、查询某入居于家族中的第几代。

族谱规则

族谱只会跟踪记录男性以及男性的后代,对于女性我们只会记录她在何时出嫁,并不记录她的后代,或者说族谱中的人员向上追溯的时候默认追溯的是父亲一支的关系;

逻辑分析

族谱与数据结构中树的概念相结合,每一个节点就是族谱中的个人,于是我们就需要知道每个人最基本的特性,于是就可以抽象化变成树中的属性;

  • 父母 (parent) --人
  • 兄弟 (brother) --人
  • 伴侣 (soulmate) --人
  • 孩子 (children) --人
  • 姓名 (name) --字符串
  • 生辰八字 (birthday) --日期
  • 性别 (gender) --性别

那么我们对应的树的结构就出来了

// def Tree node 定义节点
typedef struct _FamilyNode
{
    struct _FamilyNode* parent;
    struct _FamilyNode* brother;
    struct _FamilyNode* soulmate;
    struct _FamilyNode* children;
    char name[30];
    char birthday[20];
    char gender[6];
} FamilyNode;

// def Family Tree 定义族谱
typedef struct _FamilyTree
{
    FamilyNode* root;
    int deep;
} FamilyTree;

其他问题

  • 关于孩子的问题
    很多人的孩子不止一个,那么我们就会将二儿子/三儿子添加到对应的孩子的brother指针,并且将parent指针指向自己哥哥的父母;

  • 关于离婚的问题
    我们都是好孩子,不考虑离婚再婚.

  • 关于变性问题

    • 不考虑---不要问---问了就是不考虑

  • 简单示例
    这是小明家的族谱

    小明族谱.png

    小明->parent = NULL;
小明->brother = NULL;
小明->soulmate = NULL;
小明->children = 武大郎;

武大郎->parent = 小明;
武大郎->brother = 武松;
武大郎->soulmate = 潘金莲;
武大郎->children = 小红;

武松->parent = 小明;
武松->brother = NULL;
武松->soulmate = 玉兰;
武松->children = 龙龙;

....

代码实现部分

头文件定义

// headfile familytree.h

#ifndef _familytree_h
#define _familytree_h
#include <stdio.h>

typedef struct
{
    char name[30];
    char birthday[20];
    char gender[6];
} Human;

typedef struct _FamilyNode
{
    struct _FamilyNode *parent;
    struct _FamilyNode *brother;
    struct _FamilyNode *soulmate;
    struct _FamilyNode *children;
    Human man;
    int deep;
} FamilyNode;

// def Family Tree 定义族谱
typedef struct _FamilyTree
{
    FamilyNode *root;
    char introduce[200]; ///< 对于该族谱的简单介绍
} FamilyTree;

FamilyTree *newFamilyTree(Human origin);
void *deleteFamilyTree(FamilyTree *tree);

int insertNewBaby(FamilyNode *parent, Human baby);
int marryPeople(FamilyNode *wifi, FamilyNode *husband);
int editFamilyNode(FamilyNode *old, FamilyNode *newone);
void removeFamilyNode(FamilyTree *tree, FamilyNode *node);

FamilyNode *findFamilyNodee(Human man);
FamilyNode *findOrigin(FamilyNode *node, int generation);
FamilyNode *findParent(FamilyNode *node);

void printBrother(FamilyNode *node);
void printCousin(FamilyNode *node);

extern int
compareFamilyNode(FamilyNode *a, FamilyNode *b);

#endif // _familytree_h

增删改查基础操作

1. new 一个家族的崛起

为了方便后续的管理,我重新自定义了一个FamilyTree,实际上来说任何一个FamilyNode都是一个familytree,但是不能人人都是先祖把所以咱们得要有一个根
于是乎:

FamilyTree *newFamilyTree(Human origin, char *introduce)
{
    FamilyTree *ret = (FamilyTree *)malloc(sizeof(FamilyTree));
    if (introduce != NULL)
        strcpy(ret->introduce, introduce);
    ret->root = (FamilyNode *)malloc(sizeof(FamilyNode));
    memset(ret->root, 0, sizeof(FamilyNode));
    ret->root->man = origin;
    ret->root->deep = 1;
    return ret;
}

2. delete 这个家族覆灭了

有生就有死,不可能我只New 没有Delete,这样不符合计算机的要求,也不符合自然的规律,当这个家族不复存在时(俗称满门抄斩),我们就会将其删除.

void deleteFamilyTree(FamilyTree *tree)
{
    if (tree != NULL)
    {
        if (tree->root != NULL)
            removeFamilyNode(tree->root);
        free(tree);
    }
}

3. insert 我要当爸爸了

当新生命出现,我们的家族进一步壮大

int insertNewBaby(FamilyNode *parent, Human baby)
{
    if (parent == NULL)
        return 0;
    if (parent->soulmate == NULL)
    {
        K_ERROR("%s没有爱人\n", parent->man.name);
        return 0;
    }
    FamilyNode *chld = (FamilyNode *)malloc(sizeof (FamilyNode));
    memset(chld, 0, sizeof(FamilyNode));

    chld->man = baby;
    chld->parent = parent;
    if (parent->children == NULL)
    {
        parent->children = chld;
        chld->deep = parent->deep + 1;
    }
    else
    {
        FamilyNode *tmp = parent->children;
        while (tmp->brother != NULL)
            tmp = tmp->brother;
        tmp->brother = chld;
        chld->deep = tmp->deep;
    }
    K_INFOMATION("%s和%s的结合在%s诞生了一名叫%s的小%s孩 \n",
                 parent->man.name,
                 parent->soulmate->man.name,
                 chld->man.birthday,
                 chld->man.name,
                 (chld->man.gender == Gender_Man) ? ("男 ") : ("女"));
    return 1;
}

4. edit 我把我儿子改名叫"狗子"

   Human son;
   strcpy(son.name."二狗子");
   FamilyNode* myson = findFamilyNode(myFamilyTree,son);
   strcpy( myson->man.name,"狗子");

5. remove 我与某某人断绝父子关系

断绝关系之后,你的孙子就不是你的孙子,你的儿媳也不是你的儿媳,你就是你,既不妖艳,也不清高;

///< 递归删除当前节点下的所有子节点下的所有元素
void removeFamilyNode(FamilyNode *node)
{
    if (node == NULL)
        return;
    node->deep = 0;    //深度置0 ,表示当前节点节点需要删除
    removeFamilyNode(node->children);
    if (node->parent == NULL || node->parent->deep == 0) //如果 父母都要被删除,那么他的兄弟也要被删除
        removeFamilyNode(node->brother);
    else
    {
        FamilyNode *tmp = node->parent->children;
        if (tmp == node)
        {
            node->parent->children = NULL;
        }
        else
        {
            while (tmp->brother != node && tmp->brother  != NULL)
                tmp = tmp->brother;
            tmp->brother = node->brother;
        }
    }
    free(node);
}

6. find 皇上派我来查查你的底细

3分钟我要这个人的全部资料,这个女人朕要定了!
皇上~(颤抖),武大郎是个男的(哭了)

FamilyNode *findFamilyNode(FamilyTree *tree, Human man)
{
    if (tree == NULL || tree->root == NULL)
        return NULL;
    return findFamilyNodeByNode(tree->root, &man);
}

解决上述题目中的几个问题

  1. 找祖先
    你找第几代祖先~?
    再族谱里,你想找几代就找几代~
//使用方式: findOrigin(tigerKiller,1);  //往上找武松一代祖先
FamilyNode *findOrigin(FamilyNode *node, int generation)
{
    if (node == NULL)
        return NULL;
    FamilyNode *ret = node;
    while (ret->parent != NULL && generation != 0)
    {
        ret = ret->parent;
        generation--;
    }
    return ret;
}
  1. 找双亲
FamilyNode *findParent(FamilyNode *node)
{
    if (node == NULL)
        return NULL;
    return node->parent;
}
  1. 找兄弟
void printBrother(FamilyNode *node)
{
    if (node == NULL)
        return;
    FamilyNode *tmp = NULL;
    K_PRINT("%s的兄弟姐妹有:", node->man.name);
    if (node->parent != NULL)
        tmp = node->parent->children;
    else
        tmp = node->brother;
    while (tmp != NULL)
    {
        if (tmp != node)
            K_PRINT("  %s\n", tmp->man.name);
        tmp = tmp->brother;
    }
}
  1. 找孩子
// someone->children 后遍历 孩子的 brother 即可
  1. 找堂兄弟
void printCousin(FamilyNode *node)
{
    if (node == NULL || node->parent == NULL)
        return;
    FamilyNode *tmpuncle = NULL;
    FamilyNode *tmpbro = NULL;
    K_PRINT("%s的堂兄弟姐妹有:", node->man.name);
    if (node->parent->parent == NULL)
        tmpuncle = node->parent->brother;
    else
        tmpuncle = node->parent->parent->children;
    while (tmpuncle != NULL)
    {
        tmpbro = tmpuncle->children;
        while (tmpbro != NULL)
        {
            if (tmpbro != node)
                K_PRINT("  %s\n", tmpbro->man.name);
            tmpbro = tmpbro->brother;
        }
        tmpuncle = tmpuncle->brother;
    }
}
  1. 找后代子孙
void printFamily(FamilyNode *node)
{
    if (node == NULL)
    {
        return;
    }

    for (int i = 0; i < node->deep; i++)
    {
        char *c = " ";
        if (i == node->deep - 2)
            c = "└";
        else if (i == node->deep - 1)
            c = "--";
        else
            c = "  ";

        K_PRINT("%s", c);
    }
    K_PRINT("%s:%s生,性别 %s", node->man.name,
            node->man.birthday, GENDER_TO_STR   (node->man.gender));
    if (node->soulmate != NULL)
    {
        K_PRINT(",伴侣: %s, 性别: %s",
                node->soulmate->man.name,
                GENDER_TO_STR(node->soulmate->man.gender)   );
    }
    K_PRINT("%s", "\n");
    printFamily(node->children);
    printFamily(node->brother);
}
  1. 查询某人居于家族中的第几代
someone->deep;

运行结果

>[Congratulation] :小明和蛙蛙喜结连理,祝他们百年好合  
  >[Info] :小明和蛙蛙的结合在1969-11-11诞生了一名叫武大郎的小男孩  
  >[Info] :小明和蛙蛙的结合在1970-11-11诞生了一名叫武松的小男孩  
  >[Congratulation] :武大郎和潘金莲喜结连理,祝他们百年好合  
  >[Congratulation] :武松和玉兰喜结连理,祝他们百年好合  
  >[Info] :武大郎和潘金莲的结合在1990-11-11诞生了一名叫西红沁的小女孩  
  >[Info] :武大郎和潘金莲的结合在1993-11-11诞生了一名叫武云的小男孩  
  >[Info] :武松和玉兰的结合在1995-11-11诞生了一名叫武龙的小男孩  
  >[Info] :武松和玉兰的结合在1996-11-11诞生了一名叫武丽的小女孩  
  >[Congratulation] :武云和静香喜结连理,祝他们百年好合  
  >[Warning] :潘勇是上门女婿  
  >[Congratulation] :西红沁和潘勇喜结连理,祝他们百年好合  
  >[Congratulation] :武龙和李娜喜结连理,祝他们百年好合  
  >[Info] :武云和静香的结合在2020-01-03诞生了一名叫武毛的小女孩  
  >[Info] :武云和静香的结合在2020-01-03诞生了一名叫武重的小男孩  
--小明:1949-11-11生,性别 男,伴侣: 蛙蛙, 性别: 女  
└--武大郎:1969-11-11生,性别 男,伴侣: 潘金莲, 性别: 女  
  └--西红沁:1990-11-11生,性别 女,伴侣: 潘勇, 性别: 男  
  └--武云:1993-11-11生,性别 男,伴侣: 静香, 性别: 女  
    └--武毛:2020-01-03生,性别 女  
    └--武重:2020-01-03生,性别 男  
└--武松:1970-11-11生,性别 男,伴侣: 玉兰, 性别: 女  
  └--武龙:1995-11-11生,性别 男,伴侣: 李娜, 性别: 女  
  └--武丽:1996-11-11生,性别 女  
  >[Info] :发现武大郎的老婆潘金莲搞外遇,他的女儿不是他亲生的~  好惨啊~  
  >[Info] :将 西红沁 踢出族谱~!!!  
  >[Info] :最终的族谱为  
--小明:1949-11-11生,性别 男,伴侣: 蛙蛙, 性别: 女  
└--武大郎:1969-11-11生,性别 男,伴侣: 潘金莲, 性别: 女  
  └--武云:1993-11-11生,性别 男,伴侣: 静香, 性别: 女  
    └--武毛:2020-01-03生,性别 女  
    └--武重:2020-01-03生,性别 男  
└--武松:1970-11-11生,性别 男,伴侣: 玉兰, 性别: 女  
  └--武龙:1995-11-11生,性别 男,伴侣: 李娜, 性别: 女  
  └--武丽:1996-11-11生,性别 女  
  >[Info] :展示武大郎的兄弟  
武大郎的兄弟姐妹有:  武松  
  >[Info] :展示武云的堂兄弟  
武云的堂兄弟姐妹有:  武龙  
  武丽

后记

本问题并不考虑算法问题,因此效率/空间/时间复杂度在这里不做考虑;

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,718评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,683评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,207评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,755评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,862评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,050评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,136评论 3赞 410
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,882评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,330评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,651评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,789评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,477评论 4赞 333
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,135评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,864评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,099评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,598评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,697评论 2赞 351

推荐阅读更多精彩内容