C++实现有向图邻接表的构建
本文实例为大家分享了C++实现有向图邻接表的构建代码,供大家参考,具体内容如下
数据结构里面的一道基础题,分享下自己的写法,验证可跑。
#include<iostream>
#include<string>
const int MAX = 20;
using namespace std;
struct ArcNode { //弧结点
int adjvex = -1; //所指顶点位置
ArcNode *nextarc = nullptr; //下一条狐指针
size_t info = 0; //弧信息
};
struct VNode { //顶点
string data = "0";
ArcNode *firstarc = nullptr; //第一条依附该顶点的弧的指针
};
struct Graph { //图结构
VNode vertices[MAX]; //全部顶点
int vexnum, arcnum; //顶点数和弧数
Graph(int m, int n) :vexnum(m), arcnum(n) {};
Graph() :vexnum(0), arcnum(0) {};
};
int main()
{
int vnum, anum, tempanum = 0;
cout << "输入顶点数:";
cin >> vnum;
cout << "输入弧数:";
cin >> anum;
cout << "\n\n";
Graph G(vnum, anum);
for (int i = 0; i != vnum; ++i) {
cout << "输入结点" << i << "的信息:";
cin >> G.vertices[i].data;
if (tempanum != anum)
cout << "输入依靠此结点的弧的信息(输入-1以停止):\n";
else
cout << "已输入所有弧的信息!\n";
bool first = true;
ArcNode *p, *temp;
for (int j = 0; (j != anum) && (tempanum != vnum); ++j) {
int pointto;
cout << "输入弧" << tempanum << "所指向的顶点位置:";
cin >> pointto;
if (pointto == -1) break;
else {
++tempanum;
if (first == true) {
first = false;
G.vertices[i].firstarc = new ArcNode;
G.vertices[i].firstarc->adjvex = pointto;
p = G.vertices[i].firstarc;
}
else {
temp = new ArcNode;
temp->adjvex = pointto;
p->nextarc = temp;
p = temp;
}
}
}
cout << endl;
}
for (int i = 0; i != anum; ++i) {
cout << "顶点" << i << ": |" << G.vertices[i].data << "|";
if (G.vertices[i].firstarc) {
cout << " -> " << G.vertices[i].firstarc->adjvex;
auto pt = G.vertices[i].firstarc->nextarc;
while (pt) {
cout << " -> " << pt->adjvex;
pt = pt->nextarc;
}
cout << "-> ^";
}
else
cout << " -> ^";
cout << endl;
}
return 0;
}
由于只是单纯构建基本的无权值有向图邻接表,里面的弧结构中弧信息未利用到。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
以上是 C++实现有向图邻接表的构建 的全部内容, 来源链接: utcz.com/p/245136.html