武汉市公共交通指引系统应用与开发课程设计.doc

1、武汉工程大学计算机科学与工程学院 综合设计报告目录摘 要IIAbstractIII第一章 课题背景11.1 课题背景11.2课题内容1第二章 设计简介及设计方案论述42.1 设计简介42.2问题分析5第三章 详细设计63.1主要函数流程图6第四章 设计结果及分析84.1 设计结果8总 结9致 谢10参考文献11附录 12摘 要数据结构是计算机科学与技术专业的一门必修的、重要的专业基础课，是计算机程序设计的重要理论技术基础。通过数据结构科的学习，不仅可以使同学们掌握数据结构的基本特性、数据的逻辑结构和数据的存储结构及典型算法和使用方法，而且能够训练学生运用数据结构和算法进行具体应用问题的程序设计

2、。主要内容包括算法计算法分析、面向对象程序设计与C+、线性表、栈和队列、串、数组和广义表、树、图、查找、排序、递归和文件等内容。作为计算机专业的学生，应该努力学好各种计算机语言，培养编程创新的能力。运用数据结构的知识编写一个武汉的公交系统武汉市公共交通指引系统是一个可以方便广大市民乘车的一个系统，有着较大的现实意义。本综合设计的任务是：设计并开发一个简化版的武汉市公共交通指引系统，使学生掌握Dijkstra算法培养学生利用C+语言编写程序以及调试程序的能力，运用数据结构知识解决实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。在此次课程设计中，我设计的内容是图的相关操作，采用图的邻接矩

3、阵存储，即用一维数组存储图中顶点的信息，用二维数组存储图中边的信息（即各顶点之间的邻接关系）。 邻接表存储结构是基于顺序存储与链接存储相结合的存储方法，基本思想是：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有顶点的边表的头指针和存储顶点信息的一维数组构成了顶点表。关键词：数据结构；Dijkstra算法；程序设计 AbstractData structure in computerscience and technology professionala compulsory,an importantprofessional bas

4、ic course,is an important theoreticaland technical foundation of computer program design.Through the datastructureoflearning,can not onlymake studentsgrasp the basiccharacteristics ofthe data structure,thelogic structure anddatastorage structure ofdataand the typicalalgorithm andmethod of use,but al

5、so cantrain students to usethe data structure and algorithm ofprogram designfor applicationproblems.The main contents includeanalysis,object oriented programming and C+,linear list,stack and queue, strings, arrays andgeneralized list,tree,graph,searching,sorting,recursive andfile contentcalculationa

6、lgorithm.As a computerprofessional students, should try to learn all kinds of computerprogramminglanguage,cultivating the ability ofinnovation.Using the datastructureknowledge of the preparation oftransit system inWuhanCity public trafficguidance systemaWuhanisa convenientpublicbusof a system,is of

7、great significance.Thecomprehensivedesign task is to:WuhanCity public trafficguidance systemto design and develop asimplified version of the Dijkstra algorithm,to enable students to masterthe cultivation of students ability touse the language of C+ to programanddebug the program,the ability to use t

8、hedata structure ofknowledge to solve practical problems,to lay a solidfoundation for subsequentcomputerprofessional courses.In thiscourse design,Idesignthe content isrelated to the operationof the graph, using thegraph adjacency matrix storage,namely usingvertexone-dimensional arraystoragein the gr

9、aphinformation,a two-dimensional array ofstorage mapedge information(i.e.each vertexadjacencyrelationshipbetween).Adjacency list storage structureis thestorage method ofsequential storageandstoragebased on the combination oflink,the basic idea is:for eachvertex VIof graph, alladjacent tothe vertices

10、 of VIchaininto a single linked list,called thevertex VIedge table(fordirected graphis calledaside table,a one-dimensional array)all thevertices of theedge tableheadpointer and memoryvertexinformation forms avertex table.Keywords：Data structure；Dijkstra algorithm；Program design- 15 -第一章 课题背景1.1 课题背景

11、在科技日新月异的今天，电脑成为人的生活中不可缺少的一部分。作为计算机专业的学生，应该充分利用所学知识，把实际问题转移到电脑上去，通过电脑的编程，使复杂问题简单化，深奥问题浅显化，抽象问题具体化。在非数值计算中，处理对象已从简单数值发展到具有一定结构的数据，这就需要讨论如何有效的组织计算机的存储，并在此基础上有效的实现对象的运算，数据结构就是研究与解决这些问题的重要基础。在结构上呈积木式，注重实践应用、各种常用数据结构的介绍从实际出发，避免抽象的理论论述和复杂的公式推导，在典型的算法介绍中深入浅出、简洁明了。结合上机能够提高编程能力和程序调试能力。通常用图来表示一些问题或概念，如集成电路设计、城

