8. 数据结构——邻接表、邻接矩阵的基本操作

一、邻接表

1. 内容

2. 实现代码(直接可以复制使用)

//邻接表的相关操作
#include<bits/stdc++.h>
#define MVnum 100
#define OK 1
#define ERROR -1
using namespace std;

typedef int Status; 
typedef char VerTexType;  //假设顶点的数据类型为char
typedef int ArcType;      //假设边的权值类型为int
bool visit1[MVnum];      //dfs的时候状态数组 
bool visit2[MVnum];      //bfs的时候状态数组 
 
//定义结构体(边结点+头节点数组+相关信息)
//1.边结点
typedef struct ArcNode{
	int adjvex;  
	struct ArcNode *nextarc;
}ArcNode;

//2.头结点数组 
typedef struct VNode{
	VerTexType data;
	ArcNode *firstarc;
}VNode,AdList[MVnum]; 

typedef struct{
	AdList vertices;
	int vexnum,arcnum;  //图当前的顶点数、边数 
}ALGraph; 

//查找顶点值在图中存储的位置 
Status LocateVex(ALGraph G,VerTexType v){
	for(int i=0;i<G.vexnum;i++){
		if(G.vertices[i].data==v)
			return i;
	}
	return -1;  //表示未找到 
}


//1.创建有向图
Status CreateDG(ALGraph &G){
	VerTexType v1,v2;  //临时值 
	cout<<"输入总顶点、总边数:"<<endl;
	cin>>G.vexnum>>G.arcnum;
	cout<<"输入每个顶点的值"<<endl; 
	for(int i=0;i<G.vexnum;i++){
		cin>>G.vertices[i].data;
		G.vertices[i].firstarc=NULL;   //头结点指向为空 
	}
	for(int i=0;i<G.arcnum;i++){
		cout<<"请输入两个邻接的点:"<<endl; 
		cin>>v1>>v2;
		int t1=LocateVex(G,v1); 
		int t2=LocateVex(G,v2);
		//建立从t1->t2的边 
		ArcNode *p1=new ArcNode;  //建立一个新边结点
		p1->adjvex=t2;
		p1->nextarc=G.vertices[t1].firstarc;
		G.vertices[t1].firstarc=p1; 
//		//建立从t2->t1的边 
//		ArcNode *p2=new ArcNode;  //建立一个新边结点
//		p2->adjvex=t1;
//		p2->nextarc=G.vertices[t2].firstarc;
//		G.vertices[t2].firstarc=p2; 
	}
	return OK; 
}

//计算有向图的出度 
Status CalculateDGO(ALGraph G,VerTexType v){
	int x=0;
	int i=LocateVex(G,v);  //得到该顶点的位置
	if(i==-1) return ERROR;
	ArcNode *p=G.vertices[i].firstarc;
	while(p){
		x++;
		p=p->nextarc;
	} 
	return x;
} 
//有向图的入度
//需要把每个顶点遍历一次,找到到点i的情况,增加1 
Status CalculateDGI(ALGraph G,VerTexType v){
	int x=0;
	int i=LocateVex(G,v);  //得到该顶点的位置
	if(i==-1) return ERROR;
	for(int k=0;k<G.vexnum;k++){
		ArcNode *p=G.vertices[k].firstarc;
		while(p){
			if(p->adjvex==i)
				x++;
			p=p->nextarc;
		}
	}
	return x;
} 
//有向图的总度 
Status CalculateSum(ALGraph G,VerTexType v){
	if(LocateVex(G,v)==-1) return ERROR;
	return CalculateDGO(G,v)+CalculateDGI(G,v);
}

//深度优先遍历 
void dfs(ALGraph G,int v){
	cout<<G.vertices[v].data;
	visit1[v]=true;  //表明已经遍历过
	ArcNode *p=G.vertices[v].firstarc;
	while(p){
		if(!visit1[p->adjvex])
			dfs(G,p->adjvex);
		p=p->nextarc;	
	}
} 

//广度优先遍历 
void bfs(ALGraph G,VerTexType v){
	int x=LocateVex(G,v);
	queue<int> q;  //队列
	q.push(x);
	visit2[x]=true;  //表示已经遍历过
	while(!q.empty()){
		int t=q.front();
		q.pop();
		cout<<G.vertices[t].data;
		//找t位置结点相邻的未被访问的点
		ArcNode *p=G.vertices[t].firstarc;
		while(p){
			if(!visit2[p->adjvex]){
				q.push(p->adjvex);
				visit2[p->adjvex]=true;
			}
			p=p->nextarc;
		} 
	} 
} 

