交通咨询系统 数据结构课程设计-课程设计报告.docx

PAGE 8 上 海 电 机 学 院 课 程 设 计 报 告 课设课题： 数 据 结 构 ━━ 交通咨询系统 学 院： 电 子 信 息 学 院 1 专 业： 1 姓 名： 1 班 级： 指导老师： 1 报告日期： 年 月 制 目 录 TOC \o 1-3 \h \z \u 一、需求分析： 1 二、总体结构设计： 1 三、各子模块设计： 2 四、编程实现： 3 五、测试结果： 6 六、总结： 9 七、参考文献： 9 九、附录源代码： 10 一、需求分析： ?设计一程序，完成交通咨询系统的设计。旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径或最低费用或最少时间等问题。对于不同咨询要求，可以输入城市间的路程或所需要时间或所需费用。可用实例来验证迪杰斯特拉算法。要求“ 建立交通网络图的存储结构； 解决单源最短路径问题； 实现两个城市顶点之间的最短路径问题。　　 要求：　　根据以上功能说明，设计程序完成功能。 二、总体结构设计： 输入不同数字,来控制程序执行不同的子模块并实现相应功能。 图2.1主菜单总体设计结构 三、各子模块设计： 3.1子模块 新建城市网,按要求输入城市名字、边数以及各边权值 图3.1新建城市网流程图 3.2 子模块 输入出发地和目的地，咨询权值分别为路程、时间、费用的最短路径 图3.2求最短路径流程图 四、编程实现： 鉴于实际生活中交通网络的双向性，特建立无向网来说明各城市间的交通关系。 #includestdio.h #includestring.h #includestdlib.h #define MAXLEN 100 #define INFINITY 99999 //定义一个很大的数,邻接矩阵边的初始权值 //图的邻接矩阵存储结构如下： typedef struct { char vexs[MAXLEN][MAXLEN]; float edges_path[MAXLEN][MAXLEN]; //以路径为边的权值 float edges_money[MAXLEN][MAXLEN]; //以费用为边的权值 float edges_time[MAXLEN][MAXLEN]; //以时间为边的权值 int n,e; }MGraph; //建立一个无向图的邻接矩阵存储的算法简略如下： MGraph *CreateMGraph() { int i,j,k; float weight_path,weight_money,weight_time; char ch1[MAXLEN],ch2[MAXLEN]; MGraph *G; G=(MGraph *)malloc(sizeof(MGraph)); // 邻接矩阵初始化 for (i=0; iG-n; i++) for (j=0; jG-n; j++) { G-edges_path[i][j]=INFINITY; G-edges_money[i][j]=INFINITY; G-edges_time[i][j]=INFINITY; } //给无向图的边赋初值 for(i=0;strcmp(ch1,G-vexs[i])!=0; i++); for(j=0;strcmp(ch2,G-vexs[j])!=0; j++); { G-edges_path[i][j]=weight_path; G-edges_path[j][i]=weight_path; G-edges_money[i][j]=weight_money; G-edges_money[j][i]=weight_money; G-edges_time[i][j]=weight_time; G-edges_time[j][i]=weight_time; } } //函数功能，找到城市名字在邻接矩阵中对应的下标 int Tranform_Name_int(MGraph *G,char v0_