C++ 数组实现邻接链表 |21xrx.com

C++ 数组实现邻接链表

2023-07-11 04:19:09 深夜i -- --

C++ 数组邻接链表实现

在C++编程语言中，邻接链表是一种常用的数据结构，它用于表示图。邻接链表由若干个链式结点组成，每个结点包含一个指向相邻结点的指针和表示图边权的变量。使用邻接链表可以方便地实现图的各种操作，例如遍历、查找和修改。

在C++中实现邻接链表的方法之一是使用数组。数组是一种线性数据结构，在C++中应用广泛，它可以通过下标访问其中的元素。使用数组实现邻接链表的方法可以简化代码，提高效率。

实现邻接链表的步骤如下：

1.定义结构体

首先，需要为一个结点定义一个结构体。结构体包含两个变量：邻居结点的编号和边的权重。结构体的定义如下：

struct Node

int num;

int weight;

;

2.定义数组

接下来需要定义一个数组来存储所有的结点信息。数组的长度等于图中结点的数量。数组的每个元素是一个指向链表头的指针。如果结点之间存在边，则链表头指针指向一个链式结点，该结点包含指向邻居结点的指针和边权重。

Node* graph[N];

3.初始化数组

在程序开始执行之前，需要将数组中的所有指针初始化为NULL。这一步骤是为了避免程序出现未定义的行为。

for (int i = 0; i < N; i++) {

graph[i] = NULL;

}

4.添加边

在图中添加边是一个关键步骤。如果一条边从结点x指向y，则需要将y添加到结点x的邻居链表中。为此，需要创建一个新的链式结点，并将其插入到链表的头部。代码实现如下：

void addEdge(int x, int y, int weight) {

Node* newNode = new Node;

newNode->num = y;

newNode->weight = weight;

newNode->next = graph[x];

graph[x] = newNode;

}

5.访问邻居结点

使用邻接链表遍历图中的元素非常简单。要访问结点x的邻居结点，只需遍历指向链表头的指针，并依次访问链表中的元素。代码实现如下：

void traverse(int x) {

Node* curr = graph[x];

while (curr != NULL)

//访问 curr

curr = curr->next;

}

6.完整代码示例

下面是一个完整的使用数组实现邻接链表的示例代码：

#include

using namespace std;

const int N = 100;

struct Node {

int num;

int weight;

Node* next;

};

Node* graph[N];

void addEdge(int x, int y, int weight) {

Node* newNode = new Node;

newNode->num = y;

newNode->weight = weight;

newNode->next = graph[x];

graph[x] = newNode;

}

void traverse(int x) {

Node* curr = graph[x];

while (curr != NULL)

cout << curr->num << " ";

curr = curr->next;

cout << endl;

}

int main() {

addEdge(0, 1, 2);

addEdge(0, 2, 1);

addEdge(1, 2, 3);

addEdge(2, 3, 4);

addEdge(3, 0, 5);

traverse(0);

traverse(1);

traverse(2);

traverse(3);

return 0;

}

输出结果为：

2 1

2 3

使用数组实现邻接链表既简单又高效。这种方法可以方便地实现图的各种操作，并且可以扩展到更大的图。无论对于学习算法还是实际编程，掌握这种方法都是非常有益的。

上一篇: idea打包java可执行jar包

下一篇: Visual Studio 没有 C++，该怎么办？

评论区

()

相似文章