【数据结构】实验八：树

实验八 树

一、实验目的与要求

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 i=0;
	cout<<"请输入结点个数："<<endl;
	cin>>T->n ;
	cout<<"请输入结点的值及其双亲位于数组中的位置下标："<<endl;
	for( ;i<T->n ;i++){ 
		cin>>T->nodes[i].data>>T->nodes[i].parent ;
	}
	return;
}

//查找结点信息 
void SearchNode(PTree *T,char e){
	int i=0,flag=0;
	for( ;i<T->n ;i++){
		if(T->nodes[i].data ==e){
			flag=1;
			cout<<e<<"的父结点为："<<T->nodes[T->nodes[i].parent].data<<endl;
			cout<<"存储位置为："<<T->nodes[i].parent <<endl;
			break;
		}
	}
	if(flag==0){
		cout<<"NOT FOUND"<<endl;
	}
}

int main(){
	PTree T;
	CreateTree(&T);
	cout<<"请输入要查询的结点值：";
	char element;
	cin>>element;
	SearchNode(&T,element);
	return 0;
}

第二题：

运行结果：

 

测试用例和运行过程：

如第二题的图所示，测试用例为该树，只有R，A，C，F结点具有孩子结点，其余均为叶子结点。

主函数首先创建一个树，通过构造树函数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<<"请输入结点总数：";
	cin>>T->n;
	int i=0;
	for( ;i<T->n;i++){
		cout<<"请输入第"<<i+1<<"个结点的值：";
		cin>>T->nodes[i].data;
		cout<<"请输入该结点的孩子结点数量：";
		int num;
		cin>>num;
		ChildNode *m=NULL;
		int j=0;
		for( ;j<num;j++){
			ChildNode *s=(ChildNode *)malloc(sizeof(ChildNode)); 
			cout<<"请输入第"<<j+1<<"个孩子结点在顺序表中的存储位置：";
			cin>>s->child;
			s->next = NULL;
			if(j==0){
				T->nodes[i].firstchild = s;
				m=s;
			}
			else{
				m->next = s;
				m=s;
			}
		}
	}
}

//查找孩子结点 
void SearchChild(CTree *T){
	char e;
	cout<<"请输入要查找其孩子结点的结点：";
	cin>>e;
	int flag=-1,i=0;
	for( ;i<T->n ;i++){
		if(T->nodes[i].data == e){
			flag=i;
			break;
		}
	} 
	if(flag==-1){
		cout<<"Not Found"<<endl;
		return;
	}
	ChildNode *p=T->nodes[flag].firstchild;
	if(p==NULL){
		cout<<"此结点为叶子结点"<<endl;
		return;
	}
	cout<<e<<"的所有孩子结点为：";
	while(p!=NULL){
		cout<<T->nodes[p->child].data<<" ";
		p=p->next;
	}
}

int main(){
	CTree T;
	int i=0;
	CreateTree(&T);
	SearchChild(&T);
	return 0;
}

其他：

#include<iostream>
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(i=0;(i<ptree.n)&&(ptree.nodes[i].data!=m);i++);
	if(i>=ptree.n) 	cout<<"Node -"<<m<<" is not exist!"<<endl;
	else{
		int j=ptree.nodes[i].parent;
    	if(j==-1)
    	cout<<"Node -"<<m<<" has not parent!"<<endl;
    	else{
     		cout<<m<<"的父结点为："<<ptree.nodes[j].data<<endl;
        	cout<<ptree.nodes[j].data<<"的储存位置为："<<j<<endl;
        }
	}
}

int main(){
	PTree ptree;
	cout<<"请输入结点个数：";
	int num;cin>>num;
	ptree.n=num;
	cout<<"请输入结点的值以及双亲位于数组中的位置下标："<<endl;
	char m;int q; 
	for(int i=0;i<num;i++){
		cin>>m;cin>>q;
		ptree.nodes[i].data=m;
        ptree.nodes[i].parent=q;
	}
	while(1){
    	cout<<"请输入要查询的结点值：";
    	cin>>m;
    	if(m=='#'){
    		cout<<"查询结束！";
			break; 
		} 
    	Parent_PT(ptree,m);	
	} 
	return 0;
} 


#include<iostream>
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;

void Init_tree(CTree &ctree){
	cout<<"请输入结点总数：";
	int num;cin>>num;
	ctree.n=num;
	for(int i=0;i<num;i++){
		cout<<"请输入第"<<i+1<<"个结点的值：";
		char m;cin>>m;
		ctree.nodes[i].data=m;
		ctree.nodes[i].firstchild=NULL;
		cout<<"请输入结点"<<m<<"的孩子结点数：";
		int cnum;cin>>cnum;
		if(cnum==0) continue;
		cout<<"请输入第1个孩子结点在顺序表中的存储位置：";
		int l;cin>>l;
		ChildNode *p=new ChildNode;
		p->child=l;
		p->next=NULL;
		ctree.nodes[i].firstchild=p;
		for(int j=1;j<cnum;j++){
			cout<<"请输入第"<<j+1<<"孩子结点在顺序表中的存储位置：";
			cin>>l;
			ChildNode *q=new ChildNode;
			q->child=l;
			q->next=NULL;
			p->next=q;
			p=q;
		}
	}
}

