21xrx.com
2024-11-10 00:54:36 Sunday
登录
文章检索 我的文章 写文章
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

3

0

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

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复