数据结构课程设计-----全国交通咨询系统

太原工业等就计算机工程系数据结构课程设计设计题目全国交通网络咨询系统班级计算机科学与技术学号132054103姓名________陈敏__________指导教师刘海静____________endl;cout/zl继续更改城市时间〃〈Vendl;cout〈〃0:返回上一级菜单〃〈endl;yr-w/r-y ii-4-//fJIIIK\«ss«ss«ssendl;cinh;switch h{case1:h=l;break;case0:h=0;break;default:{cout〃选择出错〃endl;}f=z+l;〃全局静态变量z,初始值为0while z++G-cost[n[z].ctime][x[z].ctime]=m[z].ctime;}z=f；returnG;〃Floyed函数求任意两点的最短路径void FloyedunDiGraph*D,unDiGraph*M〃图D M|int i,j,k,n;//i,j为循环变量,k表中间节点的变量costAdj A,C;〃A C为图，临时表示两种最佳路线组成的矩阵，定义costAdjB Ln=cnumber;for i=l;i=n;i++forj=l;j=n;j++{A[i][j]=D-cost[i][j];〃初始化矩阵A,CC[i][j]=M-cost[i][j];Path[i][j]=-l;//初始化权矩阵p}for k=l;k=n;k++//k为逐步加入的中间结点for i=l;i=n;i++//i代表矩阵A中行号forj=l;j=n;j++ifA[i][k]+A[k][j]A[i][j]{A[i][j]=A[i][k]+A[k][j];C[i][j]=C[i][k]+C[k][j];Path[i][j]=k;〃若i经过k到j比i到j小，则选择经过K个中间点之后，i,j两点的最佳路径〃构造A C两个任意节点上的最优路径所建造的矩阵，并分别赋给B L代表时间与花费L[i][j]=C[i][j];elseB[i][j]=A[i][j];L[i][j]=C[i][j];}//end for循环coutz/\n最短路径为/zendl;}///end-Floyed〃为了求从i到j的最短路径，只需要调用如下的过程void prnpassint i,int jif Path[i][j]!=-lprn_passi,Path[i][j];〃输出最短路径经过的所有点个数k prPath[i][j],0;}〃求最少时间路径void timeint Bcity,Ecity;〃起始成市号码和终点城市号码int1,11=1;〃定义变量1hdo{pri;〃输出城市列表及相应代码cout〈〃请输入起始城市和目的城市的代码，中间以空格隔开〃《endl;cinBcity;cinEcity;〃输入起始城市和终点城市的代码if!OBcityBcitycnumber+lOEcityEcitycnumber+lBcity!=Eci tycout«/z\n出错啦！！！输入城市号码请在1-7之间，且两城市代码不能相等！！〃〈〈endl;Floyed CreateTimeG0,CreateCostG0;//调用Floyed函数pr Bcity,0;//显示起始城市prn_pass Bcity,Ecity;〃调用prn_pass函数，显示最短路径经过的城市pr Ecity,0;〃显示终点城市if B[Bcity][Ecity]8000||L[Bcity][Ecity]8000cout〈〃两地间还没有线路通过〃endl;else{cout〈〈〃火车花的时间是〃[Ecity]〈〈〃小时〃〈〈endl;}cout〈〈〃输入

0.返回主菜单/zendl;scanf〃%d〃,1;//h=l;}whileh-l;〃求最少花费路径void moneyintBcity,Ecity;〃起始成市号码和终点城市号码char1,h=l;do{pri;〃输出城市列表及相应代码cout〃请输入起始城市和目的城市的代码，中间以空格隔开〃endl;cinBcity;cinEcity;〃输入起始城市和终点城市的代码if!0BcityBcitycnumber+l0EcityEcitycnumber+lBcity!=Eci tycout«/z\n出错啦！！！输入城市号码请在1-7之间，且两城市代码不能相等！！〃endl;〃输入出错FloyedCreateCostG0,CreateTimeG0;//调用Floyed函数pr Bcity,0;//显示起始城市prn_pass Bcity,Ecity;〃调用prn_pass函数，显示最短路径经过的城市pr Ecity,0;〃显示终点城市if LEBcity][Ecity]8000||B[Bcity][Ecity]8000cout〈〃两地间还没有线路通过〃endl;else{cout〈〈〃火车花的钱是〃[Ecity]〈〈〃元〃〈〈endl;coutz/输入

