[已解决]从输入文件读取信息，构建无向图的邻接矩阵表示

sususususu · 发表于 2023-12-11 20:38:24

输入文件形如：
38,69//城市数,边数
哈尔滨
长春
沈阳
大连
呼和浩特
北京
天津
乌鲁木齐
银川
太原
石家庄
济南
青岛
西宁
兰州
西安
郑州
南京
上海
拉萨
成都
重庆
武汉
合肥
杭州
昆明
贵阳
长沙
南昌
宁波
南宁
广州
厦门
福州
海口
澳门
深圳
香港
//38个城市名称
哈尔滨,长春,1.0
长春,沈阳,1.0
沈阳,大连,1.5
沈阳,天津,3.5
沈阳,北京,3.0
大连,天津,4.0
天津,北京,0.5
天津,济南,1.0
北京,呼和浩特,2
北京,石家庄,1.0
呼和浩特,太原,4.5
呼和浩特,银川,7.5
银川,太原,6.0
银川,西安,3.0
银川,兰州,7.5
太原,石家庄,1.5
太原,郑州,2.5
太原,西安,3.0
石家庄,郑州,1.5
石家庄,济南,2.0
济南,青岛,1.5
济南,南京,2.0
青岛,上海,5.0
上海,南京,1.0
上海,杭州,1.0
南京,合肥,1.0
南京,郑州,3.0
郑州,武汉,2.0
郑州,西安,2.0
西安,重庆,4.5
西安,兰州,2.5
兰州,成都,7.0
兰州,西宁,1.0
西宁,拉萨,20
成都,重庆,1.0
成都,贵阳,3.0
重庆,武汉,6.0
重庆,贵阳,2.0
武汉,长沙,1.0
武汉,合肥,1.5
合肥,南昌,4.0
合肥,杭州,2.0
杭州,宁波,1.0
宁波,福州,1.0
南昌,福州,3.0
南昌,厦门,4.5
南昌,长沙,1.5
长沙,广州,2.5
长沙,贵阳,3.0
贵阳,南宁,5.0
贵阳,昆明,2.0
昆明,南宁,4.0
南宁,广州,3.0
广州,海口,10.0
广州,澳门,1.0
广州,深圳,0.5
厦门,深圳,2.5
厦门,福州,1.5
深圳,香港,0.5
//69条无向边的两个顶点及权值（权值表示所需时间）

从输入文件读取信息，构建无向图的邻接矩阵表示，并将邻接矩阵打印出来

最佳答案

月排行榜 / 总排行榜

人造人

2023-12-11 20:38:25

