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

时间:2021-07-30 06:01:13

本文实例为大家分享了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. }

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

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

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

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