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

本文实例为大家分享了C++实现有向图邻接表的构建代码，供大家参考，具体内容如下

数据结构里面的一道基础题，分享下自己的写法，验证可跑。

1. #include<iostream>
2. #include<string>
3. const int MAX = 20;
4. using namespace std;
5.  
6. struct ArcNode { //弧结点
7. int adjvex = -1; //所指顶点位置
8. ArcNode *nextarc = nullptr; //下一条狐指针
9. size_t info = 0; //弧信息
10. };
11.  
12. struct VNode { //顶点
13. string data = "0";
14. ArcNode *firstarc = nullptr; //第一条依附该顶点的弧的指针
15. };
16.  
17. struct Graph { //图结构
18. VNode vertices[MAX]; //全部顶点
19. int vexnum, arcnum; //顶点数和弧数
20. Graph(int m, int n) :vexnum(m), arcnum(n) {};
21. Graph() :vexnum(0), arcnum(0) {};
22. };
23.  
24. int main()
25. {
26. int vnum, anum, tempanum = 0;
27. cout << "输入顶点数：";
28. cin >> vnum;
29. cout << "输入弧数：";
30. cin >> anum;
31. cout << "\n\n";
32. Graph G(vnum, anum);
33. for (int i = 0; i != vnum; ++i) {
34. cout << "输入结点" << i << "的信息：";
35. cin >> G.vertices[i].data;
36. if (tempanum != anum)
37. cout << "输入依靠此结点的弧的信息（输入-1以停止）：\n";
38. else
39. cout << "已输入所有弧的信息！\n";
40. bool first = true;
41. ArcNode *p, *temp;
42. for (int j = 0; (j != anum) && (tempanum != vnum); ++j) {
43. int pointto;
44. cout << "输入弧" << tempanum << "所指向的顶点位置：";
45. cin >> pointto;
46. if (pointto == -1) break;
47. else {
48. ++tempanum;
49. if (first == true) {
50. first = false;
51. G.vertices[i].firstarc = new ArcNode;
52. G.vertices[i].firstarc->adjvex = pointto;
53. p = G.vertices[i].firstarc;
54. }
55. else {
56. temp = new ArcNode;
57. temp->adjvex = pointto;
58. p->nextarc = temp;
59. p = temp;
60. }
61. }
62. }
63. cout << endl;
64. }
65.  
66. for (int i = 0; i != anum; ++i) {
67. cout << "顶点" << i << ": |" << G.vertices[i].data << "|";
68. if (G.vertices[i].firstarc) {
69. cout << " -> " << G.vertices[i].firstarc->adjvex;
70. auto pt = G.vertices[i].firstarc->nextarc;
71. while (pt) {
72. cout << " -> " << pt->adjvex;
73. pt = pt->nextarc;
74. }
75. cout << "-> ^";
76. }
77. else
78. cout << " -> ^";
79. cout << endl;
80. }
81. return 0;
82. }

由于只是单纯构建基本的无权值有向图邻接表，里面的弧结构中弧信息未利用到。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

原文链接：https://blog.csdn.net/qq_40033627/article/details/80825023