sh-5.2$ cat main.cpp
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
using std::string, std::vector;
using std::ostream;
using std::cout, std::endl;
using std::map;
class node_t;
class line_t {
public:
line_t(const node_t *first, const node_t *second, double size): first(first), second(second), size(size) {}
const node_t *first, *second;
double size;
};
class node_t {
public:
node_t(const string &name = ""): name(name) {}
void add_line(const line_t line) {
this->line.push_back(line);
}
friend ostream &operator<<(ostream &os, const node_t &node);
string name;
vector<line_t> line;
};
ostream &operator<<(ostream &os, const node_t &node) {
for(const auto &i: node.line) {
const string &first = i.first->name;
const string &second = i.second->name;
cout << node.name << " -> " << (node.name != first ? first : second) << ": " << i.size << endl;
}
return os;
}
const map<string, node_t> create_graph() {
map<string, node_t> result;
char buff[2][1024];
double size;
while(scanf("%1023[^,],%1023[^,],%lf\n", buff[0], buff[1], &size) == 3) {
string name[2] = {buff[0], buff[1]};
node_t &first = result[name[0]];
node_t &second = result[name[1]];
first.name = name[0];
second.name = name[1];
line_t line(&first, &second, size);
first.add_line(line);
second.add_line(line);
}
return result;
}
ostream &operator<<(ostream &os, const map<string, node_t> &m) {
for(const auto &i: m) os << i.second;
return os;
}
int main() {
cout << create_graph() << endl;
return 0;
}
sh-5.2$ ./main <data.txt
上海 -> 青岛: 5
上海 -> 南京: 1
上海 -> 杭州: 1
兰州 -> 银川: 7.5
兰州 -> 西安: 2.5
兰州 -> 成都: 7
兰州 -> 西宁: 1
北京 -> 沈阳: 3
北京 -> 天津: 0.5
北京 -> 呼和浩特: 2
北京 -> 石家庄: 1
南京 -> 济南: 2
南京 -> 上海: 1
南京 -> 合肥: 1
南京 -> 郑州: 3
南宁 -> 贵阳: 5
南宁 -> 昆明: 4
南宁 -> 广州: 3
南昌 -> 合肥: 4
南昌 -> 福州: 3
南昌 -> 厦门: 4.5
南昌 -> 长沙: 1.5
厦门 -> 南昌: 4.5
厦门 -> 深圳: 2.5
厦门 -> 福州: 1.5
合肥 -> 南京: 1
合肥 -> 武汉: 1.5
合肥 -> 南昌: 4
合肥 -> 杭州: 2
呼和浩特 -> 北京: 2
呼和浩特 -> 太原: 4.5
呼和浩特 -> 银川: 7.5
哈尔滨 -> 长春: 1
大连 -> 沈阳: 1.5
大连 -> 天津: 4
天津 -> 沈阳: 3.5
天津 -> 大连: 4
天津 -> 北京: 0.5
天津 -> 济南: 1
太原 -> 呼和浩特: 4.5
太原 -> 银川: 6
太原 -> 石家庄: 1.5
太原 -> 郑州: 2.5
太原 -> 西安: 3
宁波 -> 杭州: 1
宁波 -> 福州: 1
广州 -> 长沙: 2.5
广州 -> 南宁: 3
广州 -> 海口: 10
广州 -> 澳门: 1
广州 -> 深圳: 0.5
成都 -> 兰州: 7
成都 -> 重庆: 1
成都 -> 贵阳: 3
拉萨 -> 西宁: 20
昆明 -> 贵阳: 2
昆明 -> 南宁: 4
杭州 -> 上海: 1
杭州 -> 合肥: 2
杭州 -> 宁波: 1
武汉 -> 郑州: 2
武汉 -> 重庆: 6
武汉 -> 长沙: 1
武汉 -> 合肥: 1.5
沈阳 -> 长春: 1
沈阳 -> 大连: 1.5
沈阳 -> 天津: 3.5
沈阳 -> 北京: 3
济南 -> 天津: 1
济南 -> 石家庄: 2
济南 -> 青岛: 1.5
济南 -> 南京: 2
海口 -> 广州: 10
深圳 -> 广州: 0.5
深圳 -> 厦门: 2.5
深圳 -> 香港: 0.5
澳门 -> 广州: 1
石家庄 -> 北京: 1
石家庄 -> 太原: 1.5
石家庄 -> 郑州: 1.5
石家庄 -> 济南: 2
福州 -> 宁波: 1
福州 -> 南昌: 3
福州 -> 厦门: 1.5
西宁 -> 兰州: 1
西宁 -> 拉萨: 20
西安 -> 银川: 3
西安 -> 太原: 3
西安 -> 郑州: 2
西安 -> 重庆: 4.5
西安 -> 兰州: 2.5
贵阳 -> 成都: 3
贵阳 -> 重庆: 2
贵阳 -> 长沙: 3
贵阳 -> 南宁: 5
贵阳 -> 昆明: 2
郑州 -> 太原: 2.5
郑州 -> 石家庄: 1.5
郑州 -> 南京: 3
郑州 -> 武汉: 2
郑州 -> 西安: 2
重庆 -> 西安: 4.5
重庆 -> 成都: 1
重庆 -> 武汉: 6
重庆 -> 贵阳: 2
银川 -> 呼和浩特: 7.5
银川 -> 太原: 6
银川 -> 西安: 3
银川 -> 兰州: 7.5
长春 -> 哈尔滨: 1
长春 -> 沈阳: 1
长沙 -> 武汉: 1
长沙 -> 南昌: 1.5
长沙 -> 广州: 2.5
长沙 -> 贵阳: 3
青岛 -> 济南: 1.5
青岛 -> 上海: 5
香港 -> 深圳: 0.5
sh-5.2$

