以下是使用C++编写的不使用STL库的带权无向图类的示例代码:
#include <iostream>
#include <fstream>
class ALDirNetwork {
private:
struct Node {
char vertex;
int weight;
Node* next;
Node(char v, int w) : vertex(v), weight(w), next(nullptr) {}
};
struct Vertex {
char label;
int weight;
Node* head;
Vertex(char l, int w) : label(l), weight(w), head(nullptr) {}
};
Vertex* vertices; // 存储顶点数组
int numVertices; // 顶点数量
public:
ALDirNetwork() : vertices(nullptr), numVertices(0) {}
~ALDirNetwork() {
if (vertices != nullptr) {
for (int i = 0; i < numVertices; ++i) {
Node* current = vertices[i].head;
while (current != nullptr) {
Node* temp = current->next;
delete current;
current = temp;
}
}
delete[] vertices;
}
}
void InsertVex(char v, int w) {
if (FindVertexIndex(v) == -1) { // 确保顶点不存在时才插入
Vertex* newVertices = new Vertex[numVertices + 1];
for (int i = 0; i < numVertices; ++i)
newVertices[i] = vertices[i];
newVertices[numVertices] = { v, w, nullptr };
++numVertices;
delete[] vertices;
vertices = newVertices;
}
}
void InsertArc(char v1, char v2, int w) {
int index1 = FindVertexIndex(v1);
int index2 = FindVertexIndex(v2);
if (index1 != -1 && index2 != -1) { // 确保顶点存在才插入边
Node* newNode = new Node(v2, w);
newNode->next = vertices[index1].head;
vertices[index1].head = newNode;
newNode = new Node(v1, w);
newNode->next = vertices[index2].head;
vertices[index2].head = newNode;
}
}
bool LoadData(const char* filename) {
std::ifstream file(filename);
if (!file.is_open()) {
return false;
}
int Vexnum, Arcnum;
file >> Vexnum >> Arcnum; //读入顶点数,弧数目;
for (int i = 0; i < Vexnum; ++i) {
char ch;
int w;
file >> ch >> w;
InsertVex(ch, w); //插入顶点
}
for (int i = 0; i < Arcnum; ++i) {
char v1, v2;
int w;
file >> v1 >> v2 >> w;
InsertArc(v1, v2, w);
}
file.close();
return true;
}
private:
int FindVertexIndex(char label) const {
for (int i = 0; i < numVertices; ++i)
if (vertices[i].label == label)
return i;
return -1; // 找不到返回-1
}
};
int main() {
ALDirNetwork graph;
if (graph.LoadData("map.txt")) {
// 数据加载成功,可以进行后续操作
} else {
// 数据加载失败,处理错误情况
}
return 0;
}
以上代码实现了一个基于邻接链表的带权无向图类ALDirNetwork
。该类包含私有成员变量vertices
(顶点数组)和numVertices
(顶点数量),以及私有嵌套结构体Node
(表示边的节点)和Vertex
(表示顶点)。通过插入顶点和边的操作,可以构建带权无向图。
在示例代码中,我们使用文件名为”map.txt”来加载数据,并根据需要实现其他功能。请确保文件存在并按正确格式存储数据。
内容由零声教学AI助手提供,问题来源于学员提问