数据结构大作业——家谱管理系统（超详细！完整代码！）

目录

设计思路：

一、项目背景

二、功能分析

查询功能流程图： 

管理功能流程图： 

三、设计

四、实现

代码实现：

头文件

结构体

函数声明及定义

创建家谱树头结点

绘制家谱树（打印）

建立右兄弟

建立左孩子

建立孩子结点信息

查找x的孩子

查找祖先

添加孩子

添加兄弟

中序遍历

删除结点

主函数

完整代码：

调试分析及测试结果：

进入主界面

建立家谱

生成树

查询操作

删除操作

写在最后

---

设计思路：

一、项目背景

家谱是一种以表谱形式，记载一个以血缘关系为主体的家族世袭繁衍和重要人物事迹的特殊图书体裁。家谱是中国特有的文化遗产，是中华民族的三大文献（国史，地志，族谱）之一，属于珍贵的人文资料，对于历史学，民俗学，人口学，社会学和经济学的深入研究，均有其不可替代的独特功能。

经历了历朝历代的连年战乱和社会动荡，历史上传世的家谱几乎丧失殆尽，许多家族的世系也因此断了线、失了传。流传至今的古代家谱，大多是明清两代纂修。在我国明清时期，出现了专门替人伪造家谱世系的“谱匠”。 

本项目旨在完成一个家谱系统，并实现家谱树所需要的查找、插入、搜索和删除等相关功能。

---

二、功能分析

完成一个简易的家谱管理系统，主要包含了管理和查询两大功能。

首先允许用户进行家谱的创建并能简易的输出整个家谱。其次，还要具有查询某结点祖先和孩子的功能，同时为保证用户可以随时修改家谱，添加了完善孩子、完善兄弟和删除结点的功能。其中删除结点规则定义为：若有孩子，则孩子一并删去；若有兄弟，则保留兄弟。最后考虑到现实中用户中输入错误的情况，还要包括健壮性的检查。

查询功能流程图： 

管理功能流程图： 

---

三、设计

该程序具有明显的树形结构，故采用树作为数据结构。我们选择采用二叉树，每个结点包括三个域，具体为lchild,rbrother,data,分别用来存储孩子、兄弟和此结点的名称。

结点代码设计如下：

typedef struct Node

{

string data;

struct Node* lchild;//左孩子

struct Node* rbrother;//右兄弟

}SLNode;

void Initiate(SLNode** T)这个函数用来创建家谱树头结点

SLNode* Insertright(SLNode* arr, string x)这个函数用来建立右兄弟

SLNode* Insertleft(SLNode* arr, string x)这个函数用来建立左孩子

void input(SLNode* arr)这个函数用来输入结点的儿子的信息

void PrintTree(SLNode* T, int n)这个函数用来打印家谱树

void Searchchild(SLNode* T, string x,bool &flag)这个函数用来查找x的孩子，在树T中查找x是否存在，并用flag来标记

void SearchAncestor(SLNode* T, string x, bool& flag)这个函数用来查找x的祖先，在树T中查找x是否存在，并用flag来标记

void addChild(SLNode* T, string x, string t)这个函数用来添加孩子，在树T中找到x结点并把t加入其左孩子之中

void addBrother(SLNode* T, string x, string t)这个函数用来添加兄弟，在树T中找到x结点并把t加入其左孩子之中

void inOrder(SLNode* T, string x, bool& flag)这个函数中序遍历查找x是否存在，并用flag来标记

void deleteNode(SLNode* T, string x)这个函数用来解散结点x的家庭

---

四、实现

完善家谱功能流程图

---

代码实现：

头文件

#include<iostream>
#include<windows.h>
#include <stdio.h>
#include <stdlib.h>
#include<string>

---

结构体

typedef struct Node
{string data;struct Node* lchild;//左孩子 struct Node* rbrother;//右兄弟 
}SLNode;

---

函数声明及定义

