数据结构课设报告(2)

19 26 27 30 0 1 28 11 2 20 36 14 31 12 32 37 15 13 3 16 38 4 17 39 18 5 43 21 6 22 23 29 24 25 42 7 33 34 41 8 35 40 9 10 公交线路图

5

3.2程序的编写

3.2.1站点信息的初始化和赋值 根据所查找的路径图，对各公交站点进行初始化信息并用二维数组对其边的权值进行初始化，用CreateUDN构建站点信息以及站点间的无向图。 3.2.2定义一个最短路径函数

利用dijikstra算法定义一个最短路径函数，可以查找最短路径问题 3.2.3定义一个一次换乘最优路径函数

在两站间有直达车或者一次换乘时，可以不考虑最短路径而输出一次换乘最优方案，这样考虑到乘客的实际情况而额外加的功能。 3.2.4输出函数

void output(int site1,int site2)输出最短路径函数的定义 3.3.5主函数的编写 void main() {

int v0,v1,n; char c;

CreateUDN(Len); for(;;) {

lable:; narrate();

printf(\要退出程序请按:【Ctrl+Pause Break】\\n\ printf(\请选择起点的公交站(0～43)：\ scanf(\ if(v0<0||v0>Len-1) {

printf(\输入有误，请重试!!!\\n\ getch();

system(\ goto lable; } loop:;

printf(\请选择终点的公交站(0～43)：\ scanf(\ if(v1<0||(v1>Len-1)||v1==v0) {

printf(\输入有误，请重试!!!\\n\ goto loop; }

loop2:;

printf(\请问您想以下面哪种方式查询？请输入对应的序号\\n\ printf(\路径最短\\n\

printf(\换乘一次的最优乘车路线\\n\

6

printf(\请输入您选择的乘车方式：\ scanf(\ if(n==1) {

shortestpath(v0);

/*计算两个城市之间的最短路径*/ output(v0,v1); /*输出结果*/ printf(\ }

if(n==2) {

printf(\本程序换乘次数不会超过1次，如果1次换乘不能达到，则建议您参考其他乘车方案\

printf(\您是否继续(y/n)？请输入y或n：\ c=getch();

if(c=='n') goto loop2;

if(c=='y') huanchewng(v0,v1); printf(\ }

if(n!=1&&n!=2) { printf(\您的错误输入导致本程序崩溃！请您重启程序\\n\ }

printf(\

system(\ system(\ } }

7

4、软件模块结构

公交路线信息查询与初始化信息 Dijkstra求最短路径 一次换乘最优路线编写 Output输出最短路径方案 主函数 5、程序设计思想

利用dijkstra算法，求出最短路径，用shortestpath(v0),再用output函数输出该路径；利用一次换乘最优算法求出一次换乘最优路径，，输出换乘方式。利用有向图存储各站点，数组存储站点信息，公交路线信息用指针定义。

8

6、程序流程图

开始 定义整型变量（V0,V1,n） 建立带权的无向图For(;;) 输入V0，V1的输入y/n来判断查询方式 Shortestpath(v0) Output(v0,v1) Huancheng(v0,v1)_ System(pause) 退出

9