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

数据结构与算法课程设计题目校园地图设计及其应用学院（系）信息工程系专业计算机科学与技术目录第1章需求分析和任务定义11.1 需求分析11.2 任务定义1第2章数据结构选择22.1 逻辑结构22.2 存储结构2第3章算法设计与实现43.1 算法设计43.1.1 设计思路43.1.2 算法描述43.2 算法实现53.2.1 算法关键函数53.2.2 main函数93.3 算法分析11第4章调试分析134.1 测试用例设计134.2 运行结果144.3 调试过程问题分析19第5章总结205.1 收获与经验总结205.2 存在问题与努力方向20参考文献21附录22致谢23摘要设计一个广东理工学院校园地图，为来访的客人提供各种信息查询服务。本文是采用C+作为开发语言，又最大程度上用了C语言的有关的语法。以ViSUalc+6.0为开发工具。旨在实现校园导航系统中，学校的简介，地点的介绍，路线查询等基本的问题。为来往客人参观校园提供方便。【关键词】visualc+6.0；校园导航系统；问路查询;AbstractComparedwiththetraditionalmap,GIShasincomparableadvantages,largeinformation,convenientswitchingandstrongscalability.Theproblemofcampusnavigationisbasedonthedifferentattractionsinthecampus,fromastranger'spointofview,forthegueststoprovideinformationaboutthecampusattractions,aswellastothegueststoproviderandomattractionsoncampusinquiries,sothatguestscanusetheshortestpossibletimefromalocationtowheretheywanttogo.Greatlysavethetimeforvisitorstovisitcampus.ThisarticleisusingC÷+asthedevelopmentlanguage,andthelargestextentintheClanguageoftherelevantgrammar.Usevisualc+÷6.0asthedevelopmenttool.Designedtoachievecampusnavigationsystem,theschool'sprofile,theintroductionofscenicspots,routeinquiriesandotherbasicissues.Itisconvenientforvisitorstovisitthecampus.KeyWordsVisualc+6.0;Campusnavigationsystem;askingfordirections;第1章需求分析和任务定义1.1 需求分析许多刚来学校的师生以及来访学校的客人都对学校并不是很了解，不知道每一栋建筑的位置，比如教学楼、宿舍、食堂等所在位置，不了解任意两个地点之间的路线。基于此背景，我们小组决定开发这个项目，设计一个广东理工学院校园地图，为师生、来访客人提供任意建筑地点相关信息的查询，以及为来访客人提供任意地点的问路查询，即查询任意两个地点之间的一条最短的简单路径，从而方便各位师生和来访客人。另外,构建校园网的主要目的就是提高教学质量，为学校的教育提供优质的教学服务，因此,师生和来访客人必须尽可能的节省问路的时间，甚至是要避免迷路的情况。1.2 任务定义本系统包含一个文件，设计分有菜单、显示信息、floyd算法、迪杰斯特拉算法，其中floyd算法是求两个地点之间距离最短的算法，同时在本系统中又添加一些新的功能，这些在模块分析中将介绍到。本系统的基本任务有1、 设计校园平面图，在校园地点选15个左右地点。以图中顶点表示校园内各地点，存放地点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2)2、 为来访客人提供图中任意地点相关信息的查询。3)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。正门操场招生办礼堂后门48栋研究院东福堂5栋西食堂图书馆智顺通便身塔造恩湖财政部正门O281OO8510<×>1300<×>245461246844088操场28103597438886268452271150081618招生办208359088140088888888112礼京87438029710008306268594754859OO8OO后门5108OO297012008571618554CO865112OO848栋8<X>14001000120005044581600OOCO241<×>OO1300研究院1300888308575040155OO88126888东饭堂8886261614581550OO8CO1698885栋245OO283881600880144OO888301西食堂461452202594554COOO81440199OO8OO317图书馆246271370754888<×>8199088578<×>智Ig诵815008859865241126169888088288健身常440888112888OO8888208192镜恩湖816188OO<×>8OO885788808财政部OO811288130088301317©O819280无向图与无向加权图的邻接矩阵AnXn是对称矩阵，可用一维数组压缩存储，仅存其第3章算法设计与实现1.1 算法设计1.1.1 设计思路校园地图是由各个地点和地点以及场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表地点或场所，用图的边代表地点或场所之间的路径。所以首先应创建图的存储结构。结点值代表地点信息，边的权值代表地点间的距离。结点值及边的权值采用图存储。本系统需要查询地点信息和求一个地点到另一个地点的最短路径长度及路线，为方便操作，所以给每个地点一个代码，用结构体类型实现。计算路径长度，最短路线和最佳路径时可分别用迪杰斯特拉（DijkaStra）算法和哈密而顿回路算法实现。最后用switch选择语句选择执行浏览地点信息或查询最短路径和距离。1.1.2 算法描述采用工程思想，将系统共分一下几个模块:数据结构定义模块、导航图建立模块、求最短路径模块、主菜单；下面是具体各功能简单的实际应用：数据结构定义模块：模块定义了导航图中各个节点的基本结构类型，主要采用邻接矩阵的存储结构来真实反映各节点到其他所有节点的路径长度（权值大小）。导航图建立模块：采用上述结构体类型对导航图中每个节点进行赋值。包括：各定点的名称（地点名），各个节点到其他所有节点的真实路径长度（赋权值）。求最短路径模块：本模块的基本思想是采用迪杰斯特拉算法求最短路径。次模块是本校园导航系统的核心模块，求两点间的最短路径与求一点到其他所有点最短路径两个子功能均是在最短路径算法模块的基础上进行调用，进而实现导航功能。主菜单：主菜单中主要是显示导航图中的所有导航节点，能够快速方便的对各个地4点进行导航。以上程序的几个模块，构成了校园导航系统的基本组成部分，程序运行良好，达到了课程设计的基本要求。流程如图3-1。图3-11.2 算法实现1.2.1 算法关键函数1. »defineMax32767用Max来表示权值为此时的两点间直接不可达defineNUM15选取了学校的十七个地点用数组存储，其中数组第一个元素不存储地点以方便操作typedefstructVertexTypeintnumber;char*sight;VertexType;定义顶点的结构体类型，number表示顶点编号，字符数组表示顶点的名称typedefstruct(VertexTypevexNUM;intarcsNUMNUM;intvexnum;MGraph;定义图的结构体类型，vexNUM数组存储顶点，arcspNUMNUM矩阵存储边的权值，VeXnUm表示顶点的个数MGraphG;生成G表示结构体变量MGraphintPNMNM;定义全局变量PNUMNUM存储点之间的最短路径longintDNM;定义全局变量DNUM存储点之间最短路径的权值2. Dijkstra(intnum)通过迪杰斯特拉算法求num点到其余点的最短路径，并将最短路径保存在数组PNUMNUM中，将最短路径的权值保存在数组DNUM中voidDijkstra(intnum)intv,w,i,t;intfinalNUM;intmin;for(v=l;v<NUM;v+)(finalv=0;置空最短路径终点集Dv=G.arcsnumv;置初始的最短路径长度for(w=l;w<NUM;w+)Pvw=0;置空最短路径if(Dv<32767)(Pvnum=l;PMv=l;Dnum=O;finalnum=l;初始化num顶点属于S集for(i=l;i<NUM;+i)开始循环,每次求得num到某个顶点的最短路径,并添加到S集(min=Max;/min为当前所知的num到顶点的最短距离for(w=l;w<NUM;+w)if(!finalw)/w顶点在V-S集中if(Dw<min)(v=w;min=Dw;)finalv=l;与num相距最近的顶点并入S集for(w=l;w<NUM+w)更新最短路径if(!final(min+G.arcsvw)<Dw)修改Dw和Pw,W在V-S集中(Dw=min+G.arcsvw;for(t=0;t<NUM;t+)Pwt=Pvt;PMw=l;)charMenuO主菜单显示于操作界面从而让用户选择查询路径功能或者查询地点信息功能charc;i11tflag;定义标志flag确定循环条件do(fIag=I;Map();printf(zztt1.查询地点路径r);Printf(“tt2.地点信息简介n)；printf(/,ttc.退出n)；Printf(t*广东理工学院*11");Printf("ttt请输入您的选择：)；scanf("%c",&c);if(c=-Ic=三,2'Ic='e,)fIag=O;while(flag);returnc;3. voidDisplay(intsightl,intsight2)/输出函数用于通过数组PNUMNUM提取出从点sightl到点sight2的最短路径，从DNUM中输出点sightl到点sight2的最短路径的权值(inta,b,c,d,q=0;a=sight2;if(a!=sightl)(printf(,nt从%s到%s的最短路径是，G.vexsightl.sight,G.vexsight2.sight);Printf("t(最短距离为%dm.)nnt",Da);从DNUM中提取出sightl到sight2的最短距离的权值输出Printf(“t%s”,G.vexsightl.sight);d=sightl;for(c=0;c<NUM;+c)Pasightl=0;for(b=0;b<NUM;b+)if(G.arcsdb<32767&&Pab)通过P NUM NUM确定Printf("一>%s",G.vexb.sight);sightl到sight2的最短路径q=q+l;Pab=0;d=b;if(q%8=0)Printf(n)；Map( )5Dijkstra( )5Display()1.2.2 main函数Info()图：主函数对各个函数的调用voidmain()主函数(intv,vl;chare;charck;CreateMGraph(NUM);Do用dowhile循环确保循环至少进行一次(SySten("cls");用SySten("cls")清屏使屏幕简洁ck=Menu();switch(ck)用SWitCh语句确定用户选择功能(case,:gate:门函数使程序退回到gate位置system(zzclszz);Map();do(Printf("nnttt请选择出发地序号(114)：);scanf(%d，&v0);if(v<lv>17)printfCznntttt输入错误!n");while(v<l(v>17);do(Printf("ttt请选择目的地序号(114)：)；scanf("%d”,&vl);if(vl<lIvl>14vl=v)printf(,zn11tttt输入错误!n");while(vl<lvl>14vl=v);Dijkstra(v);Display(v,vl);printfCz11ntttt请按任意键继续,按e退回首页r);getchar();scanf("%c",&c);if(e=三,e,)当标识符e等于e时跳出语句break;gotogate;case,2,:system(zzclszz);Info();printf(zznntttt请按回车键退回首页.n)；getchar();getchar();break;)；while(ck!=，e,);当标识符ck不等于e时继续循环)1.3 算法分析L本程序实现了查询校园中任意两景点的最短路径的功能，同时也显示了两景点最短路径的实际距离。也可以查询任意景点的信息，包括按景点编号查询和按景点名称查询。2 .考虑道路网多是稀疏网，故采用邻接矩阵作存储结构。对于一个具有n个顶点，m条边的图来说，其空间复杂度为O(n2),此时的时间复杂度也为O(M)。构建邻接矩阵的时间复杂度为O(m),输出路径的时间复杂度为O(n+m)。由此，本系统程序的时间复杂度为O(n)+O(m)=O(n+rn)o3 .在创建造图函数时，由于两个地点的距离是相互的，所以要对图中对称的边要同时赋值开始时没有注意到这一点，导致程序总是有错误。4 .本程序除了迪杰斯特拉算法外，基本全是用最简单的C+语言编写的，行数比较多。5 .可扩展的功能有求校园图的关节点,提供校园图中多个地点的最佳访问路线查询,即求途经这多个地点的最佳路径。第4章调试分析4.1 测试用例设计在程序系统中，对功能的测试，在本章就开始进行基本的功能测试，所以在测试中，主要是测试逻辑结构是否正确，是否符合最初的性能需求。首先设计测试用例。1 .测试在没有选中起始点与终点时，系统是否会崩溃。在系统刚开始运行时，并没有选择起始点和终点，运行系统，看是否会出错。打开系统，进入到导航主系统，什么操作也不做，点击查询路径按钮，看系统是否会崩溃。2 .测试系统的性能，连续输入错误两次或两次以上，看系统是否会崩溃。用例ID1用例名称页面搜索查询用例描述进入程序后选择查询地点最短路径页面信息包括：地点序号，选择出发及目的地输入框用例入口打开程序进入系统查询页面，输入1,回车键进入查询最短路径界面测试用例ID场景测试步骤预期结果备注TCl初始页面显示从用例入口处进入页面元素完整，显示与详细设计一致TC2初始页面显不，请输入你的选择输入2输入成功TC3介绍页面输入e显示地点介绍TC4介绍页面输入3输入失败，程序无反应输入数据不在规定选项中TC5初始页面显示，请输入你的选择输入1显示地点序号TC6出发地选择页面显示输入出发地序号1显示出发地序号TC7目的地选择页面显示输入目的地序号2输入成功，显示出目的地序号和1，2两点之间最短路径TC8出发地选择页面显示输入出发地序号2显示出发地序号TC9目的地选择页面显不输入目的地序号2程序无反应出发地与目的地序号相同，需重新输入目的地TClO目的地选择页面显示输入目的地序号4输入成功，显示2,4之间的最短路径.4.2 运行结果进入演示程序后随即显示如下的文本方式的用户界面如图4-121 D:JMSOFTCYuYanbinwwtemp.exe*广东理工学院地图导航系统*口门堂除恩饭 正知舄健财招48礼弼 23456789012345逋馆部办请输入您的选择:图4-1输入2,进入“广东理工学院各地点介绍”，结果如图42心地*集11正门传的侧人的宣舍理理锡生亶倭饭场广广收理有交招区中鼠吃操图自吃广.；的«.院通.馆部办.：.孝堂堂012345123456789111111按回车键返回首页.图4-2输入e,结果如图4-3所示，再按回车键则退出程序12)D:JMSOFTCYuYanbinwwtemp.exe院通寓办 堂国堂 否顺门w栋堂像恩饭 研正冒健财招48礼弼矍 123456789012345Pressanykeytocontinue图4-3输入1进入“查询地点之间最短路径”，结果如图4-4统 系 肮 导 图 地 院 学 工 理 东 -Mr院通馆部办 堂匾堂 裨顺门*W栋堂东恩饭 123456789012345请选择出发地序号(15)：图4-4输入出发地序号1,再输入目的地序号2,结果如图4-5DcJMSOFTCYuYanbinwwtemp.exe导 图 地 院 学 工 理 东123456789012345院通馆部办 KC 顺门 <一 研正知昌健财招，一：一栋堂栋?!噂4S礼5fi请选择出 请选举目殳地星号(115)：1N地序号(1-15)：2从研究院到正门的最短路径是最短距离为1300m.)研究院一正门接回车键继续,按e退回首页图4-53D:JMSOFTCYuYanbinwwtemp.exe(1 15), 2(1-15)： 2请选择目前鹘(5)：4从正门到后门的最短路径是<最短距离为510n.>正门一后门接回车键继续,按e退回苜页按回车键后，返回查询地点之间最短路径界面，结果如图4-8统 系 肮 导 图 地 院 学 工 理 东 -Mr院通馆部办 堂匾堂 裨顺门*W栋堂东恩饭 123456789012345请选择出发地序号(15)：图4-8输入e后，返回首页，结果如图4-93D:JMSOFTCYuYanbinwwtemp.exeM广东理工学院地图导航系统院通馆部办堂匾堂裨顺门*W栋堂东恩饭123456789012345e退出请输入您的选择:图4-94.3 调试过程问题分析调试过程中出现闪屏问题，应该是程序中的未知BUG问题；调试中又可能会出现崩溃，可能是调试过程调试不当，或者是程序语法有细小错误。解决问题方法：及时修复漏洞，完善语法。第5章总结5.1 收获与经验总结随着计算机软硬件的不断发展，导航系统在客户需求中的应用已成必然。本系统在开发中也是严格按照学校的实际情况进行开发的，在开发中，查阅了很多相关的算法资料，巩固了数据结构、C语言和c+方面的知识，同时也学习了新的算法知识。最重要的是在开发过程中，通过不断地学习，不断提高我们的编程能力和实际应用能力，还有助于改善我们的逻辑思维能力，这对我们以后对软件的开发提供很大的帮助。另外通过此次课程的设计使我们认识到对知识的掌握不全面，即在学习专业知识的同时还需要再加强其他方面知识的学习，因为软件的开发有时候涉及到其他方面的知识，只有了解了其他方面的知识才能收集资料，然后用于软件开发。5.2 存在问题与努力方向经程序调试和用实地运用后发现存在以下问题：地点与地点之间最短距离有一定的误差，确切的地点方位不明确；程序运行过程偶尔出现崩溃情况（经重新启动程序或重启可继续运行），数据显示不明确，乱码，编译错误，有时运行时异常。经小组各成员使用后反馈我们应该进一步完善地图及精确各地点间的最短距离，完善程序可能会出现的除语法外的问题。参考文献1黄露，谢忠，罗显刚.感知校园服务平台的设计与实现J.测绘科学，2015,40(9)：69-73.2陈卫卫，王庆瑞.数据结构与算法M.2版.北京：高等教育出版社，2015-07：90-102.3李林.基于GOOgleMaPSAPl的校园电子地图的设计与实现.科学论坛，2012(12)：66-69.4程钢，梁晓莉，张得群，蔡圣准.基于地图APl的校园在线电子地图设计与实现.测绘工程，2014,23(1)：5-11.5黄梅红.基于C#的泉州师范学院电子地图的设计与实现N泉州：新乡学院学报，2013(1):P20-P22.附录内容（小四、宋体，行距1.5倍、首行缩进2字符）