复制代码

跳转到最佳答案楼层

人造人 · 发表于 2023-12-11 20:38:25

sh-5.2$ cat main.cpp
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
using std::string, std::vector;
using std::ostream;
using std::cout, std::endl;
using std::map;
class node_t;
class line_t {
public:
line_t(const node_t *first, const node_t *second, double size): first(first), second(second), size(size) {}
const node_t *first, *second;
double size;
};
class node_t {
public:
node_t(const string &name = ""): name(name) {}
void add_line(const line_t line) {
this->line.push_back(line);
}
friend ostream &operator<<(ostream &os, const node_t &node);
string name;
vector<line_t> line;
};
ostream &operator<<(ostream &os, const node_t &node) {
for(const auto &i: node.line) {
const string &first = i.first->name;
const string &second = i.second->name;
cout << node.name << " -> " << (node.name != first ? first : second) << ": " << i.size << endl;
}
return os;
}
const map<string, node_t> create_graph() {
map<string, node_t> result;
char buff[2][1024];
double size;
while(scanf("%1023[^,],%1023[^,],%lf\n", buff[0], buff[1], &size) == 3) {
string name[2] = {buff[0], buff[1]};
node_t &first = result[name[0]];
node_t &second = result[name[1]];
first.name = name[0];
second.name = name[1];
line_t line(&first, &second, size);
first.add_line(line);
second.add_line(line);
}
return result;
}
ostream &operator<<(ostream &os, const map<string, node_t> &m) {
for(const auto &i: m) os << i.second;
return os;
}
int main() {
cout << create_graph() << endl;
return 0;
}
sh-5.2$ ./main <data.txt
上海 -> 青岛: 5
上海 -> 南京: 1
上海 -> 杭州: 1
兰州 -> 银川: 7.5
兰州 -> 西安: 2.5
兰州 -> 成都: 7
兰州 -> 西宁: 1
北京 -> 沈阳: 3
北京 -> 天津: 0.5
北京 -> 呼和浩特: 2
北京 -> 石家庄: 1
南京 -> 济南: 2
南京 -> 上海: 1
南京 -> 合肥: 1
南京 -> 郑州: 3
南宁 -> 贵阳: 5
南宁 -> 昆明: 4
南宁 -> 广州: 3
南昌 -> 合肥: 4
南昌 -> 福州: 3
南昌 -> 厦门: 4.5
南昌 -> 长沙: 1.5
厦门 -> 南昌: 4.5
厦门 -> 深圳: 2.5
厦门 -> 福州: 1.5
合肥 -> 南京: 1
合肥 -> 武汉: 1.5
合肥 -> 南昌: 4
合肥 -> 杭州: 2
呼和浩特 -> 北京: 2
呼和浩特 -> 太原: 4.5
呼和浩特 -> 银川: 7.5
哈尔滨 -> 长春: 1
大连 -> 沈阳: 1.5
大连 -> 天津: 4
天津 -> 沈阳: 3.5
天津 -> 大连: 4
天津 -> 北京: 0.5
天津 -> 济南: 1
太原 -> 呼和浩特: 4.5
太原 -> 银川: 6
太原 -> 石家庄: 1.5
太原 -> 郑州: 2.5
太原 -> 西安: 3
宁波 -> 杭州: 1
宁波 -> 福州: 1
广州 -> 长沙: 2.5
广州 -> 南宁: 3
广州 -> 海口: 10
广州 -> 澳门: 1
广州 -> 深圳: 0.5
成都 -> 兰州: 7
成都 -> 重庆: 1
成都 -> 贵阳: 3
拉萨 -> 西宁: 20
昆明 -> 贵阳: 2
昆明 -> 南宁: 4
杭州 -> 上海: 1
杭州 -> 合肥: 2
杭州 -> 宁波: 1
武汉 -> 郑州: 2
武汉 -> 重庆: 6
武汉 -> 长沙: 1
武汉 -> 合肥: 1.5
沈阳 -> 长春: 1
沈阳 -> 大连: 1.5
沈阳 -> 天津: 3.5
沈阳 -> 北京: 3
济南 -> 天津: 1
济南 -> 石家庄: 2
济南 -> 青岛: 1.5
济南 -> 南京: 2
海口 -> 广州: 10
深圳 -> 广州: 0.5
深圳 -> 厦门: 2.5
深圳 -> 香港: 0.5
澳门 -> 广州: 1
石家庄 -> 北京: 1
石家庄 -> 太原: 1.5
石家庄 -> 郑州: 1.5
石家庄 -> 济南: 2
福州 -> 宁波: 1
福州 -> 南昌: 3
福州 -> 厦门: 1.5
西宁 -> 兰州: 1
西宁 -> 拉萨: 20
西安 -> 银川: 3
西安 -> 太原: 3
西安 -> 郑州: 2
西安 -> 重庆: 4.5
西安 -> 兰州: 2.5
贵阳 -> 成都: 3
贵阳 -> 重庆: 2
贵阳 -> 长沙: 3
贵阳 -> 南宁: 5
贵阳 -> 昆明: 2
郑州 -> 太原: 2.5
郑州 -> 石家庄: 1.5
郑州 -> 南京: 3
郑州 -> 武汉: 2
郑州 -> 西安: 2
重庆 -> 西安: 4.5
重庆 -> 成都: 1
重庆 -> 武汉: 6
重庆 -> 贵阳: 2
银川 -> 呼和浩特: 7.5
银川 -> 太原: 6
银川 -> 西安: 3
银川 -> 兰州: 7.5
长春 -> 哈尔滨: 1
长春 -> 沈阳: 1
长沙 -> 武汉: 1
长沙 -> 南昌: 1.5
长沙 -> 广州: 2.5
长沙 -> 贵阳: 3
青岛 -> 济南: 1.5
青岛 -> 上海: 5
香港 -> 深圳: 0.5
sh-5.2$

