现需建立一个城市交通系统,可以用图的结构来表示实际交通网络,顶点表示城市,边代表城市间的交通线路,边上权值表示线路花销(单位:百元)。请用写C语言代码实现以下功能,系统具体功能需求如下: 1、从键盘输入城市及城市之间线路的信息,建立城市交通网,以下为城市之间的权值(即线路花销)a->b为15 a->c为2 a->d为12 b->e为6 c->e为8 c->f为4 d->g为3 e->g为9 f->d为5 f->g为10 g->b为4 2、输出该交通网的存储表示; 3、指定某个出发城市,对交通网进行深度优先遍历并打印结果; 4、指定某个出发城市,输出该城市到网中其他城市,花销最小的路径; 5、指定某条路线,修改路线花销。 图1.2 城市交通网 实现要求: 1、以邻接矩阵作为图的存储结构; 2、使用迪杰斯特拉算法求最短路径; 3、为该系统制定一个功能菜单,输入对应的功能编号,则执行相应功能
时间: 2024-03-14 10:44:13 浏览: 238
好的,以下是C语言代码实现城市交通系统功能:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CITY 20
#define INF 1000000
typedef struct Graph {
int matrix[MAX_CITY][MAX_CITY]; // 邻接矩阵
int city_num; // 城市数量
char cities[MAX_CITY][20]; // 城市名称
} Graph;
// 初始化图
void init_graph(Graph *g) {
int i, j;
for (i = 0; i < MAX_CITY; ++i) {
for (j = 0; j < MAX_CITY; ++j) {
g->matrix[i][j] = INF; // 初始化邻接矩阵
}
}
g->city_num = 0; // 初始化城市数量为0
}
// 添加城市
void add_city(Graph *g, char *city_name) {
strcpy(g->cities[g->city_num], city_name); // 存储城市名称
g->city_num++; // 城市数量加1
}
// 添加路线
void add_route(Graph *g, char *city1, char *city2, int cost) {
int i, j, index1 = -1, index2 = -1;
// 找到城市1和城市2的下标
for (i = 0; i < g->city_num; ++i) {
if (strcmp(g->cities[i], city1) == 0) {
index1 = i;
}
if (strcmp(g->cities[i], city2) == 0) {
index2 = i;
}
}
// 添加路线
g->matrix[index1][index2] = cost;
}
// 输出图的存储表示
void print_graph(Graph *g) {
int i, j;
printf("\n城市交通网存储表示:\n");
printf(" ");
for (i = 0; i < g->city_num; ++i) {
printf("%s ", g->cities[i]); // 输出城市名称
}
printf("\n");
for (i = 0; i < g->city_num; ++i) {
printf("%s ", g->cities[i]); // 输出城市名称
for (j = 0; j < g->city_num; ++j) {
if (g->matrix[i][j] == INF) {
printf("∞ "); // 输出无穷大
} else {
printf("%d ", g->matrix[i][j]); // 输出路线花销
}
}
printf("\n");
}
}
// 深度优先遍历
void dfs(Graph *g, int v, int visited[]) {
int i;
visited[v] = 1; // 标记为已访问
printf("%s ", g->cities[v]); // 输出城市名称
for (i = 0; i < g->city_num; ++i) {
if (g->matrix[v][i] != INF && visited[i] == 0) {
dfs(g, i, visited); // 递归访问相邻未访问节点
}
}
}
// 深度优先遍历并打印结果
void dfs_search(Graph *g, char *start_city) {
int i, start_index = -1, visited[MAX_CITY];
// 找到出发城市的下标
for (i = 0; i < g->city_num; ++i) {
if (strcmp(g->cities[i], start_city) == 0) {
start_index = i;
break;
}
}
// 初始化visited数组为0
for (i = 0; i < g->city_num; ++i) {
visited[i] = 0;
}
printf("\n从%s出发深度优先遍历结果:\n", start_city);
dfs(g, start_index, visited);
}
// 迪杰斯特拉算法求最短路径
void dijkstra(Graph *g, int start, int end, int path[], int dist[]) {
int i, j, min_dist, min_index, visited[MAX_CITY];
// 初始化path数组为-1,表示没有路径
for (i = 0; i < g->city_num; ++i) {
path[i] = -1;
}
// 初始化visited数组为0,表示所有节点都未访问
for (i = 0; i < g->city_num; ++i) {
visited[i] = 0;
}
// 初始化dist数组为每个节点到起点的距离
for (i = 0; i < g->city_num; ++i) {
dist[i] = g->matrix[start][i];
if (dist[i] == INF) {
path[i] = -1; // 如果起点到该节点没有直接路线,设置path为-1
} else {
path[i] = start; // 如果起点到该节点有直接路线,设置path为起点
}
}
visited[start] = 1; // 起点已访问
for (i = 0; i < g->city_num - 1; ++i) {
min_dist = INF;
min_index = -1;
// 找到未访问节点中距离起点最近的节点
for (j = 0; j < g->city_num; ++j) {
if (visited[j] == 0 && dist[j] < min_dist) {
min_dist = dist[j];
min_index = j;
}
}
visited[min_index] = 1; // 标记为已访问
// 更新dist数组和path数组
for (j = 0; j < g->city_num; ++j) {
if (visited[j] == 0 && g->matrix[min_index][j] != INF && dist[min_index] + g->matrix[min_index][j] < dist[j]) {
dist[j] = dist[min_index] + g->matrix[min_index][j];
path[j] = min_index;
}
}
}
}
// 输出路径
void print_path(Graph *g, int start, int end, int path[]) {
if (path[end] == -1) {
printf("不存在从%s到%s的路线", g->cities[start], g->cities[end]);
return;
}
int p[MAX_CITY], i, j = 0, k;
p[j] = end;
k = path[end];
while (k != start) {
j++;
p[j] = k;
k = path[k];
}
j++;
p[j] = start;
printf("\n从%s到%s的最短路径为:\n", g->cities[start], g->cities[end]);
for (i = j; i > 0; --i) {
printf("%s -> ", g->cities[p[i]]);
}
printf("%s,花费:%d百元\n", g->cities[p[0]], dist[end]);
}
// 修改路线花销
void modify_cost(Graph *g, char *city1, char *city2, int new_cost) {
int i, j, index1 = -1, index2 = -1;
// 找到城市1和城市2的下标
for (i = 0; i < g->city_num; ++i) {
if (strcmp(g->cities[i], city1) == 0) {
index1 = i;
}
if (strcmp(g->cities[i], city2) == 0) {
index2 = i;
}
}
// 修改路线花销
g->matrix[index1][index2] = new_cost;
printf("\n%s到%s的路线花费已修改为%d百元\n", city1, city2, new_cost);
}
int main() {
Graph g;
char city1[20], city2[20], city_name[20], start_city[20];
int cost, choice, start, end, i, path[MAX_CITY], dist[MAX_CITY];
init_graph(&g); // 初始化图
// 添加城市
add_city(&g, "北京");
add_city(&g, "上海");
add_city(&g, "广州");
add_city(&g, "深圳");
add_city(&g, "杭州");
add_city(&g, "南京");
add_city(&g, "武汉");
add_city(&g, "成都");
// 添加路线
add_route(&g, "北京", "上海", 15);
add_route(&g, "北京", "广州", 2);
add_route(&g, "北京", "武汉", 12);
add_route(&g, "上海", "杭州", 6);
add_route(&g, "广州", "杭州", 8);
add_route(&g, "广州", "成都", 4);
add_route(&g, "武汉", "南京", 3);
add_route(&g, "杭州", "深圳", 9);
add_route(&g, "杭州", "南京", 5);
add_route(&g, "南京", "成都", 10);
add_route(&g, "成都", "上海", 4);
while (1) {
printf("\n城市交通系统功能菜单:\n");
printf("1. 输出城市交通网存储表示\n");
printf("2. 指定出发城市,深度优先遍历并打印结果\n");
printf("3. 指定出发城市和终点城市,输出最短路径和花销\n");
printf("4. 修改路线花销\n");
printf("5. 退出系统\n");
printf("请选择功能编号:");
scanf("%d", &choice);
switch (choice) {
case 1:
print_graph(&g);
break;
case 2:
printf("请输入出发城市:");
scanf("%s", start_city);
dfs_search(&g, start_city);
break;
case 3:
printf("请输入出发城市和终点城市:");
scanf("%s %s", city1, city2);
start = -1;
end = -1;
// 找到出发城市和终点城市的下标
for (i = 0; i < g.city_num; ++i) {
if (strcmp(g.cities[i], city1) == 0) {
start = i;
}
if (strcmp(g.cities[i], city2) == 0) {
end = i;
}
}
if (start == -1 || end == -1) {
printf("城市不存在!");
} else {
dijkstra(&g, start, end, path, dist);
print_path(&g, start, end, path, dist);
}
break;
case 4:
printf("请输入路线的起点、终点和新的花销:");
scanf("%s %s %d", city1, city2, &cost);
modify_cost(&g, city1, city2, cost);
break;
case 5:
printf("已退出城市交通系统\n");
return 0;
default:
printf("输入错误,请重新选择!\n");
break;
}
}
}
```
注意事项:
1. 代码中使用了邻接矩阵作为图的存储结构;
2. 深度优先遍历和迪杰斯特拉算法的实现可能需要些许时间来理解;
3. 代码中使用了一些全局变量,这不是一个很好的实践,但是为了简化代码,这里先这样处理。在实际项目开发中,需要尽量避免使用全局变量。
阅读全文