数据结构与算法课程设计-校园地图设计及其应用

数据结构与算法课程设计题目校园地图设计及其应用学院（系）信息工程系专业计算机科学与技术目录第1章需求分析和任务定义 第1章需求分析和任务定义1.1需求分析许多刚来学校的师生以及来访学校的客人都对学校并不是很了解，不知道每一栋建筑的位置，比如教学楼、宿舍、食堂等所在位置，不了解任意两个地点之间的路线。基于此背景，我们小组决定开发这个项目，设计一个广东理工学院校园地图，为师生、来访客人提供任意建筑地点相关信息的查询，以及为来访客人提供任意地点的问路查询，即查询任意两个地点之间的一条最短的简单路径，从而方便各位师生和来访客人。另外，构建校园网的主要目的就是提高教学质量，为学校的教育提供优质的教学服务，因此，师生和来访客人必须尽可能的节省问路的时间，甚至是要避免迷路的情况。1.2任务定义本系统包含一个文件，设计分有菜单、显示信息、floyd算法、迪杰斯特拉算法，其中floyd算法是求两个地点之间距离最短的算法，同时在本系统中又添加一些新的功能，这些在模块分析中将介绍到。本系统的基本任务有设计校园平面图，在校园地点选15个左右地点。以图中顶点表示校园内各地点，存放地点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2）为来访客人提供图中任意地点相关信息的查询。3）为来访客人提供任意地点的问路查询，即查询任意两个地点之间的一条最短路径。

第2章数据结构选择2.1逻辑结构逻辑结构采用无向加权图结构，如图2-1图2-1图2-1为自定义地图，工程制图为无向流通图。而在无向流通图中，如果删去顶点v，以及与v关联的边，图的剩余部分就变成不连通，那么，则称v是关节点。如果v、w、和x是互不相同的3个顶点，且v到w必过x，则x必是关节点。不存在关节点的无向连通称为双连通图，也称二连通图。而在图2-1中，有2个关节点（4后门和7招生办），3个双连通分量。2.2存储结构图2-1邻接矩阵如图2-2，采用一维数组压缩储存，压缩存储结构如图2-3。图2-2

图2-2无向图与无向加权图的邻接矩阵Anxn是对称矩阵，可用一维数组压缩存储，仅存其下三角部分。又由于顶点没有到自身的边，邻接矩阵对角线元素全为0，所以对角线元素也用不着存储，而只存严格下三角部分。于是，可推导出图2-3。图2-3