0.返回主菜单〃〈endl;scanf1;//h=1;}whileh==l;void add_city//对城市的增加static int i=l;int j;cout〈〃请输入你要增加的城市的个数〃〈endl;cin»j;for i=l;i=j;i++{cout〈〈〃请输入你要增加的城市名〃〈endl;pri,l;〃将添加的内容放置于add数组中，并以i为代码cnumber=cnumber+l;cout〈〈〃城市增加完毕〃endl;void chose〃选择最少时间或最小花费|int h;cout«，zl:最小花费〃endl;cout«，z2:最小时间”endl;cout〈〃请选择〃〈endl;cinh;if h==l{money;elsetime;void edit」ine〃增加编辑火车的费用CreateCostGl;void edit_hour〃增加编辑火车的时间{CreateTimeGl;void administrator〃管理员功能int h=l;while h{A///•■Xi1I f1I I I\\^Ts TsZr%*rx XTS^rs zT^ZiX**r^Tx Xr%*TX^TS TSZr%*rx xTs^Ts zT^ZiX**r^Tx Xr%*TX^TS TSZr%*rxXTS^TS ZJSZTX#*T^#JX Xr%#rs*Tx^Ts**〃endl;coutz，l:增加城市〃〈〈endl;cout«/z2:添加或编辑火车费用〃endl;cout/z3:添加或编辑火车时间〃〈〈endl;cout〈〃0:返回主菜单〃〈endl;^-V11I,\Tx-4-//“slz slz£z%fz^lz xl✓zjx%£^slz%tz lzvly%slz slz£z y^xj%xfz✓sjlxz%£^^lz%tz lzvl ys%lz slz slz y^^xfjzx x✓ljzx xy^%£y^x^✓lzj%slzy%%tz xlzvlx**〃endl;cout〈〈〃请选择〃〈endl;cinh;switch h{case1:add_city;break;case2edit_line;break;case3:edit_hour;break;case0:h=0;break;default:cout〈〃选择出错!〃〈〈endl;〃主函数void mainchar n;int x;while x!=0coutendl;cout〈〈〃输入你希望查询的种类代码，你将得到最佳方案!〃endl;cout〈〃******************全国交通网络模拟系统******************〃〈endl;cout/z*主菜单*〃〈endl;coutz/*

1.查看城市*，z«endl;coutz/*

2.选择最短时间路线*z，endl;cout，z*

3.选择最节约费用路线*〃endl;

4.管理员程序cout〈〃**z/endl;

0.退出程序coutz/**〃〈endl;cout〈〈〃xl*slz xl*xlz slz*1*xlx xlz xlz xlzxl*xl*//z—\-J]•ZTS^T%XTST%#T%^TS✓T%#TSXTSXTX ZT%^TS#TX^TST%TSTS^TS^T%✓TH^TS^TSXTX^T%^TS#TXXTST%TSTS^TSTX\\j-II|1coutendlendlendlendlendl;cout〈〃请选择0-

七、测试结果:开始界面输入你希望查询的种类代码，颂到藜撮隹瑁;a XX-xxxxxxxxxx全国父通网络模拟系统*xxxxxxxxxxxxxxxxxx主菜单*工•宜看…短时间路线*

2.选怪

3.选择最节约费用路线

4.管理房程序

1、查看程序XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXMXXXXX.成都.广州.上海.徐州.郑州.西安.北京I234567XXMMXXXXMMXXXXMMtOOOCXJOCXXXXJOCXXXXJOCXXXX

2、最快到达咨询（举例）鼠短路径为蠕主播花的时间是小时50IJ当输入出错时，系统会提示出错信息，并返回输入窗口让用户重新输入

八、心得体会及总结通过这次课程设计，我在本次实验中，对于图和最短路径的内容作了进一步加深，但是也发现了自己在“栈”的内容上不熟练，所以讲原本的最优路径的临时存放由原先设想的栈改换成加变量k进行每个节点的循环来找最优路径本次实验之后，应当利用更多的时间来实践课本内容，以求能熟练上手目录

一、课程设计题目

六、程序代码

