1、校园导航系统 数据结构课程设计 C+开发分类号 编 号 华北*大学 North China Institute of Water Conservancy and Hydroelectric Power 课 程 设 计题目 校园导航 院 系 信息工程学院 专 业 计算机科学与技术 姓 名 * 学 号 201117000 指 导 教 师 * 2012年7月 6 日 1.需求分析 11.1问题描述 11.2课程设计目的 11.3设计要求 12.概要设计 22.1任务定义 22.2数据结构 22.3 校园平面图展示 22.4系统功能图 43.详细设计 43.1各个模块名称和功能 43.2具体函数模块详
2、解 53.2.1校园平面图展示 53.2.2任意两点的所有路径 53.2.3校园基础设施介绍 63.2.4指定两点间最短路径 63.2.5单点到其他左右顶点间最短路径 63.2.6华北水利水电学院简介 73.2.7访客留言 73.2.8浏览访客留言 73.3 主要算法思想描述 73.4各函数之间的调用关系示意图 74.测试与分析 84.1测试显示 84.2调试分析 124.21调试过程中遇到的问题与解决方案 124.2.2算法的时空复杂度分析 125.用户使用说明 126.实验总结 147.参考文献 148.附件 15 校园导航系统1.需求分析1.1问题描述我们熟悉一个地方的地形情况通常是借助
3、于一张地图，通常的地图包含的信息十分的有限，而且具体到某一个建筑物，你不能了解到它的进一步的详细的情况。因此，导航系统就应运而生了。具体到本系统，作为用户浏览校园时，只拿着学校的地图是能够游遍全校，但是各建筑内部的情况就必须实地考察才能了解，既费时又费力。有了我们的校园的导航系统，用户可以根据自己的需要，迅速找到所关心的地点，并且可以看到它的详细的信息。1.2课程设计目的本课程设计的目的就是要达到理论与实际应用相结合，使我们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，培养程序设计技能如下：(1)了解并掌握数据结构算法的设计方法，具备初步的独立分析和
4、设计能力；(2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；(3) 独立完成，提高运用所学的理论知识和方法独立分析和解决问题的能力；1.3设计要求设计一个校园导航系统，为来访的客人提供导航服务，具体要求：(1) 设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。（2）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息(3) 为来访客人提供图中任意景点相关信息的查询。(4) 提供途中任意景点问路查询，即求任意两个景点间的一条最短的简
5、单路径以及任意景点到其他所有景点的最短路径查询。(5) 列出所有校内无重复排列的景点，将所有景点的距离以邻接矩阵的方式呈现给使用者，提供使用者选择功能界面，按照提示进行操作。 2.概要设计2.1任务定义本系统包含一个文件，设计分有菜单、显示信息、弗洛伊德算法、迪杰斯特拉算法，其中弗洛伊德算法是求两个景点之间距离最短的算法，同时在本系统中又添加一些新的功能，这些在模块分析中将介绍到，本系统的基本任务有1）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2）为来访客人提供图中任意景点相关信息的查询。3）为
6、来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径2.2数据结构class CNode /留言功能建立的类 public: CNode(char *strMessage1,char *strTime1,int visited1); char strMessageID_LEN; char strTime30; int visited; CNode *next;class CList /建立链表，并保存链表的内容（留言的内容）public: void Save();void Load(); void Show(); void InsertToLast(char* strMessa
7、ge,char* strTime,int visited); CNode* Tail();private: CNode m_head; typedef struct edgenode /声明邻接表所定义的结构体 int adjvex; int value; struct edgenode *next;ArcNode;typedef struct vexnode char data15; ArcNode * firstarc;VHeadNode;typedef struct VHeadNode adjlistn;AdjList 2.3 校园平面图展示本课程设计的内容为“校园导航”，校园平面图中取
8、华北水利水电学院的7个常去地点，在图中已标出主要路线，各路线的长度如图中所示，本系统的基本任务是设计你的学校的平面图，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径，为来访客人提供图中任意景点相关信息的查询，同时为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径，其平面图如下： 180 100 150 50 80 150 50 120 30 80 120 200 22050100 100 300 140 300 100 50 180 270 80 80 280 50 220 200 250 图1 华水校园平面图2.4系统功能图图2 系统功
9、能图3.详细设计3.1各个模块名称和功能本系统可以分为9个模块，每个模块实现了一种功能，同时每个模块中又有若干个函数构成，即各个模块的名称和实现的功能如下表：源文件 模块名称 校园导航.cpp校园平面图展示利用邻接表的方法展示校园各个设施的大概位置任意两点的所有路径任意两个景点之间距离小于4的所有路径校园基础设施介绍任意输入一个设施名称，显示对应设施的基本信息指定两点间最短路径提供任意两点间最短路径单点到其他左右顶点间最短路径单点到其他点所有最短路径华北水利水电学院简介介绍我校基本情况，让访客更加了解我校访客留言访客可以直观的评价我校浏览访客留言访客可以浏览他人或自己的留言退出程序退出导航系统
10、表1 模块功能略图3.2具体函数模块详解3.2.1校园平面图展示平面图展示包含的函数有show ()和MatToList(Graph &t,AdjList *&G)，在show ()函数中调用MatToList(Graph &t,AdjList *&G)，将初始化的邻接矩阵转换为邻接表，然后将邻接表显示在程序中，比较笼统地展示了校园的平面图。3.2.2任意两点的所有路径该模块是新添的功能，在任意两点的所有路径模块中包含的函数有PathAll() , MatToList(Graph &t,AdjList *&G)和T_PathAll(AdjList *G,int u,int v,int l,in
11、t path,int d)，其中PathAll()是调用T_PathAll(AdjList *G,int u,int v,int l,int path,int d)，然后返回给主函数bool值，判断程序的下一步的操作，MatToList(Graph &t,AdjList *&G)是将邻接矩阵转化为邻接表，而本模块中最重要的函数是T_PathAll(AdjList *G,int u,int v,int l,int path,int d)。该函数核心代码是利用回溯的深度优先搜索方法，从定点u开始，进行深度优先搜索。由于在搜索过程中，每个顶点只访问一次，所以这条路径必定是一条简单路径。因此，只要在搜
12、索过程中，需要把当前的搜索线路记录下来。为了记录当前的搜索线路，设立一个数组path保存走过的路径，用d记录走过的长度。若当前扫描到的结点u到结点v的长度不大于l,表示找到了一条路径，则输出路径path. 3.2.3校园基础设施介绍 该模块中的核心函数是Search()，其核心代码是此函数用于为用户提供相关信息的查询服务，本函数提供华北水利水电学院相关基础设施的查询服务。用户只需输入相关的设施名称就能查询到相关的华北水利水电学院基础设施的相关信息。3.2.4指定两点间最短路径本模块中包含的函数有shuangdian()和pointpath(Graph &t1,char cstart,char
13、cend)，此函数为一辅助函数，该函数体中调用了pointpath(Graph &t1,char cstart,char cend)，实际上该函数的功能就是求出起始点到终点的最小路径，只不过为了更好在函数调用过程中理清各函数间的关系同时也是为了使界面设计过程中避免各基础函数代码冗余，从而引进该函数做辅助用。本模块色核心函数是pointpath(Graph &t1,char cstart,char cend)，该函数核心代码为迪杰斯特拉算法，用以求任意两景点之间最短路径。具体思想为设置并逐步扩充集合path，存放以求出的最短路劲的顶点，尚未确定最短路径的顶点放置在另一集合V中，按最短路径长度的递
14、增顺序将V中的顶点加到path中，直到path中包含所有顶点。实现过程中引入了一个辅助数组distance，它的每一个分量distancei表示当前找到的从原点到终点的最短路径的长度。3.2.5单点到其他左右顶点间最短路径本模块在以狄克斯特拉为原型的基础上稍加改变，在采用狄克斯特拉算法时新增一个终点参数，在输出最小路径时不需要使用for循环将所有原点与其他顶点的路径信息输出，只需输出起点和终点两点间的最短距离即可。本模块中包含的函数有dandian()和shortest_path(Graph &t,char csource)，此函数为一辅助函数，该函数体中调用了shortest_path(Gr
15、aph &t,char csource)，实际上该函数的功能就是求出一点到其他所有点的最小路径，只不过为了更好在函数调用过程中理清各函数间的关系同时也是为了使界面设计过程中避免各基础函数代码冗余，从而引进该函数做辅助用。单源最短路径采用狄克斯特拉算法，在集合s的初态只表包含顶点，当是si为0时表示未找到源点到顶点的最短路径，当si为1时表示已找到源点到顶点的最短距离，数组distance记录从源点到其他各顶点当前的最短距离，起初值为distancei= t.arcsbi(b为源顶点)，从s之外的顶点集合中选择一个顶点，使distanceu的值最小，于是从源点到达v只通过s中的顶点，把u加入集合
16、s中调整distance中的记录从源点到每个顶点的距离：从原点的distancej和distanceu+ t.arcsuj中选择较小的值作为新的distancej,重复上述过程，直到s中包含其余各顶点的最短路径。另外设置一个数组path用于保存最短路径长度，其中pathi保存从源点到终点当前最短路径中的前一个顶点的景点名称， 3.2.6华北水利水电学院简介该模块是新添的功能，在该模块中的核心函数是Intro()，其核心代码是输出华北水利水电学院的办学历史和发展状况，该模块比较简单，就不在这里赘述了！3.2.7访客留言该模块是新添的功能，在该模块中的核心函数是W()，在该函数中应用了文件，其目的
17、是将历史记录保存下来，以供访客浏览，在该函数中遇到的问题是留言条数变量intV，如何让它真实的显示出来留言条数，我解决的办法是把变量intV也写入到文件中，在每次保存留言时读出该变量，使该变量加1，把留言写入到文件后，将重新把该变量写入到文件中，依次进行，这样就把留言写入到文件中，而留言记录也是正确的数值，同时留言时间是调用系统函数ctime(),这样访客留言就完成了。3.2.8浏览访客留言该模块是新添的功能，在该模块中的核心函数是R()，在该函数中应用了文件，是将访客的留言读出来，同时将要更新留言记录中的留言条数变量。3.3 主要算法思想描述 迪杰斯特拉算法思想 按路径长度递增次序产生最短路
18、径算法：把V分成两组：（1）已求出最短路径的顶点的集合（2）尚未确定最短路径的顶点集合，将T中顶点按最短路径递增的次序加入到S中。保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点：从V0到此顶点的最短路径长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。3.4各函数之间的调用关系示意图主函数main()菜单函数menu() 选择1 选择2 选择3 选择4 选择5 选择6 选择7 选
19、择8 图 3 各函数调用示意图4.测试与分析4.1测试显示图 4 主界面在主界面中可以显示本系统中包含的所有操作，用户可以选择对应操作的序号，输入正确将进入对应的操作界面。图 5 两点路径小于4的路径在该界面中显示所有从起点景点到终点景点长度小于4的所有路径，在所有的路径中可以选择其中的一条路线。图6 基础设施介绍 用户可以输入导航景点中出现的景点名称，程序将出现相对应景点的基本信息，在该过程中如果输入的景点错误，系统将循环出现要求用户输入正确的景点名称。图 7 两景点最短路径用户将在这一界面根据导航景点名称中出现的景点输入起点景点和终点景点，输入正确后，将会出现一条最短了路径，在该路径中包含
20、有经过的景点名称，和两个景点之间的距离。图8 一点到其他景点的最短距离用户将在这一界面根据导航景点名称中出现的景点任意输入一个景点名称，输入正确后，将会出现若干条该景点到其他景点的最短了路径，在这些路径中包含有经过的景点名称，和两个景点之间的距离。图 9 华水简介本界面中将介绍华北水利水电学院的办学历史和近年来取得的成就，以及华水的人文和育人环境，。图 10 访客留言 本界面是访客留言，在该界面中用户可以输入字数小于300的留言内容，留言完毕后，将会出现“你的留言成功！”提示语，同时出现两个菜单选项，可供用户选择。图 11 浏览访客留言本界面是浏览访客留言，在该界面中访客可以浏览本人的留言和其
21、他访客的留言，在显示留言内容外，还显示留言时间和留言总记录的条数。4.2调试分析4.21调试过程中遇到的问题与解决方案本系统中的重要内容是最短路径，在运用最短路径时经常使用的算法是弗洛伊德算法，在这个算法中出现了一个错误，就是在输入一条路径长度大于3的路径时仅仅显示3个景点名称，在系统中使用断点进行测试，发现在系统中一个循环语句使用错误，经过改正后，可以输出该条路径上所有的景点名称。同时在系统中新添了一个功能中，就是输出两点之间路径小于4的所有简单路径，在这个过程中，忽略了把对应的两点距离输出，或者是挑选出几条最有的路径，这些是经过老师的指导下发现了诸多的问题，希望在以后注意到这些问题。4.2
22、.2算法的时空复杂度分析对应题目的要求，我总共提供了八个选项操作对于每一个操作的分析如下：1.校园平面图展示，实现这个功能仅仅显示出来关于华北水利水电学院的17个经常去的景点，用邻接表大概表示学校景点的地理位置，故其时间复杂度为o(1)，空间复杂度为o(1)；2任意两点的所有路径，实现这个功能用到了Floyd算法，他用到了一个三重的for()循环，故其时间复杂度为o(n3)，空间复杂度为o(1)；3.校园基础设施介绍，在这个操作中允许使用者输入一个景点名称，然后再根据景点名称来或取其相关的信息，这个操作要扫描线性表，其时间复杂度为o(n)，空间复杂度为o(n)；4.定两点间最短路径，实现这个功
23、能用到了Floyd算法，他用到了一个三重的for()循环，故其时间复杂度为o(n3)，空间复杂度为o(1)；5.到其他左右顶点间最短路径，实现这个功能用到了Floyd算法，他用到了一个三重的for()循环，故其时间复杂度为o(n3)，空间复杂度为o(1)；6.水利水电学院简介，实现这个功能仅仅显示出来关于华北水利水电学院的基本信息，故其时间复杂度为o(1)，空间复杂度为o(1)；7.访客留言，实现这一功能要使用文件，首先建立链表，将留言存放在链表中，将链表的内容存放到文件中，时间复杂度为o(n)，空间复杂度为o(1)； 8. 浏览访客留言，首先将存放在文件中的留言读出存放在链表中，将链表的内容
24、显示出来，时间复杂度为o(n)，空间复杂度为o(1)；其他操作的时空性1在系统的设计中考虑到道路网的复杂性，故采用邻接矩阵作为存储结构，其空间复杂度为O（e）此时的空间复杂度也为O(e)。构建邻接矩阵的时间复杂度为O（n2+e*n），故本系统在构件图的时候的时间复杂度为O（n2+e*n）。2由于本系统在执行的时候，需要用户临时输入求最短的路径。迪杰斯特拉算法的时间复杂度比弗洛伊德算法的时间复杂度低。从这一角度考虑用地杰斯特拉算法更为合适。且其算法的时间复杂度为O（n3）.5.用户使用说明本系统使用说明：当用户将程序经过编译，连接后，点击运行，在DOS环境里面将看到一个选项菜单，菜单里面提供了8
25、种操作，同时输出了一行提示信息：“请选择导航功能”，然后用户可以输入一个18之间的数字进行选择性的操作，例如，您想进行显示华北水利水电学院平面图，您可以从键盘输入数字1，这样华水的校园平面图将显示出来；同时，您想查询华北水利水电学院的基础设施，您可以从键盘中输入数字“3”，当然，一般而言先应该进行“浏览所有景点名称”操作。如果您选择了浏览所有景点名称操作，在屏幕上将会显示出17个景点的名称，这些景点是事先加进去的，用户可以对这些景点进行任何程序所提供的操作。下面，我将详细介绍本程序的使用方法：在浏览景点后，菜单将会继续显示出来，为您提供操作选择。 如果您想进行“校园平面图展示”操作，输入数字1
26、，然后程序将以邻接表的形式显示出来华水的平面图，显示完毕后，显示出两个菜单 1.返回主菜单 2.退出程序，选择1可以返回到主菜单，选择2可以退出程序。如果您想进行“任意两点的所有路径”操作，首先输入数字2，然后程序将会提醒您输入起始景点名称，接着提醒输入终点景点名称，在该操作中如果输入错误，将显示出两个菜单 1.返回主菜单 2.退出程序，选择1可以返回到主菜单，选择2可以退出程序；输入正确，系统将显示出全部长度小于4的所有路径，接着系统出现三个菜单1.返回主菜单 2 返回上一级 3退出程序，我们可以跟着提示选择自己的操作。如果您想进行“校园基础设施介绍”操作，首先输入数字3，然后程序将会提醒您
27、输入要查询景点名称，在该操作中如果输入错误，将显示出一句提示“Iam sorry,我校没有此类设施!”接着系统出现三个菜单1.返回主菜单 2 返回上一级 3退出程序，我们可以跟着提示选择自己的操作；如果输入的景点名称正确将显示出该设施的基本信息，同时会出现三个菜单1.返回主菜单 2 返回上一级 3退出程序，我们可以跟着提示选择自己的操作。如果您想进行“指定两点间最短路径”操作，首先输入数字4，然后程序将会提醒您输入起始景点名称，接着提醒输入终点景点名称，在该操作中如果输入错误，系统将进行循环的要求输入景点的名称，直到输入的景点名正确；如果输入正确，系统将显示出两个景点之间的最短路径，接着系统出
28、现三个菜单1.返回主菜单 2 返回上一级 3退出程序，我们可以跟着提示选择自己的操作。如果您想进行“单点到其他左右顶点间最短路径”操作，首先输入数字5，然后程序将会提醒您任意输入一个景点名称，在该操作中如果输入错误，系统将进行循环的要求输入景点的名称，直到输入的景点名正确；如果输入正确，系统将显示出该景点到其他景点的所有最短路径，接着系统出现三个菜单1.返回主菜单 2 返回上一级 3退出程序，我们可以跟着提示选择自己的操作。如果您想进行“华北水利水电学院简介”操作，首先输入数字6，接着将显示出华北水利水电学院的简单介绍，接着系统出现两个菜单1.返回主菜单 2退出程序，我们可以跟着提示选择自己的
29、操作。如果您想进行“访客留言”操作，首先输入数字7，接着将显示出提示“你输入你的留言(300字以内)”，输入完成后，接着系统出现提示“你的留言成功!”和两个菜单1. 继续留言 2退出，我们可以跟着提示选择自己的操作。如果您想进行“浏览访客留言”操作，首先输入数字8，接着将显示出所有的留言记录，接着将出现两个菜单1. 继续浏览 2退出，我们可以跟着提示选择自己的操作。 这些将是本系统中的全部操作说明，请使用者务必按步骤操作。备注：经过测试，本程序的所有操作都能正常执行，您可以选择性的对他进行操作。 6.实验总结本次课程设计的题目是校园导航系统，校园导航体现了一个管理系统的需求分析、系统设计、数据
30、结构设计、界面设计和开发实现的完成过程，同时经过这两周紧张而又充实的课程设计，使我对数据结构这一门课程的相关知识有了全面深刻的认识，尤其是对图这一数据结构的相关知识掌握的更加全面和牢固，特别是对迪杰斯特拉算法的思想和具体实现有了进一步的认识。在这次试验中，我实现了课题选定、资料查找、流程图设置、各模块的算法 设计、各模块和主程序的源程序编程、最后的调试等步骤、最后的调试等步骤，完成了“校园导航系统”这个程序的设计，在确定了大致上的方向后，我也遇到了很多细节方面的问题，不过在我的努力在，一个个问题都最终解决了，通过这次课程设计，是我充分认识了自己一些方面的不足，同时经过课程设计时与同学们不断讨论
31、，使我对数据结构有了更深入和更全面的认识。同时经过此次课程设计，使我懂得任何一门计算机语言学习，都是应该理论与实际的结合，光有理论知识是不行的。数据结构这门课程的学习已经告一段落，但不代表这门课程的学习彻底结束，同时通过本次课程设计暴露出还有很多很多的知识还没掌握，同时也暴露了我在很多上面有误解，每门课都是要踏踏实实的学的，而不是到考前恶补，可能成绩会比较好看，但是实际就什么都不会了，脚踏实地是非常重要的学习态度，同时也是很重要的重要的态度。 本次实验对于我来说是非常重要的经历，因为在做程序的过程中，基本上体验了课题选定、资料查找、流程图设置、各模块的算法设计、各模块和主程序的源程序编程、最后的调试等步骤的流程，为我们以后做项目打