第3章算法设计与实现3.1算法设计3.1.1设计思路校园地图是由各个地点和地点以及场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表地点或场所，用图的边代表地点或场所之间的路径。所以首先应创建图的存储结构。结点值代表地点信息，边的权值代表地点间的距离。结点值及边的权值采用图存储。本系统需要查询地点信息和求一个地点到另一个地点的最短路径长度及路线，为方便操作，所以给每个地点一个代码，用结构体类型实现。计算路径长度，最短路线和最佳路径时可分别用迪杰斯特拉（Dijkastra）算法和哈密而顿回路算法实现。最后用switch选择语句选择执行浏览地点信息或查询最短路径和距离。3.1.2算法描述采用工程思想，将系统共分一下几个模块:数据结构定义模块、导航图建立模块、求最短路径模块、主菜单；下面是具体各功能简单的实际应用：数据结构定义模块：模块定义了导航图中各个节点的基本结构类型，主要采用邻接矩阵的存储结构来真实反映各节点到其他所有节点的路径长度（权值大小）。导航图建立模块：采用上述结构体类型对导航图中每个节点进行赋值。包括：各定点的名称（地点名），各个节点到其他所有节点的真实路径长度（赋权值）。求最短路径模块：本模块的基本思想是采用迪杰斯特拉算法求最短路径。次模块是本校园导航系统的核心模块，求两点间的最短路径与求一点到其他所有点最短路径两个子功能均是在最短路径算法模块的基础上进行调用，进而实现导航功能。主菜单：主菜单中主要是显示导航图中的所有导航节点，能够快速方便的对各个地点进行导航。以上程序的几个模块，构成了校园导航系统的基本组成部分，程序运行良好，达到了课程设计的基本要求。流程如图3-1。图3-1图3-13.2算法实现3.2.1算法关键函数1.#defineMax32767//用Max来表示权值为此时的两点间直接不可达#defineNUM15//选取了学校的十七个地点用数组存储，其中数组第一个元素不存储地点以方便操作typedefstructVertexType{ intnumber; char*sight;}VertexType;//定义顶点的结构体类型，number表示顶点编号，字符数组表示顶点的名称typedefstruct{ VertexTypevex[NUM]; intarcs[NUM][NUM]; intvexnum;}MGraph;//定义图的结构体类型，vex[NUM]数组存储顶点，arcsp[NUM][NUM]矩阵存储边的权值，vexnum表示顶点的个数MGraphG;{生成G表示结构体变量MGraph}intP[NUM][NUM];//定义全局变量P[NUM][NUM]存储点之间的最短路径longintD[NUM];//定义全局变量D[NUM]存储点之间最短路径的权值2.Dijkstra(intnum)//通过迪杰斯特拉算法求num点到其余点的最短路径，并将最短路径保存在数组P[NUM][NUM]中，将最短路径的权值保存在数组D[NUM]中voidDijkstra(intnum){ intv,w,i,t; intfinal[NUM]; intmin; for(v=1;v<NUM;v++) { final[v]=0;//置空最短路径终点集 D[v]=G.arcs[num][v];//置初始的最短路径长度 for(w=1;w<NUM;w++) P[v][w]=0;//置空最短路径 if(D[v]<32767) { P[v][num]=1; P[v][v]=1; } } D[num]=0; final[num]=1;//初始化num顶点属于S集 for(i=1;i<NUM;++i)//开始循环,每次求得num到某个顶点的最短路径,并添加到S集 { min=Max;//min为当前所知的num到顶点的最短距离 for(w=1;w<NUM;++w) if(!final[w])//w顶点在V-S集中 if(D[w]<min) { v=w; min=D[w]; } final[v]=1;//与num相距最近的顶点并入S集 for(w=1;w<NUM;++w)//更新最短路径 if(!final[w]&&((min+G.arcs[v][w])<D[w]))//修改D[w]和P[w]，w在V-S集中 { D[w]=min+G.arcs[v][w]; for(t=0;t<NUM;t++) P[w][t]=P[v][t]; P[w][w]=1; } }}charMenu()//主菜单显示于操作界面从而让用户选择查询路径功能或者查询地点信息功能 charc; intflag;//定义标志flag确定循环条件 do{ flag=1; Map(); printf("\t\t1.查询地点路径\n"); printf("\t\t2.地点信息简介\n"); printf("\t\te.退出\n"); printf("\t*************广东理工学院*****\n"); printf("\t\t\t请输入您的选择："); scanf("%c",&c); if(c=='1'||c=='2'||c=='e') flag=0; }while(flag); returnc;}3.voidDisplay(intsight1,intsight2)//输出函数用于通过数组P[NUM][NUM]提取出从点sight1到点sight2的最短路径，从D[NUM]中输出点sight1到点sight2的最短路径的权值{ inta,b,c,d,q=0; a=sight2; if(a!=sight1) { printf("\n\t从%s到%s的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight); printf("\t(最短距离为%dm.)\n\n\t",D[a]);//从D[NUM]中提取出sight1到sight2的最短距离的权值输出 printf("\t%s",G.vex[sight1].sight); d=sight1; for(c=0;c<NUM;++c) { P[a][sight1]=0; for(b=0;b<NUM;b++) { if(G.arcs[d][b]<32767&&P[a][b]) { printf("-->%s",G.vex[b].sight);//通过P[NUM][NUM]确定sight1到sight2的最短路径 q=q+1; P[a][b]=0; d=b; if(q%8==0)printf("\n"); } } } }}3.2.2main函数图：主函数对各个函数的调用voidmain()//主函数{ intv0,v1; chare; charck; CreateMGraph(NUM); Do//用dowhile循环确保循环至少进行一次 { system("cls");//用system("cls")清屏使屏幕简洁 ck=Menu(); switch(ck)//用switch语句确定用户选择功能 { case'1':gate://门函数使程序退回到gate位置 system("cls"); Map(); do { printf("\n\n\t\t\t请选择出发地序号（1～14）："); scanf("%d",&v0); if(v0<1||v0>17) printf("\n\n\t\t\t\t输入错误!\n"); }while(v0<1||v0>17); do { printf("\t\t\t请选择目的地序号（1～14）："); scanf("%d",&v1); if(v1<1||v1>14||v1==v0) printf("\n\n\t\t\t\t输入错误!\n"); }while(v1<1||v1>14||v1==v0); Dijkstra(v0); Display(v0,v1); printf("\n\n\t\t\t\t请按任意键继续,按e退回首页\n"); getchar(); scanf("%c",&e); if(e=='e'){当标识符e等于e时跳出语句} break; gotogate; case'2': system("cls"); Info(); printf("\n\n\t\t\t\t请按回车键退回首页...\n"); getchar(); getchar(); break; }; }while(ck!='e');//当标识符ck不等于e时继续循环}3.3算法分析1.本程序实现了查询校园中任意两景点的最短路径的功能，同时也显示了两景点最短路径的实际距离。也可以查询任意景点的信息，包括按景点编号查询和按景点名称查询。2.考虑道路网多是稀疏网，故采用邻接矩阵作存储结构。对于一个具有n个顶点，m条边的图来说，其空间复杂度为O（n2），此时的时间复杂度也为O（n²）。构建邻接矩阵的时间复杂度为O（m），输出路径的时间复杂度为O（n+m）。由此，本系统程序的时间复杂度为O（n）+O（m）=O（n+m）。3.在创建造图函数时，由于两个地点的距离是相互的，所以要对图中对称的边要同时赋值开始时没有注意到这一点，导致程序总是有错误。4.本程序除了迪杰斯特拉算法外，基本全是用最简单的c++语言编写的，行数比较多。5.可扩展的功能有求校园图的关节点，提供校园图中多个地点的最佳访问路线查询，即求途经这多个地点的最佳路径。

