数据结构校园导游程序课程设计报告

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 visitedm

5、ax;/全局数组，用来记录各顶点被访问的情况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,int j)

7、和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）重复（3）知道某个顶点vi的所有邻接点都已经被访问

8、过，此时后退一步查找前一个顶点vi-1的邻接点；（5）如果存在尚未被访问过的顶点，则访问此邻接点，并再从该顶点出发按深度优先的规则进行访问；（6）如果vi-1的邻接点也都已经被访问过，则再后退一步，直到找到有尚未被访问过的邻接点的顶点；（7）重复上述步骤，直到图中的所有顶点都已被访问。4、查询景点的信息（1）按照景点的编号查询：当输入要查询的景点的编号a时，通过循环找到图中相应的顶点，然后输出景点的introduction，具体代码如下：printf("nntt请输入您要查找的景点编号："); scanf("%d",&a); for(i=0;i&

9、lt;9;i+) if(a=g->vexsi.number) printf("ntt您要查找景点信息如下:"); printf("nnttt%-25sn",g->vexsi.sight); printf("nttt%-25sn",g->vexsi.introduction);（2）按照景点的名称查询：当输入要查询的景点的名称name时，通过调用系统函数strcmp()，比较name与sight是否相等，如果相等，输出景点的introduction，否则没有找到。算法实现如下：printf("nntt请输入您

10、要查找的景点名称："); scanf("%s",name); for(i=0;i<9;i+) if(!strcmp(name,g->vexsi.sight) printf("ntt您要查找景点信息如下:"); printf("nnttt%-25sn",g->vexsi.introduction);5、查询图中任意两个景点的最短路径：用迪杰斯特拉算法来实现从某点出发到其他各个点的所有最短路径。定义dijkstra(mgraph *g,int v0,int p)函数并实现该功能。具体实现如下：(1)基本思想初始

11、时，顶点集合s只有一个源点，以后陆续将已求得的当前最短路径所依附的顶点不断地加入到集合s中，直到全部顶点都加入到集合s时，该过程结束。算法中另设一个一维数组dist，图中的每个顶点对应着该数组的一个分量，该分量存放着从源点到相应顶点的当前最短路径长度。(2)算法描述：用邻接矩阵表示带权有向图 ，s为已求得的最短路径所依附的顶点集合，disti数组的每个分量表示当前求得的从源点v0到达vi的最短路径。1>初始状态s=v0，disti=costv0,vi viv(g)2>选择vk使distk=mindisti|viv-s,viv(g)，则vk是目前求得的一条从v0出发的最短路径的终点。

12、令s=s+vk。3>修改所有不在s中的顶点的最短路径长度，即：如果 distvk+costvk,vi<distvi，则 distvi=distvk+costvk,vi4>重复2>、3>共n-1次，即可求得由源点到各顶点之间的最短路径。四、上机调试1、解决问题(1)刚拿到这个题目，开始我一点想法也没有，不知道如何下手。感到这个题目很难。通过第一次上机课，李老师给我们讲解了一个题目。如何去写程序，如何写报告。我有了思想，通过算法使其成为程序。运行程序的第一个错误是：在无向图的初始化上出现了大量错误，经调试和观察后发现，结构体中关于景点的名称和简介定义错误，应将语句：t

13、ypedef struct int number; char sight; char introduction;vertex;改为：typedef struct int number; char *sight; char *introduction;vertex;(2)重新对程序进行编译、构建，均正确，当执行后报错。分析可知，可能是mgraph的对象没有分配内存空间。仔细观察建图函数create_mgraph()可知，应在函数中语句“mgraph *g;”后加上“g=(mgraph *)malloc(sizeof(mgraph);”。(3)重新编译构建后，执行均正确。2、算法时间复杂度分析本程

14、序算法集中于迪杰斯特拉算法，设costi,j=0,s为已经求得最短路径的顶点集合，distancei数组的每个元素表示当前状态下就远点v0到vi的最短路径。(1)初始化：s=vo.distancei=cost0,i(2)选择一个重点vj,满足distancej=mindistancei|vi属于v-s(3)把vi加入到s中(4)修改distance数组元素，修改逻辑为对于所有不再s中的顶点viif(distancej+costi,j<distancei)distancei=distancej+costi,j(5)重复(2)(3)(4)，直到全部定点加入到s中。void dijkstra(

15、mgraph *g,int v0,int p) /采用 dijkstra算法求从顶点v0到顶点p的最短路径/*s为已找到最短路径的终点集合,若si=1,则is;path1i中存放顶点i的当前最短路径上该点的前趋顶点; disti中存放顶点i的当前最短路径长度*/ int distmax,path1max; int smax; int min_dist,i,j,u,k=g->m; for(i=0;i<k;i+) disti=g->edgesv0i; /距离初始化 si=0; /s置空 if(g->edgesv0i<inf) /路径初始化 path1i=v0; els

16、e path1i=-1; sv0=1; /源点编号v0放入s中 path1v0=0; for(i=0;i<k;i+) min_dist=inf; u=-1; for(j=0;j<k;j+) if(sj=0&&distj<min_dist) u=j; /选取不在s中具有最小距离的顶点u min_dist=distj; su=1; /顶点u加入s中 for(j=0;j<k;j+) /修改不在s中的顶点的距离 if(sj=0)if(g->edgesuj<inf&&distu+g->edgesuj<distj) distj

17、=distu+g->edgesuj; /修正disti,path1i path1j=u; dispath(g,dist,path1,s,k,v0,p); /输出最短路径第一个for循环时间为o（n），第二个for循环共执行n-1次，里面还有两个for循环，均执行n次，因此整个算法时间复杂度为o（n*n）。 3、经验和体会 ： 通过这两个星期的课程设计，让我知道一些解决问题方法。比如遇到问题首先自己解决，解决不了的可以问老师也可以到图书馆里找去。千万不能遇到问题就逃避，或自己不想就去问老师和同学。在这两个星期的课程设计过程中，我深深感受到自己所掌握知识还不足，已掌握也不牢固。两个星期的课程

18、设计，使我渐渐熟悉了数据结构有了一定的了解，虽然这次设计的只是一个小程序，但是这其间我还是学到了不少东西。在这次课程设计的过程，我得到来自老师以及同学们的帮助和鼓励。在没有上数据结构课程设计时，我对数据结构不是十分的熟悉。因为上课时也没好好听，从而让我在设计时感到学的知识不够。通过这两个星期的书写和调试程序，对数据结构不是像开始那样的陌生了，我觉得这个程序的难点就在于无向图的建立、迪杰斯特拉算法和深度优先遍历，其他的并不是很难。这次的课程设计让我获益匪。觉得这门课开的十分重要。通过这次的程序设计的确学到很多东西，但也认识自己有很多不足的地方，也使我对自己的学习有了一个阶段性的了解。也使认识到平

19、时的学习的重要性。 通过这次课程设计也使我正确认识我们专业的情景。通过本次的数据结构课程设计，让我学会了把书本上的知识应用到了实际中来。虽然在这几周中有过挫折和坎坷，有的问题一直到了最后才被解决，但是我认为这未必就不是好事，这样能锻炼我的意志，磨练我的耐心，失败是成功之母，这话一点都没错，没有失败就没有成功。让我没有失去信心的是关怀我们的老师，当我们有了问题和疑问，老师就很耐心的给予讲解，让我们有了一个良好的学习氛围。五、测试结果及其分析1、程序运行的界面如图3所示：图32、按1查询景点间的所有路径，如图4、图5：图4 图53、按2查询景点的信息，如图6-11：图6图7图8图9图10图114、

20、按3查询景点间的最短游览路径，如图12、13所示：图12图13六、用户使用说明1、主菜单界面程序运行进入主菜单可以看到选择操作菜单如下图14图142、由菜单显示信息选择相应操作(1)选择1，查询景点间的所有路径 输入景点编号。 程序输出景点建的所有路径。(2)选择2，查询景点的信息，选择查询方式，如图15图15(3)选择3，查询景点间的最短游览路径 按提示输入查找的两点。 程序输出两点间所有路径。(4)选择e，退出程序程序循环运行结束。 若不选择e操作，程序将继续等待操作选择不结束。3、程序编译环境为microsoft visual c+ 6.0。七、参考文献1谭浩强.c程序设计(第三版).北

21、京：清华大学出版社，2005年7月.2王昆仑,李红.数据结构与算法.北京：中国铁道出版社，2007年6月第1版.3章炯民，窦亮，黄国兴.数据结构与算法教程.上海：华东师范大学出版社，2007年7月第1版.4侯风巍.数据结构要点分析c语言版.北京：北京航空航天大学出版社，2007年3月第1版.八、附录（源代码）#include"stdio.h"#include"malloc.h"#include "string.h"#include "stdlib.h"#define inf 20000 /用20000表示无穷大#d

22、efine 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 visitedmax; /全局数组，用来记录各顶点被访问的情况int a=0;

23、 /全局变量，用来记录每对顶点之间的所有路径的条数char menu(mgraph *g); /主菜单void searchpath1(mgraph *g); /查询两个景点间的所有路径mgraph *create_mgraph(); /构建校园旅游的无向图void disppath(mgraph *g,int i,int j); /输出两景点间所有路径void path(mgraph *g,int i,int j,int k); /找到从i到j的所有路径并输出void searchpath2(mgraph *g); /查询两个景点间的最短路径void ppath(mgraph *g,int

24、path1,int i,int v0); /输出最短路径中景点的名称void dispath(mgraph *g,int dist,int path1,int s,int k,int v0,int i); /由path1计算从v0到i的最短路径void dijkstra(mgraph *g,int v0,int p); /采用 dijkstra算法求从顶点v0到顶点p的最短路径char searchmenu(mgraph *g); /查询景点信息的子菜单void search(mgraph *g); /查询景点信息 void tuxing(); /输出校园游览图/char menu(mgrap

25、h *g) /主菜单 char c; int flag; do flag=1;/循环结束标志 system("cls");/清屏函数 tuxing(); printf("nttt n"); printf("ttt n"); printf("ttt 1、查询景点间的所有路径 n"); printf("ttt 2、查询景点的信息 n"); printf("ttt 3、查询景点间的最短游览路径 n"); printf("ttt e、退出 n"); printf(

26、"ttt n"); printf("ttt n"); printf("tttt请输入您的选择："); scanf("%c",&c); if(c='1'|c='2'|c='3'|c='e') flag=0; while(flag); return c;/mgraph *create_mgraph() /构建校园旅游的无向图 mgraph *g; g=(mgraph *)malloc(sizeof(mgraph); int i,j; g->m

27、=9; /初始化结构中的景点数 g->n=10; /初始化结构中的边数 for(i=0;i<g->m;i+) g->vexsi.number=i; /初始化每一个景点的编号 g->vexs0.sight="南门" g->vexs0.introduction="校门整体建筑高大宏伟，富有时代气息。学校所有进出车辆必须由此登记并检验通过。" g->vexs1.sight="行政楼" g->vexs1.introduction="学校主要部门的办公地点，主要有院长办公室、财务处、教务

28、处、学生工作处、后勤集团和人事处等" g->vexs2.sight="厚德大厦" g->vexs2.introduction="学校的主教学楼，有10层，配有两部电梯总建设面积将近10000平方米，可同时容纳1500人上课。拥有现代化的机房和多媒体教室，硬件设施堪称一流 。" g->vexs3.sight="图书馆" g->vexs3.introduction="图书馆藏书丰富、建筑宏伟、环境优雅。馆内服务功能完备，拥有多种现代化的服务设施。" g->vexs4.sight=

29、"艺术楼" g->vexs4.introduction="艺术楼的建筑精美别致、结构合理、功能齐备，内部配备了反映国内较先进的现代教育技术设备、实验设备、音乐美术器材等" g->vexs5.sight="东门" g->vexs5.introduction="学校师生主要从东门出入，门口有两个庄严的石刻狮子，栩栩如生。" g->vexs6.sight="保卫处" g->vexs6.introduction="主要负责学校学生的户籍管理、安全管理、门卫管理以及

30、新生的军训等" g->vexs7.sight="致用礼堂" g->vexs7.introduction="举办校内或者校外的各种文娱活动，既可以陶冶学生情操，开阔学生眼界，又可以缓解学生压力，增强心理承受能力" g->vexs8.sight="第一食堂" g->vexs8.introduction="第一食堂是我们学校的老食堂了，饭菜可口，物美价廉，童叟无欺，享誉省内外。在这里，你可以尝到地地道道的安徽菜。欢迎前来品尝！" for(i=0;i<g->m;i+) for(

31、j=0;j<g->m;j+) g->edgesij=inf; /这里把所有的边假定为inf=20000，含义是这两个景点之间是不可到达 g->edges01=g->edges10=20; g->edges02=g->edges20=22; g->edges13=g->edges31=17; g->edges23=g->edges32=6; g->edges34=g->edges43=10; g->edges47=g->edges74=25; g->edges25=g->edges52=16;

32、g->edges56=g->edges65=5; g->edges78=g->edges87=4; g->edges05=g->edges50=45; return g;/void searchpath1(mgraph *g) /查询两个景点间的所有路径 int i,j; printf("tt选择出发景点："); scanf("%d",&i); printf("tt选择目地景点："); scanf("%d",&j); for(int k=0;k<g->

33、m;k+) /g->m表示网中的顶点个数 if(i=g->vexsk.number) i=k; /在网中找到其编号与输入的出发景点的编号相同的顶点 for(int s=0;s<g->m;s+) if(j=g->vexss.number) j=s; /在网中找到其编号与输入的目地景点的编号相同的顶点 printf("tt从%s到%s的所有游览路径有:n",g->vexsi.sight,g->vexsj.sight); /输出出发景点和目地景点的名称 disppath(g,i,j); /调用disppath函数,用来输出两个景点间的所有

34、路径/void disppath(mgraph *g,int i,int j) /输出两景点间所有路径 int k; d0=i; for(k=0;k<g->m;k+) visitedi=0; /初始化各顶点的访问标志位，即都为未访问过的 a=0; /初始化路径的条数 path(g,i,j,0); /通过调用path函数，找到从vi到vj的所有路径并输出/void path(mgraph *g,int i,int j,int k) /找到从i到j的所有路径并输出 int s; if(dk=j) /找到一条路径 a+; /路径的条数值加1 printf("tt第%d条:&qu

35、ot;,a); for(s=0;s<=k-1;s+) /输出一条路径printf("%s->",g->vexsds.sight); printf("%s",g->vexsds.sight); printf("n"); else /深度优先遍历邻接矩阵 s=0; while(s<g->m)if(s!=i) /保证找到的是简单路径 if(g->edgesdks!=inf&&visiteds=0) visiteds=1; /置访问标志位为1,即已访问的 dk+1=s; /将顶点s加入

36、到d数组中 path(g,i,j,k+1); /递归调用之 visiteds=0; /重置访问标志位为0，即未访问的，以便该顶点能被重新使用 s+; /void searchpath2(mgraph *g) /查询两个景点间的最短路径 int i,j; printf("tt选择出发景点："); scanf("%d",&i); printf("tt选择目地景点："); scanf("%d",&j); for(int k=0;k<g->m;k+) /g->m表示网中的顶点个数 if(i

37、=g->vexsk.number) i=k; /在网中找到其编号与输入的出发景点的编号相同的顶点 for(int s=0;s<g->m;s+) if(j=g->vexss.number) j=s; /在网中找到其编号与输入的目地景点的编号相同的顶点 dijkstra(g,i,j); /调用dijkstra函数,用来输出两个景点间的最短路径/void dijkstra(mgraph *g,int v0,int p) /采用 dijkstra算法求从顶点v0到顶点p的最短路径/*s为已找到最短路径的终点集合,若si=1,则is;path1i中存放顶点i的当前最短路径上该点的

38、前趋顶点; disti中存放顶点i的当前最短路径长度*/ int distmax,path1max; int smax; int min_dist,i,j,u,k=g->m; for(i=0;i<k;i+) disti=g->edgesv0i; /距离初始化 si=0; /s置空 if(g->edgesv0i<inf) /路径初始化 path1i=v0; else path1i=-1; sv0=1; /源点编号v0放入s中 path1v0=0; for(i=0;i<k;i+) min_dist=inf; u=-1; for(j=0;j<k;j+) if

39、(sj=0&&distj<min_dist) u=j; /选取不在s中具有最小距离的顶点u min_dist=distj; su=1; /顶点u加入s中 for(j=0;j<k;j+) /修改不在s中的顶点的距离 if(sj=0)if(g->edgesuj<inf&&distu+g->edgesuj<distj) distj=distu+g->edgesuj; /修正disti,path1i path1j=u; dispath(g,dist,path1,s,k,v0,p); /输出最短路径/void dispath(mg

40、raph *g,int dist,int path1,int s,int k,int v0,int i)/由path1计算从v0到i的最短路径 if(si=1&&i!=v0) printf("tt从%s到%s的最短游览路径是:n",g->vexsv0.sight,g->vexsi.sight); printf("tt%s->",g->vexsv0.sight); ppath(g,path1,i,v0); /调用ppath函数，输出路径中的顶点 printf("%s ",g->vexsi.s

41、ight); printf("路径长度：%d米n",disti); /void ppath(mgraph *g,int path1,int i,int v0) /输出最短路径中景点的名称 int k; k=path1i; if(k=v0) /找到最短路径后返回 return; ppath(g,path1,k,v0); /否则，递归调用之 printf("%s->",g->vexsk.sight); /依次输出路径中的景点名称/char searchmenu(mgraph *g) /查询景点信息子菜单 char c; int flag; do

42、flag=1; system("cls"); tuxing(); printf(" n"); printf(" n"); printf(" 1、按照景点编号查询 n"); printf(" 2、按照景点名称查询 n"); printf(" 3、返回 n"); printf(" n"); printf(" n"); printf("tttt请输入您的选择："); scanf("%c",&c)

43、; if(c='1'|c='2'|c='3') flag=0; while(flag); return c;/void search(mgraph *g) /查询景点信息 int a; int i; char c; char name20; do system("cls"); c=searchmenu(g); switch (c) case '1': system("cls"); tuxing(); printf("nntt请输入您要查找的景点编号："); scanf(&

44、quot;%d",&a); for(i=0;i<9;i+) if(a=g->vexsi.number) printf("ntt您要查找景点信息如下:"); printf("nnttt%-25sn",g->vexsi.sight); printf("nttt%-25sn",g->vexsi.introduction); printf("nttt按任意键返回."); getchar(); getchar(); break; if(i=9) printf("nnttt没有找到！"); printf("nnttt按任意键返回."); getchar(); getchar(); break; case '2': system("cls"); tuxing(); printf("