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

本文主要是介绍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图的邻接储存，数据结构的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！