第4章调试分析4.1测试用例设计在程序系统中，对功能的测试，在本章就开始进行基本的功能测试，所以在测试中，主要是测试逻辑结构是否正确，是否符合最初的性能需求。首先设计测试用例。1.测试在没有选中起始点与终点时，系统是否会崩溃。在系统刚开始运行时，并没有选择起始点和终点，运行系统，看是否会出错。打开系统，进入到导航主系统，什么操作也不做，点击查询路径按钮，看系统是否会崩溃。2.测试系统的性能，连续输入错误两次或两次以上，看系统是否会崩溃。用例ID1用例名称页面搜索查询用例描述进入程序后选择查询地点最短路径页面信息包括：地点序号，选择出发及目的地输入框用例入口打开程序进入系统查询页面，输入1，回车键进入查询最短路径界面测试用例ID场景测试步骤预期结果备注TC1初始页面显示从用例入口处进入页面元素完整，显示与详细设计一致TC2初始页面显示，请输入你的选择输入2输入成功TC3介绍页面输入e显示地点介绍TC4介绍页面输入3输入失败，程序无反应输入数据不在规定选项中TC5初始页面显示，请输入你的选择输入1显示地点序号TC6出发地选择页面显示输入出发地序号1显示出发地序号TC7目的地选择页面显示输入目的地序号2输入成功，显示出目的地序号和1，2两点之间最短路径TC8出发地选择页面显示输入出发地序号2显示出发地序号TC9目的地选择页面显示输入目的地序号2程序无反应出发地与目的地序号相同，需重新输入目的地TC10目的地选择页面显示输入目的地序号4输入成功，显示2,4之间的最短路径…….…..…..4.2运行结果进入演示程序后随即显示如下的文本方式的用户界面如图4-1图4-1输入2，进入“广东理工学院各地点介绍”，结果如图4-2图4-2输入e，结果如图4-3所示，再按回车键则退出程序图4-3

输入1进入“查询地点之间最短路径”，结果如图4-4图4-4输入出发地序号1，再输入目的地序号2，结果如图4-5图4-5

若输入出发地和目的地的序号相同，则错误，需重新输入目的地，结果如图4-6图4-6再次输入目的地4，结果如图4-7图4-7

按回车键后，返回查询地点之间最短路径界面，结果如图4-8图4-8输入e后，返回首页，结果如图4-9图4-94.3调试过程问题分析调试过程中出现闪屏问题，应该是程序中的未知BUG问题；调试中又可能会出现崩溃，可能是调试过程调试不当，或者是程序语法有细小错误。解决问题方法：及时修复漏洞，完善语法。

第5章总结5.1收获与经验总结随着计算机软硬件的不断发展，导航系统在客户需求中的应用已成必然。

本系统在开发中也是严格按照学校的实际情况进行开发的，在开发中，查阅了很多相关的算法资