如何构建实现有向图的邻接表？

本文共计1003个文字，预计阅读时间需要5分钟。

本文分享了C++实现有向图邻接表结构的代码，供大家参考。主要内容包括数据结构中的一道基础题，以及作者的个人写作风格和验证过程。

数据结构中，有向图邻接表是一种常见的表示方式。以下是一个简单的C++实现：

cpp#include #include using namespace std;

// 定义有向图的邻接表节点struct Node { int vertex; // 邻接顶点 Node* next; // 指向下一个邻接点的指针};

// 定义有向图的邻接表class AdjacencyList {public: vector adjList; // 存储所有顶点的邻接表节点

// 构造函数 AdjacencyList(int v) { adjList.resize(v); for (int i=0; i

// 添加边 void addEdge(int src, int dest) { // 创建新的邻接表节点 Node* newNode=new Node; newNode->vertex=dest; newNode->next=adjList[src];

// 将新节点添加到邻接表的头部 adjList[src]=newNode; }

// 打印邻接表 void printGraph() { for (int i=0; i

// 析构函数 ~AdjacencyList() { for (Node* node : adjList) { Node* temp=node; while (temp) { Node* prev=temp; temp=temp->next; delete prev; } } }};

int main() { // 创建一个有向图，顶点数量为4 AdjacencyList g(4);

// 添加边 g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3);

// 打印邻接表 g.printGraph();

return 0;}

个人写作风格和验证过程：

1.遵循C++编程规范，代码清晰、易读。

2.使用结构体和类封装邻接表数据结构，提高代码复用性。

3.添加了注释，解释关键代码部分的功能。

4.编写测试用例，验证代码的正确性。

以上就是一个简单的有向图邻接表实现。希望对大家有所帮助！

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

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

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