一、课程设计题目全国交通网络咨询系统

二、需求分析

1、实现功能对城市信息（城市名、城市间的里程）进行编辑具备添加、修改、删除功能；对城市间的交通工具火车对列车时刻表进行编辑里程、和列车班次的添加、修改、删除;提供两种最优决策最快到达或最省钱到达全程只考虑一种交通工具，可以不考虑回程；咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面由用户选择最优决策原则和交通工具，输入起始站、终点站、出发时间，输出信息最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间，并详细说明依次于何时何地乘坐哪一趟列车何时到达何地

2、设计思路

（1）数据存储城市信息（城市名、代码）、交通信息（城市间的里程、各航班和列车时刻）存储于磁盘文件在实验中本想用文本储存数据，但操作不熟悉，而是改用图的邻接矩阵储存原始信息，而后用数组进行添加删改

（2）数据的逻辑结构根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构,可看作为无向图，图的顶点是城市，边是城市之间所耗费的时间（要包括中转站的时间）或旅费

（3）数据的存储结构采用邻接表和邻接矩阵都可作为数据的存储结构，这里建议采用邻接矩阵作为数据的存储结构

（4）用不同的功能模块对城市信息和交通信息进行编辑添加、修改、删除功能可用菜单方式或命令提示方式只要能方便的对城市信息和交通信息进行管理即可,但要注意人机界面,具体实现由学生自行设计，也可参考有关程序（届时在网上提供）这些工作有不小的工作量

（5）最优决策功能模块

①读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息、;表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市（代码、里程、列车车次）

②根据具体最优决策的要求，用floyd算法求出出发城市到其它各城市的最优值（最短时间或最小的费用，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中其目的城市所代表的元素中就保存了所需的最优决策结果其相应的初始值可为8,并在表头数组对应的城市元素中保存响应的信息

③主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作

四、概要设计本程序运用了关于图这种数据结构它的抽象数据类型定义如下typedef structunDiGraph〃结点int numVerts;邻接矩阵costAdj cost;//}unDiGraph,*UNG;基本操作unDiGraph*CreateCostG操作结果构造带权费用图unDiGraph*CreateTimeG操作结果构造带权时间图构造飞机带权费用图PathMat*FloyedunDiGraph*D操作结果函数求任意两点的最短路径Floyed

五、调用关系图

六、程序代码ftinclude windows.httinclude stdio.hftinclude crtdbg.hftinclude string.h#includeiostream.hftinclude malloc.httdefine INF10000〃定义一个最大数定为无穷值ftdefine MAX7static intcnumber=7;static intk=0;static intv=0,z=0;〃定义静态变量typedef struct zhu〃定义结构体zhuint ccost;〃定义结构变量int ctime;}zhu;zhu m

[20],x

[20],n

[20];〃定义数组为structzhu类型数组,且三个数组分别储存添加后的数据，且表示花费m,起点n,和终点xtypedef intcostAdj[MAX+1][MAX+1];〃定义图的邻接矩阵，并从1开始int Path[MAX+l][MAX+l];〃路程矩阵，表示经过存放的点ktypedef structunDiGraph{int numV;〃结点costAdj cost;〃邻接矩阵}unDiGraph,*UNG;typedef structcedit{char a

[10];}cedit;cedit add

