用C语言编写以下程序:从文件 graph.txt 中读取相应数据, 创建一个带权的无向图,使用邻接矩阵表示图。以图中顶点表示学校内8个景点,存放景点的名称、景点介绍信息等;以边表示路径,存放路径长度信息。景点信息查询:为来访客人提供校园任意景点相关信息的介绍;问路查询:为来访客人提供校园任意两个景点之间的一条最短路径
时间: 2024-03-14 07:47:47 浏览: 128
邻接矩阵表示的带权有向图网演示程序.doc
很高兴为您解答!以下是使用C语言实现读取文件中的数据,创建带权无向图并进行景点信息查询和问路查询的程序:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 999999 // 定义正无穷
// 定义景点结构体
typedef struct {
char name[20]; // 景点名称
char intro[100]; // 景点介绍
} Spot;
// 定义图结构体
typedef struct {
Spot spots[8]; // 存放景点信息
int edges[8][8]; // 存放边的长度
} Graph;
// 读取文件中的数据,创建带权无向图
void createGraph(Graph* g) {
FILE* fp = fopen("graph.txt", "r"); // 打开文件
if (fp == NULL) { // 文件打开失败
printf("文件打开失败!\n");
exit(1); // 终止程序
}
// 读取景点信息
for (int i = 0; i < 8; i++) {
fscanf(fp, "%s%s", g->spots[i].name, g->spots[i].intro);
}
// 初始化边的长度
memset(g->edges, INF, sizeof(g->edges));
// 读取边的信息并存储在邻接矩阵中
int u, v, w;
while (fscanf(fp, "%d%d%d", &u, &v, &w) != EOF) {
g->edges[u][v] = g->edges[v][u] = w;
}
fclose(fp); // 关闭文件
}
// 景点信息查询
void spotInfoQuery(Graph* g) {
int n;
printf("请输入要查询的景点编号(0-7):");
scanf("%d", &n);
printf("%s:%s\n", g->spots[n].name, g->spots[n].intro);
}
// 问路查询(使用Dijkstra算法)
void shortestPathQuery(Graph* g) {
int start, end, dist[8], prev[8], visited[8] = { 0 };
printf("请输入起点和终点编号(0-7):");
scanf("%d%d", &start, &end);
// 初始化
for (int i = 0; i < 8; i++) {
dist[i] = g->edges[start][i];
prev[i] = start;
}
visited[start] = 1;
// Dijkstra算法
for (int i = 1; i < 8; i++) {
int minDist = INF, u = start;
for (int j = 0; j < 8; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}
visited[u] = 1;
for (int v = 0; v < 8; v++) {
if (!visited[v] && g->edges[u][v] < INF && dist[u] + g->edges[u][v] < dist[v]) {
dist[v] = dist[u] + g->edges[u][v];
prev[v] = u;
}
}
}
// 输出最短路径及其长度
printf("从 %s 到 %s 的最短路径为:", g->spots[start].name, g->spots[end].name);
int path[8], cnt = 0, p = end;
while (p != start) {
path[cnt++] = p;
p = prev[p];
}
path[cnt++] = start;
for (int i = cnt - 1; i >= 0; i--) {
printf("%s", g->spots[path[i]].name);
if (i > 0) {
printf(" -> ");
}
}
printf("\n最短路径长度为:%d\n", dist[end]);
}
int main() {
Graph g;
createGraph(&g); // 创建带权无向图
int choice;
do {
printf("\n====== 校园导游系统 ======\n");
printf("1. 景点信息查询\n");
printf("2. 问路查询\n");
printf("0. 退出\n");
printf("==========================\n");
printf("请选择操作:");
scanf("%d", &choice);
switch (choice) {
case 1:
spotInfoQuery(&g); // 景点信息查询
break;
case 2:
shortestPathQuery(&g); // 问路查询
break;
case 0:
printf("谢谢使用!\n");
break;
default:
printf("输入有误,请重新选择!\n");
break;
}
} while (choice != 0);
return 0;
}
```
在以上程序中,我们使用了邻接矩阵来表示带权无向图,并使用了Dijkstra算法来进行最短路径查询。同时,我们还提供了景点信息查询和问路查询两种功能。
阅读全文