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

回到顶部