Catalog
  1. 1. 题目
  2. 2. 项目简介
  3. 3. 代码清单
数据结构课程设计实验五

题目

交通咨询系统

项目简介

1.建立交通网络图的存储结构

2.解决单源最短路径问题

3.解决两个城市顶点之间的最短路径问题

代码清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<string>

using namespace std;

const int MAXN = 100;
const int INF = 99999;
int map[MAXN][MAXN], dis[MAXN], path[MAXN];
int arcnum, vexnum, startpoint, endpoint;

void dijkstra(int startpoint, int vexnum)
{
int min, min_vex;
int vis[MAXN] = { 0 };
for (int i = 1; i <= vexnum; i++)
dis[i] = map[startpoint][i];

vis[startpoint] = 1;
dis[startpoint] = 0;
for (int i = 2; i <= vexnum; i++) {
min = INF;
for (int j = 1; j <= vexnum; j++) {
if (!vis[j] && dis[j] < min) {
min = dis[j];
min_vex = j;
}
}
vis[min_vex] = 1;
for (int j = 1; j <= vexnum; j++) {
if (dis[j] > min + map[min_vex][j]) {
path[j] = min_vex;
dis[j] = min + map[min_vex][j];
}
}
}
return;
}

void passby(int startpoint,int endpoint, int vexnum)
{
int i = endpoint;
stack<int> q;
while (path[i] != -1) {
q.push(i);
i = path[i];
}
q.push(i);
if (dis[endpoint] != INF) {
printf("源点:%d 终点:%d 总路程:%d米 途径地点:%d", startpoint, endpoint, dis[endpoint], startpoint);
while (!q.empty()) {
printf("->%d", q.top());
q.pop();
}
printf("\n");
}
else
printf("源点:%d 到 终点:%d 之间不连通\n", startpoint, endpoint);

return;
}

int main()
{
printf("**********欢迎使用交通咨询系统**********\n");
printf("##########现在请先构建交通网络##########\n");
printf("请输入顶点个数:");
scanf("%d", &vexnum);
printf("请输入路径的个数:");
scanf("%d", &arcnum);

memset(path, -1, sizeof(path));
memset(dis, INF, sizeof(dis));
for (int i = 1; i <= vexnum; i++) {
for (int j = 1; j <= vexnum; j++) {
map[i][j] = (i == j ? 0 : INF);
}
}
for (int i = 1; i <= arcnum; i++) {
printf("请输入第%d条弧的信息:起点编号 终点编号 路径长度(单位:米):", i);
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
map[u][v] = w;
}
printf("#############交通网络构建完毕#############\n");

while (1) {
printf("\n***************************************\n");
printf("请选择您所需功能的对应编号:\n");
printf("1.查询某一地点到其他地点的最短路径\n");
printf("2.查询某一地点到另一个制定地点的最短路径\n");
printf("3.退出系统\n");
int func;
scanf("%d", &func);

if (func == 1) {
printf("请输入源点的编号:");
scanf("%d", &startpoint);
printf("请输入终点的编号:");
scanf("%d", &endpoint);

dijkstra(startpoint, vexnum);
passby(startpoint, vexnum, vexnum);
}
else if (func == 2) {
printf("请输入源点的编号:");
scanf("%d", &startpoint);
dijkstra(startpoint, vexnum);
for (int i = 1; i <= vexnum; i++)
passby(startpoint, i, vexnum);
}
else {
printf("感谢您使用本系统,再见!\n");
return 0;
}
}
return 0;
}
Author: Christopher Shen
Link: https://www.pasxsenger.com/2020/03/24/数据结构课程设计实验五/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