1、- 1 - 数据结构 课程设计报告 班级： 学号： 姓名： 指导老师： 日期： 2 7 7全国交通咨询模拟全国交通咨询模拟 出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中 的时间尽可能短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。 编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。要求： （1）提供对城市信息进行编辑（如添加或删除）的功能。 （2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑 （增设或删除）的功能。 （3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。 （4）旅
2、途中耗费的总时间应该包括中转站的等候时间。 （5）咨询以用户和计算机的对话方式进行。 1.需求分析 1、设计最短路径的算法及其需要信息的存储：本设计中最短路径的算法利用迪杰斯特拉算 法，存储方法利用邻接矩阵存储。 2、 该程序所做的工作的是模拟全国交通咨询，为旅客提供种最优决策的交通咨询。此程序 规定： 在程序中输入城市名称时，需输入 10 个字母以内的字母串；输入列车或飞机编号时需输入 一个字符串类型； 输入列车或飞机的费用时需输入一个实型数据； 输入列车或飞机开始时间 和到达时间时均需输入一个整型数据， 在选择功能时， 应输入与所选功能对应的一个整型数 据。 程序的输出信息主要是：最快需要
3、多少时间才能到达，或最少需要多少旅费才能到达，说明 在途中经过的城市名称； 程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供两种 最优决策：最快到达、最省钱到达。 2.设计 2.1 设计思想 本系统整体上分为存储系统和求最短路径两部分， 存储系统运用到数组和结构体。 该系统 分别存储火车列次，航班，出发点与目的地以及所需要走的路程和所用费用。最短路径使用 迪杰斯特拉算法编程求算得出最近或最便宜路径。该算法主要分为三步：1、起始点（V0） 与其相邻点的权值（即当前最短路径） 。2、求出当前最短路径中的最小值即是该起始点(V0) 与另一点(Vi)的最短路径。3、V0 到
4、 Vi 的距离加上 Vi 到 Vj 的距离小于 V0 到 Vj 则将 V0 到 3 Vi 的距离加上 Vi 到 Vj 的距离记为 V0 到 Vj 当前最短路径，循环第二、三步。如此得到 V0 到各点的最短路径，进而可以得到想要的一条。 （1）数据结构设计： struct Tra/火车或飞机的存储结构 char cc20; /用“车次“的前两个字母表示火车或飞机航班的代码 char start20; /出发点 char destination20; /目的地 float time; /路途时间 float price; /价钱 ; （2）算法设计 A，本设计采用的数据结构有图中的最短路径。 (1
5、)、开始- (2)、得到存储最少花费或最短时间信息的邻接矩阵- (3)、得到起始点与相邻的点的权值（即当前最短路径）并记录点- (4)、求出当前最短路径中的最小值即是该起始点(V0)与另一点(Vi)的最短路径- (5)、V0 到 Vi 的距离加上 Vi 到 Vj 的距离小于 V0 到 Vj 则将 V0 到 Vi 的距离加上 Vi 到 Vj 的距离记为 V0 到 Vj 当前最短路径并且记录前一个点。 (6)、重复（4） ， （5）步得到所有点最短路径。 (7)、以终点开始逐步向前赋值得到所需路径并输出该路径的权值。 代码： void short_path(struct Tra* timetabl
6、e,char* start,char* dest,char city20,int tn,int cn,int choice) int i,j,k,st,et; float min,t; char pcity1020; float edge1515,dist15; int path15,s15; for(i=0;icn;i+) for(j=0;jcn;j+) edgeij=max; for(i=0;itn;i+) j=search(city,timetablei.start,cn); k=search(city,timetablei.destination,cn); if(choice=0) t=timetablei.time; if(tedgejk) edgejk=t; 4 else t=timetablei.price;
