《数据结构课程设计交通旅游图的最短路径问题.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计交通旅游图的最短路径问题.doc（25页珍藏版）》请在三一办公上搜索。
1、CENTRAL SOUTH UNIVERSITY数据结构课程设计报告题 目交通旅游图的最短路径问题学生姓名*指导教师*学 院*专业班级*完成时间*摘 要数据结构主要是一门研究非数值计算的程序设计问题中的计算机操作对象以及它们之间的关系和操作等的学科。数据结构在计算机科学与技术中是一门综合性的专业基础课，其研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着更密切的关系。不论是编译程序过程还是操作系统都涉及到数据元素在存储器中的分配问题。在计算机科学与技术中，数据结构不仅是一般程序性的基础，而且也是其他系统程序和大型程序的重要基础。在交通网络非常发达，交通工具和交通方式不断更新的今天，
2、人们在出差、旅游或做其它出行时，不仅关心节省费用，而且对里程和所需时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示站点之间的交通关系。这个交通系统可以回答旅客提出的各种问题。比如任意一个站点到其他站点的最短路径，任意两个站点之间的最短路径问题。本次设计的交通咨询系统主要是运用C语言来完成交通图的存储、图中顶点的最短路径和任意一对顶点间的最短路径问题。关键字：数据结构 课程设计 交通咨询系统目 录前言1第一章 设计要求21.1设计内容21.2设计目的31.3设计分析4第二章系统功能模块的设计52.1 系统功能分析与设计
3、5 2.1.1系统简介.52.1.2 系统流程图.52.2 各功能模块简介62.2.1结构体的建立62.2.2 图的建立与初始化62.2.3 邻接矩阵的输出8 2.2.4 显示函数.8 2.2.5 最短路径算法.9 2.2.6主函数.10第三章 实践结果与调试.123.1运行结果.123.1.1主界面.12 3.1.2查询站点编号模块.12 3.1.3邻接矩阵查询模块.12 3.1.4最短路径查询模块.133.2运行调试及发现问题.15 3.2.1调试过程.15 3.2.2发现问题.15第四章设计总结与心得.16附录：程序源代码.18前 言乘汽车旅行的人总希望找出到目的地的尽可能短的行程。如果
4、有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？计算机网络中的路由就是通过互联的网络把信息从源地址传输到目的地址的活动。为了高效引导数据的传输，如何找出源和目的地址之间的最优路径？这些问题中的网络（交通网，计算机通信网）可以使用一个带权图来建模，寻找最优路的需求可转换为带权图的最短路径问题。最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和边组成的）中两结点之间的最短路径。问题具体的形式包括：确定起点的最短路径问题，即已知起始结点，求最短路径的问题。适合使用Dijkstra算法。确定终点的最短路径问题，与确定起点的问题相反，该问题是已知终结结点，求最短路径的
5、问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题，即已知起点和终点，求两结点之间的最短路径。全局最短路径问题，求图中所有的最短路径。适合使用Floyd-Warshall算法。第一章 设计要求1.1 设计内容一问题描述：已知某市每条公共路线及沿途所经站名，试设计一个问路程序，用户可以在任一车站通过终端询问知道：是否有公共汽车到达指定的目的地? 若有，告诉乘车路线。如需中途换车，应指示再那里换车 二基本要求：（1）自己提出一个公共汽车路线图，可以在网上搜索现实城市公交路线图（如长沙市的），至少要有7条公交线路，每条
6、线路至少要有7个公共汽车站。（2）数据结构：将公共汽车路线图看成是一个有向图，选择合适的数据结构，除了反映顶点(站)之间的邻接关系外，还应反映途经的路线号。注意，两站之间可能存在往返两个方向，每个方向又可能对应多个路线号。 （3）算法：按选定的数据结构设计相应的算法。注意，当从乘车站到目的站存在多种乘车路线时，必须确定路线选取标准。例如，要求换车次数最少等。 数据结构可以采用链接结构：structNODEchar* stname;struct NODE* link;struct NODE hdtpMAX+1；数据结构也可以采用顺序结构：struct NODEint go,back;struct
7、 NODE amax+1,max+1;其中，aI，j.go0 表示第i条线路上，向站j 去方向的下一站号；ai，j.back0表示第i条线路上，站j回来的下一站号。若站j不在第i条线路上，ai，j.go 和ai，j.back 均为0。（4）另外，还需建立两个数组；一个是线路序号和线路号“值”的对照表；另一个是站号和站名对照表。（5）对所采用的算法进行算法分析 三. 实现提示假定顶点编号为1.n，数据结构采用连接结构。设置表头数组为head1.n，headi包含站i的名字和一指针，该指针指向i的所有邻接顶点组成的单链表。单链表中的每个结点包含3个域：一个站号域，两个指针域。一个指针指向i的下一个
8、邻接顶点，另一个指针指向从i到该结点的所有线路号组成的链表。 struct LINENODEint lineno;struct LINENODE* next;struct STNODEint stno;struct LINENODE* Link1,*Link2;如果按途经站数最少的原则来确定乘车路线，实际上是最短路径问题，则可以采用Djkstra算法或图的宽度优先搜索算法。在保证站数最少的前提下，如果存在多种乘车路线，则可以进一步挑选换车次数最少的路线。1.2 设计目的一.设计思想：用邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单源最短路径问题，然后运用费洛伊德算法实现图中任意一
9、对顶点间最短路径问题，这样就会实现旅客所要咨询的问题。 二.设计要求：该交通咨询系统要完成城市网络图的存储，并要实现求任意一个顶点到其他顶点的最短路径问题，还要实现任意两个车站顶点间的最短路径问题。故设计要分成三部分，一是建立交通网络图的存储结构；二是解决路径问题；最后再实现两个车站之间的最短路径问题。三.设计目的：通过课程设计我们不仅可以巩固已学到的书本知识，还可以从亲自动手设计这项课程设计的过程中发现问题，并学会用自己所学的知识解决问题。这不仅使我们能学会很多书本中学不到的知识、经验，还能提高我们自己的动手能力，同时开发自身的创新思想，拓展思维。1.3 设计分析一通过对题目的分析知，是要让
10、我们能够通过利用所学的数据结构的基本知识和技能来解决程序设计问，因此在搞程序设计之前先好好的把书复习一遍，弄清楚各个知识之间的联系。二根据这些功能和基本要求，可充分运用我们所学的数据结构的基本知识和技能去逐步的解决。其中将函数进行模块化。在数据结构中，通过队列，栈，图的声明来实现系统的各种功能的存储各站点之间乘车的时间，距离，以及最少的中转站。利用结点来实现站点之间各种操作，而这些知识点都是我们学习数据结构必须掌握和学会运用的。三完成程序功能的设置后，应对程序进行调试，以便在调试中能及时地找出错误并加以更正，这样能使程序功能进一步的完善和正确。这就要求我们在编程和调试过程中养成认真分析和善于发
11、现问题并及时解决的习惯，不懂的及时问老师或者其他同学。第二章 系统功能模块的设计2.1 系统功能分析及设计2.1.1系统简介该课题可以分为如下几个模块：控制选择功能项的main函数、定义各类抽象结构体的模块typedef struct、有向图的建立与初始化函数MGraph InitGraph(void)、邻接矩阵的输出函数void DispMat(MGraph g)、显示输出函数void out()、求最小路径的函数void Floyd(MGraph g)、以及中转站的输出函数void ppath(int pathMAXV,int i,int j)。2.1.2 系统流程图 2.2各功能模块简介
12、2.2.1结构体的建立本次设计中需要运用有向图来显示交通网络图，顾建立抽象数据结构体便是很重要的一项工序。首先要先建立顶点的结构体，边的结构体以及图的结构体。这些均是为了以后的数据存储和算法的实现做的基本定义。此模块如下：typedef int InfoType; /假设InfoType为int类型typedef struct int no;/顶点编号InfoType info;/顶点其他信息，这里用于存放边的权值 char name30; /顶点名称 VertexType;/顶点类型typedef struct int lengh; /边的权值，表示路径长度 int ivex,jvex; /
13、边得两端顶点号EdgeType; /边的类型typedef struct /图的定义 int edgesMAXVMAXV; /邻接矩阵 int n,e; /顶点数，弧数VertexType vexsMAXV;/存放顶点信息 MGraph;/图的邻接矩阵类型2.2.2图的建立与初始化图是这个题目课程设计的核心。所以对图的建立是必要的，并且对图的初始化赋值也同样重要。在创建图是，同时进行对顶点的编号，名称的填写以及邻接矩阵的输入。这样才能构成完整的有向图，才能建立确切的交通网络图，以便实现交通的查询。此函数为：MGraph G;MGraph InitGraph(void) MGraph G; in
14、t i,j; G.n=14; G.e=24; Int A1414=32767,32767,32767,32767,32767,32767,32767,8,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,8,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,3
15、2767,32767,32767,5,32767,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,9,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,8,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,6,32767,32767,327
16、67,32767,32767,32767,32767,32767,32767,32767,32767,32767,8,32767,32767,5,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,8,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,7,6,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,327
17、67,32767,32767,6,32767,32767,32767,32767,32767,32767,1,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,32767,32767,1,32767,32767,32767,32767,32767,32767,9,8,32767,32767,32767,32767,32767,32767,32767,32767; for (i=0;i14;i+) for (j=0;j14;j+) G.edgesij=Aij; for(i=0;iG.n;i+) G.vexsi.no=i; strcpy
18、(G.vexs0.name,湖南林业科技大学);strcpy(G.vexs1.name,潇湘晨报);strcpy(G.vexs2.name,市中心医院);strcpy(G.vexs3.name,铁道学院);strcpy(G.vexs4.name,新开铺路口); strcpy(G.vexs5.name,南郊公园); strcpy(G.vexs6.name,后湖路口); strcpy(G.vexs7.name,猴子石大桥); strcpy(G.vexs8.name,桃源村); strcpy(G.vexs9.name,沙泥塘); strcpy(G.vexs10.name,王家湾); strcpy(G
19、.vexs11.name,中南大学校本部); strcpy(G.vexs12.name,八字墙); strcpy(G.vexs13.name,左家垅); /站点和路径数据源初始化2.2.3邻接矩阵的输出邻接矩阵是用来存储边权信息的。通过邻接矩阵可直接读出两顶点间是否有直通路线，同时还可以找到是否转战，但不如图形直观。但邻接矩阵是用来存储有向图通路信息的最普遍方法之一，顾我们这次同样选择用邻接矩阵来储存。在我们的系统中设置了专门显示邻接矩阵情况的函数模块，一边直观的观察到邻接矩阵输入状况以及通路状况。所以函数为：void DispMat(MGraph g) /输出邻接矩阵gint i,j;for
20、 (i=0;i14;i+) for (j=0;j14;j+)if (g.edgesij=INF)printf(%3s,);elseprintf(%3d,g.edgesij);printf(n); printf(nn); 2.2.4 显示函数显示函数是本系统中的第二项重要功能。可以显示出站点名及编号，以便用户查询方便。此功能函数为：void out() printf(n站名编号为：n 0.湖南林业科技大学 1.潇湘晨报n 2.市中心医院 3.铁道学院n 4.新开铺路口 5.南郊公园n 6.后湖路口 7.猴子石大桥n 8.桃源村 9.沙泥塘n 10.王家湾 11.中南大学校本部n 12.八字墙 1
21、3.左家垅nnn);另外，我们为实现可以显示中转站的功能，又另设立一函数为求出起点与终点的路径中所经的站点编号，这样方便旅者转车。此部分函数为：void ppath(int pathMAXV,int i,int j) /输出各条最短路经 int k;k=pathij;if (k=-1) return;ppath(path,i,k);printf(%3d,k);ppath(path,k,j); 2.2.5 最短路径算法本设计中用多源有向图来显示交通网络的交通图，顾采用弗洛里德算法来求两顶点之间的最短路径问题。此功能为人工输入要查询的起点及终点，系统将自动输出两点之间的最短路径，以及期间所经过的站
22、点编号。此功能为交通咨询系统的最核心函数。其代码如下：void Floyd(MGraph g)/弗洛伊德算法从每对顶点之间的最短路径int AMAXVMAXV,pathMAXVMAXV;int i,j,k,r,f,n=14; for (i=0;in;i+)/给A数组置初值for (j=0;jn;j+)Aij=g.edgesij;pathij=-1;for (k=0;kn;k+)/计算Akfor (i=0;in;i+) for (j=0;j(Aik+Akj)Aij=Aik+Akj; pathij=k; printf(请输入需要查找的两个站点(站点编号为0-13):n); out(); print
23、f(起点:);scanf(%3d,&f); while(f=n) printf(该站不存在，请重新输入！n); printf(起点:);scanf(%3d,&f); ; printf(终点:);scanf(%3d,&r); while(r=n) printf(该站不存在，请重新输入！n); printf(终点:);scanf(%3d,&r); ; while(r=f) printf(不能等于起点，请重新输入！n); printf(终点:);scanf(%3d,&r);printf(n输出最短路径:n);if (Afr=INF) if(f!=r)printf(从%3d到%3d没有路径nnn,f,
24、r);else printf(从%3d到%3d路径为:,f,r); printf(%3d,f); ppath(path,f,r); printf(%3d,r); printf(n路径长度为:%3d km nnn,Afr);2.2.6主函数主函数在此系统中主要实现主界面的设置，菜单功能的实现。同时使其他模块函数的功能连接起来，共同组成一个完整的咨询系统。顾主函数如下：void main() int i,j,n,k=1; MGraph InitGraph(void);while(k=1) printf( *欢迎进入公交查询系统* n); printf( 制作人：韦千慧 周韵n); printf(
25、请输入选择：n); printf( 1.查询站点n); printf( 2.查看邻接矩阵n); printf( 3.查找路径n); printf( 4.退出n); printf( * n); scanf(%d,&n); switch(n) case 1:system(cls);out();break; case 2: system(cls); printf(交通网路的邻接矩阵为n); DispMat(G); break;case 3: system(cls); Floyd(G);break;case 4:k=2;break; default:printf(输入错误！请重新输入！); 第三章 实
26、践结果与调试3.1运行结果 3.1.1主界面主界面运行结果如下图：输入选项编号后即可进入功能输出！3.1.2查询站点编号模块查询站点编号模块运行如下图：此模块为输出顶点即站点的编号与名称所对应的列表。3.1.3邻接矩阵查询模块邻接矩阵查询模块运行如下图：此为邻接矩阵的数值输入状况。3.1.4最短路径查询模块最短路径查询模块运行如下图：（1）两点之间没有路径： 此图为输入的起点与终点之间没有路径可以到达。（2）两点之间有直接通路：此图为两点之间的通路是直接通路，并输出了路径长度。 （3）两点之间间接通路：此图为两点之间的通路是间接的，不仅输出了路径长度，并且将中转站点的编号也一同输出，方便旅客转
27、车。3.2运行调试及发现问题3.2.1调试过程一开始运行此系统，会发现很多错误而无法运行。在不断的查找资料与复习书本上所学习过的内容不断改正后正式运行成功。然而，每个模块都有小小的不足之处，运行出的结果也并不与我们所想象的一样。首先，主界面的运行就需要许多的调试，比如并未对齐，或词语串行等等，都需要我们不断调整空格格数以及语句的筛选才能实现理想的结果。其次，对于显示的函数同样存在着与主界面同样的问题，我们需要一点一点的调整才可以完全输出想要的结果。另外，最短路径的输出函数，一开始并未正确的输出，这需要我们不断的查找问题并解决，最后再进行一步步的调整，才可以正确的输出。并且在没有直通路径的时候还
28、需要输出所经站点的编号，这也需要我们调整。一切完成后才可正常工作。最后，退出系统的功能也需要自己编译以及调试。有时候无法跳出主函数的循环，或者无法跳出系统的循环，这都是编译出了问题，均需要一点点调试才可。3.2.2发现问题这次课程设计的系统并不完善，只实现了最基本的功能。其实还可以更加完善，多添加几个模块功能，使其更加完整，比如：管理员身份登录后可以修改线路的权值，站点的名称，可以添加、删除、修改这些信息。这样就使得这个系统更加的人性化，并且更加先进，可以及时更新最新信息。另外在用户查询中，也可多添加几项为旅游服务的项目，比如：为站点做简介，介绍当地的特色以及景点，还可以提供查询路径时不仅可查
29、出距离的长短，还有时间花费等均可以查询。以上仅仅只是发现这次所做系统的不足，功能的缺少，但并未能真正的实现。然而在已有的功能中，查询最短路径函数中，也有小小的不足：在查询后显示出的并非站点名称而是编号，这还需用户自己对照列表进行查找，这便不是很直观方便了。我们想了很多种方法想要更正这一点，但怎么都无法实现。我想我们学习的还是不够，动手能力还是没有真正的达到随心所欲的境界，这还需要我们不断的积累经验，不断的动手实践才能完成心中所想得效果吧。第四章 设计总结与心得做了一个星期的程序设计终于做完了，在这次程序设计课中，真是让我获益匪浅，我突然发现写程序还挺有意思的。由于上学期的C语言跟数据结构都算不
30、上真正的懂，对于书上的稍微难点的知识就是是而非的，所以我只是对老师的程序理解，我也试着去改变了一些变量，自己也尽量多的去理解老师做程序的思路。当我第一天坐在那里的时候，我就不知道该做些什么，后来我只有下来自己看了一遍书来熟悉下以前学过的知识。通过这次的程序设计，发现一个程序设计就是算法与数据结构的结合体，自己也开始对程序产生了前所未有的兴趣，以前偷工减料的学习也不可能一下子写出一个程序出来，于是我就认真看老师写的程序，发现我们看懂了一个程序其实不难，难的是对于一个程序的思想的理解，我们要掌握一个算法，不仅仅限于读懂，主要的是要理解老师的思路，学习老师的解决问题的方法。这次试验中，我发现书本上的
31、知识是一个基础，但是我基础都没掌握，更别说写出一个整整的程序了。自己在写程序的时候，也发现自己的知识太少了，特别是基础知识很多都是模模糊糊的一个概念，没有落实到真正的程序，所以自己写的时候也感到万分痛苦，基本上涉及一个知识我就会去看看书，对于书本上的知识没掌握好。在饭后闲暇时间我也总结了一下，自己以前上课也认真的听了，但是还是写不出来，这主要归结于自己的练习太少了，而且也总是半懂就不管了。在改写老师的程序中也出现了很多的问题，不断的修改就是不断的学习过程，当我们全身心的投入其中时，实际上是一件很有乐趣的事情。通过此次课程设计，使我更加扎实的掌握了有关数据结构方面的知识，在设计过程中虽然遇到了一
32、些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。过而能改，善莫大焉。在课程设计过程中，我们不断发现错误，不断改正，不断领悟，不断获取。最终的检测调试环节，本身就是在践行“过而能改，善莫大焉”的知行观。这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在老师的指导下，终于游逆而解。在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，
33、而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得到社会及他人对你的认可！课程设计诚然是一门专业课，给我很多专业知识以及专业技能上的提升，同时又是一门讲道课，一门辩思课，给了我许多道，给了我很多思，给了我莫大的空间。同时，设计让我感触很深。使我对抽象的理论有了具体的认识。我认为，在这学期的实验中，不仅培养了独立思考、动手操作的能力，在各种其它能力上也都有了提高。更重要的是，在实验课上，我们学会了很多学习的方法。而这是日后最实用的，真的是受益匪浅。要面对社会的挑战，只有不断的学习、实践，再学习、再实践。这对于我们的将来也有很大的帮助。以后，不管有多苦，我想我们都能变苦为乐，找寻有趣
34、的事情，发现其中珍贵的事情。就像中国提倡的艰苦奋斗一样，我们都可以在实验结束之后变的更加成熟，会面对需要面对的事情。实验过程中，也对团队精神的进行了考察，让我们在合作起来更加默契，在成功后一起体会喜悦的心情。果然是团结就是力量，只有互相之间默契融洽的配合才能换来最终完美的结果。此次设计也让我明白了思路即出路，有什么不懂不明白的地方要及时请教或上网查询，只要认真钻研，动脑思考，动手实践，就没有弄不懂的知识，收获颇丰。附录：程序源代码#include #include#include#include#defineMAXV 20/最大顶点个数#define INF 32767 /用32767表示ty
35、pedef int InfoType; /假设InfoType为int类型/以下定义邻接矩阵类型typedef struct int no;/顶点编号InfoType info;/顶点其他信息，这里用于存放边的权值 char name30; /顶点名称 VertexType;/顶点类型typedef struct int lengh; /边的权值，表示路径长度 int ivex,jvex; /边得两端顶点号EdgeType; /边的类型typedef struct /图的定义 int edgesMAXVMAXV; /邻接矩阵 int n,e; /顶点数，弧数VertexType vexsMAXV;/存放顶点信息 MGraph;/图的邻接矩阵类型MGraph G;MGraph InitGraph(void) MGraph G; int i,j; G.n=14; G.e=24; for(i=0;iG.n;i+) G.vexsi.no=i;strcpy(G.vexs0.name,湖南林业科技大学);strcpy(G.vexs1.name,潇湘晨报);strcpy(G.vexs2.name,市中心医院);strcpy(G.vexs3.name,铁道学院);strcpy(G.vexs4.name,新开铺路口);strcpy(G.vexs5.name,
