这个程序是一个图的实现,使用邻接表来表示图的结构:
1. 结构定义部分:
- `AdjListNode` 结构定义了邻接表中的节点,每个节点包含一个名称和一个指向下一个邻接节点的指针。
- `Node` 结构定义了图中的节点,每个节点包含一个名称和一个指向邻接表头部的指针。
邻接表通常是用链表来实现的。在这个程序中,每个节点(Node
)都有一个指向邻接表头部的指针(AdjListNode* head
),而邻接表中的每个节点(AdjListNode
)也是链表中的一个节点,通过指针连接起来。
2. 图类的方法:
- `addNode` 方法用于向图中添加新的节点。它创建一个新的 `Node` 对象并将其添加到节点数组中。vector<Node> nodes; // 存储图中所有节点的数组
- `addEdge` 方法用于向图中添加边。它首先查找源节点和目标节点在数组中的索引,然后创建一个新的邻接表节点表示目标节点,并将其插入到源节点的邻接表头部。
- `printGraph` 方法用于打印图的邻接表。它遍历节点数组,对于每个节点,遍历其邻接表并打印节点名称。
3. main函数:
- 在 `main` 函数中,首先创建了一个 `Graph` 对象。
- 然后通过调用 `addNode` 方法向图中添加了几个节点。
- 接着通过调用 `addEdge` 方法向图中添加了几条边。
- 最后调用 `printGraph` 方法打印了图的邻接表。
总体来说,这个程序展示了如何使用 C++ 实现图的基本操作,包括添加节点、添加边和打印邻接表。
vector<Node> nodes; // 存储图中所有节点的数组
这行代码声明了一个名为 nodes 的 vector,用于存储图中所有节点的数组。
在 C++ 中,vector 是一种动态数组,可以自动调整大小以容纳更多的元素。
在这个程序中,nodes 向量存储的是 Node 结构的对象,即图中的节点。
通过 vector 的特性,我们可以方便地添加、删除和访问图中的节点,而不需要手动管理数组的大小和内存。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 邻接表节点结构
struct AdjListNode {
string name; // 节点名称
AdjListNode* next; // 指向下一个邻接节点的指针
// 构造函数
AdjListNode(string name) {
this->name = name; // 初始化节点名称
this->next = nullptr; // 初始化指针为空
}
};
// 图的节点结构
struct Node {
string name; // 节点名称
AdjListNode* head; // 指向邻接表头部的指针
// 构造函数
Node(string name) {
this->name = name; // 初始化节点名称
this->head = nullptr; // 初始化指针为空
}
};
// 图类
class Graph {
private:
vector<Node> nodes; // 存储图中所有节点的数组
public:
// 添加节点到图中
void addNode(string nodeName) {
nodes.push_back(Node(nodeName)); // 将新节点添加到节点数组中
}
// 添加边到图中
void addEdge(string source, string dest) {
int sourceIndex = findNodeIndex(source); // 查找源节点在数组中的索引
int destIndex = findNodeIndex(dest); // 查找目标节点在数组中的索引
if (sourceIndex != -1 && destIndex != -1) { // 如果找到了源节点和目标节点
AdjListNode* newNode = new AdjListNode(dest); // 创建一个新的邻接表节点,表示目标节点
newNode->next = nodes[sourceIndex].head; // 将新节点插入到源节点的邻接表头部
nodes[sourceIndex].head = newNode;
// 这段代码并没有处理无向图的情况,所以会有缺陷
// 如果需要处理无向图,需要额外添加一条边,指向源节点
}
}
// 打印图的邻接表
void printGraph() {
for (const auto& node : nodes) { // 遍历每个节点
cout << node.name << " -> "; // 打印节点名称
AdjListNode* current = node.head; // 获取当前节点的邻接表头部
while (current) { // 遍历邻接表
cout << current->name; // 打印邻接节点的名称
if (current->next) cout << " -> "; // 如果存在下一个节点,打印箭头
else cout << " -> nullptr"; // 否则打印链表末尾
current = current->next; // 移动到下一个邻接节点
}
if (node.head == nullptr) cout << "nullptr"; // 如果当前节点没有邻接节点,则输出 nullptr
cout << endl; // 换行
}
}
private:
// 查找节点在数组中的索引
int findNodeIndex(string nodeName) {
for (size_t i = 0; i < nodes.size(); ++i) { // 遍历节点数组
if (nodes[i].name == nodeName) { // 如果找到节点名称匹配的节点
return i; // 返回节点在数组中的索引
}
}
return -1; // 如果没找到,返回-1
}
};
int main() {
Graph graph; // 创建图对象
graph.addNode("A"); // 添加节点
graph.addNode("B");
graph.addNode("C");
graph.addNode("D");
graph.addNode("E");
graph.addEdge("A", "B"); // 添加边
graph.addEdge("B", "C");
graph.addEdge("C", "A");
graph.addEdge("C", "D");
graph.addEdge("D", "A");
graph.printGraph(); // 打印图的邻接表
return 0;
}
// 该程序用于实现一个简单的图(Graph)的数据结构,图中包含多个节点,每个节点具有一个名称,并且每个节点可以与其他节点相连,以表示图中边的关系。
// 节点(Node)和邻接表(AdjListNode)
// Node:每个 Node 对象具有两个成员变量:一个字符串变量 name,用于保存节点的名称,以及一个指针变量 head,用于指向该节点的邻接表。
// AdjListNode:每个 AdjListNode 对象具有两个成员变量:一个字符串变量 name,用于保存邻接节点的名称,以及一个指针变量 next,用于指向下一个邻接节点。
// 这两行代码一起完成了将新创建的邻接表节点插入到源节点的邻接表的头部的操作。让我解释一下:
// newNode->next = nodes[sourceIndex].head;:
// 这行代码将新节点 newNode 的 next 指针指向了源节点的邻接表的头部。这样,新节点就被插入到了邻接表的头部位置。
// nodes[sourceIndex].head = newNode;:
// 接着,这行代码将源节点的邻接表的头指针指向了新节点 newNode。这样,新节点就成为了邻接表的新的头部,而原来的邻接表头部节点成为了新节点的下一个节点,从而完成了插入操作。
// 当你有一个指向对象的指针时,你可以使用 -> 运算符来访问该对象的成员,
// 而不必先解引用指针再使用 . 运算符。这在处理动态分配的对象时特别有用,因为你通常会使用指针来引用它们。
// -> 是 C++ 中用于访问对象成员的运算符,通常用于访问类的成员或者指向对象的指针的成员。
// 在这个语境中,newNode->next 是指针 newNode 所指向的对象的成员 next。
// 也就是说,newNode->next 表示访问 newNode 指向的邻接表节点的下一个节点的指针。
// -> 符号用于访问指针的成员。在这里,newNode 是指向 AdjListNode 对象的指针,我们想访问它的 next 成员。
// -> 符号与 .(->) 等价,但它是一种简写方式来访问指针的成员。
// 因此,newNode->next 等价于 (newNode)->next。它说的是“从 newNode 指向的对象中找出 next 成员”
A -> B -> nullptr
B -> C -> nullptr
C -> D -> A -> nullptr
D -> A -> nullptr
E -> nullptr
请按任意键继续. . .
// 该程序用于实现一个简单的图(Graph)的数据结构,图中包含多个节点,每个节点具有一个名称,并且每个节点可以与其他节点相连,以表示图中边的关系。
// 节点(Node)和邻接表(AdjListNode)
// Node:每个 Node 对象具有两个成员变量:一个字符串变量 name,用于保存节点的名称,以及一个指针变量 head,用于指向该节点的邻接表。
// AdjListNode:每个 AdjListNode 对象具有两个成员变量:一个字符串变量 name,用于保存邻接节点的名称,以及一个指针变量 next,用于指向下一个邻接节点。
// 这两行代码一起完成了将新创建的邻接表节点插入到源节点的邻接表的头部的操作:
// newNode->next = nodes[sourceIndex].head;:
// 这行代码将新节点 newNode 的 next 指针指向了源节点的邻接表的头部。这样,新节点就被插入到了邻接表的头部位置。
// nodes[sourceIndex].head = newNode;:
// 接着,这行代码将源节点的邻接表的头指针指向了新节点 newNode。这样,新节点就成为了邻接表的新的头部,而原来的邻接表头部节点成为了新节点的下一个节点,从而完成了插入操作。