C++采用尾插法建立邻接表 |21xrx.com

C++采用尾插法建立邻接表

2023-07-01 11:31:56 深夜i 28 0

C++ 尾插法邻接表建立

C++是一种强大的编程语言，被广泛应用于计算机科学和工程领域。在C++中，邻接表是一种常用的数据结构，用于表示图形。建立邻接表可以帮助程序员更好地理解和处理图形数据。

在C++中，采用尾插法建立邻接表是一种常见的方法。该方法使用链表来表示图形中每个节点的所有相邻节点。具体过程如下：

1. 定义一个结构体，表示图形中的每个节点，包括该节点的值和相邻节点的链表。

struct Node {
  int val; //该节点的值
  Node* next; //相邻节点的链表
};

2. 定义一个动态数组，用于存储图形中的所有节点。

vector<Node*> graph; //图形中的所有节点

3. 对于图形中的每个节点，创建一个新的节点对象，并将其添加到动态数组中。

for (int i = 0; i < n; i++) { //n为节点总数
  Node* node = new Node(i); //创建一个新的节点对象
  graph.push_back(node); //将新节点添加到动态数组中
}

4. 对于每个节点，遍历其所有相邻节点，并将这些节点添加到相邻节点的链表中。

for (int i = 0; i < n; i++) { //遍历所有节点
  int m; //m为相邻节点总数
  cin >> m;
  Node* node = graph[i]; //当前节点
  for (int j = 0; j < m; j++) { //遍历所有相邻节点
    int neighbor;
    cin >> neighbor;
    Node* neighbor_node = graph[neighbor]; //相邻节点
    //将相邻节点添加到当前节点的相邻节点链表中
    if (node->next == nullptr)
      node->next = neighbor_node;
     else {
      Node* p = node->next;
      while (p->next != nullptr)
        p = p->next;
      
      p->next = neighbor_node;
    }
  }
}

5. 此时，所有节点的邻接表已经建立完成。可以通过遍历动态数组来访问每个节点的邻接表，并对其进行操作。

for (int i = 0; i < n; i++) { //遍历所有节点
  Node* node = graph[i];
  cout << node->val << ": ";
  if (node->next != nullptr) { //访问相邻节点链表
    Node* p = node->next;
    while (p != nullptr)
      cout << p->val << " ";
      p = p->next;
    
  }
  cout << endl;
}

采用尾插法建立邻接表是一种简单有效的方法，它能够使程序员更好地理解和处理图形数据。在实际应用中，可以根据具体的需求选择合适的方法来建立邻接表，以提高程序的效率和可维护性。

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

下一篇: 如何在C++中表示次方运算

评论区

相似文章