[10];costAdj B,L;〃功能一输出相应的城市信息int pr int i,int j〃pr函数表输出功能int h=0;if j==0{h=i;}else ifj==lcinadd[i].a;switch h{case0:cout〈〃〃；break;case1:cout〈〈〃成都〃；break;case2:cout〈〃广州〃；break;case3:cout〈〈〃上海〃；break;case4:cout〈〃徐州〃；break;case5:cout〈〃郑州〃；break;case6:cout〈〈〃西安〃；break;case7:cout〈〈〃北京〃；break;return1;void pri〃声明pri函数，即利用pr函数输出代码为i的城市信息int i;cout〈〃城市以及其代码〃endl;cout〈〈〃**************************************〃〈Vendl;for i=l;i=cnumber;i++couti/z.z，;pri,0;cout〃****************************************〃〈end1;〃构造CostG图，表示其费用unDiGraph*CreateCostGint o〃火车的花费的存贮和编辑功能unDiGraph*G;int i;int j;〃定义的i,j做循环变量int8=0,40,415二1;〃£变量初始为1,h初始值为1,a=0,b=0临时表示开始城市代码以及目的城市代码if!G=unDiGraph*mallocsizeof unDiGraph〃为G图分配存储空间return NULL;for i=l;i=cnumber;i++for j=l;j=cnumber;j++G-cost[i][j]=INF;〃初始化矩阵cost每一项，使其无穷大G-numV=cnumber;G-cost[l]

[6]=G-cost

[6][l]=90;G-cost[l]

[2]=G-cost

[2]

[1]=84;G-cost

[2]

[3]=G-cost

[3]

[2]=51;G-cost

[2]

[5]=G-cost

[5]

[2]=67;G-cost

[3]

[4]=G-cost

[4][353;G-cost

[4]

[5]=G-cost

[5]

[4]=40;G-cost

[4]

[7]=G-cost

[7]

[4]=88;G-cost

[5]

[6]=G-cost

[6]

[5]=90;G-cost

[5]

[7]=G-cost

[7]

[5]=67;G-cost

[6]

[7]=G-cost

[7]

[6]=60;if o{whileh=l〃h初始值为1{v=v+l;//V为全局静态变量，初始值为0,v表示编辑的火车花费的组数,三个编辑数组中的存放代码pri;cout〈〈〃火车花费编辑〃endl;cout〈〃请输入开始城市的代码〃〈〈endl;cina;cout〃请输入目的城市的代码〃endl;cinb;cout〈〈〃请输入你的两地花费〃〈endl;cinm[v].ccost;n[v].ccost=a;x[v].ccost=b;cout〈〃请选择〃〈endl;T1-4-//xlz xlz xlzxlzxlz“11I\Xendl;cout/zl继续更改城市费用〃endl;cout〈〃0:返回上一级菜单〃〈endl;^-VT-4-//slz slzlz%fz^lzxlz%£^slz%tz lzvl slzslz£z%fz^lz%£^^lz%tz lzvl slzslz%fz^fz xlz%£^^lzslz%tz xlzvl11I\x✓jx y%y^xjx✓jx y%y^xjx✓jx xy^yx✓j%endl;cinh;switchh{case1:h=l;break;case0:h=0;break;default:{cout〈〃选择出错〃〈endl;年丫+1;〃初始定义变量£为1,全局变量丫为0,即1=0+1while v++//v++代表的意思G-cost[n[v].ccost][x[v].ccost]=m[v].ccost;}v=f;return G;〃构造TimeG图，表示其花费时间unDiGraph*CreateTimeGint o〃火车的时间的存贮和编辑功能unDiGraph*G;inti,j;〃循环变量int a=0,b=0,f,h=l;//a,b表增加城市的代码if!G=unDiGraph*malloc sizeofunDiGraph〃为G分配存储空间return NULL;for i=l;i=cnumber+l;i++for j=l;j=cnumber+l;j++G-cost[i][j]=INF;〃初始化使G-〉cost[i][j]为无穷G-numV=cnumber;G-cost

[1]

[6]=G-cost

[6]

[1]=9;G-cost[l]

[2]=G-cost

[2]

[1]=8;G-cost

[2]

[3]=G-cost

[3]

[2]=5;G-cost

[2]

[5]=G-cost

[5]

[2]=3;G-cost

[3]

[4]=G-cost

[4]

[3]=5;G-cost

[4]

[5]=G-cost

[5]

[4]=4;G-cost

[4]

[7]=G-cost

[7]

[5]=6;G-cost

[5]

[6]=G-cost

[6]

[5]=9;G-cost

[5]

[7]=G-cost

[7]

[5]=6;G-cost

[6]

[7]=G-cost

[7]

[6]=6;if owhileh==lz=z+1;〃全局静态变量,初始值为0,即1=0+1pri;cout〈〃火车时间编辑〃*endl;cout〃请输入开始城市的代码〃《endl;cina;cout〈〃请输入结尾城市的代码〃Gendl;cinb;cout〃请输入你的两地时间〃〈endl;cinm[z].ctime;n[z].ctime=a;x[z].ctime=b;cout〈〃请选择〃endl;iyr-k i-4—//■I1III\\。