建材网站建设公司,网站首页没有权重,建设网站联系方式,佛山网页设计制作实验八 树
一、实验目的与要求
1#xff09;理解树的定义#xff1b;
2#xff09;掌握树的存储方式及基于存储结构的基本操作实现#xff1b;
二、 实验内容
题目一#xff1a;采用树的双亲表示法根据输入实现以下树的存储#xff0c;并实现输入给定结点的双亲结点…实验八 树
一、实验目的与要求
1理解树的定义
2掌握树的存储方式及基于存储结构的基本操作实现
二、 实验内容
题目一采用树的双亲表示法根据输入实现以下树的存储并实现输入给定结点的双亲结点的查找。 双亲表示法的存储结构描述如下
#define MaxSize 100 //树中最多结点数
typedef struct{ //树的结点定义 char data; //数据元素 int parent; //双亲位置域
}PTNode; typedef struct{ //树的类型定义 PTNode nodes[MaxSize]; //双亲表示 int n; //结点数
}PTree; 提示一组连续空间来存储每个结点同时在每个结点中增设一个伪指针指示其双亲结点在数组中的位置。根结点的下标为0其伪指针域为-1。
示列 题目二采用树的孩子表示法实现以上树的存储要求实现输入结点查找输出该结点的所有孩子结点没有孩子结点输出-1。选做 存储结构描述
#define MaxSize 100
typedef struct ChildNode{ //链表中每个结点的定义 //链表中每个结点存储的不是数据本身而是数据在数组中存储的位置下标 int child; struct ChildNode *next;
}ChildNode; typedef struct{ //树中每个结点的定义 char data; //结点的数据类型 ChildNode *firstchild; //孩子链表头指针
}CHNode; typedef struct{ CHNode nodes[MaxSize]; //存储结点的数组 int n;
}CTree; 示列 三、实验结果
1请将调试通过的运行结果截图粘贴在下面并说明测试用例和运行过程。
2请将源代码cpp文件和实验报告一起压缩上传。 第一题
运行结果 测试用例和运行过程
如第一题A图和B图所示测试用例为该树各个结点对应的data和parent分别为{ (R,-1) , (A,0) , (B,0) , (C,0) , (D,1) , (E,1) , (F,3) , (G,6) , (H,6) , (K,6) }。
主函数首先创建一个树通过构造树函数CreateTree依次录入结点的值及其双亲位于数组中的位置下标再输入需要查询的结点值通过查找结点函数SearchNode中的for循环遍历各个结点当且仅当结点值匹配时输出其父结点和存储位置然后跳出循环。
最终结果如运行截图所示。 实验代码
#include iostream
#include cstdio
using namespace std;#define MaxSize 100 //树中最多结点数
typedef struct{ //树的结点定义char data; //数据元素int parent; //双亲位置域
}PTNode;typedef struct{ //树的类型定义PTNode nodes[MaxSize]; //双亲表示int n; //结点数
}PTree;//构造树
void CreateTree(PTree *T){int i0;cout请输入结点个数endl;cinT-n ;cout请输入结点的值及其双亲位于数组中的位置下标endl;for( ;iT-n ;i){ cinT-nodes[i].dataT-nodes[i].parent ;}return;
}//查找结点信息
void SearchNode(PTree *T,char e){int i0,flag0;for( ;iT-n ;i){if(T-nodes[i].data e){flag1;coute的父结点为T-nodes[T-nodes[i].parent].dataendl;cout存储位置为T-nodes[i].parent endl;break;}}if(flag0){coutNOT FOUNDendl;}
}int main(){PTree T;CreateTree(T);cout请输入要查询的结点值;char element;cinelement;SearchNode(T,element);return 0;
}第二题
运行结果 测试用例和运行过程
如第二题的图所示测试用例为该树只有RACF结点具有孩子结点其余均为叶子结点。
主函数首先创建一个树通过构造树函数CreateTree首先录入结点的总数再通过外层for循环依次输入每一个结点的值、当前结点的孩子结点数量紧接着通过内层for循环依次输入当前结点的孩子结点在顺序表中存储的位置最终完成树的创建。然后通过查找孩子结点函数SearchChild输入要查找其孩子结点的结点通过for循环查找元素一致的结点确定之后判断孩子是否为空若非空则通过while循环输出每一个非空的孩子结点。
最终结果如运行截图所示。 实验代码
#include iostream
#include cstdio
#include malloc.h
using namespace std;#define MaxSize 100
typedef struct ChildNode{ //链表中每个结点的定义//链表中每个结点存储的不是数据本身而是数据在数组中存储的位置下标int child;struct ChildNode *next;
}ChildNode;typedef struct{ //树中每个结点的定义char data; //结点的数据类型ChildNode *firstchild; //孩子链表头指针
}CHNode;typedef struct{CHNode nodes[MaxSize]; //存储结点的数组int n;
}CTree;//实现输入结点查找输出该结点的所有孩子结点没有孩子结点输出-1//创建树
void CreateTree(CTree *T){cout请输入结点总数;cinT-n;int i0;for( ;iT-n;i){cout请输入第i1个结点的值;cinT-nodes[i].data;cout请输入该结点的孩子结点数量;int num;cinnum;ChildNode *mNULL;int j0;for( ;jnum;j){ChildNode *s(ChildNode *)malloc(sizeof(ChildNode)); cout请输入第j1个孩子结点在顺序表中的存储位置;cins-child;s-next NULL;if(j0){T-nodes[i].firstchild s;ms;}else{m-next s;ms;}}}
}//查找孩子结点
void SearchChild(CTree *T){char e;cout请输入要查找其孩子结点的结点;cine;int flag-1,i0;for( ;iT-n ;i){if(T-nodes[i].data e){flagi;break;}} if(flag-1){coutNot Foundendl;return;}ChildNode *pT-nodes[flag].firstchild;if(pNULL){cout此结点为叶子结点endl;return;}coute的所有孩子结点为;while(p!NULL){coutT-nodes[p-child].data ;pp-next;}
}int main(){CTree T;int i0;CreateTree(T);SearchChild(T);return 0;
}其他
#includeiostream
using namespace std;#define MaxSize 100 //树中最多结点数typedef struct{ //树的结点定义char data; //数据元素int parent; //双亲位置域
}PTNode;typedef struct{ //树的类型定义PTNode nodes[MaxSize]; //双亲表示int n; //结点数
}PTree;void Parent_PT(PTree ptree,char m){int i;for(i0;(iptree.n)(ptree.nodes[i].data!m);i);if(iptree.n) coutNode -m is not exist!endl;else{int jptree.nodes[i].parent;if(j-1)coutNode -m has not parent!endl;else{coutm的父结点为ptree.nodes[j].dataendl;coutptree.nodes[j].data的储存位置为jendl;}}
}int main(){PTree ptree;cout请输入结点个数;int num;cinnum;ptree.nnum;cout请输入结点的值以及双亲位于数组中的位置下标endl;char m;int q; for(int i0;inum;i){cinm;cinq;ptree.nodes[i].datam;ptree.nodes[i].parentq;}while(1){cout请输入要查询的结点值;cinm;if(m#){cout查询结束;break; } Parent_PT(ptree,m); } return 0;
}
#includeiostream
using namespace std;#define MaxSize 100typedef struct ChildNode{ //链表中每个结点的定义//链表中每个结点存储的不是数据本身而是数据在数组中存储的位置下标int child;struct ChildNode *next;
}ChildNode;typedef struct{ //树中每个结点的定义char data; //结点的数据类型ChildNode *firstchild; //孩子链表头指针
}CHNode;typedef struct{CHNode nodes[MaxSize]; //存储结点的数组int n;
}CTree;void Init_tree(CTree ctree){cout请输入结点总数;int num;cinnum;ctree.nnum;for(int i0;inum;i){cout请输入第i1个结点的值;char m;cinm;ctree.nodes[i].datam;ctree.nodes[i].firstchildNULL;cout请输入结点m的孩子结点数;int cnum;cincnum;if(cnum0) continue;cout请输入第1个孩子结点在顺序表中的存储位置;int l;cinl;ChildNode *pnew ChildNode;p-childl;p-nextNULL;ctree.nodes[i].firstchildp;for(int j1;jcnum;j){cout请输入第j1孩子结点在顺序表中的存储位置;cinl;ChildNode *qnew ChildNode;q-childl;q-nextNULL;p-nextq;pq;}}
}void Children(CTree ctree,char f){int j;for(j0;(jctree.n)(ctree.nodes[j].data!f);j);if(jctree.n) coutNode -f is not exist!;else{ChildNode *pctree.nodes[j].firstchild;if(!p) coutNode -f has not children!;else{coutf的所有孩子结点为 ;coutctree.nodes[p-child].data ;while(p-next!NULL){pp-next;coutctree.nodes[p-child].data ;}}}
}void Destroy(CTree ctree){for(int i0;ictree.n;i){ChildNode *pctree.nodes[i].firstchild;ChildNode *q;if(!p) continue;while(p){qp;pp-next;q-nextNULL;delete q;}ctree.nodes[i].firstchildNULL;}
} int main(){CTree ctree;Init_tree(ctree);//初始化 while(1){cout--------------------------------------endl;cout请输入要查找其孩子结点的结点; char f;cinf;if(f#){cout查询结束;break; } Children(ctree,f); coutendl;}Destroy(ctree);//释放new出的空间 return 0;
}
