交通咨询系统设计报告

1、重庆科技学院?数据结构?课程设计报告学院：电气与信息工程学院专业班级：计科2学生姓名：学号:设计地点单位计算机根底自主学习中央设计题目:一交通咨询系统设计_完成日期：2021年7月6日指导教师评语：.成绩五级记分制：指导教师签字：重庆科技学院课程设计任务书设计题目：交通咨询系统的设计学生姓名课程名称数据结构课程设计专业班级计地点计算机根底自主学习中央起止时间2021.6.25-2021.7.6设计内容及要求人们在出差、旅游出行时,往往关心节省交通费用或节省所需要的时间等问题.可以用一个图结构来表示交通网络,图中顶点表示城市,边表示城市之间的交通情况,其权值可代表里程、交通费用或时间.设计一个交

2、通咨询系统,能让旅客咨询从任一个城市到另一个城市之间的最短路径里程、最少交通费用或最少时间等问题.该设计的内容主要分两局部：一是建立交通网络图的存储结构；二是实现求两个城市顶点之间的最短路径算法.要求表示城市之间的交通关系的边的信息中包括里程、费用、时间三个值.程序可实现求任两个城市之间的最短里程、最少时间或最少费用的路线.建立图的存储结构时要求从文本文件中读入顶点和边的信息.设计参数测试数据要求：交通图中顶点数不少于16个,边数不少于20,每条边有三个权值里程、交通费用、时间.进度要求2021.6.25完成任务的讲解、并接受课程设计任务,选定课程设计的题目2021.6.26了解任务的算法、并

3、画出算法的程序流程图,对任务的关键技术进行验证、并确定解决方法2021.6.27-2021.6.29程序设计及编码,上机调试2021.7.02对程序进行调试,设计测试用例进行测试2021.7.03整理课程设计的过程、并进行总结,完善程序功能2021.7.04编写课程设计报告初稿2021.7.05完善课程设计报告、并准备答辨2021.7.06提交课程设计报告和程序,进行答辨参考资料1 .严蔚敏吴伟民,数据结构,清华大学出版社,2007.32 .程杰,大话数据结构,清华大学出版社,2021.63 .美StephenPrata,CPrimerPlus中文版第五版,人民邮电出版社,2005.2其它说明

4、1.本表应在每次实施前一周由负责教师填写二份,学院审批后交学院教务办备案,一份由负责教师留用.2.假设填写内容较多可另纸附后.3.一题多名学生共用的,在设计内容、参数、要求等方面应有所区别.系主任：雷亮指导教师：黄永文/王双明/熊茜/彭军/王成敏2021年6月200摘要在交通网络非常兴旺,人们在出差、旅游出行时,往往关心节省交通费用或节省所需要的时间等问题.对于这样一个人们关心的问题,可以用一个图结构来表示交通网络,利用计算机建立一个交通咨询系统.图中顶点表示城市,边表示城市之间的交通情况,其权值可代表里程、交通费用或时间.比方任意一个城市到其他城市的最短路径,任意两个城市之间的最短路径问题.

5、本次设计的交通咨询系统主要是运用C语言的数据结构来完成交通图的存储、图中顶点的单源最短路径和任意一对顶点间的最短路径问题.关键词：数字结构C语言交通咨询最短路径目录1设计内容和要求11.1问题描述1L2需求分析12课程需求分析22. 1算法思路22.2 数据结构体22.3 根本操作32.4 算法应用32.5 程序设计流程图43功能模块详细设计53. 1测试数据53.2程序调试54课程总结与体会195参考文献20216致谢1设计内容和要求1.1 问题描述：设计、实现一个全国大城市间的交通咨询程序,为旅客提供三种最优决策方案：1时间最短2费用最小3里程最少.1.2 需求分析：该程序所做的工作的是模

6、拟全国交通咨询,为旅客提供三种最优决策的交通咨询.此程序规定：1在程序中输入城市名称时,需输入20个字符以内的字符串；输入费用时需输入一个实型数据；输入时间时需输入一个整型数据；在选择功能时,应输入与所选功能对应的一个整型数据.2程序的输出信息主要是：最快需要多少时间才能到达,或最少需要多少旅费才能到达,或两城市间需要走过的最短路程,并详细说明如何坐车才能最省.3程序的功能包括：提供对城市信息的编辑,对两城市间时间、花费、还有路程的编辑,提供三种最优决策：最快到达、最省钱到达、最少路程到达.2课程需求分析2.1 算法思路(1)数据存储.城市信息、交通信息(城市间的里程、旅费和时间)存储于磁盘文

