C語言使用樹設(shè)計族譜
完整代碼地址: Github
本項目可使用vscode 打開并編譯,詳情請參考環(huán)境搭建教程:教程鏈接
問題描述
家屬關(guān)系查詢系統(tǒng)
- 問題描述：用樹結(jié)構(gòu)表示你所在家族的家譜關(guān)系侧巨，實現(xiàn)家族信息的管理與查詢司忱。
- 具體要求：此系統(tǒng)應(yīng)實現(xiàn)如下功能畴蹭。
- 建立(打開)家族關(guān)系樹叨襟。
- 添加(刪除)家屬成員糊闽。
- 家屬關(guān)系查詢提澎，例如查找某人的祖先盼忌、雙親、兄弟絮宁、孩子绍昂、堂兄弟窘游、后代子孫、查詢某入居于家族中的第幾代寺庄。
族譜規(guī)則
族譜只會跟蹤記錄男性以及男性的后代,對于女性我們只會記錄她在何時出嫁,并不記錄她的后代,或者說族譜中的人員向上追溯的時候默認追溯的是父親一支的關(guān)系;
邏輯分析
族譜與數(shù)據(jù)結(jié)構(gòu)中樹的概念相結(jié)合,每一個節(jié)點就是族譜中的個人,于是我們就需要知道每個人最基本的特性,于是就可以抽象化變成樹中的屬性;
- 父母 (parent) --人
- 兄弟 (brother) --人
- 伴侶 (soulmate) --人
- 孩子 (children) --人
- 姓名 (name) --字符串
- 生辰八字 (birthday) --日期
- 性別 (gender) --性別
那么我們對應(yīng)的樹的結(jié)構(gòu)就出來了
// def Tree node 定義節(jié)點
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;
其他問題
關(guān)于孩子的問題
很多人的孩子不止一個,那么我們就會將二兒子/三兒子添加到對應(yīng)的孩子的brother指針,并且將parent指針指向自己哥哥的父母;關(guān)于離婚的問題
我們都是好孩子,不考慮離婚再婚.-
關(guān)于變性問題
-
不考慮---不要問---問了就是不考慮
-
-
簡單示例
這是小明家的族譜
小明族譜.png小明->parent = NULL; 小明->brother = NULL; 小明->soulmate = NULL; 小明->children = 武大郎; 武大郎->parent = 小明; 武大郎->brother = 武松; 武大郎->soulmate = 潘金蓮; 武大郎->children = 小紅; 武松->parent = 小明; 武松->brother = NULL; 武松->soulmate = 玉蘭; 武松->children = 龍龍; ....
代碼實現(xiàn)部分
頭文件定義
// 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
增刪改查基礎(chǔ)操作
1. new 一個家族的崛起
為了方便后續(xù)的管理,我重新自定義了一個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,這樣不符合計算機的要求,也不符合自然的規(guī)律,當(dāng)這個家族不復(fù)存在時(俗稱滿門抄斬),我們就會將其刪除.
void deleteFamilyTree(FamilyTree *tree)
{
if (tree != NULL)
{
if (tree->root != NULL)
removeFamilyNode(tree->root);
free(tree);
}
}
3. insert 我要當(dāng)爸爸了
當(dāng)新生命出現(xiàn),我們的家族進一步壯大
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的結(jié)合在%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 我與某某人斷絕父子關(guān)系
斷絕關(guān)系之后,你的孫子就不是你的孫子,你的兒媳也不是你的兒媳,你就是你,既不妖艷,也不清高;
///< 遞歸刪除當(dāng)前節(jié)點下的所有子節(jié)點下的所有元素
void removeFamilyNode(FamilyNode *node)
{
if (node == NULL)
return;
node->deep = 0; //深度置0 ,表示當(dāng)前節(jié)點節(jié)點需要刪除
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);
}
解決上述題目中的幾個問題
-
找祖先
你找第幾代祖先~?
再族譜里,你想找?guī)状驼規(guī)状鷡
//使用方式: 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;
}
- 找雙親
FamilyNode *findParent(FamilyNode *node)
{
if (node == NULL)
return NULL;
return node->parent;
}
- 找兄弟
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;
}
}
- 找孩子
// someone->children 后遍歷 孩子的 brother 即可
- 找堂兄弟
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;
}
}
- 找后代子孫
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);
}
- 查詢某人居于家族中的第幾代
someone->deep;
運行結(jié)果
>[Congratulation] :小明和蛙蛙喜結(jié)連理,祝他們百年好合
>[Info] :小明和蛙蛙的結(jié)合在1969-11-11誕生了一名叫武大郎的小男孩
>[Info] :小明和蛙蛙的結(jié)合在1970-11-11誕生了一名叫武松的小男孩
>[Congratulation] :武大郎和潘金蓮喜結(jié)連理,祝他們百年好合
>[Congratulation] :武松和玉蘭喜結(jié)連理,祝他們百年好合
>[Info] :武大郎和潘金蓮的結(jié)合在1990-11-11誕生了一名叫西紅沁的小女孩
>[Info] :武大郎和潘金蓮的結(jié)合在1993-11-11誕生了一名叫武云的小男孩
>[Info] :武松和玉蘭的結(jié)合在1995-11-11誕生了一名叫武龍的小男孩
>[Info] :武松和玉蘭的結(jié)合在1996-11-11誕生了一名叫武麗的小女孩
>[Congratulation] :武云和靜香喜結(jié)連理,祝他們百年好合
>[Warning] :潘勇是上門女婿
>[Congratulation] :西紅沁和潘勇喜結(jié)連理,祝他們百年好合
>[Congratulation] :武龍和李娜喜結(jié)連理,祝他們百年好合
>[Info] :武云和靜香的結(jié)合在2020-01-03誕生了一名叫武毛的小女孩
>[Info] :武云和靜香的結(jié)合在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] :發(fā)現(xiàn)武大郎的老婆潘金蓮搞外遇,他的女兒不是他親生的~ 好慘啊~
>[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] :展示武云的堂兄弟
武云的堂兄弟姐妹有: 武龍
武麗
后記
本問題并不考慮算法問題,因此效率/空間/時間復(fù)雜度在這里不做考慮;
