用c++编写程序,已知有向图有n个顶点,请写算法,根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的<vi,vj>(以其中之一为0标志结束),对于每条这样的边,申请一个结点,并插入到的单链表中,如此反复,直到将图中所有边处理完毕。提示:先产生邻接表的n个头结点(其结点数值域从1到n)
时间: 2024-04-15 19:30:32 浏览: 91
编写算法,由依次输入的顶点数目、弧的数目、各顶点信息和各条弧信息建立有向图的邻接表。
4星 · 用户满意度95%
下面是用C++编写的算法,根据用户输入的偶对建立有向图的邻接表:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 邻接表的结点定义
struct Node {
int vertex; // 目标顶点
Node* next; // 下一个邻接结点
Node(int v) : vertex(v), next(nullptr) {}
};
// 建立有向图的邻接表
vector<Node*> buildAdjacencyList(int n) {
vector<Node*> adjacencyList(n + 1, nullptr); // 邻接表的头结点数组
int vi, vj;
cout << "请输入边的顶点对(以0标志结束):" << endl;
while (true) {
cin >> vi >> vj;
if (vi == 0 || vj == 0)
break;
// 创建新的邻接结点
Node* newNode = new Node(vj);
// 将新结点插入到对应的单链表中
if (adjacencyList[vi] == nullptr) {
adjacencyList[vi] = newNode;
} else {
Node* cur = adjacencyList[vi];
while (cur->next != nullptr) {
cur = cur->next;
}
cur->next = newNode;
}
}
return adjacencyList;
}
// 打印有向图的邻接表
void printAdjacencyList(const vector<Node*>& adjacencyList) {
cout << "有向图的邻接表:" << endl;
for (int i = 1; i < adjacencyList.size(); i++) {
cout << "顶点 " << i << ":";
Node* cur = adjacencyList[i];
while (cur != nullptr) {
cout << cur->vertex << " ";
cur = cur->next;
}
cout << endl;
}
}
int main() {
int n;
cout << "请输入顶点个数n:";
cin >> n;
vector<Node*> adjacencyList = buildAdjacencyList(n);
printAdjacencyList(adjacencyList);
// 释放申请的内存
for (int i = 1; i < adjacencyList.size(); i++) {
Node* cur = adjacencyList[i];
while (cur != nullptr) {
Node* temp = cur;
cur = cur->next;
delete temp;
}
}
return 0;
}
```
上述代码首先定义了邻接表的结点结构体 `Node`,包含了目标顶点和下一个邻接结点的指针。然后,根据用户输入的偶对,依次建立有向图的邻接表。最后,打印出建立的邻接表,并释放申请的内存。
注意:为了简化代码,这里假设用户输入的边的顶点对都是合法的,即不会超出顶点个数的范围。实际应用中,可能需要添加一些错误处理的代码来保证输入的合法性。
阅读全文