7、件.建议把城市信息、交通信息还有城市和交通信息数目分开存于三个文件中,用fread和fwrite函数操作.(2)数据的逻辑结构.根据设计任务的描述,其城市之间的旅游交通问题是典型的图结构,可看作为有向图,图的顶点是城市,边是城市之间所消耗的时间、旅费、里程.(3)数据的存储结构.采用邻接矩阵作为数据的存储结构,提升空间的存储效率.(4)用不同的功能模块对城市信息和交通信息进行编辑,可用菜单方式或命令提示方式.只要能方便的对城市信息和交通信息进行治理即可.(6)主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行,要求在程序运行过程中可以反复操作.2.2 数据结构体typedefst

8、ructlu/*交通信息数据类型*/intdistance；/*城市间里程*/intcost；/*城市间旅费*/inttime；/*城市间时间*/lu,lujinmaxmax；typedefstructcity/*城市数据类型*/(charname20；/*城市名称*/citysmax；typedefstruct/*网络图的数据类型*/citysclist；/*城市信息*/lujinarcs；/*边的信息*/intc_n,l_n；/*边和顶点数目*/Graph；typedefstruct/*最短路径*/charadjvex；intmincost；/*最少旅费*/intmindistance；/

9、*最短里程*/intminlime；/*最少时间*/closedge；1.2 3根本操作voidzairu(Graph*G);/*导入文件中的信息,能否是程序运行*/voidAdminister(GraphG)；/*治理员操作界面,由主函数调用*/voidshow(GraphG)；/*显示系统中的全部城市信息和交通信息*/intinsertcity(Graph*G)；/*增加城市信息*/intinsertlu(Graph*G)；/*增加交通信息*/intLocated(Graph*G,char*p)；/*返回邻接矩阵的位置下标,系统中的关键*/voidbaocun(GraphG)；/*将城市信

10、息、交通信息保存在文件中*/intserchlu(Graph*G)；/*搜索交通信息*/voidmindistance(Graph*G,intvO,intvl);/*最少里程计算,迪杰斯特拉算法*/voidmincost(Graph*G,intvO,intvl);/*最少旅费计算,迪杰斯特拉算法*/voidmintime(Graph*G,intvO,intvl);/*最少时间计算,迪杰斯特拉算法*/2.4 算法应用在判断源点到其余各点的最短路径时运用迪杰斯特拉算法：一般情况下,假设S为以求得最短路径的终点的集合,那么可证实：下一条最短路径设其终点为X或者是弧v,k,或者是中奖只经过S中的顶点而

11、最后到达顶点x的路径.这可用反证法来证实,假设此路径上有一个顶点不在S中,那么说明存在一条终点不在S而长度比此路径短的路径.但是,这是不可能的.由于我们是根据路径长度递增的次序来产生各最短路径的,故长度比此路径段的所有路径均已产生,它们的终点必定在S中,即假设不成立.因此,在一般情况下,下一条长度次短的最短路径的长度必是r>J=eV-S其中,Di或者是弧小匕上的权值,或者是Dk“*eS和弧以,匕上的权值之和.1假设用带权的邻接矩阵arcs来表示带权有向图,arcsij表示弧V上的权值.假设<vi,vj>存在,那么置arcsij为8在计算机上可用允许的最大值代替.S为已找到从v

12、出发的最短路径的终点的集合,他的初始状态为空集.那么,从v出发到图上其余个顶点终点vi可能达到的最短路径长度的初值为：Z)z=arcLocateVex(Gyv)/vzeV2选择勺,使得Z?z=A7Z«DZIvzeV-S勺就是当前求得的一条从v出发的最短路径的终点.令s=s5/3修改从v出发到集合V-S上任一顶点v,可达的最短路径长度.如果£>/+arcs刀幻<Dk.幻=.刀+口-cs刀幻(4)重复操作(2)、(3)共nT次.由此求得从v到图上其余各点的最短路径是依路径长度递增的序列.2.5 程序设计流程图：重庆广安501300重庆成都1002500广安成都601

