交通咨询系统设计报告

下载可编辑重庆科技学《数结构》程计报告

:_院级计2名

:点位___计算机基

____目________

计______7月6语________________________________________________________________________________________________________________________________________________________________________________________________.专.整理.下载可编辑____________________制__________师字重庆科技学院课程设计任务设计题目：交通咨询系统的设计学生姓名课程名称

数据结构课程设计

专业班级

计地

点

计算机基础自主学习中心

起止时间

2012.6.25-2012.7.6设计内容及要求设计

人们在出差旅游出行时往往关心节省交通费用或节省所需要的时间等问。可以用一个图结构来表示交通网络，图顶点表示城市边示城市之间的交通情况其权值可代表里交费或时间设一个交通咨询系统能旅客咨询从任一个城市到另一个城市之间的最短路径里最交通费用或最少时间等问题该设计的内容主要分两部分一建立交通网络图的存储结；二是实现求两个城市顶点之间的最短路径算法要求表示城市之间的交通关系的边的信息中包括里、费用时间三个值程可实现求任两个城市之间的最短里、最少时间或最少费用的路线建图的存储结构时要求从文本文件中读入顶点和边的信测试数据要求交通图中顶点数不少于16个边不少于20，每边有三个权里程交通.专.整理.参数

下载可编辑费用时。完任务的讲解并接受课程设计任，选定课程设计的题目

了解任务的算法、并出法的程序流程图对务的关键技术进行验证并确定解决办法进度要求参考资料其它说明

程序设计及编码上机调试对序进行调试设计测试用例进行测试整课程设计的过程并进行总，完善程序功能编课程设计报告初稿完课程设计报并备答辨提课程设计报告和程序进行答辨．严蔚敏吴民数据结构清大学出，．程杰大数据结，清华大学出版2011.6．（美）StephenPrata,CPlus中文版（第五版），人民邮电出版社，2005.21.本应在每次实施前一周由负责教师填写二份学院审批后交学院教务办案一份由负责教师留用若写内容较多可另纸附后。3.一多名学生共用的在计内容参要求等方面应有所区系主任雷亮

指导教：

黄永文王双明熊茜军王成敏月日摘要.专.整理.下载可编辑在交通网络非常发达，们在出、旅游出行，往往关心节省交通费用或节省所需要的时间等问题。对于这样一个人们关心的题可以用一个图结构来表示交通网络，利用计算机建立一个交通咨询系统。图中顶点表示城市边表示城市之间的交通情，权值可代表里、交通费用或时。比如任意一个城市到其他城市的最短路径，任意两个城市之间的最短路径问题。本次设计的交通咨询系统主要是运用C语言的数据结构来完成交通图的存、图中顶点的单源最短路径和任意一对顶点间的最短路径问题关键词数字结构

C语言

交通咨询

最短路径.专.整理.下载可编辑目录1设计内容要求....................................................................................................................................11.1问题描...............................................................................................................................11.2需求分析.................................................................................................................................12课程需求析........................................................................................................................................2.1算法思...............................................................................................................................22.2数据结体..........................................................................................................................22.3基本操...............................................................................................................................42.4算法应...............................................................................................................................4.专.整理.下载可编辑2.5程序设流程图.................................................................................................................53功能模块细设计...............................................................................................................................3.1测试数...............................................................................................................................63.2程序调...............................................................................................................................74课程结与体会...............................................................................................................................245考文献...............................................................................................................................................6致谢.......................................................................................................................................................27.专.整理.下载可编辑.专.整理.下载可编辑1设计内容和要求1.1问题描述设计、实现一个全国大城市间的交通咨询程序为旅客提供三种最优决策方案：（1）时间最短（2）费用最小（3）里程最少。1.2需求分：该程序所做的工作的是模拟全国交通咨询为旅客提供三种最优决策的交通咨询。此程序规定：（1）在程序中输入城市名称时，需输入20字符以内的字符串；输入费用时需输入一个实型数；入时间时需输入一个整型数据在选择功能，应输入与所选功能对应的一个整型数据。（2）程序的输出信息主要是：最快需要多少时间才能到达或最少需要多少旅费才能到达，或两城市间需要走过的最短路程并详细说明如何坐车才能最省。（3程序的功能包：提供对城市信息的编辑两城市间时、花费、还有路程的编辑，提供三种最优决策：最快到达、最省钱到达、最少路程到达.专.整理.下载可编辑2课程需求分析2.1算法思(1)数据存储市信息通信息(城市间的里程费和时间)存储于磁盘文建议把城市信息交通信息还有城市和交通信息数目分开存于三个文件中fread和函数操。