12、市交通道路规划、作业调度等。图和树一样，是一种非线性数据结构。研究两顶点之间是否相连的关系，在图中，结点之间的关系是任意的，任意两个元素之间都有可能相关。图结构提供了简单的方式来描述一个问题、系统或状况。数据结构是计算机科学与技术专业的一门必修的、重要的专业基础课，是计算机程序设计的重要理论技术基础。通过数据结构科的学习，不仅可以使同学们掌握数据结构的基本特性、数据的逻辑结构和数据的存储结构及典型算法和使用方法，而且能够训练学生运用数据结构和算法进行具体应用问题的程序设计。主要内容包括算法计算法分析、面向对象程序设计与C+、线性表、栈和队列、串、数组和广义表、树、图、查找、排序、递归和文件等内

13、容。作为计算机专业的学生，应该努力学好各种计算机语言，培养编程创新的能力。1.2课题内容武汉市公共交通指引系统是一个可以方便广大市民乘车的一个系统，有着较大的现实意义。本综合设计的任务是：设计并开发一个简化版的武汉市公共交通指引系统，使学生掌握Dijkstra算法培养学生利用C+语言编写程序以及调试程序的能力，运用数据结构知识解决实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。一、目的：对应数据结构课程所学的基本原理和方法，学习图状结构求最短路径的算法，将理论知识运用于实际。二、任务：请根据图1.3和表1.2，设计一个武汉市交通导引系统。用户输入起点站和目标站，系统显示起点站到目标站

14、的最短路径。表1-2 车站表图1.3 路线图三、要求：提示用户输入起点站和目标站系统向用户显示一条最短路径（经过站数最少的路线），如果有两条以上最短路线，则按换乘次数排序显示。显示每一条路线时，不仅要显示应搭乘的车次，还要显示应搭乘站的站名。第二章 设计简介及设计方案论述2.1 设计简介先分析整个系统的构成，然后可以很清晰的看到要想构造和完成这一个系统，必须要先把公交线路的图输入成一个数据结构，构造完公交线路的图之后，再来完成最短线路的查找，然后我们就用Dijkstra算法去查找最短线路，这样子就可以得到了从一个顶点到其他顶点的距离和线路，在基于Dijkstra算法之上，从那么多个顶点中筛选所

15、需要的终点站，便可以得到从起点站到终点站的一条最短路劲和长度，与公交线路匹配得出公交线路。Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。算法本身并不是按照我们的思维习惯求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列，但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图

16、中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。Dijkstra算法是用来求任意两个顶点之间的最短路径。在该实验中，我们用邻接矩阵来存储图。在该程序中设置一个二维数组来存储任意两个顶点之间的边的权值。用户可以将任意一个图的信息通过键盘输入，让后在输入要查找的两个顶点，程序可以自动求出这两个顶点之间的最短路径。2.2问题分析（1）地图录入：建立有向图的数据结构录入到系统中去。（2）寻找最短路劲：通过Dijkstra算法寻找一个站点到另一个站点的最短路劲。（3）寻找公交线路：把得到的最短路劲与公交线路对比得到其适合的线路。（4）输出：把所得到的结果输出到屏幕上第三章

17、 详细设计3.1主要函数流程图（1）主函数如流程图3.1开始输入起点站，终点站构造最短路劲匹配公交路线结束图3.1 流程图（2）Dijkstra算法流程如流程图3.2：图3.2 流程图第四章 设计结果及分析4.1 设计结果（1）输出结果如结果图4.1图4.1 结果图总 结课程设计是对我们综合能力的考察。通过这个程序，我们可以更加深刻的了解图，更深层次的了解了数据结构。不仅仅对于书本知识的熟悉，更是数据结构的实践性进展。理论结合实践，既能使学生学习高级编程语言的知识、编程技术和基本算法，又能掌握程序设计的思想和方法，更具备利用计算机求解实际问题的能力，能灵活运用高级语言进行程序设计。课程设计前，

18、要查阅资料了解相关要求和步骤，做好准备工作，定好设计思想。 在做课程设计过程中要注意积累经验,把出现的错误写到一处,然后对每一条进行总结，为以后数据结构的深入学习打下基础。致 谢在浩瀚宇宙中，每个人都是渺小的。在计算机这个更新速度比光速还快的世界中，个人的力量实在太渺小了。这是我第一次接触计算机语言，书上的内容很精致，但是要利用书上所学的知识来让我们编写一个实际的程序实在是非常困难。在调试过程中屡调屡败的状态下，我急得想哭，就在这时，老师给了我热情的帮助，老师指导我调试程序，说哪些是错的，哪些是多余的，哪些是必要的，一个杂乱无章的程序被修改得有条不紊，很显然结果也是最最正确的。在此，我真诚的感

19、谢帮助我的老师们，老师就是黑暗中的指明灯，没有老师的指导，就没有我们顺利的完成任务的喜悦。老师每天都来机房为我们指导，及时解决我们所面临的问题，老师的工作态度让我们佩服，老师的一流技术让我们信服，老师的无私奉献让我们折服。当然，同学们的帮助也是我前进的力量，也让我体会到真诚的友谊。团结就是力量，在老师、同学的帮助下，我顺利完成了此次的课程设计。也让我体会到了成功的来之不易，只有真正付出过才有满意的收获。在此，我诚心的对所有帮助过我的老师学长同学们说一句：谢谢！ 参考文献1谭浩强.C程序设计（第三版）. 北京: 清华大学出版社,2005.2谭浩强.C程序设计题解与上机指导.北京：清华大学出版社,