//输出在数据库中本身存储形式 
void Reverse(ALGraph G){
	for(int i=0;i<G.vexnum;i++){
		if(i!=0)  cout<<endl;
		cout<<G.vertices[i].data;
		ArcNode *p=G.vertices[i].firstarc;
		while(p){
			cout<<"->"<<G.vertices[p->adjvex].data;
			p=p->nextarc;
		}
	} 
} 

void menu(){
	cout<<"==========================="<<endl;
	cout<<"          菜单             "<<endl; 
	cout<<"==========================="<<endl;
	cout<<"     1.图的建立            "<<endl;
	cout<<"     2.求顶点的度          "<<endl;
	cout<<"     3.深度优先遍历        "<<endl;
	cout<<"     4.广度优先遍历        "<<endl; 
	cout<<"     5.输出存储结构        "<<endl; 
	cout<<"     0.退出程序            "<<endl; 
	cout<<"==========================="<<endl; 
} 

int main(void) {
	VerTexType v;
	ALGraph G;
	char order;
	int t;
	menu();
	cout<<"请输入你的选择:";
	cin>>order;
	while(order!='0'){
		switch(order){
			case '1':
				CreateDG(G);
				cout<<"此有向图的邻接表建立成功!!!"<<endl;
				cout<<"此有向图在邻接表中存储结构为:"<<endl; 
				Reverse(G);
				cout<<endl;
				break;
			case '2':
				cout<<"请输入需要查找度数的顶点:";
				cin>>v;
				if(LocateVex(G,v)==-1)
					cout<<v<<"不存在于此图中"<<endl;
				else {
					cout<<"顶点"<<v<<"的出度为:"<<CalculateDGO(G,v)<<endl;
					cout<<"顶点"<<v<<"的入度为:"<<CalculateDGI(G,v)<<endl;
					cout<<"顶点"<<v<<"的总度为:"<<CalculateSum(G,v)<<endl; 
				}		
				break;
			case '3':
				cout<<"请输出深度优先遍历的起点:";
				cin>>v; 
				memset(visit1,false,sizeof(visit1));
				t=LocateVex(G,v);
				cout<<"深度优先遍历结果为:";
				dfs(G,t);
				cout<<""<<endl; //实现换行 
				break;
			case '4':
				cout<<"请输出广度优先遍历的起点:";
				cin>>v; 
				memset(visit2,false,sizeof(visit2));
				cout<<"广度优先遍历结果为:";
				bfs(G,v);
				cout<<""<<endl; //实现换行 
				break;		
			case '5':
				cout<<"此有向图在邻接表中存储结构为:"<<endl; 
				Reverse(G);
				cout<<endl;
				break;	
			case '0':
				cout<<"程序终止";
				break;
			default:
				cout<<"输入不合法,重新输入"<<endl;				 
			}
		if(order!='0'){
			menu();
			cout<<"请输入你的选择:";
			cin>>order;
		}
	}
	return 0;
}

二、邻接矩阵

因为邻接矩阵大部分实现代码和邻接表一致,故这里就只写了邻接矩阵的创建。

#include<bits/stdc++.h>
#define MVnum 100
using namespace std;
 
typedef int Status;
typedef char VerTexType;   //假设每个顶点的数据类型是char 
typedef int ArcType;      //假设每条边权值的数据类型是int

typedef struct{
	VerTexType vexs[MVnum];   //顶点表 
	int vexnum,arcnum;  //图当前的顶点数和边数
	ArcType arcs[MVnum][MVnum];  //邻接矩阵存储权值 
}AMGraph; 

//给定顶点值,找到其位置 
Status LocateVex(AMGraph G,VerTexType v){
	for(int i=0;i<G.vexnum;i++){
		if(G.vexs[i]==v)
			return i;
	}
	return -1;
}

//1.建立有向图 
Status CreateDG(AMGraph &G){
	VerTexType v1,v2; 
	cout<<"输入总顶点、总边数:"<<endl;
	cin>>G.vexnum>>G.arcnum;
	cout<<"输入每个顶点的值"<<endl; 
	for(int i=0;i<G.vexnum;i++){
		cin>>G.vexs[i];
	}
	for(int i=0;i<G.arcnum;i++){
		cout<<"请输入两个邻接的点:"<<endl; 
		cin>>v1>>v2; 
		int t1=LocateVex(G,v1); 
		int t2=LocateVex(G,v2);
		G.arcs[t1][t2]=1;
	}
}