用(2)数据的逻辑结构据设计任务的描述城市之间的旅游交通问题是典型的图结，看作为有向，的顶点是城，边是城市之间所耗费时间旅费里程。数据的存储结构。采邻接矩阵作为数据的存储结构，提高空间的存储效率用不同的功能模块对城市信息和交通信息进行编，可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可(6)主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。2.2数据结体typedefstructlu/*交通信息数据类型*/{.专.整理.下载可编辑intdistance;市间里程*/intcost;/*城市间旅费*inttime;/*城市间时间*/}lu,lujin[max][max];typedefstructcity/*市数据类型*/{charname[20];/*城市名称/}citys[max];typedefstruct网络图的数据类型*{citysclist;/*城市信息*/lujinarcs;/*边的信息*/intc_n,l_n;/*和顶点数目*/}Graph;typedefstruct/*最短路径/{charadjvex;intmincost;/*最少旅费/intmindistance;/*最短里程/.专.整理.下载可编辑intmintime;/*少时间*/}closedge;2.3基本操voidzairu(Graph导入文件中的信息能否是程序运行*/voidAdminister(GraphG);/*管理员操作界面，由主函数调用/voidshow(Graph显示系统中的全部城市信息和交通信息*/intinsertcity(Graph*G);/*加城市信息*/intinsertlu(Graph增加交通信息*/intLocated(Graphchar*p);/*返回邻接矩阵的位置下标系统中的关键*/voidbaocun(GraphG);/*将城市信息、交通信息保存在文件中*/intserchlu(Graph*G);/*搜索交通信息*/voidmindistance(Graphintv0,intv1);/*最少里程计算，迪杰斯特拉算法*/voidmincost(Graphintv0,intv1);/*少旅费计算，迪杰斯特拉算法/voidmintime(Graphintv0,intv1);/*最少时间计算，迪杰斯特拉算法*/2.4算法应在判断源点到其余各点的最短路径时运用迪杰斯特拉算法一般情况下，设S为以求得最短路径的终点的集，则可证明下一条最短路径（设其终点为x）或者是弧(，或者是中奖只经过的顶点而最后到达顶点x路径。可用反证法来证，设此路径上有一个顶点不在S中则说明存在一条终点不在S而长度比此路径短的路。但是，这是不可能。为我们是按照路径长度递增的次序来产生各最短路径的，长度比此路径段的所有路径均已产生，它们的终点必定在S中，即假设不成立。因此，在一般情况下，下一条长度次短的最短路径的长度必是.专.整理.下载可编辑D[j]Min{D[i]}i其中者是，或者是()和弧vik

i

上的权值之和。（1）假设用带权的邻接矩阵来表示带权有向图，示v<vi,vj>上的权值。<vi,vj>存在则置∞计算机上可用允许的最大值代。为已找到从出发的短路径的终点的集合他的初始状态为空集。那么，v出发到图上其余个顶点终点)vi能达到的最短路径长度的初值为D[i][Locate（2）选择，使得j

()[i]Viv

j

D[i]Min{D[i]vS}i就是当前求得的一条从v出发的最短路径的终点。令S{j}(3)修改从v发到集合上任一顶点

可达的最短路径长度。如果D[i][j][]D[k]则修改

D[k]

为D[][j]arcs[j][k](4)重复操作(、共。由此求得从到图上其余各点的短路径是依路径长度递增的序列。2.5程序设流程图.专.整理.返上返上下载可编辑交通咨系统图2.1序设计流程图管理员

显示所交通路线

用户

退出添城

添交3

功能模块细少

查最

查最

返上路

级单

花路

时路

里路

级单3.1测试数表3.1市信息北京重庆九江

天津成都武汉

石家庄郑州广安

济南徐州无锡表3.2通信息表起始重庆重庆广安北京济南成都浙江

目的广安成都成都天津天津南京郑州

旅费（元）5010060100200500300

时间（小时）12030

里程（公里）3005001002503007001000.专.整理.下载可编辑九江南京石家庄浙江重庆成都无锡徐州上海济南天津广安上海

武汉无锡北京徐州南京郑州北京上海温州重庆武汉济南重庆

200100100300500400700200100150530300534

10552423304015815282328

50020030015002000240035008953005002593184214343.2程序调1.主界面包括四个选项选项一：管理员管理界面选择该项可进行城市交通系统的管理选项二用户咨询界，择该项可进行最少费、最时间最短里程的决策咨；选项：显示城市交通系统，择该项可显示城市交通系统的所有信息包括城市、交通路线信息；选项四：退出程序，选择该项将退出程序。.专.整理.下载可编辑图程序主面在该系统运行的开始会从文件读取交通信息，如果文件不存在会导致程序运行错误！出现下图情况：图3.2件不存在该函数代码如下：voidzairu(Graph读取文本中的信息{FILE*fpout,*fpin;intcnum,lnum;.专.整理.下载可编辑charFromc[20],Toc[20];inti,j;for(i0;<max;i++)for(j0;<max;j++){G->arcs[i][j].distanceG->arcs[j][i].distancezuida;G->arcs[i][j].costG->arcs[j][i].costzuida;G->arcs[i][j].timeG->arcs[j][i].time=zuida;}fpoutfopen("number.txt","r");assert(fpout);if(fscanf(fpout,%d",&cnum,&lnum)==2){G->c_ncnum;G->l_n=lnum;fclose(fpout);//取城市顶点信息fpoutfopen("city.txt","r");for(t=t<G->c_n;t++)fscanf(fpout,"%s",G->clist[t].name);fclose(fpout);//取边的信息.(起点、终点、距离千米)、费元)、时间(分钟).专.整理.下载可编辑fpoutfopen("lu.txt",for(t=t<G->l_n;t++){fscanf(fpout,"%s%s",Fromc,Toc);=Located(G,=Located(G,fscanf(fpout,"%d%d%d",&G->arcs[i][j].distance,&G->arcs[i][j].cost,&G->arcs[i][j].time);G->arcs[j][i].distanceG->arcs[i][j].distance;G->arcs[j][i].costG->arcs[i][j].cost;G->arcs[j][i].timeG->arcs[i][j].time;}fclose(fpout);}else{fpin=fopen("number.txt","w");assert(fpin);fprintf(fpin,0");G->l_n=G->c_n0;fclose(fpin);.专.整理.下载可编辑}}．管理员管理界面首先出现登陆界面采用加密技术始密码为，菜单项包括个选项：选项增城市信；选项二增加交通路线信；选项：存新增信息返回上一级菜可返回主界。.专.整理.下载可编辑图3.3管理员界面在该界面中调用了三个重要函数对城交通信息进行编辑和保存intinsertcity(Graph*G)//增加城市{charname[20];入要增加的城市:");scanf("%s",name);getchar();if(G->c_n{strcpy(G->clist[0].name,name);G->c_n++;}else{for(int=0;<G->c_n;if(strcmp(G->clist[i].name,name)==0)return-1;elsestrcpy(G->clist[G->c_n].name,name);.专.整理.下载可编辑G->c_n++;}return}图3.4加城市intinsertlu(Graph增加城市交通信息{charFromc[20],Toc[20];inti,j;intd,t;输入增加路径的出发城市目的城市(公)(元时间():\n");scanf("%s%s%d%d%d",Fromc,Toc,&d,&c,&t);.专.整理.下载可编辑getchar();=Located(G,=Located(G,if(i==||j==-1)return-1;else{G->arcs[i][j].distanceG->arcs[j][i].distanced;G->arcs[i][j].costG->arcs[j][i].costc;G->arcs[i][j].timeG->arcs[j][i].time=t;G->l_n++;}return}.专.整理.下载可编辑图增加通信息voidbaocun(Graph保存新增信息于文件中{FILE*fpin;inti,m,k;边和顶点的个数fpin=fopen("number.txt","w");assert(fpin);fprintf(fpin,%d",G.c_n,G.l_n);fclose(fpin);顶点信.fpin=fopen("city.txt","w");assert(fpin);for(i0;<G.c_n;i++){fprintf(fpin,"%s",G.clist[i].name);m=i%10;if(m==0).专.整理.下载可编辑printf("\n");}fclose(fpin);边的信.fpin=fopen("lu.txt",assert(fpin);for(i0;<G.c_n;i++){for(k=+1;<G.c_n;k++){if(G.arcs[i][k].distancezuida)fprintf(fpin,"%s%s%d%d%d\n",G.clist[i].name,G.clist[k].name,G.arcs[i][k].distance,G.arcs[i][k].cost,G.arcs[i][k].time);}}fclose(fpin);}保存文件在该系统中是一个重要的组成部分用于对城市和交通信息的保存，将其储存在文件之中！用户查询路线下图：.专.整理.下载可编辑图3.6找方法该系统的查找方法每一种查找最短路径的算法都是运用迪杰斯特拉算法代码如：voidmindistance(Graphintv0,intv1)//最短距离{

该int*d;intvd,w,i,j,v;intmind,*pred,*finald;finald=(int*)malloc(G->c_nsizeof(int));//判断顶点是否已求出最短路径.专.整理.下载可编辑d=(int*)malloc(G->c_nsizeof(int));//储存起始点到各点的最短路径pred(int*)malloc(G*sizeof(int));//最后用于输出最短路径for(v=0;vG->c_n;v++){finald[v];d[v]=G->arcs[v0][v].cost;if(d[v]<zuida)pred[v]=v0;elsepred[v]=-1;}d[v0]=0;//到起始点无路径finald[v0]=1;//v0放入到final数组里for(i=1;i<G->c_n;i++)//从1开因为起始点已经在final里剩下-1个顶循环-1次{mind=zuida;for(w=0;w<G->c_n;w++){if(!finald[w])//没有放进final里面的终点进行选择最短路径出来.{.专.整理.下载可编辑if(d[w]<mind){mind=d[w];vd=w;}}找到最短路径终点G->vexs[v]finald[vd]=1;//放入final中for(w0;<G->c_n;{if(!finald[w]&&(mind+G->arcs[vd][w].distanced[w]))//到每个终点当前的最短路径该终点已在final里

更新源点{d[w]mindG->arcs[vd][w].distance;pred[w]vd;}}}if(pred[v1]-1){

跳出语、printf("%s

到

%s",G->clist[v0].name,G->clist[v1].name);短路程为():%d\t\t",d[v1]);.专.整理.下载可编辑printf("%sG->clist[v0].name);j=pred[v1];while(j!=v0){printf("-->%s",G->clist[j].name);j=pred[j];}printf("-->%s\n",G->clist[v1].name);}elseprintf("%s到%s没有信.\n",G->clist[v0].name,G->clist[v1].name);}该代码在系统中是核心算法.专.整理.下载可编辑图3.7短路径显示所有交通信息图3.8通信息.专.整理.下载可编辑该函数代码如下voidshow(Graph{inti,system("cls");printf("\n\n目前交通系统中含有%d个城条旅游路径\n\n\n",G.c_n,G.l_n);大城:\n");for(i0;<G.c_n;i++){printf("%sG.clist[i].name);if((i+1)%10==0)printf("\n");}printf("\n\n************************************************************\n\n");城t\t城\t\t距()\t花(元)时()\n");for(i0;<G.c_n;i++)for(k=+1;<G