C++实现有向图邻接表的构建

181 阅读 0 评论 120 点赞

我是靠谱客的博主平淡溪流，这篇文章主要介绍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 << "nn";
 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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 << "nn";
 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;
}