请用c语言实现首先从文件 graph.txt 中读取相应数据, 创建一个图,使用邻接矩阵表示图 ; 然后利用景点信息查询:为来访客人提供校园任意景点相关信息的介绍; 最后问路查询:为来访客人提供校园任意两个景点之间的一条最短路径。请写出该代码并且运行输出
时间: 2024-02-03 14:13:47 浏览: 294
基于C语言实现校园导游咨询系统【100012887】
抱歉,作为一名AI语言模型,我无法在本地进行代码编译和运行。但是,我可以给您提供一个实现思路供参考。
1. 读取图数据
首先需要从文件 `graph.txt` 中读取相应的数据,然后创建一个图,使用邻接矩阵表示图。可以使用 `fopen` 和 `fscanf` 函数来实现文件读取,使用二维数组来表示邻接矩阵。
2. 景点信息查询
为了为来访客人提供校园任意景点相关信息的介绍,需要先实现一个景点信息查询函数。该函数可以接受一个景点名称,然后在邻接矩阵中查找该景点的相关信息,包括相邻景点、距离等等。
3. 问路查询
为了为来访客人提供校园任意两个景点之间的一条最短路径,需要先实现一个最短路径算法,例如 Dijkstra 算法或 Floyd 算法。然后再实现一个问路查询函数,该函数可以接受两个景点名称,然后使用最短路径算法计算出两个景点之间的最短路径,并返回路径信息。
最后,在主函数中可以分别调用景点信息查询函数和问路查询函数,根据用户输入的不同指令来执行相应的操作。
下面是一个伪代码实现供参考:
```c
#include <stdio.h>
#include <string.h>
#define MAX_VERTEX_NUM 100
#define INF 0x7FFFFFFF
int graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int dist[MAX_VERTEX_NUM];
int visited[MAX_VERTEX_NUM];
char name[MAX_VERTEX_NUM][20];
int vertex_num, edge_num;
void read_graph() {
FILE *fp = fopen("graph.txt", "r");
fscanf(fp, "%d %d", &vertex_num, &edge_num);
for (int i = 0; i < vertex_num; i++) {
fscanf(fp, "%s", name[i]);
}
memset(graph, 0x3f, sizeof(graph)); // 初始化邻接矩阵为INF
for (int i = 0; i < edge_num; i++) {
int u, v, w;
fscanf(fp, "%d %d %d", &u, &v, &w);
graph[u][v] = graph[v][u] = w; // 无向图,注意双向边
}
fclose(fp);
}
void print_vertex_info(int v) {
printf("%s: ", name[v]);
for (int i = 0; i < vertex_num; i++) {
if (graph[v][i] != INF) {
printf("%s(%d) ", name[i], graph[v][i]);
}
}
printf("\n");
}
void query_vertex_info() {
char vname[20];
printf("请输入要查询的景点名称:");
scanf("%s", vname);
for (int i = 0; i < vertex_num; i++) {
if (strcmp(name[i], vname) == 0) {
print_vertex_info(i);
return;
}
}
printf("没有找到该景点\n");
}
void dijkstra(int start) {
memset(dist, 0x3f, sizeof(dist)); // 初始化距离为INF
memset(visited, 0, sizeof(visited)); // 初始化visited为0
dist[start] = 0;
for (int i = 0; i < vertex_num; i++) {
int min_dist = INF, min_vertex = -1;
for (int j = 0; j < vertex_num; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
min_vertex = j;
}
}
if (min_vertex == -1) {
break; // 所有点都已经访问完毕,退出循环
}
visited[min_vertex] = 1;
for (int j = 0; j < vertex_num; j++) {
if (!visited[j] && graph[min_vertex][j] != INF) {
if (dist[min_vertex] + graph[min_vertex][j] < dist[j]) {
dist[j] = dist[min_vertex] + graph[min_vertex][j];
}
}
}
}
}
void print_path(int start, int end, int path[], int len) {
printf("%s->", name[start]);
for (int i = 0; i < len; i++) {
printf("%s(%d)->", name[path[i]], graph[start][path[i]]);
start = path[i];
}
printf("%s\n", name[end]);
}
void query_shortest_path() {
char vname1[20], vname2[20];
printf("请输入起点景点名称:");
scanf("%s", vname1);
printf("请输入终点景点名称:");
scanf("%s", vname2);
int start = -1, end = -1;
for (int i = 0; i < vertex_num; i++) {
if (strcmp(name[i], vname1) == 0) {
start = i;
}
if (strcmp(name[i], vname2) == 0) {
end = i;
}
}
if (start == -1 || end == -1) {
printf("没有找到起点或终点景点\n");
return;
}
dijkstra(start);
if (dist[end] == INF) {
printf("没有找到从%s到%s的路径\n", vname1, vname2);
return;
}
int path[MAX_VERTEX_NUM], len = 0;
int cur = end;
while (cur != start) {
for (int i = 0; i < vertex_num; i++) {
if (graph[i][cur] != INF && dist[i] + graph[i][cur] == dist[cur]) {
path[len++] = i;
cur = i;
break;
}
}
}
print_path(start, end, path, len);
}
int main() {
read_graph();
while (1) {
printf("请输入指令:\n");
printf("(1) 查询景点信息\n");
printf("(2) 查询最短路径\n");
printf("(3) 退出\n");
int cmd;
scanf("%d", &cmd);
if (cmd == 1) {
query_vertex_info();
} else if (cmd == 2) {
query_shortest_path();
} else if (cmd == 3) {
break;
} else {
printf("指令无效,请重新输入\n");
}
}
return 0;
}
```
阅读全文