1、数据结构课程设计全国交通模拟汇总 数据结构 课程设计报告 班级：191113 学号：20111000611 姓名：黄建钊 指导老师：朱晓莲 日期：2013年3月7全国交通咨询模拟出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。要求：（1）提供对城市信息进行编辑（如添加或删除）的功能。（2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。（3）提供两种最优决策：最快到达或最省
2、钱到达。全程只考虑一种交通工具。（4）旅途中耗费的总时间应该包括中转站的等候时间。（5）咨询以用户和计算机的对话方式进行。1.需求分析1、设计最短路径的算法及其需要信息的存储：本设计中最短路径的算法利用迪杰斯特拉算法，存储方法利用邻接矩阵存储。2、 该程序所做的工作的是模拟全国交通咨询，为旅客提供种最优决策的交通咨询。此程序规定：在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个字符串类型；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入一个整型数据，在选择功能时，应输入与所选功能对应的一个整型数据。程序的输出信息主要是：最
3、快需要多少时间才能到达，或最少需要多少旅费才能到达，说明在途中经过的城市名称；程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供两种最优决策：最快到达、最省钱到达。2.设计2.1设计思想本系统整体上分为存储系统和求最短路径两部分，存储系统运用到数组和结构体。该系统分别存储火车列次，航班，出发点与目的地以及所需要走的路程和所用费用。最短路径使用迪杰斯特拉算法编程求算得出最近或最便宜路径。该算法主要分为三步：1、起始点（V0）与其相邻点的权值（即当前最短路径）。2、求出当前最短路径中的最小值即是该起始点(V0)与另一点(Vi)的最短路径。3、V0到Vi的距离加上Vi到Vj
4、的距离小于V0到Vj则将V0到Vi的距离加上Vi到Vj的距离记为V0到Vj当前最短路径，循环第二、三步。如此得到V0到各点的最短路径，进而可以得到想要的一条。（1）数据结构设计：struct Tra/火车或飞机的存储结构 char cc20; /用车次的前两个字母表示火车或飞机航班的代码 char start20; /出发点 char destination20; /目的地 float time; /路途时间 float price; /价钱;（2）算法设计A，本设计采用的数据结构有图中的最短路径。(1)、开始-(2)、得到存储最少花费或最短时间信息的邻接矩阵-(3)、得到起始点与相邻的点的权
5、值（即当前最短路径）并记录点-(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* timetable,char* start,char* dest,char city20,int tn,int cn,int choice) int i,j,k,st,et;
6、 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; else t=timetablei.price; if(tedgejk) ed
7、gejk=t; st=search(city,start,cn); et=search(city,dest,cn); for(i=0;icn;i+) disti=edgesti; si=0; if(i!=st&distimax) pathi=st; else pathi=-1; sst=1; distst=0; for(i=0;icn-1;i+) min=max; k=st; for(j=0;jcn;j+) if(!sj&distjmin)k=j;min=distj; sk=1; for(j=0;jcn;j+) if(!sj&edgekjmax&distk+edgekj=0;j-) print
8、f(%s ,pcityj); printf(n); if(choice=0) printf(tt所需总时间为:%5.1f小时n,distet); else printf(tt所需的总费用为:%7.2f元n,distet); printf(n);B，界面以及主函数功能板块本设计采用的是在界面上通过输入相应的字符表示的要求来实现对于不同目的不同函数的调用，主要用到的数据结构有图中的交通网的各种信息的邻接矩阵的存储。通过顾客输入不同的字符来实现不同的功能，主界面上注释着这个程序的系统名称，组员以及指导老师等基本学生信息，用星号来加以修饰；然后就是用一个swich语句来实现多功能的选取以及程序的退出；
9、主要有一：1:修改地图 2:编辑火车时刻表 t3:编辑飞机航班表 t4:选择出游路线 t5:退出；继而通过选中其中的数字来实现自己的目的；然后再引用程序再用一个switch case语句来实现1 2 3选项中的添加删除以及退出功能，然后在4中再用if语句来实现自己的需求考虑。可以随时退出程序。最后再经调用函数再来输出结果；代码：# include#include#includeconst float max=FLT_MAX;void main () int i,j,k,m,n,cn=5,tn=6,fn=6; printf(tt*n);printf(tt*n);loop1: printf(t请选
10、择所需功能：ntt1:修改地图 ntt2:编辑火车时刻表 ntt3:编辑飞机航班表 ntt4:选择出游路线 ntt5:退出);switch(i) /switch语句 case 1: /第一种情况，修改地图* while(j!=1&j!=2&j!=3) case 2: /修改火车时间表case 3:/修改飞机航班表，和列车相似case 4: printf(tt请选择交通工具(1.火车 2.飞机):); scanf(%d,&j);printf(n); if(j=1&k=1)short_path(train,citym-1,cityn-1,city,6,5,0); if(j=1&k=2) short
11、_path(train,citym-1,cityn-1,city,6,5,1); if(j=2&k=1) short_path(flight,citym-1,cityn-1,city,6,5,0); if(j=2&k=2) short_path(flight,citym-1,cityn-1,city,6,5,1); goto loop1;/回到主菜单case5：return;/退出系统2.2设计表示函数调用关系图 Main() short_path() Search()各模块调用关系 主菜单修改地图 编辑火车时刻表 编辑飞机航班表 选择出游路线 退出 修改地图 增加城市 删除城市 返回 编辑火
12、车时刻表 添加 删除 返回 编辑飞机航班表 添加 删除 返回 选择出游路线 飞机 火车 最短时间 最少花费 最短时间 最少花费2.3详细设计void main () int i,j,k,m,n,cn=5,tn=6,fn=6; printf(tt*n); printf(tt* 欢迎使用全国交通咨询模拟 *n); printf(tt* 黄建钊 *n); printf(tt* 191113 *n); printf(tt* 20111000611 *n); printf(tt* 计算机学院 *n); printf(tt* 指导老师：朱晓莲 *n); printf(tt*n);char city1520
13、=深圳,成都,南昌,杭州,北京;/现有城市，最多15个城市 struct Tra train20= T1,杭州,深圳,10,190, T2,北京,深圳,18,270, T3,北京,南昌,13,150, T4,北京,成都,25,300, T5,北京,杭州,14,160, T6,南昌,杭州,11,200 ; struct Tra flight20= F1,杭州,北京,3,1500, F2,深圳,北京,2.5,1300, F3,北京,成都,1,600, F4,南昌,北京,3,1400, F5,深圳,南昌,1,700, F6,成都,杭州,3,1650 ; printf(tt现有城市); /输出现有地图
14、上的城市,便于后面的输入和修改 for(j=0;jcn;j+) printf(%d.%st,j+1,cityj); printf(nn);loop1: printf(t请选择所需功能：ntt1:修改地图 ntt2:编辑火车时刻表 ntt3:编辑飞机航班表 ntt4:选择出游路线 ntt5:退出); printf(nt请选择:); scanf(%d,&i);while(i!=1&i!=2&i!=3&i!=4&i!=5) printf(tt输入有误，请重新输入:); scanf(%d,&i); /避免按错而导致程序错误switch(i) /switch语句 case 1: /第一种情况，修改地图l
15、oop2: printf(t现有城市：ntt); for(j=0;jcn|k1) printf(tt输入有误，请重新输入:); scanf(%d,&k); /避免按错而导致程序错误 if(k=cn) cn-; else for(m=k-1;mcn-1;m+) strcpy(citym,citym+1); /k后面的城市依次往前移一位 cn-; /城市总数减少一个 goto loop2; /查看修改后的地图，便于判断或是再次修改 else goto loop1; /回到主菜单 case 2: /修改火车时间表loop3: printf(ntt现有火车时刻表：n); printf(tt 车次 起点
16、站 终点站 路途时间(h) 票价(元)n); /输出各火车时刻表 for(j=0;jtn;j+) printf(tt%d:%st%st%st%5.1ftt%5.2ftn,j+1,trainj.cc,trainj.start,trainj.destination,trainj.time,trainj.price); printf(nn); printf(t功能：1.添加t2.删除t3.返回n); printf(t请选择：); scanf(%d,&j);while(j!=1&j!=2&j!=3) printf(tt输入有误，请重新输入:); scanf(%d,&j); /避免按错而导致程序错误pr
17、intf(n); if(j=1) printf(现有城市：n); for(k=0;ktn|k1) printf(tt输入有误，请重新输入:); scanf(%d,&k); /避免按错而导致程序错误if(k=tn) tn-; /火车车次减一 else for(m=k-1;mtn-1;m+) /k后面的列车依次往前移一位 trainm=trainm+1; tn-; goto loop3; /回到loop3，查看修改后的列车信息 else goto loop1; /回到主菜单 case 3:/修改飞机航班表，和列车相似loop4: printf(tt现有飞机航班表：n); printf(tt 班次
18、起点 终点 路途时间（h） 票价（元）n); for(j=0;jfn;j+) printf(tt%d: %st%st%st%5.1ftt%5.2ftn,j+1,flightj.cc,flightj.start,flightj.destination, flightj.time,flightj.price); printf(nn); printf(tt功能：1.添加t2.删除t3.返回n); printf(tt请选择：); scanf(%d,&j); while(j!=1&j!=2&j!=3) printf(tt输入有误，请重新输入:); scanf(%d,&j); /避免按错而导致程序错误 p
19、rintf(n); if(j=1) printf(现有城市：n); for(k=0;kfn|k1) printf(tt输入有误，请重新输入:); scanf(%d,&k); /避免按错而导致程序错误 if(k=fn) fn-; else for(m=k-1;mfn-1;m+)/k后面的航班依次往前移一位 flightm=flightm+1; fn-; goto loop4; else goto loop1;/回到主菜单 case 4: printf(tt请选择交通工具(1.火车 2.飞机):); scanf(%d,&j); while(j!=1&j!=2) printf(tt输入有误，请重新输
20、入:); scanf(%d,&j); /避免按错而导致程序错误printf(tt请选择决策方案(1.最短时间 2.最少花费):); scanf(%d,&k); while(k!=1&k!=2) printf(tt输入有误，请重新输入:); scanf(%d,&k); /避免按错而导致程序错误printf(t现有城市：n); for(i=0;icn|mcn|n1) /cn为现有城市数目 printf(tt输入有误，请重新输入:); scanf(%d,&n); /避免按错而导致程序错误 printf(n); if(j=1&k=1)short_path(train,citym-1,cityn-1,city,6,5,0); if(j=1&k=2) short_path(train,citym-1,cityn-1,city,6,5,1); if(j=2&k=1) short_path(flight,citym-1,cityn-1,city,6,5,0); if(j=2&k=2) short_path(flight,citym-1,cityn-1,city,6,5,1); goto loop1;/回到主菜单 case 5: return;/退出系统 void sh
