要求:输入城市及城市间路线的信息,建立城市交通网;输出该交通网的存储表示;指定某个出发城市,对交通网进行深度优先遍历并打印结果,输出该城市到网中其他城市花销最小的路径;指定某条路线,修改路线花销
时间: 2024-03-13 09:46:17 浏览: 30
好的,以下是符合您要求的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CITY 10
#define INF 10000
typedef struct {
char name[20]; // 城市名称
} City;
typedef struct {
int cost; // 路线花销
} Edge;
typedef struct {
City cities[MAX_CITY]; // 城市列表
Edge edges[MAX_CITY][MAX_CITY]; // 邻接矩阵
int city_num; // 城市数量
} Graph;
// 初始化图
void initGraph(Graph *g) {
int i, j;
g->city_num = 0;
for (i = 0; i < MAX_CITY; i++) {
for (j = 0; j < MAX_CITY; j++) {
g->edges[i][j].cost = INF;
}
}
}
// 添加城市
void addCity(Graph *g, char *name) {
City city;
strcpy(city.name, name);
g->cities[g->city_num++] = city;
}
// 添加路线
void addRoute(Graph *g, int src, int dest, int cost) {
g->edges[src][dest].cost = cost;
g->edges[dest][src].cost = cost;
}
// 查找城市编号
int findCity(Graph *g, char *name) {
int i;
for (i = 0; i < g->city_num; i++) {
if (strcmp(g->cities[i].name, name) == 0) {
return i;
}
}
return -1;
}
// 深度优先遍历
void dfs(Graph *g, int v, int *visited) {
int i;
visited[v] = 1;
printf("%s ", g->cities[v].name);
for (i = 0; i < g->city_num; i++) {
if (g->edges[v][i].cost != INF && !visited[i]) {
dfs(g, i, visited);
}
}
}
// Dijkstra算法求最短路程
void dijkstra(Graph *g, int src, int *dist) {
int i, j, k, min;
int visited[MAX_CITY] = {0};
for (i = 0; i < g->city_num; i++) {
dist[i] = g->edges[src][i].cost;
}
visited[src] = 1;
for (i = 0; i < g->city_num - 1; i++) {
min = INF;
k = src;
for (j = 0; j < g->city_num; j++) {
if (!visited[j] && dist[j] < min) {
min = dist[j];
k = j;
}
}
visited[k] = 1;
for (j = 0; j < g->city_num; j++) {
if (!visited[j] && g->edges[k][j].cost != INF && dist[k] + g->edges[k][j].cost < dist[j]) {
dist[j] = dist[k] + g->edges[k][j].cost;
}
}
}
}
int main() {
Graph g;
int src, dest, i, j, cost, choice;
char city_name[20], src_name[20], dest_name[20];
int visited[MAX_CITY] = {0};
int dist[MAX_CITY];
initGraph(&g);
printf("请输入城市数量:");
scanf("%d", &g.city_num);
printf("请输入城市名称:");
for (i = 0; i < g.city_num; i++) {
scanf("%s", city_name);
addCity(&g, city_name);
}
printf("请输入路线数量:");
scanf("%d", &j);
printf("请输入路线信息(起点 停靠点 路线花销):\n");
while (j--) {
scanf("%s%s%d", src_name, dest_name, &cost);
src = findCity(&g, src_name);
dest = findCity(&g, dest_name);
addRoute(&g, src, dest, cost);
}
printf("交通网存储表示:\n");
for (i = 0; i < g.city_num; i++) {
for (j = 0; j < g.city_num; j++) {
printf("%d ", g.edges[i][j].cost);
}
printf("\n");
}
while (1) {
printf("请输入出发城市名称(输入-1退出):");
scanf("%s", city_name);
if (strcmp(city_name, "-1") == 0) {
break;
}
src = findCity(&g, city_name);
if (src == -1) {
printf("城市不存在,请重新输入!\n");
continue;
}
printf("深度优先遍历结果:");
dfs(&g, src, visited);
printf("\n请输入目的城市名称:");
scanf("%s", city_name);
dest = findCity(&g, city_name);
if (dest == -1) {
printf("城市不存在,请重新输入!\n");
continue;
}
dijkstra(&g, src, dist);
printf("%s到%s花销最小的路径为:", g.cities[src].name, g.cities[dest].name);
while (dest != src) {
printf("%s<-", g.cities[dest].name);
dest = (dist[dest] == INF) ? -1 : findCity(&g, g.cities[dest].name);
for (i = 0; i < g.city_num; i++) {
if (g.edges[dest][i].cost != INF && dist[dest] - dist[i] == g.edges[dest][i].cost) {
dest = i;
break;
}
}
}
printf("%s,花销为%d百元\n", g.cities[src].name, dist[src]);
printf("请选择要修改的路线花销(输入-1退出):\n");
for (i = 0; i < g.city_num; i++) {
if (i != src && g.edges[src][i].cost != INF) {
printf("%s-%s:%d百元\n", g.cities[src].name, g.cities[i].name, g.edges[src][i].cost);
}
}
scanf("%d", &choice);
if (choice == -1) {
break;
}
printf("请输入新的路线花销:");
scanf("%d", &cost);
g.edges[src][choice].cost = cost;
g.edges[choice][src].cost = cost;
}
return 0;
}
```
该程序使用邻接矩阵表示城市交通网络,支持添加城市和路线,并实现了深度优先遍历和Dijkstra算法求最短路程。用户可以选择要修改的路线花销,并输入新的路线花销。程序会返回修改后的邻接矩阵表示。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)