中和阗盛工程建设有限公司网站,wordpress 文章透明,kindeditor wordpress,wordpress模板放目录
设计思路#xff1a;
一、项目背景
二、功能分析
查询功能流程图#xff1a;
管理功能流程图#xff1a;
三、设计
四、实现
代码实现#xff1a;
头文件
结构体
函数声明及定义
创建家谱树头结点
绘制家谱树#xff08;打印#xff09;
建立右兄弟…目录
设计思路
一、项目背景
二、功能分析
查询功能流程图
管理功能流程图
三、设计
四、实现
代码实现
头文件
结构体
函数声明及定义
创建家谱树头结点
绘制家谱树打印
建立右兄弟
建立左孩子
建立孩子结点信息
查找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的家庭 四、实现
完善家谱功能流程图 代码实现
头文件
#includeiostream
#includewindows.h
#include stdio.h
#include stdlib.h
#includestring 结构体
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;//打印家谱时为左孩子n1,整体向右推移一位右兄弟依然是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-datax时通过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;
} 完整代码
#includeiostream
#includewindows.h
#include stdio.h
#include stdlib.h
#includestringusing 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;//打印家谱时为左孩子n1,整体向右推移一位右兄弟依然是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-datax时通过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
此篇终感谢大家支持。