//2.输出 
void Reverse(AMGraph G){
	for(int i=0;i<G.vexnum;i++){
		if(i!=0) cout<<endl;
		for(int j=0;j<G.vexnum;j++){
			cout<<G.arcs[i][j]<<" ";
		}
	}
}

int main(void){
	AMGraph G;
	CreateDG(G);
	Reverse(G);
	return 0;
} 

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

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

相关文章

Kafka 基础入门

文章内容是学习过程中的知识总结&#xff0c;如有纰漏&#xff0c;欢迎指正 文章目录 前言 1. 核心概念 1.1 Producer 1.2 broker 1.3 consumer 1.4 zookeeper 1.5 controller 1.6 Cluster 2. 逻辑组件 2.1 Topic 2.2 Partition 2.3 Replication 2.4 leader & follower 3. …

qt QDialog详解

1、概述 QDialog是Qt框架中用于创建对话框的类&#xff0c;它继承自QWidget。QDialog提供了一个模态或非模态的对话框&#xff0c;用于与用户进行交互。模态对话框会阻塞其他窗口的输入&#xff0c;直到用户关闭该对话框&#xff1b;而非模态对话框则允许用户同时与多个窗口进…

从0开始学PHP面向对象内容之(类,对象,构造/析构函数)

上期我们讲了面向对象的一些基本信息&#xff0c;这期让我们详细的了解一下 一、面向对象—类 1、PHP类的定义语法&#xff1a; <?php class className {var $var1;var $var2 "constant string";function classfunc ($arg1, $arg2) {[..]}[..] } ?>2、解…

双向链表及如何使用GLib的GList实现双向链表

双向链表是一种比单向链表更为灵活的数据结构&#xff0c;与单向链表相比可以有更多的应用场景&#xff0c;本文讨论双向链表的基本概念及实现方法&#xff0c;并着重介绍使用GLib的GList实现单向链表的方法及步骤&#xff0c;本文给出了多个实际范例源代码&#xff0c;旨在帮助…

一键搞定表格文件管理与转换,轻松将XLS格式的表格文件转换为TXT格式的文本文档,办公软件是提高工作效率的方法

在办公的海洋里&#xff0c;表格文件如同繁星点点&#xff0c;而XLS格式更是其中的璀璨明珠。但有时候&#xff0c;我们需要将这些明珠的光芒以另一种形式展现——比如&#xff0c;转换成TXT格式的文本文档。这时&#xff0c;首助编辑高手软件就像一位魔法师&#xff0c;轻轻一…

初始Docker

概述&#xff1a; 容器&#xff0c;作为云原生技术的重要组成部分&#xff0c;与虚拟机一样&#xff0c;均属于虚拟化技术的范畴。然而&#xff0c;容器技术以其独特的优势&#xff0c;在虚拟化领域中脱颖而出。与虚拟机不同&#xff0c;容器能够摆脱操作系统的束缚&#xff0…

TikTok如何用邮箱注册?用哪种邮箱比较好?

要在TikTok上创建一个账号&#xff0c;首先需要进行注册&#xff0c;这是一个简单但至关重要的步骤。在本篇文章中&#xff0c;我们将详细介绍如何用邮箱注册TikTok的整个过程&#xff0c;包括每个步骤的细节和注意事项。此外&#xff0c;我们还将讨论选择哪种邮箱比较好&#…

输电线路绝缘子缺陷分割系统:轻松训练模式

输电线路绝缘子缺陷分割系统源码&#xff06;数据集分享 [yolov8-seg&#xff06;yolov8-seg-C2f-MSBlock等50全套改进创新点发刊_一键训练教程_Web前端展示] 1.研究背景与意义 项目参考ILSVRC ImageNet Large Scale Visual Recognition Challenge 项目来源AAAI Global Al …

flink 自定义kudu connector中使用Metrics计数平均吞吐量,并推送到自定义kafkaReporter

文章目录 前言1. Registering metrics2. Metrics 的类型2.1 counter2.2 Gauge2.3 Histogram2.4 meter 3. 指标划分3.1 指标所属的范围3.2 默认所属 4. 自定义kudu connector中使用Metrics4.1 sink算子继承RichFunction4.2 注册指标4.3 计数逻辑4.4 自定义Reporter&#xff0c;推…

Calling short variants with GATK4