复制代码

FishC · 发表于 2023-12-11 20:39:25

你可以通过以下步骤来实现：

1. 读取输入文件的第一行，获取城市数和边数。
2. 创建一个城市列表，读取输入文件的后续城市名称部分，并将其添加到列表中。
3. 创建一个城市数量的二维数组作为邻接矩阵，并将其初始化为0。
4. 读取输入文件的边信息部分，对于每一条边，更新邻接矩阵中对应位置的值为边的权值。
5. 打印邻接矩阵。

下面是完整的代码实现：

def build_adjacency_matrix(file_name):
with open(file_name, 'r') as file:
# 读取城市数和边数
city_num, edge_num = map(int, file.readline().strip().split(','))
# 读取城市名称列表
city_list = []
for _ in range(city_num):
city_name = file.readline().strip()
city_list.append(city_name)
# 创建邻接矩阵并初始化为0
adjacency_matrix = [[0] * city_num for _ in range(city_num)]
# 读取边信息并更新邻接矩阵
for _ in range(edge_num):
edge_info = file.readline().strip().split(',')
start_city = city_list.index(edge_info[0])
end_city = city_list.index(edge_info[1])
weight = float(edge_info[2])
adjacency_matrix[start_city][end_city] = weight
adjacency_matrix[end_city][start_city] = weight
# 打印邻接矩阵
for row in adjacency_matrix:
print(' '.join(map(str, row)))
build_adjacency_matrix('input.txt')

复制代码

希望这个能帮到你！如果还有其他问题，请随时问我。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

Exusiaii · 发表于 2023-12-15 10:55:53

FishC 发表于 2023-12-11 20:39
你可以通过以下步骤来实现：

1. 读取输入文件的第一行，获取城市数和边数。

