《数据结构 校园导游程序课程设计报告》由会员分享，可在线阅读，更多相关《数据结构 校园导游程序课程设计报告（21页珍藏版）》请在金锄头文库上搜索。
1、合肥学院计算机科学与技术系课程设计报告2009 2010 学年第 二学期课程 数据结构与算法课程设计名称 校园导游程序学生姓名 王 伟学号 0804013006专业班级 08 计科(3)班指导教师 李 红 沈亦军2010 年 6 月题目：校园导游程序题目：用无向网表示你所在学校的校园景点平面图，图中定点表示主要景点，存放景点的编号、名称、简介等信息。要求能够回答有关景点介绍、游览路经等问题。要求：(1)查询各景点相关信息；(2)查询图中任意两个景点的最短路径。(3)查询图中任意两个景点的所有路径。.选作内容：求多个景点的最佳游览路经。一、问题分析与任务定义1、问题分析我们将每个建筑看作图中的一
2、个点,而建筑物之间直接相连的道路看作是无向图的边, 那么就可以得到一个无向图,而问题也就变成无向图中给定起点和终点的最短路径问题。而求查询图中任意两个景点的所有路径。就可以用深度优先遍历算法来实现。任意两个顶点之间的最短路径用 Dirjstra 算法来实现。从 v1 到 v2 的路径要么是 v1-v2，要么中间经过了若干顶点。显然我们要求的是这些路径中最短的一条。这样一来，问题就很好解决了最初都是源点到目的点，然后依次添加顶点，使得路径逐渐缩短，顶点都添加完了，算法就结束了。景点信息的查询可通过循环查找图中的景点，然后输出其对应的Introducion。在这里用 Create_Mgraph()
3、函数实现原始数据的输入 。2、任务定义根据设计的基本要求，可知本系统应实现以下几个功能：(1)景点查询：景点查询，输出所查询景点的相关信息(2)景点之间最佳路径查询功能：输出所选择的两点之间的最短路径及路径长度。(3)两景点间所有路径：输出两点间存在的所有路径。二、数据结构的选择和概要设计1、图的定义：图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。图的信息以邻接矩阵存储，利用二维数组作为矩阵坐标，二维数组的值表示图的两点间的距离，即无向图的权值，若两点间无直接路径，则以无穷大（此程序中为 INF=20000）为权值。2、校园导游程序的数据
4、结构类型如下：#define INF 20000 /用 20000 表示无穷大#define max 20 /最多顶点个数typedef struct /定义景点类型int number; /景点序号char *sight; /景点的名称char *Introduction; /景点的简介Vertex;typedef struct /定义图的类型int m; /景点个数int n; /边或弧的数目Vertex vexsmax; /一维数组，存储景点int edgesmaxmax; /二维数组，存储边或弧的权值MGraph;int Dmax;/全局数组，用来存放路径上的个顶点int visite
5、dmax;/全局数组，用来记录各顶点被访问的情况int a=0;/全局变量，用来记录每对顶点之间的所有路径的条数3、概要设计图的信息以邻接矩阵形式存储，邻接矩阵以二维数组的数据结构存储。vexsij；当 i=j 及 i 点与 j 点无直接连通时，其值为无穷大，定义一个很大的整数 INF 代替无穷大。当 i 与 j 点邻接时，其值为两点间的权值即两景点距离。(1)查询景点信息1按照景点编号查询2按照景点名称查询(2)两点间最短路径利用迪杰斯特拉（Dirjstra）算法求两点之间最短路径。(3)两点间所有路径利用邻接矩阵的“深度优先遍历”查找路径，从起始点 a 开始依次遍历，如果找到终点 b,则输
6、出相应路径，否则继续递归查找。程序框架图如图 1 所示：主函数Dirjstra算法最短路径创建图输入临接矩阵遍历输出所有路径查询景点相关信息图 1 程序框架三、详细设计和编码1、首先确定以无向图为数据结构的校园地图如图 2：图 2 校园地图2、设计主函数：调用各子函数完成选择功能。主函数中以 switch 语句选择操作：1查询景点间的所有路径2查询景点的信息: 1按照景点编号查询2按照景点名称查询3查询景点间的最短游览路径e退出程序3、按深度优先遍历输出图中任意两个景点间的所有路径，通过调用函数Searchpath2(MGraph *G)， disppath(MGraph *G,int i,i
7、nt j)和 path(MGraph *G,int i,int j,int k)其中函数 Searchpath2(MGraph *G)用来输出两景点间所有路径，函数disppath(MGraph *G,int i,int j)用来找到从 i 到 j 的所有路径并输出，函数path(MGraph *G,int i,int j,int k)用来查询两个景点间的最短路径。算法实现如下：（1）首先某一个指定的顶点 V0（即起始点） ；（2）然后从 V0 出发，访问一个与 V0 邻接且没有被访问过的顶点 V1；（3）再从 V1 出发，选取一个与 V1 邻接且没有被访问过的顶点 V2 进行访问；（4）重复
8、（3）知道某个顶点 Vi 的所有邻接点都已经被访问过，此时后退一步查找前一个顶点 Vi-1 的邻接点；（5）如果存在尚未被访问过的顶点，则访问此邻接点，并再从该顶点出发按深度优先的规则进行访问；（6）如果 Vi-1 的邻接点也都已经被访问过，则再后退一步，直到找到有尚未被访问过的邻接点的顶点；（7）重复上述步骤，直到图中的所有顶点都已被访问。4、查询景点的信息（1）按照景点的编号查询：当输入要查询的景点的编号 a 时，通过循环找到图中相应的顶点，然后输出景点的 Introduction，具体代码如下：printf(nntt 请输入您要查找的景点编号：);scanf(%d,for(i=0;ive
9、xsi.number)printf(ntt 您要查找景点信息如下:);printf(nnttt%-25sn,G-vexsi.sight);printf(nttt%-25sn,G-vexsi.Introduction);（2）按照景点的名称查询：当输入要查询的景点的名称 name 时，通过调用系统函数strcmp()，比较 name 与 sight 是否相等，如果相等，输出景点的 Introduction，否则没有找到。算法实现如下：printf(nntt 请输入您要查找的景点名称：);scanf(%s,name);for(i=0;ivexsi.sight)printf(ntt 您要查找景点信息
10、如下:);printf(nnttt%-25sn,G-vexsi.Introduction);5、查询图中任意两个景点的最短路径：用迪杰斯特拉算法来实现从某点出发到其他各个点的所有最短路径。定义 Dijkstra(MGraph *G,int v0,int p)函数并实现该功能。具体实现如下：(1)基本思想初始时，顶点集合 S 只有一个源点，以后陆续将已求得的当前最短路径所依附的顶点不断地加入到集合 S 中，直到全部顶点都加入到集合 S 时，该过程结束。算法中另设一个一维数组 dist，图中的每个顶点对应着该数组的一个分量，该分量存放着从源点到相应顶点的当前最短路径长度。(2)算法描述：用邻接矩阵
11、表示带权有向图 ，S 为已求得的最短路径所依附的顶点集合，disti数组的每个分量表示当前求得的从源点 v0到达 vi的最短路径。1初始状态S=v0，disti=costv 0,vi viV(G)2选择 vk使 distk=mindisti|viV-S,v iV(G)，则 vk是目前求得的一条从 v0出发的最短路径的终点。令 S=S+vk。3修改所有不在 S 中的顶点的最短路径长度，即：如果 distv k+costvk,vi重复 2、3共 n-1 次，即可求得由源点到各顶点之间的最短路径。四、上机调试1、解决问题(1)刚拿到这个题目，开始我一点想法也没有，不知道如何下手。感到这个题目很难。通
12、过第一次上机课，李老师给我们讲解了一个题目。如何去写程序，如何写报告。我有了思想，通过算法使其成为程序。运行程序的第一个错误是：在无向图的初始化上出现了大量错误，经调试和观察后发现，结构体中关于景点的名称和简介定义错误，应将语句：typedef structint number;char sight;char Introduction;Vertex;改为：typedef struct int number;char *sight;char *Introduction;Vertex;(2)重新对程序进行编译、构建，均正确，当执行后报错。分析可知，可能是 Mgraph的对象没有分配内存空间。仔细观
13、察建图函数 Create_MGraph()可知，应在函数中语句“MGraph *G;”后加上“G=(MGraph *)malloc(sizeof(MGraph);” 。(3)重新编译构建后，执行均正确。2、算法时间复杂度分析本程序算法集中于迪杰斯特拉算法，设 costi,j=0,S 为已经求得最短路径的顶点集合，distancei数组的每个元素表示当前状态下就远点 v0 到 vi 的最短路径。(1)初始化：S=vo.distancei=cost0,i(2)选择一个重点 vj,满足 distancej=MINdistancei|vi 属于 V-S(3)把 Vi 加入到 S 中(4)修改 dist
14、ance 数组元素，修改逻辑为对于所有不再 S 中的顶点 ViIf(distancej+costI,jm;for(i=0;iedgesv0i; /距离初始化Si=0; /s置空if(G-edgesv0iedgesujedgesujedgesuj; /修正 disti,path1ipath1j=u;dispath(G,dist,path1,S,k,v0,p); /输出最短路径第一个 for 循环时间为 O（n） ，第二个 for 循环共执行 n-1 次，里面还有两个 for 循环，均执行 n 次，因此整个算法时间复杂度为 O（n*n） 。3、经验和体会 ：通过这两个星期的课程设计，让我知道一些解
15、决问题方法。比如遇到问题首先自己解决，解决不了的可以问老师也可以到图书馆里找去。千万不能遇到问题就逃避，或自己不想就去问老师和同学。在这两个星期的课程设计过程中，我深深感受到自己所掌握知识还不足，已掌握也不牢固。两个星期的课程设计，使我渐渐熟悉了数据结构有了一定的了解，虽然这次设计的只是一个小程序，但是这其间我还是学到了不少东西。在这次课程设计的过程，我得到来自老师以及同学们的帮助和鼓励。在没有上数据结构课程设计时，我对数据结构不是十分的熟悉。因为上课时也没好好听，从而让我在设计时感到学的知识不够。通过这两个星期的书写和调试程序，对数据结构不是像开始那样的陌生了，我觉得这个程序的难点就在于无向图的建立、迪杰斯特拉算法和深度优先遍历，其他的并不是很难。这次的课程设计让我获益匪。觉得这门课开的十分重要。通过这次的程序设计的确学到很多东西，但也认识自己有很多不足的地方，也使我对自己的学习有了一个阶段性的了解。也使认识到平时的学习的重要性。通过这次课程设计也使我正确认识我们专业的情景。通过本次的数据结构课程设计，让我学会了把书本上的知识应用到了实际中来。虽然在这几周中有过挫折和坎坷，有的问题一直到了最后才被解决，但是我认为这未必就不是好事，这样能锻炼我的意志，磨练我的耐心，失败是成
