数据结构与算法课程设计--校园地图设计及其应用.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)
