STL图的邻接储存,数据结构

2021/11/25 6:13:51

本文主要是介绍STL图的邻接储存,数据结构,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

这里的代码也是修改了好久bug才跑起来的,具体为什么行与不行我也不是很懂,因为我没有系统学过STL,好了废话不多说。
在这里插入图片描述
一共四个头文件,一个cpp文件
C.h存放需要用到的头文件
AdjListGraph.h设计有向图邻接表储存结构类
ArcT.h是为模板确定具体的弧信息结构
VerT.h是为模板确定具体的结点信息结构
main.cpp主程序

复制过去直接可以跑起来

C.h
#ifndef _C_H_
#define _C_H_
//#include<bits/stdc++.h>
#include<iostream>
#include<fstream> //fin等
#include<iomanip> //setw()等
#include<cmath> //数学函数等头文件
#include<vector> //STL向量
#include<list> //STL链表
#include<stack> //STL栈
#include<queue> //STL队列和优先队列
#include<deque> //STL双向队列
#include<string>
#include<bitset> //位集合
#include<algorithm> //STL中通用算法
#include<ctime> //clock()等
#include<cstdarg> //提供宏va_start\va_arg\va_end,用于存取边长参数列表
#include<assert.h> //assert宏
using namespace std;
#endif
ArcT.h
struct A
{
	double weight;
};

VerT.h
#ifndef _VerT_H_
#define _VerT_H_
#include "C.h"
struct V
{
	string name;
};
#endif
AdjListGraph.h
#ifndef _ADJLISTGRAPH_H_
#define _ADJLISTGRAPH_H_
#include "C.h"
template<typename ArcT>
struct ArcTNode
{
	int adjvex;//邻接顶点序号
	ArcT arc;//弧信息
};
template<typename VerT,typename ArcT>
struct VerTNode
{
	VerT vex;//顶点信息
	int k;//顶点序号,在图中的位置
	list<ArcTNode<ArcT>> arcs;//列表表示邻接表的一行
};
template<typename VerT, typename ArcT>
class AdjListGraph
{
public:
	vector<VerTNode<VerT, ArcT>> vexs;//公有成员
	int vexnum, arcnum;//图当前的顶点数和弧数
	double weight;//是否是带权图,默认有向图
	void Create()
	{
		int n, m, g;
		ArcTNode<ArcT> e;//好像是这两个没有构造函数
		VerTNode<VerT, ArcT> v;
		cin >> n >> m >> g;
		vexnum = n;
		arcnum = m;
		weight = g;
		//vexs.assign(n,v);//开辟n个数据空间
		for (int i = 0; i < n; i++)//顶点从零开始
		{
			//cin >> v.vex;
			v.k = i;
			vexs.push_back(v);
		}
		for (int i = 0; i < m; i++)
		{
			//输入结点信息,进行定位
			int k;//从零开始
			cin >> k >> e.adjvex;//先输入结点
			if (weight)
			{
				cin >> e.arc.weight;
			}
			vexs[k].arcs.push_front(e);
		}
	}
	void Display()const
	{//输出邻接表矩阵
		int i;
		//typename 
		//typename list<ArcTNode<ArcT>>::iterator p;
		string s1 = "无权图";
		if (weight)
		{
			s1 = "有权图";
		}
		cout << "此图含 " << vexnum << " 个顶点 " << arcnum << " 条弧的" << s1 << endl;
		cout << "各顶点依次是" << endl;
		for (i = 0; i < vexnum; i++)
		{
			//cout << vexs[i].vex;
		}
		cout << endl;
		cout << "各条弧分别是" << endl;
		for (i = 0; i < vexnum; i++)
		{
			for (typename list<ArcTNode<ArcT>>::const_iterator p = vexs[i].arcs.begin(); p != vexs[i].arcs.end(); p++)
			{
				//OutputArc(weight, vexs[i].vex, vexs[p->adjvex].vex, p->arc);
				cout << i << " " << p->adjvex << " ";
				if (weight)
				{
					cout << p->arc.weight;
				}
				cout << endl;
			}
		}
	}
};
#endif
main.cpp
#include "AdjListGraph.h"
#include "VerT.h"
#include "ArcT.h"
//hhh我终于成了
int main()
{
	AdjListGraph<V, A> g;
	g.Create();
	g.Display();
}


输入样例
顶点数 弧数 是否为有权图(0无1有)
n m k
然后是m条弧信息
尾结点 头节点 (如果有权值输入权值)
一条一行

3 3 1
0 1 2
0 2 3
1 2 5

在这里插入图片描述
注意默认第一个顶点为0,如有两个顶点,则分别为0和1

写的还不够完善,输出其实和不用模板没什么区别,理想的效果是不输入数字,比如输入a代表一个结点,然后接受a并在图中定位属于他的序号,弧信息存储在该序号结点中。这点不难实现,但我认为那样输入太麻烦了,还是直接输入序号方便
在这里插入图片描述
参考书籍:数据结构算法与解析(STL版) 高一凡



这篇关于STL图的邻接储存,数据结构的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程