13、100北京天津1001250济南天津2002300成都南京50020700浙江郑州300301000九江武汉20010500南京无锡1005200石家庄北京1005300浙江徐州300241500重庆南京500232000成都郑州400302400无锡北京700403500徐州上海20015895上海温州1008300济南重庆15015500天津武汉530282593广安济南300231842上海重庆5342814343.2程序调试1.主界面包括四个选项：选项一：治理员治理界面,选择该项可进行城市交通系统的治理；选项二：用户咨询界面,选择该项可进行最少费用、最少时间、最短里程的决策咨询；选项三

14、：显示城市交通系统,选择该项可显示城市交通系统的所有信息,包括城市、交通路线信息；选项四：退出程序,选择该项将退出程序.图3.1程序主界面在该系统运行的开始会从文件读取交通信息,如果文件不存在会导致程口H图3.2文件不存在该函数代码如下：voidzairu(Graph*G)读取文本中的信息(FILE*fpout,*fpin；intcnum,Inum；charFromc20,Toe20；intt,i,j；for(i=0；i<max；i+)for(j=0；j<max；j+)G->arcsij.distance=G->arcsji.distance=zuida；G->a

15、rcsij.cost=G->arcsji.cost=zuida；G->arcsij.time=G->arcsji,time=zuida；fpout=fopen('rnumber,txt","r")；assert(fpout)；if(fscanf(fpout,"%d%d",&cnum,&lnum)=2)(G->c_n=enum；G->l_n=Inum；fclose(fpout)；读取城市顶点信息fpout=fopen("city,txt","r")；fo

16、r(t=0；t<G->c_n；t+)fscanf(fpout,"%s,G->)；fclose(fpout)；读取边的信息.(起点、终点、距离(千米)、花费(元)、时间(分钟)fpout=fopen(nlu.txt,r,"r")；for(t=0；t<G->l_n；t+)fscanf(fpout,"%s%s",Fromc,Toe)；i=Located(G,Fromc)；j=Located(G,Toe)；fscanf(fpout,r%d%d%d",&G->arcsij.dis

17、tance,&G->arcsij.cost,&G->arcsij.time)；G->arcsji.distance=G->arcsij.distance；G->arcsji.cost=G->arcsij.cost；G->arcsji.time=G->arcsij.time；)fclose(fpout)；elsefpin=fopen("number,txt","w");assert(fpin)；fprintf(fpin,"00")；G->l_n=0；G->c_n

18、=0；fclose(fpin)；)2 .治理员治理界面首先出现登陆界面,采用加密技术,初始密码为admin,菜单项包括5个选项：选项一：增加城市信息；选项二：增加交通路线信息；选项三：保存新增信息,返回上一级菜单,可返回主界面.图3.3治理员界面在该界面中调用了三个重要函数,对城市、交通信息进行编辑和保存.intinsertcity(Graph*G)增加城市(charname20；printf(输入要增加的城市：)；scanf("%s",name)；getchar()；if(G->c_n=0)(strcpy(G->,name)；G->

19、c_n+；)else(for(inti=0；i<G->c_n；i+)if(strcmp(G->,name)=0)returnT；elsestrcpy(G->clistG->c_,name)；G->c_n+；)return1；)图3.4增加城市intinsertlu(Graph*G)增加城市交通信息(charFromc20,Toe20；inti,j；intd,c,t；printf"输入增加路径的出发城市、目的城市、距离公里费元、时间小时：nM；scanf(,r%s%s%d%d%d,Fromc,Toe,&d,&

20、amp;c,&t)；getchar()；i=Located(G,Fromc)；j=Located(G,Toe)；if(i=-1IIj=-1)returnT；elseG->arcsij.distance=G->arcsji.distance=d;G->arcsij.cost=G->arcsji.cost=c；G->arcsij.time=G->arcsji.time=t；G->1n+；return1；,I:otilxifresultDebugresult.exe*市城9发0出20的0径30:鬻择入南加先左曾目的城市、距离公里、花费元、时间小时:派

