设计一个旅游景点导游模拟程序,为来访的客人提供景点最短路径的信息查询服务,任意选取n城市,构成一个有向带权图,图中顶点表示城市,边上的权值表示两点间的距离,根据用户指定的始点和终点输出相应的最短路径。咨询以用户和计算机的对话方式进行,由用户输入起始点和终点,输出信息:最短路径、并指出所经过的城市。存储结构选用邻接矩阵。使用c语言,并添加菜单选项
时间: 2024-04-21 15:25:45 浏览: 9
以下是使用 C 语言编写的旅游景点导游模拟程序,包含菜单选项和注释说明:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAX_CITY 20 // 最大城市数量
#define INF INT_MAX // 无穷大
// 邻接矩阵图的结构体
typedef struct {
int matrix[MAX_CITY][MAX_CITY]; // 邻接矩阵
char city_names[MAX_CITY][20]; // 城市名称
int num_city; // 城市数量
} Graph;
// 初始化图的邻接矩阵
void init_graph(Graph* graph) {
int i, j;
for (i = 0; i < MAX_CITY; i++) {
for (j = 0; j < MAX_CITY; j++) {
graph->matrix[i][j] = INF;
}
strcpy(graph->city_names[i], "");
}
graph->num_city = 0;
}
// 添加城市到图中
void add_city(Graph* graph, char* city_name) {
strcpy(graph->city_names[graph->num_city], city_name);
graph->num_city++;
}
// 添加有向边到图中
void add_edge(Graph* graph, int src, int dest, int weight) {
graph->matrix[src][dest] = weight;
}
// 打印图的邻接矩阵
void print_graph(Graph* graph) {
int i, j;
printf(" ");
for (i = 0; i < graph->num_city; i++) {
printf("%-10s", graph->city_names[i]);
}
printf("\n");
for (i = 0; i < graph->num_city; i++) {
printf("%-10s", graph->city_names[i]);
for (j = 0; j < graph->num_city; j++) {
if (graph->matrix[i][j] == INF) {
printf("%-10s", "INF");
} else {
printf("%-10d", graph->matrix[i][j]);
}
}
printf("\n");
}
}
// 计算最短路径
void shortest_path(Graph* graph, int start, int end) {
int i, j, k;
int dist[MAX_CITY][MAX_CITY]; // 存储每个节点到其他节点的最短距离
int pred[MAX_CITY][MAX_CITY]; // 存储每个节点到其他节点的最短路径的前驱节点
int path[MAX_CITY]; // 存储最短路径
int path_length = 0; // 最短路径的长度
int curr = end; // 当前节点
int pred_node; // 前驱节点
// 初始化距离和前驱节点
for (i = 0; i < graph->num_city; i++) {
for (j = 0; j < graph->num_city; j++) {
if (graph->matrix[i][j] == INF) {
dist[i][j] = INF;
pred[i][j] = -1;
} else {
dist[i][j] = graph->matrix[i][j];
pred[i][j] = i;
}
}
}
// Floyd 算法计算最短路径
for (k = 0; k < graph->num_city; k++) {
for (i = 0; i < graph->num_city; i++) {
for (j = 0; j < graph->num_city; j++) {
if (dist[i][k] == INF || dist[k][j] == INF) {
continue;
}
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
pred[i][j] = pred[k][j];
}
}
}
}
// 输出最短路径
printf("\nShortest path from %s to %s:\n", graph->city_names[start], graph->city_names[end]);
printf("%s", graph->city_names[curr]);
while (curr != start) {
pred_node = pred[start][curr];
path[path_length] = curr;
path_length++;
curr = pred_node;
}
printf(" -> ");
for (i = path_length - 1; i >= 0; i--) {
printf("%s", graph->city_names[path[i]]);
if (i > 0) {
printf(" -> ");
}
}
printf("\n");
printf("Total distance: %d km\n", dist[start][end]);
}
int main() {
Graph graph;
int choice;
char city_name[20];
int start, end;
init_graph(&graph);
// 添加城市
add_city(&graph, "Beijing");
add_city(&graph, "Shanghai");
add_city(&graph, "Guangzhou");
add_city(&graph, "Chengdu");
add_city(&graph, "Xi'an");
// 添加有向边
add_edge(&graph, 0, 1, 1064);
add_edge(&graph, 0, 2, 1888);
add_edge(&graph, 0, 3, 1443);
add_edge(&graph, 0, 4, 1216);
add_edge(&graph, 1, 2, 1210);
add_edge(&graph, 1, 3, 1610);
add_edge(&graph, 1, 4, 1936);
add_edge(&graph, 2, 3, 1430);
add_edge(&graph, 2, 4, 1236);
add_edge(&graph, 3, 4, 579);
while (1) {
printf("\n1. Display graph\n");
printf("2. Find shortest path\n");
printf("3. Quit\n");
printf("Enter your choice (1-3): ");
scanf("%d", &choice);
switch (choice) {
case 1:
print_graph(&graph);
break;
case 2:
printf("\nEnter start city (0-%d): ", graph.num_city - 1);
scanf("%d", &start);
printf("Enter end city (0-%d): ", graph.num_city - 1);
scanf("%d", &end);
shortest_path(&graph, start, end);
break;
case 3:
exit(0);
default:
printf("\nInvalid choice!\n");
}
}
return 0;
}
```
该程序使用菜单选项,用户可以选择显示图的邻接矩阵、查找最短路径或退出程序。用户可以输入起始城市和终点城市,程序会计算出它们之间的最短路径和所经过的城市,并输出到屏幕上。