void Children(CTree &ctree,char f){
	int j;
	for(j=0;(j<ctree.n)&&(ctree.nodes[j].data!=f);j++);
	if(j>=ctree.n) cout<<"Node -"<<f<<" is not exist!";
	else{
		ChildNode *p=ctree.nodes[j].firstchild;
		if(!p) cout<<"Node -"<<f<<" has not children!";
		else{
			cout<<f<<"的所有孩子结点为： ";
			cout<<ctree.nodes[p->child].data<<" ";
			while(p->next!=NULL){
				p=p->next;
		    	cout<<ctree.nodes[p->child].data<<" ";
			}
		}
	}
}

void Destroy(CTree &ctree){
	for(int i=0;i<ctree.n;i++){
		ChildNode *p=ctree.nodes[i].firstchild;
		ChildNode *q;
		if(!p) continue;
		while(p){
			q=p;
			p=p->next;
			q->next=NULL;
			delete q;
		}
		ctree.nodes[i].firstchild=NULL;
	}
} 

int main(){
	CTree ctree;
	Init_tree(ctree);//初始化 
	while(1){
		cout<<"--------------------------------------"<<endl;
    	cout<<"请输入要查找其孩子结点的结点："; 
    	char f;cin>>f;
    	if(f=='#'){
    		cout<<"查询结束！";
			break; 
		} 
    	Children(ctree,f);	
    	cout<<endl;
	}
	Destroy(ctree);//释放new出的空间 
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/49497.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

QT: 用定时器完成闹钟的实现

QT: 用定时器完成闹钟的实现

闹钟项目&#xff1a; widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QTimerEvent> #include <QTime> #include <QDebug> #include <QTextToSpeech> #include <QMessageBox> #include <QTimer>QT_BEGIN…
阅读更多...
在本地git仓库查看远端的URL

在本地git仓库查看远端的URL

右键调出选项栏 选择git-远端&#xff0c;选择远端的内容就可以看到URL了
阅读更多...
大数据未来的前景怎么样？_光点科技

大数据未来的前景怎么样？_光点科技

随着科技的迅猛发展和互联网的普及&#xff0c;大数据已成为当今社会中不可或缺的重要资源。大数据是指庞大而复杂的数据集合&#xff0c;这些数据通过高级计算技术进行处理和分析&#xff0c;可以揭示出有价值的信息和趋势。在过去几年中&#xff0c;大数据已经在各行各业产生…
阅读更多...
JVM-类加载

JVM-类加载

1.了解冯诺依曼计算机结构 1.1计算机处理数据过程 (1)提取阶段:由输入设备把原始数据或信息输入给计算机存储器存起来 (2)解码阶段:根据CPU的指令集架构(ISA)定义将数值解译为指令 (3)执行阶段:再由控制器把需要处理或计算的数据调入运算器 (4)最终阶段:由输出设备把最后运…
阅读更多...
一百三十七、Hive——HQL运行报错（持续更新中）

一百三十七、Hive——HQL运行报错（持续更新中）

一、timestamp字段与int字段相加 &#xff08;一&#xff09;场景 change_time字段是timestamp字段&#xff0c;代表一个红绿灯周期的开始时间&#xff08;先是绿灯、再是黄灯、最后红灯&#xff09;&#xff0c;而green是int字段&#xff0c;代表绿灯的秒数&#xff0c;现在…
阅读更多...
github前端开源json2html

github前端开源json2html

软件介绍 前端低代码工具包&#xff0c;通过 JSON 配置就能生成各种页面。 应用场景 json解析超大数据动态渲染&#xff0c;渲染速度、性能解决问题 包引用列表 vue3 (cdn模式开发)element plusnodehttp-serveraxios 操作步骤 1.环境准备下载node&#xff1a;https://no…
阅读更多...
【多任务编程-线程通信】

【多任务编程-线程通信】

进程/线程通信的方式 某些应用程序中&#xff0c;进程/进程和线程/线程之间不可避免的进行通信&#xff0c;进行消息传递&#xff0c;数据共享等 同一进程的线程之间通信方式包括Windows中常用Event, Message等。 不同进程之间的通信可以利用Event, FileMapping(内存共享), W…
阅读更多...
基于SSM+JSP+LayUI的宿舍管理系统

基于SSM+JSP+LayUI的宿舍管理系统

修正初始账号密码 默认账号&#xff1a;admin&#xff0c;默认密码&#xff1a;123456修复后台管理头像消失功能相对简单些&#xff0c;可能需要添加一些功能&#xff0c;需要源码免费提供需要运行服务、添加功能等联系我视频教程&#xff1a;【源码分享-Java系列】毕设 基于SS…
阅读更多...
[NLP]使用Alpaca-Lora基于llama模型进行微调教程

[NLP]使用Alpaca-Lora基于llama模型进行微调教程

Stanford Alpaca 是在 LLaMA 整个模型上微调&#xff0c;即对预训练模型中的所有参数都进行微调&#xff08;full fine-tuning&#xff09;。但该方法对于硬件成本要求仍然偏高且训练低效。 [NLP]理解大型语言模型高效微调(PEFT) 因此&#xff0c; Alpaca-Lora 则是利用 Lora…
阅读更多...
【Kafka】消息队列Kafka进阶

【Kafka】消息队列Kafka进阶

目录 Kafka分区机制生产者分区写入策略轮询策略随机策略&#xff08;不用&#xff09;按key分配策略乱序问题自定义分区策略 消费者组Rebalance机制消费者分区分配策略Range范围分配策略RoundRobin轮询策略Stricky粘性分配策略 Kafka副本机制producer的ACKs参数acks配置为0acks…
阅读更多...
Redis系列：Redis 的事务机制

Redis系列：Redis 的事务机制

1 复习下何为事务机制&#xff1f; Transaction&#xff08;事务&#xff09;是计算机的特有术语&#xff0c;它一般指单个逻辑工作单位&#xff0c;由一系列的操作组合而成&#xff0c;在这些操作执行的时候&#xff0c;要么都执行成功&#xff0c;要么都不执行&#xff0c;防…
阅读更多...
okhttp原理分析

okhttp原理分析

工程目录图 请点击下面工程名称&#xff0c;跳转到代码的仓库页面&#xff0c;将工程 下载下来 Demo Code 里有详细的注释 01okhttp module里 包含的设计模式&#xff1a;建造者设计模式、责任链设计模式 CustomInject 演示自定义注解 代码&#xff1a;okhttp原理分析、Andro…
阅读更多...
transformer理解

transformer理解

transformer的理解 Q、K、V的理解 核心是自注意力机制。即每个位置的结果为所有位置的加权平均和。为了得到每个位置的权重，需要Q*K得到。 整个多头的self-attention过程 单个encoder encoder-decoder encoder中的K和V会传到decoder中的encoder-decoder attention中。 …
阅读更多...
Docker 全栈体系（八）

Docker 全栈体系（八）

Docker 体系&#xff08;高级篇&#xff09; 六、Docker轻量级可视化工具Portainer 1. 是什么 Portainer 是一款轻量级的应用&#xff0c;它提供了图形化界面&#xff0c;用于方便地管理Docker环境&#xff0c;包括单机环境和集群环境。 2. 安装 官网 https://www.portain…
阅读更多...
第三章 数据链路层

第三章 数据链路层

第三章 数据链路层 3.1 数据链路层的几个基本概念 数据发送模型 数据链路层主要的两种信号类型 点对点信号&#xff1a;这种信道使用一对一的点对点通信方式&#xff1b;广播信道&#xff1a;这种信道使用一对多的广播方式&#xff0c;因此过程比较复杂。广播信道上连接的主机…
阅读更多...
【【萌新的stm32学习-1】】

【【萌新的stm32学习-1】】

萌新的stm32学习 冯诺依曼结构 采用了分时复用的结构 优点&#xff1a;总线资源占用少 缺点&#xff1a;执行效率低 哈佛结构 执行效率高 总线资源占用多 RISC 这是精简指令集的意思 arm公司 ARMv9是2021年发布的最新 Cortex-A 最好高性能 Cortex-R 中 Cortex-M 低 何为STM…
阅读更多...
八、Kafka时间轮与常见问题

八、Kafka时间轮与常见问题

Kafka与时间轮 Kafka中存在大量的延时操作。 1、发送消息-超时重试机制 2、ACKS 用于指定分区中必须要有多少副本收到这条消息&#xff0c;生产者才认为写入成功&#xff08;延时 等&#xff09; Kafka并没有使用JDK自带的Timer或者DelayQueue来实现延迟的功能&#xff0c;而…
阅读更多...
实验室功率放大器怎么选择参数

实验室功率放大器怎么选择参数

实验室功率放大器是一种用于实验室研究和测试的电子设备&#xff0c;其主要功能是将微弱电信号放大到足够的水平以便进行研究和分析。在选择实验室功率放大器时&#xff0c;需要考虑多个参数&#xff0c;以便确保符合实验的需求。 以下是一些常见的实验室功率放大器参数和选择方…
阅读更多...
工欲善其事必先利其器，IT工作电脑更要维护好

工欲善其事必先利其器，IT工作电脑更要维护好

目录 一&#xff1a;电脑的组成 二&#xff1a;维护措施 三&#xff1a;助力记忆 一&#xff1a;电脑的组成 当谈到电脑主机时&#xff0c;我们通常指的是电脑的中央处理器(CPU)、内存、主板、电源、硬盘、显卡、声卡、网卡等核心部件组成的整体。这些部件共同协作&#xff…
阅读更多...
探索单例模式：设计模式中的瑰宝

探索单例模式：设计模式中的瑰宝

文章目录 常用的设计模式有以下几种&#xff1a;一.创建型模式&#xff08;Creational Patterns&#xff09;&#xff1a;二.结构型模式&#xff08;Structural Patterns&#xff09;&#xff1a;三.行为型模式&#xff08;Behavioral Patterns&#xff09;&#xff1a;四.并发…
阅读更多...
最新文章

Copyright @ 2022~2023