公交路线查询课程设计

《算法与数据结构》课程设计报告题目：公交线路专业：软件工程班级：1003学号：41姓名：简指导教师：魏完成日期：2012年06月17日一、课程设计目的本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、课程设计内容建立某城市（如福州）主要公交线路图查询站点路线三、课程设计过程[基本要求]输入任意两站点，给出最佳的乘车线路和转车地点。如：该城市共有n条公交线路，m个公交站点。其中，公交线路1经过编号为1，2，4，7的站点，公交线路2经过编号为3，5，7，8，的站点，则从站点2到站点8的最佳乘车线路是：乘坐公交线路1从站点2到站点7再乘坐公交线路2到站点8。[测试数据]该城市共有3条公交线路，6个公交站点，其中：第1条公交线路经过站点：1，2第2条公交线路经过站点：2，3，4第3条公交线路经过站点：4，5用图的最短路径算法实现（转乘次数最少）2．概要设计1）为了实现上述程序功能，需要定义图数据类型：typedefstruct//图的定义{charname[MAX_VERTEX_NUM];intvexs[MAX_VERTEX_NUM];intvexnum,arcnum;//顶点信息弧的信息intln,l,n;//ln是路线数，l是路线,n是站点数,d是站点,nu路径数intvexno[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//顶点:路线，路线中的站点数intarclin[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//弧:站点-站点，，存的是权值}mgraph;基本操作：voidcreate(mgraph&g)输入路线，站点信息，站点间关系操作结果：创建公交线路图，voidfloyd(mgraphg,intv,intw)计算最少换乘路径。并输出，且相应查找各所需换乘车信息，并计算换乘次数操作结果：显示所查询站的路线，换乘车次，及换乘最少路径Menu()操作结果：在屏幕上显示操作菜单voidvisit(mgraphg,intv,intw)查找站点信息并输出操作结果：输出所查询站点信息intmain()有个switch，可以对Menu里的功能进行选择操作，操作结果：各个其他函数进行实现2）本程序包含5个函数：①主函数main()②建设公交图函数voidcreate(mgraph&g)③显示操作菜单函数menu()④计算最小路径算法函数voidfloyd(mgraphg,intv,intw)⑤查找显示站点信息的函数voidvisit(mgraphg,intv,intw)各函数间关系如下：meanMaincraetefloydvisit3．详细设计实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。1)图的定义typedefstruct{charname[MAX_VERTEX_NUM];intvexs[MAX_VERTEX_NUM];intvexnum,arcnum;intln,l,n;intvexno[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intarclin[MAX_VERTEX_NUM][MAX_VERTEX_NUM];}mgraph;2)公交路线建设到查询的基本操作建图：：voidcreate(mgraph&g){inti,j,k,e,d;printf(请输入公交站数和路径数：);scanf(%d,%d,,&g.vexnum,&g.arcnum);printf(请输入公交站点和其站名：);for(d=1;d=g.vexnum;d++)scanf(%d,%c,&g.vexs[d],&g.name[d]);for(i=1;i=g.vexnum;i++)for(j=1;j=g.vexnum;j++)g.arclin[i][j]=infi;printf(请输入可达两站点的编号：\n);for(k=1;k=g.arcnum;k++){scanf(%d,%d,&i,&j);g.arclin[i][j]=1;g.arclin[j][i]=1;}printf(请输入公交路线数：);scanf(%d,&g.ln);for(k=1;k=g.ln;k++){printf(请输入路线和所含站点数：);scanf(%d,%d,&g.l,&g.n);printf(请输入此路线的所含站点：);for(e=1;e=g.n;e++){scanf(%d,&j);if(jinfi)g.vexno[g.l][j]=g.l;}}}Floyd算法：求最少换乘路径：voidfloyd(mgraphg,intv,intw)//floyd算法算出各点间的最小路径{Intpath[MAX_VERTEX_NUM][MAX_VERTEX_NUM],a[MAX_VERTEX_NUM],b[MAX_VERTEX_NUM];inti,j,k,/*u,temp,*/top=0,top1=0;for(i=1;i=g.vexnum;i++)for(j=1;j=g.vexnum;j++){if(i==j)path[i][j]=0;elseif(g.arclin[i][j]infi)path[i][j]=i;elsepath[i][j]=0;}for(k=1;k=g.vexnum;k++)for(i=1;i=g.vexnum;i++)for(j=1;j=g.vexnum;j++)if(g.arclin[i][k]+g.arclin[k][j]g.arclin[i][j]){g.arclin[i][j]=g.arclin[i][k]+g.arclin[k][j];path[i][j]=path[k][j];}//计算结束，开始判断输出所要了解的信息if(path[v][w]==v){printf(%d--%d\n,v,w);for(i=1;i=MAX_VERTEX_NUM;i++){if(i==g.vexno[i][v]&&i==g.vexno[i][w])printf(您只需要乘坐く%d路つ车，此两站能有直达车!\n\n,g.vexno[i][v]);}}Elseif(path[v][w]){intf=0;printf(%d,v);a[++top]=w;b[++top1]=w;while(path[v][w]!=v){k=path[v][w];a[++top]=k;b[++top1]=k;w=k;}while(top){++f;intu=a[top--];printf(--);printf(%d,u);}for(i=1;i=MAX_VERTEX_NUM;i++)if(i==g.vexno[i][v]&&i==g.vexno[i][b[top1]])//用判断两站点所在的路线是否同一条，若同一条，则输出这条路线printf(\n这两站没有直达车,您需要乘坐公交路线为：く%d路,g.vexno[i][v]);while(top1-1){intt=b[top1];for(i=1;i=MAX_VERTEX_NUM;i++){if(i==g.vexno[i][t+1]&&g.vexno[i][t])printf(-%d路つ,i);}--top1;}printf(\n);printf(您需要转乘次数为：%d次!\n\n,f);printf(\n);}elseprintf(此俩站点不存在通车路径!!请做其它操作，谢谢!\n\n);}voidvisit(mgraphg,intv,intw)//对于站点的信息的输出{for(inti=1;i=g.vexnum;i++)for(intj=1;j=g.vexnum;j++){if(i==v&&j==w){printf(此两站点信息为：);printf(%c,%c\n,g.name[i],g.name[j]);}}printf(最少换乘路径为：);}功能选择菜单：：voidmenu(){printf(#################ぃぃぃ1:建设公交线路图!ぃぃぃ#################\n);printf(#################ぃぃぃ2:查询您所需要了解的线路!ぃぃぃ#################\n);printf(#################ぃぃぃ3:退出!ぃぃぃ#################\n);}4．调试分析在调试的过程中会出现括号的缺失，或者是功能的不可行，最大难题就是路线方面，经过调试，检查语句合法与否，实现功能的程序是否符合逻辑，一步步完善直到实现要求的所有功能。5．用户使用说明程序名为bus.exe，运行环境为DOS。程序执行后显示在输入序号后输入数字选择执行不同的功能。要求首先先建设公交线路图，在建完图之后会用矩阵输出你所以建设的信息。每执行一次功能，就会显示执行的结果，有包含所以需要查询的站点信息，最少换乘路线，及所以需要搭乘的车路。选择1：显示“首先请先建设公交线路图:”，要求输入站点个数，通车路径数，站点信息，各站点间的关系，公车线路数，每条公车线路所以含站点。选择2：显示“请输入待查任意两个站点v和w:”，要求输入等查询的两个两个站点编号，执行并输出有关站点，路径，换乘信息选择3：显示“是否继续？Y（请输入1），N（请输入0）\n”，要求输入1或0，1可以继续，0可以退出并结束运行6．测试结果程序名为Bus.exe，运行环境为DOS。程序执行后显示在输入序号后输入数字选择执行不同的功能。要求首先先建设公交线路图，在建完图之后会用矩阵输出你所以建设的信息。每执行一次功能，就会显示执行的结果，有包含所以需要查询的站点信息，最少换乘路线，及所以需要搭乘的车路。选择1：建图选择2：查询有直达车：没有通车有路线且需要转车。要求输入两个站点编号，经过FLOYD计算后，输出两站点信息，并输出最少换乘路线及换乘的公交。选择3：退出程序7．附录#includestdio.h#includestring#defineMAX_VERTEX_NUM100intvisited[MAX_VERTEX_NUM];//访问标志数组#defineinfi9999//typedefstruct//{//int//charname[30];//};typedefstruct//图的定义{charname[MAX_VERTEX_NUM];intvexs[MAX_VERTEX_NUM];intvexnum,arcnum;//顶点信息弧的信息intln,l,n;//ln是路线数，l是路线,n是站点数,d是站点,nu路径数intvexno[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//顶点:路线，路线中的站点数intarclin[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//弧:站点-站点，，存的是权值}mgraph;voidcreate(mgraph&g)//输出邻接矩阵g{inti,j,k,e,d;//k为循环变量,e为内循环的变量,i,j为路线，站点变量printf(请输入公交站数和路径数：);scanf(%d,%d,,&g.vexnum,&g.arcnum);printf(请输入公交站点和其站名：);for(d=1;d=g.vexnum;d++)scanf(%d,%c,&g.vexs[d],&g.name[d]);/*printf(g:%c,