计算生物学实验5: Calling short variants with GATK4 1. 实验目的 本实验目的是利用 GATK4 工具准确高效地检测出基因组中的短变异。通过该工具对样本基因组进行分析&#xff0c;旨在发现单核苷酸变异&#xff08;SNV&#xff09;和小的插入缺失&#xff08;Indel&#xff0…

【D3.js in Action 3 精译_038】4.2 D3 折线图的绘制方法及曲线插值处理

当前内容所在位置&#xff08;可进入专栏查看其他译好的章节内容&#xff09; 第一部分 D3.js 基础知识 第一章 D3.js 简介&#xff08;已完结&#xff09; 1.1 何为 D3.js&#xff1f;1.2 D3 生态系统——入门须知1.3 数据可视化最佳实践&#xff08;上&#xff09;1.3 数据可…

《机器学习by周志华》学习笔记-神经网络-04全局最小误差与局部极小误差

1、神经网络中误差的概念及公式 根据上文《逆误差传播算法》我们可以知道误差公式的演化: ① 第k个训练样例的误差函数: ②该训练集的累积误差函数: ③正则化误差目标函数: 其中: :表示第k个训练样例的误差;:表示连接权重和阈值任意参数;根据上文我们可知需要确定的参…

每日读则推(十四)——Meta Movie Gen: the most advanced media foundation models to-date

premiere n.首映,首次公演 v.首次公演(戏剧、音乐、电影) a.首要的,最早的 Today we’re premiering Meta Movie Gen: the most advanced media foundation models to-date. 迄今,到现在为止 …

大模型面试题全面总结:每一道都是硬核挑战

节前&#xff0c;我们组织了一场算法岗技术&面试讨论会&#xff0c;邀请了一些互联网大厂同学、参加社招和校招面试的同学&#xff0c;针对算法岗技术趋势、大模型落地项目经验分享、新手如何入门算法岗、该如何准备、面试常考点分享等热门话题进行了深入的讨论。 今天分享…

c++文件操作中的seekp函数使用方法

seekp函数能设置输出流的位置 比如我先向文件输入了123456&#xff0c;现在我想在第四个字符后面再加上ABC&#xff0c;这个时候我们就可以用seekp函数来设置输出的位置 #include <iostream> #include <fstream> #include <string>using namespace std;int …

Python小白学习教程从入门到入坑------第二十三课 封装(语法进阶)

面向对象的三大特征&#xff1a;封装、继承、多态 一、封装 1.1 何为封装 封装&#xff1a;在Python中指的是隐藏对象中一些不希望被外部所访问到的属性或者方法。将复杂的信息、流程给包起来&#xff0c;内部处理&#xff0c;让使用者只需要通过简单的操作步骤&#xff0c;…

less解决function中return写法在浏览器被识别成Object导致样式失败的问题

问题描述&#xff1a; 一开始写的是: baseFontSize: 37.5px;//基于屏幕尺寸/10得出的基准font-size// return失败,浏览器显示为[object Object],[object Object] .pxToRem(px){value: px / baseFontSize * 1rem;return value; } 使用height: .pxToRem(40px);之后浏览器却是这…

OpenCV视觉分析之目标跟踪(4)目标跟踪类TrackerDaSiamRPN的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 cv::TrackerDaSiamRPN 是 OpenCV 中用于目标跟踪的一个类&#xff0c;它实现了 DaSiam RPN&#xff08;Deformable Siamese Region Proposal Net…

高效视频制作大提速,视频剪辑软件的高级自定义命令功能批量调整视频的色调、饱和度和亮度,轻松驾驭视频编辑技巧

在浩瀚的数字海洋中&#xff0c;视频如同璀璨的星辰&#xff0c;而每一颗星辰都渴望被精心雕琢&#xff0c;闪耀出最独特的光芒。想象一下&#xff0c;你手握一把神奇的钥匙&#xff0c;能够轻松解锁批量视频剪辑的奥秘&#xff0c;让每一帧画面都跃动着你的创意与激情。这把钥…

Vue3入门--[vue/compiler-sfc] Unexpected token, expected “,“ (18:0)

新手小白学习Vue–入门就踩坑系列 问题描述 创建了一个Person.vue&#xff0c;保存后直接报错&#xff1a; [plugin:vite:vue] [vue/compiler-sfc] Unexpected token, expected "," (18:0) 在网上搜了半天也没找到原因&#xff0c;最后还得靠自己&#xff0c;现将解…