void Initiate(SLNode** T);
SLNode* Insertright(SLNode* arr, string x);
SLNode* Insertleft(SLNode* arr, string x);
void input(SLNode* arr);
void PrintTree(SLNode* T, int n);
void Searchchild(SLNode* T, string x);
void SearchAncestor(SLNode* T, string x);
void addChild(SLNode* T, string x, string t);
void addBrother(SLNode* T, string x, string t);
void inOrder(SLNode* T, string x, bool& flag);
void deleteNode(SLNode* T, string x);
SLNode* p;

---

创建家谱树头结点

void Initiate(SLNode** T)
{*T = new SLNode;(*T)->lchild = NULL;(*T)->rbrother = NULL;
}

---

绘制家谱树（打印）

void PrintTree(SLNode* T, int n)
{int i, j;if (T){for (i = 0; i < n; i++) cout << "       " ;cout << T->data;cout << endl;//打印家谱时为左孩子n+1,整体向右推移一位，右兄弟依然是nPrintTree(T->lchild, n + 1);PrintTree(T->rbrother, n);}
}

---

建立右兄弟

SLNode* Insertright(SLNode* arr, string x)
{SLNode* m;if (arr == NULL) return NULL;if (arr->rbrother != NULL)  arr = arr->rbrother;m = new SLNode;m->data = x;m->rbrother = arr->rbrother;m->lchild = NULL;arr->rbrother = m;return arr->rbrother;
}

---

建立左孩子

SLNode* Insertleft(SLNode* arr, string x)
{SLNode* m;if (arr == NULL) return NULL;else if (arr->lchild == NULL)//为什么这里要判空？//因为有可能插入多个孩子，如果已经插入一个或多个了，就需要执行else块里的右兄弟函数往下递归找到空指针在插入 {//开始创建要插入的左孩子 m = new SLNode;//malloc无法为string分配正确内存，所以用newm->data = x;m->lchild = arr->lchild;//方便下次插入孩子结点 m->rbrother = NULL;arr->lchild = m;//孩子结点插入完成 return arr->lchild;}else{Insertright(arr->lchild, x);}
}

---

建立孩子结点信息

void input(SLNode* arr)
{string p;if (arr == NULL) return;cout << "请输入"<<arr->data<<"所有的儿子结点, 若没有儿子或者输完所有儿子，输入#即可:" << endl;cin >> p;while (p != "#"){Insertleft(arr, p);cin >> p;}//这个建立家谱的过程，为了防止输入混乱，先递归兄弟结点，再递归孩子结点 if (arr->rbrother != NULL)input(arr->rbrother);if (arr->lchild != NULL)input(arr->lchild);/*if (arr->rbrother != NULL )input(arr->rbrother);if (arr->lchild != NULL )input(arr->lchild);}

---

查找x的孩子

void Searchchild(SLNode* T, string x,bool &flag)
{SLNode* p;//要用T->data和x比较，所以要保证T不为空指针if (T != NULL && T->data != x){Searchchild(T->lchild, x,flag);Searchchild(T->rbrother, x,flag);}//加入限定条件只允许T->data==x时通过if (T != NULL && T->lchild != NULL && T->data == x){cout << T->data << "结点的儿子结点为：" << T->lchild->data << endl;p = T->lchild;while (p->rbrother != NULL)//右兄弟，找到一个儿子结点后去右子树找兄弟结点{cout << p->rbrother->data << endl;p = p->rbrother;}}
}

---

查找祖先

void SearchAncestor(SLNode* T, string x, bool& flag)//函数为找x的祖先 
{if (T != NULL && T->data != x)//如果T不为空并且data不是x {SearchAncestor(T->lchild, x, flag);//不断向下递归找左孩子 SearchAncestor(T->rbrother, x, flag);//右兄弟 }//保证p为不变的指针，指向选择的结点if (T != NULL && T->data == x)//T不为空并且已经找到了结点 {p = T;//此时的结点赋给p flag = true;//说明已经找到了 }//下面找p的祖先即可 ，T是p的祖先，可能T的左孩子就是了也可能是T的左孩子的兄弟 if (T != NULL && T->lchild != NULL && (T->lchild == p || T->lchild->rbrother == p))	{cout << "他的祖先结点为：" << T->data << endl;p = T;}
}

---

添加孩子

void addChild(SLNode* T, string x, string t)
{//考虑到现实生活中会有二胎三胎，这个函数的作用即为添加孩子添加孩子结点 if (T != NULL && T->data != x){addChild(T->lchild, x, t);addChild(T->rbrother, x, t);}if (T != NULL && T->data == x){p = T;Insertleft(p, t);//调用前面的插入左孩子函数进行添加 }
}

---

添加兄弟

void addBrother(SLNode* T, string x, string t)
{if (T != NULL && T->data != x){addBrother(T->rbrother, x, t); addBrother(T->lchild, x, t);}if (T != NULL && T->data == x){p = T;Insertright(p, t);return;}
}

---

中序遍历

void inOrder(SLNode* T, string x, bool& flag)//中序遍历
{if (T == NULL || flag == true) return;inOrder(T->lchild, x, flag);if (T->data == x){flag = true;//如果要完善的结点在家谱里，flag为真 return;}inOrder(T->rbrother, x, flag);
}

---

删除结点

void deleteNode(SLNode* T, string x)
{//先定义删除规则：//如果有孩子，孩子一并删去，有兄弟则保留兄弟。if (T == NULL) return;//因为T为头结点，这里从T->lchild开始遍历if ( T->lchild != NULL && T->lchild->data == x){SLNode* p = T->lchild->lchild;free(p);//根据删除规则，孩子一并删除T->lchild = T->lchild->rbrother;//保留兄弟}if (T->rbrother != NULL && T->rbrother->data == x){SLNode* p = T->rbrother->lchild;free(p);//根据删除规则，孩子一并删除T->rbrother = T->rbrother->rbrother;//保留兄弟}deleteNode(T->lchild, x);deleteNode(T->rbrother, x);//先根再左在右，先序遍历的方式删除
}

---

主函数

int main()
{SLNode* T;string p;int n;Initiate(&T);do{system("color 75");cout << "                                                           " << endl;cout << "                        家谱管理系统                    " << endl;cout << "------------------------- 功能选项 -------------------------";cout << endl << endl;cout << "                    **  1-开始建立家谱  **" << endl;cout << "                    **  2-查询-家谱树   **" << endl;cout << "                    **  3-查询-儿子     **" << endl;cout << "                    **  4-查询-祖先     **" << endl;cout << "                    **  5-完善-孩子     **" << endl;cout << "                    **  6-完善-兄弟     **" << endl;cout << "                    **  7-删除-结点     **" << endl;cout << "                    **  0-退出系统      **" << endl;cout << endl << endl;cout << "------------------------------------------------------------";cout << endl;cout << "请选择需要的功能(数字) :";char ch;ch = getchar();switch (ch){case '1':{cout << "请输入祖先结点：" << endl;cin >> p;Insertleft(T, p);input(T->lchild); getchar(); break;};case '2':{cout << endl;PrintTree(T->lchild, 1); getchar(); break;};case '3':{bool flag_1 = false;//flag_1用来标记是否有孩子bool flag_2 = false;//flag_2用来标记家谱里是否有要查询的结点cout << "请输入要查询的结点" << endl;cin >> p;inOrder(T, p, flag_2);//inOrder(T, p, flag_1); while (!flag_2){cout << "您要查询的结点并不存在, 请重新输入：" << endl;cin >> p;inOrder(T, p, flag_2);}Searchchild(T, p,flag_1); //直接在此函数中输出getchar(); break;};case '4':{cout << "请输入要查询的结点：" << endl;cin >> p;bool flag = false;while (p == T->lchild->data)//T是头结点，祖先存储在T的lchild域里{cout << "这个结点为祖先，请重新输入：" << endl;cin >> p;}SearchAncestor(T->lchild, p, flag);while (flag == false){cout << "此结点不存在,请重新输入:" << endl;cin >> p;while (p == T->lchild->data)//T是头结点，祖先存储在T的lchild域里{cout << "这个结点为祖先，请重新输入：" << endl;cin >> p;}SearchAncestor(T->lchild, p, flag);}getchar(); break;};case '5':{bool flag = false;//flag用来标记要完善的结点是否在家谱里 cout << "请输入要完善的结点：" << endl;cin >> p;inOrder(T, p, flag);//查找结点是否在家谱里while (!flag){cout << "您要完善的结点并不存在, 请重新输入：" << endl;cin >> p;inOrder(T, p, flag);}cout << "要添加的孩子为：" << endl;string x;cin >> x;addChild(T, p, x); getchar(); break;};case '6':{bool flag = false;//flag用来标记要完善的结点是否在家谱里cout << "请输入要完善的结点：" << endl;cin >> p;inOrder(T, p, flag);//查找结点是否在家谱里while (!flag){cout << "您要完善的结点并不存在,请重新输入：" << endl;cin >> p;inOrder(T, p, flag);}cout << "要添加的兄弟为：" << endl;string x;cin >> x;addBrother(T, p, x); getchar(); break;}case '7':{bool flag = false;//标记要删除的结点是否在家谱里cout << "请输入要删除的结点：" << endl;cin >> p;inOrder(T, p, flag);//查找结点是否在家谱里while (!flag){cout << "您要删除的结点并不存在,请重新输入：" << endl;cin >> p;inOrder(T, p, flag);}deleteNode(T, p); getchar(); break;}case '0':{cout << " 感谢您的使用，下次再见！" << endl;exit(0);}default:{cout << "输入有误，请重新输入：" << endl;ch = getchar();}}} while (1);return 0;
}

---

完整代码：

#include<iostream>
#include<windows.h>
#include <stdio.h>
#include <stdlib.h>
#include<string>using namespace std;typedef struct Node
{string data;struct Node* lchild;//左孩子 struct Node* rbrother;//右兄弟 
}SLNode;//extern SLNode* p;void Initiate(SLNode** T);
SLNode* Insertright(SLNode* arr, string x);
SLNode* Insertleft(SLNode* arr, string x);
void input(SLNode* arr);
void PrintTree(SLNode* T, int n);
void Searchchild(SLNode* T, string x);
void SearchAncestor(SLNode* T, string x);
SLNode* p;void Initiate(SLNode** T)
{*T = new SLNode;(*T)->lchild = NULL;(*T)->rbrother = NULL;
}SLNode* Insertright(SLNode* arr, string x)
{SLNode* m;if (arr == NULL) return NULL;if (arr->rbrother != NULL)  arr = arr->rbrother;m = new SLNode;m->data = x;m->rbrother = arr->rbrother;m->lchild = NULL;arr->rbrother = m;return arr->rbrother;
}SLNode* Insertleft(SLNode* arr, string x)
{SLNode* m;if (arr == NULL) return NULL;else if (arr->lchild == NULL)//为什么这里要判空？//因为有可能插入多个孩子，如果已经插入一个或多个了，就需要执行else块里的右兄弟函数往下递归找到空指针在插入 {//开始创建要插入的左孩子 m = new SLNode;//malloc无法为string分配正确内存，所以用newm->data = x;m->lchild = arr->lchild;//方便下次插入孩子结点 m->rbrother = NULL;arr->lchild = m;//孩子结点插入完成 return arr->lchild;}else{Insertright(arr->lchild, x);}
}void input(SLNode* arr)
{string p;if (arr == NULL) return;cout << "请输入"<<arr->data<<"所有的儿子结点, 若没有儿子或者输完所有儿子，输入#即可:" << endl;cin >> p;while (p != "#"){Insertleft(arr, p);cin >> p;}//这个建立家谱的过程，为了防止输入混乱，先递归兄弟结点，再递归孩子结点 if (arr->rbrother != NULL)input(arr->rbrother);if (arr->lchild != NULL)input(arr->lchild);/*if (arr->rbrother != NULL )input(arr->rbrother);if (arr->lchild != NULL )input(arr->lchild);//这里是先递归兄弟节点，再递归孩子结点*/
}void PrintTree(SLNode* T, int n)
{int i, j;if (T){for (i = 0; i < n; i++) cout << "       " ;cout << T->data;cout << endl;//打印家谱时为左孩子n+1,整体向右推移一位，右兄弟依然是nPrintTree(T->lchild, n + 1);PrintTree(T->rbrother, n);}
}void Searchchild(SLNode* T, string x,bool &flag)//flag用来标记是否有孩子
{SLNode* p;//要用T->data和x比较，所以要保证T不为空指针if (T != NULL && T->data != x){Searchchild(T->lchild, x,flag);Searchchild(T->rbrother, x,flag);}//加入限定条件只允许T->data==x时通过if (T != NULL && T->lchild != NULL && T->data == x){cout << T->data << "结点的儿子结点为：" << T->lchild->data << endl;p = T->lchild;while (p->rbrother != NULL)//右兄弟，找到一个儿子结点后去右子树找兄弟结点{cout << p->rbrother->data << endl;p = p->rbrother;}}
}void SearchAncestor(SLNode* T, string x, bool& flag)//函数为找x的祖先 
{if (T != NULL && T->data != x)//如果T不为空并且data不是x {SearchAncestor(T->lchild, x, flag);//不断向下递归找左孩子 SearchAncestor(T->rbrother, x, flag);//右兄弟 }//保证p为不变的指针，指向选择的结点if (T != NULL && T->data == x)//T不为空并且已经找到了结点 {p = T;//此时的结点赋给p flag = true;//说明已经找到了 }//下面找p的祖先即可 ，T是p的祖先，可能T的左孩子就是了也可能是T的左孩子的兄弟 if (T != NULL && T->lchild != NULL && (T->lchild == p || T->lchild->rbrother == p)){cout << "他的祖先结点为：" << T->data << endl;p = T;}
}void addChild(SLNode* T, string x, string t)
{//考虑到现实生活中会有二胎三胎，这个函数的作用即为添加孩子添加孩子结点 if (T != NULL && T->data != x){addChild(T->lchild, x, t);addChild(T->rbrother, x, t);}if (T != NULL && T->data == x){p = T;Insertleft(p, t);//调用前面的插入左孩子函数进行添加 }
}
void addBrother(SLNode* T, string x, string t)
{if (T != NULL && T->data != x){addBrother(T->rbrother, x, t); addBrother(T->lchild, x, t);}if (T != NULL && T->data == x){p = T;Insertright(p, t);return;}
}
void inOrder(SLNode* T, string x, bool& flag)//中序遍历
{if (T == NULL || flag == true) return;inOrder(T->lchild, x, flag);if (T->data == x){flag = true;//如果要完善的结点在家谱里，flag为真 return;}inOrder(T->rbrother, x, flag);
}
void deleteNode(SLNode* T, string x)
{//先定义删除规则：//如果有孩子，孩子一并删去，有兄弟则保留兄弟。if (T == NULL) return;//因为T为头结点，这里从T->lchild开始遍历if ( T->lchild != NULL && T->lchild->data == x){SLNode* p = T->lchild->lchild;free(p);//根据删除规则，孩子一并删除T->lchild = T->lchild->rbrother;//保留兄弟}if (T->rbrother != NULL && T->rbrother->data == x){SLNode* p = T->rbrother->lchild;free(p);//根据删除规则，孩子一并删除T->rbrother = T->rbrother->rbrother;//保留兄弟}deleteNode(T->lchild, x);deleteNode(T->rbrother, x);//先根再左在右，先序遍历的方式删除
}
int main()
{SLNode* T;string p;int n;Initiate(&T);do{system("color 75");cout << "                                                           "<<endl;cout << "                        家谱管理系统                    "<<endl;cout << "------------------------- 功能选项 -------------------------";cout << endl << endl;cout << "                    **  1-开始建立家谱  **" << endl;cout << "                    **  2-查询-家谱树   **" << endl;cout << "                    **  3-查询-儿子     **" << endl;cout << "                    **  4-查询-祖先     **" << endl;cout << "                    **  5-完善-孩子     **" << endl;cout << "                    **  6-完善-兄弟     **" << endl;cout << "                    **  7-删除-结点     **" << endl;cout << "                    **  0-退出系统      **" << endl;cout << endl << endl;cout << "------------------------------------------------------------";cout << endl;cout <<"请选择需要的功能(数字) :";char ch;ch = getchar();switch (ch){case '1':{cout << "请输入祖先结点：" << endl;cin >> p;Insertleft(T, p);input(T->lchild); getchar(); break;};case '2':{cout << endl;PrintTree(T->lchild, 1); getchar(); break;};case '3':{bool flag_1 = false;//flag_1用来标记是否有孩子bool flag_2 = false;//flag_2用来标记家谱里是否有要查询的结点cout << "请输入要查询的结点" << endl;cin >> p;inOrder(T, p, flag_2);while (!flag_2){cout << "您要查询的结点并不存在, 请重新输入：" << endl;cin >> p;inOrder(T, p, flag_2);}Searchchild(T, p,flag_1); //如果有孩子，则直接在此函数中输出if (!flag_1)//flag_1为假，即没有孩子，执行if{cout << "此结点没有儿子!" << endl;}getchar(); break;};case '4':{cout<< "请输入要查询的结点：" << endl;cin >> p;bool flag = false;while(p == T->lchild->data)//T是头结点，祖先存储在T的lchild域里{cout << "这个结点为祖先，请重新输入：" << endl;cin >> p;}SearchAncestor(T->lchild, p,flag);while (flag == false) {cout << "此结点不存在,请重新输入:" << endl;cin >> p;while(p== T->lchild->data)//T是头结点，祖先存储在T的lchild域里{cout << "这个结点为祖先，请重新输入：" << endl;cin >> p;}SearchAncestor(T->lchild, p, flag);}getchar();break;};case '5':{bool flag = false;//flag用来标记要完善的结点是否在家谱里 cout << "请输入要完善的结点：" << endl;cin >> p;inOrder(T, p, flag);//查找结点是否在家谱里while (!flag){cout << "您要完善的结点并不存在, 请重新输入：" << endl;cin >> p;inOrder(T, p, flag);}cout << "要添加的孩子为：" << endl;string x;cin >> x;addChild(T, p, x); getchar(); break;};case '6':{bool flag = false;//flag用来标记要完善的结点是否在家谱里cout << "请输入要完善的结点：" << endl;cin >> p;while (p == T->lchild->data) //T是头结点，祖先存储在T的lchild域里{cout << "这个结点为祖先，请重新输入：" << endl;cin >> p;}inOrder(T, p, flag);//查找结点是否在家谱里while (!flag){cout << "您要完善的结点并不存在,请重新输入：" << endl;cin >> p;inOrder(T, p, flag);}cout << "要添加的兄弟为：" << endl;string x;cin >> x;addBrother(T, p, x); getchar(); break;}case '7':{bool flag = false;//标记要删除的结点是否在家谱里cout << "请输入要删除的结点：" << endl;cin >> p;inOrder(T, p, flag);//查找结点是否在家谱里while (!flag){cout << "您要删除的结点并不存在,请重新输入：" << endl;cin >> p;inOrder(T, p, flag);}deleteNode(T, p); getchar(); break;}case '0':{ cout << " 感谢您的使用，下次再见！" << endl;exit(0);}default:{cout << "输入有误，请重新输入：" << endl;ch = getchar();}}} while (1);//cout << "hello world!" << endl;return 0;
}

---

调试分析及测试结果：

本项目以《红楼梦》贾府建立家谱树为例

进入主界面

---

建立家谱

---

生成树

---

查询操作

---

删除操作

---

写在最后

此次大作业是博主在为完成数据结构课程设计与团队共同完成，此项目比较简单，涉及到的知识点与数据结构都是在树之中扩展的，如果想完成课程设计大作业，此项目分数可以80+（根据学校不同），如果追求更高的成绩，也可以在此项目扩展功能，例如：增加称呼功能（对于任意两个人可以查询出互相称呼什么）、完善个人信息（完善结点结构体，增加年龄、性别、性格等属性）。若你们大作业距离答辩仅剩1-3天，此项目可以用来应急，具体源代码、答辩PPT、测试数据会统一放到一个资源里面，下面会更新链接。也可以私信博主，免费提供给大家。

获取文件可以添加博主vx好友，备注来意，联系我传送门：https://bbs.csdn.net/topics/619404381

最后特此鸣谢团队三人，@池鱼c0de

此篇终，感谢大家支持。