20、2005.3谭浩强.C程序设计教程.北京：清华大学出版社,2007.4谭浩强.C+程序设计.北京：清华大学出版社，2004.5李春葆.数据结构教程（第4版）M.北京：清华大学出版社，2014.6李春葆.数据结构教程与上机实验指导（第4版）M.北京：清华大学出版社，2014.附录主要代码：#include#include#include#include#define MAXV 100#define INF 32767int distMAXV,pathMAXV,B10,k1=0;typedef structint no;int info;VertexType;typedef structint e

21、dgesMAXVMAXV;int n,e;VertexType vexsMAXV;MGraph;void Ppath(int path , int i , int v )int k;k= pathi;if(k=v) return;Ppath(path , k , v);printf(%d,k+1);void Ppath1(int path , int i , int v ,char* A130,int B10)int k;k= pathi;if(k=v) return;Ppath1(path , k , v,A1,B);printf(%s,A1k);Bk1=k+1;k1+;void Dispa

22、th(int dist , int path , int s, int n,int v)int i;for(i=0;in;i+)if(si=1)printf(从%d到%d的最短路径长度为：%dt,v+1,i+1,disti);printf(%d,v+1);Ppath(path,i,v);printf(%dn,i+1);void Dijkstra(MGraph g,int v)int sMAXV;int mindis,i,j,u;for(i=0;ig.n;i+)disti=g.edgesvi;si=0;if(g.edgesviINF)pathi=v;elsepathi=-1;sv=1;pathv

23、=0;for(i=0;ig.n;i+)mindis = INF;u=-1;for(j=0;jg.n;j+)if(sj=0&distjmindis)u=j;mindis=distj;su=1;for(j=0;jg.n;j+)if(sj=0)if(g.edgesujINF & distu+g.edgesujdistj)distj=distu+g.edgesuj;pathj=u;Dispath(dist,path,s,g.n,v);int change(char* Q1,char* A130)for(int i=0;i30;i+)if(strcmp(Q1,A1i)=0)break;return i;

24、void change2(int i, char* A130)printf(%st,A1i);int main()int A3030 = 0,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,0,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF

25、,1,INF,0,1,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,1,0,INF,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,0,1,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF

26、,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,0,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,1,INF,0,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,0,1,1,INF

27、,INF,INF,INF,INF,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,0,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,0,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,I

28、NF,INF, /10INF,INF,1,INF,INF,INF,INF,INF,INF,INF,0,1,INF,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF, INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,0,1,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,0,1,INF,INF,INF,IN

29、F,INF,INF,INF,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,1,0,1,INF,INF,INF,INF,1,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,INF,1,0,1,INF,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,IN

30、F,INF,INF,INF,INF,INF,1,0,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,0,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,1,0,1,INF,INF,INF,INF,INF,1,INF,INF,INF,INF,

31、INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,INF,1,0,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,INF,INF,INF,1,0,1,INF,INF,INF,INF,1,INF,INF,INF,INF, /10INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,INF,INF,INF,

32、INF,1,0,1,INF,INF,INF,INF,1,INF,INF,INF, INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,0,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,1,0,1,INF,INF,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF

33、,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,0,INF,INF,INF,INF,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,0,INF,INF,INF,INF,INF, /25INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,INF,INF,INF,1,0,1,I

34、NF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,INF,INF,INF,1,0,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,INF,INF,1,0,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF

35、,INF,INF,INF,INF,INF,INF,INF,1,1,INF,INF,0,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,INF,INF,1,INF,0;char* A130=机场,汉口站,黄浦路,航空路,江汉路,武汉港,武胜路,琴台,动物园,归元寺, /10岳家咀,东湖,磨山,武大,洪山广场,汉阳门,黄鹤楼,大东门,19,街道口,卓刀泉,体院,鲁巷,华中科大,武昌站,武汉理工大,化四院,武汉化院,华中农大,关山;int A21

36、320=2,4,7,8,17,18,25,2,4,7,5,6,2,4,7,8,17,18,19,20,21,22,23,24,30,1,3,4,4,7,8,17,18,19,15,11,3,4,9,8,7,5,3,10,8,17,18,16,15,14,12,4,3,11,12,13,25,26,27,28,30,29,26,20,14,29,25,18,17,8,30,24,23,13,12,6,5,3,11,15,19,20,21,27,28,30;int i,j,u=0,i1;MGraph g;g.n=30;g.e=30;char* Q1;char* Q2;Q1 =(char*)malloc(50*sizeof(char);Q2 =(char*)malloc(50*sizeof(char);for(i=0;ig.n;i+)for(j=0;jg.n;j+)g.edgesij=Aij;printf(请输入起始站地址：n);scanf(%s,Q1);printf(n请输入终点站地址：n);scanf(%s,Q2);i=change(Q1,A1);j=change(Q2,A1);Dijkstra(g,i);printf(n经过的站点为：%s,Q1);Ppath1(path,j,i,A1,B);printf(%sn,Q2);return 0;