21、请选择治理工程增加城市.Xi=：派2噂加职游患鱼派3=退回上一级票单图3.5增加交通信息voidbaocun(GraphG)保存新增信息于文件中(FILE*fpin；intijn,k；边和顶点的个数fpin=fopen("number,txt","w")；assert(fpin)；fprintf(fpin,"%d%d,G.c_n,G.l_n)；fclose(fpin)；顶点信息.fpin=fopen(,rcity.txt'r,Hwn)；assert(fpin)；ford=0；i<G.c_n；i+)(fprintf(fpin,*&#

22、39;%s,G.)；m=i%10；if(m=0)fclose(fpin)；边的信息.fpin=fopen("lu.txt","w")；assert(fpin)；for(i=0；i<G.c_n；i+)(for(k=i+1；k<G.c_n；k+)(if(G.arcsik.distance!=zuida)fprintf(fpin,f%s%s%d%d%dn'r,G.,G.,G.arcsik.distance,G.arcsik.cost,G.arcsik.time)；)fclos

23、e(fpin)；)保存文件在该系统中是一个重要的组成局部,用于对城市和交通信息的保存,将其储存在文件之中！3 .用户查询路线进入该界面,提示输入要查询的两个城市,然后系统进入查询方法界面如下列图:图3.6查找方法该系统的查找方法,每一种查找最短路径的算法都是运用迪杰斯特拉算法,该代码如下：voidmindistance(Graph*G,intvO,intvl)最短距离(int*d；intvd,w,i,j,v；intmind,*pred,*finald；finald=(int*)malloc(G->c_n*sizeof(int)；判断顶点是否已求出最短路径d=(int*)malloc(G-

24、>c_n*sizeof(int)；储存起始点至U各点的最短路径pred=(int*)malloc(G->c_n*sizeof(int)；最后用于输出最短路径for(v=0；v<G->c_n；v+)(finaldv=0；dv=G->arcsv0v.cost；if(dv<zuida)predv=v0；elsepredv=-l；)dv0=0;到起始点无路径finaldv0=l；/v0放入到final数组里for(i=l；i<G->c_n;i+)从1开始、由于起始点已经在final里面、剩下n-1个顶点、循环n-1次.(mind=zuida；for(w=

25、0；w<G->c_n；w+)(if(!finaldw)没有放进final里面的终点进行选择最短路径出来.if(dw<mind)(mind=dw；vd=w；)找到最短路径终点G->vexsvfinaldvd=1；放入final中for(w=0；w<G->c_n；w+)(if(!finaldw&&(mind+G->arcsvdw.distance<dw)/更新源点到每个终点w当前的最短路径.假设该终点已在final里面、跳出if语句、dw=mind+G->arcsvdw.distance；predw=vd；)if(predvl!

26、=-1)printf(H%s到%s",G->clistvO.name,G->)；printf("最短路程为(公里):%dttM,dvl)；printf(M%s二G->clistvO.name)；j=predvl；while(j!=vO)(printf(u->%s,r,G->)；j=predj；)printf(H->%sn,G->)；)elseprintf(H%s到%s没有信息.n",G->clistvO.name,G->clistvl.nam

27、e)；)该代码在系统中是核心算法！结构课程没计resultDebugresult.exB图3.7最短路径4.显示所有交通信息,1:35JUC好果程iSi+ro%uKDobLigrEuMqxo"花茯元X00700200530XXXXXXXXXXXXXXXMXXXXXXXXXXXXXXXMMXXXXXXXXXXXXXXXXXXXXXXXXXXM目前交通系统中含有个城市,21条海游路径08n3830154221221223北正景庆庆庆寒天浴K1鱼BI主密州徐州九江武汉距冏公里250300350030025935001R425M030014J42UUU24003001ss5s534SUU-1

28、00图3.8交通信息该函数代码如下：voidshow(GraphG)inti,k；system('rcls")；printf(Hnn目前交通系统中含有%d个城市,%d条旅游路径nnn",G.c_n,G.l_n)；printf("各大城市：n")；for(i=0；i<G.c_n；i+)(printf(n%s'G.)；if(i+l)%10=0)printf("n")；)printf("nn*nn")；printf城市tt城市tt距离公里t花费元t时间小时nw；for(i=0；i<G.c_n；i+)for(k=i+1；k<G.c_n；k+)if(G.arcsik.distance!=zuida)printf(H%stt%stt%dtt%dtt%dn",G.,G.,G.arcsik.distance,G.arcsik.cost,G.arcsik.time)；system("pause")；该短代码中主要是读取三个文件,然后分别将信息输出