#include<stdio.h>
#include<stdlib.h>
#define Maxvertex 100
typedef char DataType;
typedef int Infotype;//Ȩֵ
typedef struct EdgeNode{
int adjvex;
Infotype info;
EdgeNode* next;
}EdgeNode;
typedef struct {
DataType vertex;
EdgeNode* firstedge;
}VertexNode;
typedef struct ALGraph {
VertexNode adjlist[Maxvertex];
int vertexnum, edgenum;
}ALGraph;
ALGraph* Create() {
ALGraph* G;
G = (ALGraph*)malloc(sizeof(ALGraph));
printf("请输入顶点数和边数");
scanf_s("%d %d", &(G->vertexnum), &(G->edgenum));
printf("请输入顶点名称");
for (int i = 0; i < (G->vertexnum); i++) {
scanf_s("%c", &(G->adjlist[i].vertex));
G->adjlist[i].firstedge = NULL;
}
printf("请输入边的两个顶点<i,j>的对应序号及其权值q");
int i, j, q;
for (int k = 0; k < (G->vertexnum); k++) {
scanf_s("%d,%d %q", &i, &j,&q);
EdgeNode* p;
p = (EdgeNode*)malloc(sizeof(EdgeNode));
p->adjvex = j;
p->info = q;
p->next = G->adjlist[i].firstedge;
G->adjlist[i].firstedge = p;
}
}

复制代码

在用邻接表构建图的时候这段代码有什么问题

FishC · 发表于 2023-12-15 10:56:35

Exusiaii 发表于 2023-12-15 10:55
#include
#include
#define Maxvertex 100
typedef ...

在代码中存在以下问题：1. 邻接表的定义部分缺少头文件包含。你需要添加头文件 `#include <cstdlib>` 和 `#include <cstdio>` 以包含标准库函数。2. `ALGraph` 结构体中的 `adjlist` 只能表示一个顶点，而不是所有顶点的链表。你需要将其改为指向 `VertexNode` 数组的指针。3. 在创建邻接表时，你应该为每个顶点分配内存，并使用循环来初始化 `adjlist` 的每个元素。4. 在输入边信息时，你没有处理具有相同起始顶点的多条边的情况。你需要在创建新的 `EdgeNode` 时，将其连接到已有链表的末尾。5. 输入顶点名称时，可以使用 `getchar()` 来读取字符，以避免读取换行符的问题。6. 最后，你应该在函数结束前返回创建好的图 `G`。下面是修改后的代码：

#include <cstdlib>#include <cstdio>#define Maxvertex 100typedef char DataType;typedef int Infotype;typedef struct EdgeNode{ int adjvex; Infotype info; EdgeNode* next;}EdgeNode;typedef struct { DataType vertex; EdgeNode* firstedge;}VertexNode;typedef struct ALGraph { VertexNode* adjlist; int vertexnum, edgenum;}ALGraph;ALGraph* Create() { ALGraph* G; G = (ALGraph*)malloc(sizeof(ALGraph)); printf("请输入顶点数和边数: "); scanf_s("%d %d", &(G->vertexnum), &(G->edgenum)); G->adjlist = (VertexNode*)malloc(G->vertexnum * sizeof(VertexNode)); printf("请输入顶点名称: "); getchar(); // 读取换行符 for (int i = 0; i < G->vertexnum; i++) { G->adjlist[i].vertex = getchar(); G->adjlist[i].firstedge = NULL; getchar(); // 读取换行符 } printf("请输入边的两个顶点的对应序号及其权值: "); int i, j, q; for (int k = 0; k < G->edgenum; k++) { scanf_s("%d,%d %d", &i, &j, &q); EdgeNode* p; p = (EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex = j; p->info = q; p->next = G->adjlist[i].firstedge; G->adjlist[i].firstedge = p; } return G;}int main() { ALGraph* G = Create(); // 打印邻接表 for (int i = 0; i < G->vertexnum; i++) { printf("%c：", G->adjlist[i].vertex); EdgeNode* p = G->adjlist[i].firstedge; while (p != NULL) { printf(" -(%d)-> %c", p->info, G->adjlist[p->adjvex].vertex); p = p->next; } printf("\n"); } return 0;}

复制代码

希望这次能帮到你！如果还有其他问题，请随时问我。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

账号		自动登录	找回密码
密码			立即注册