校园导游系统.doc

课 程 设 计 说 明 书 课程名称： 数据结构与算法 设计题目： 校园导游系统 院 系： 计算机科学与信息工程学院 学生姓名： 学 号： 专业班级：计算机科学与技术信息技术方向11-1 指导教师： 2013年6月21日课 程 设 计 任 务 书设计题目校园导游系统学生姓名孙玮所在院系计算机科学与信息工程学院专业、年级、班11计科信息技术方向设计要求： 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题学生应完成的工作：孙 玮 图的结构以及初始化徐开放 一个景点到其他所有景点的最短路径王彩霞 景点的输出以及查询梁梦莉 两个景点之间的所有路径何冉冉 两个景点之间的最短路径郑银凤 增加，删除，修改景点信息参考文献阅读：1.数据结构(C语言版) 严蔚敏 吴伟民 编著 清华大学出版社 20112.C程序设计（第四版）谭浩强 主编 清华大学出版工作计划： 1、第一周的第一天：小组布置设计题目；说明进度安排。2、第一周的第二天：小组审题，查阅资料，进行设计前的必要资料准备。3、第一周的第三天、第四天、第五天：程序编写、上机调试4、第二周的第一天至第三天： 上机调试程序、结果分析。5、第二周的第四天： 撰写设计报告。6、第二周的第五天： 设计答辩及成绩评定。 任务下达日期： 2013年 6月 10 日 任务完成日期： 2013年 6月 21 日指导教师（签名）： 学生（签名）： 校园导游系统摘 要：随着社会经济的发展，人们接近自然的机会就越多，因此外出旅游现在被越来越多的都市人所看中，所以如何快速方便的找到我们想要的旅游景点的信息和最短路径，如何简单的修改相关的信息，就成了很重要的问题。本设计基于图的结构，用数组表示法创建一个无向图，针对游客的实际需求，将安阳工学院的景点编号、名称、介绍等信息放入到图的顶点当中，将路径长度的信息存放在弧当中。利用弗洛伊德算法求出两个景点之间的最短路径，利用迪杰斯特拉算法来求从一个景点到其他剩余的所有景点的最短距离；用相应的函数来查找景点，并显示出它的编号，信息，简介。并进行一定的界面美化，更贴近用户，相应的提示使用户操作起来更容易。关键词：最短路径、查找景点信息、无向图目 录1. 设计背景41.1程序设计内容41.2程序设计要求42设计方案52.1 校园景点图52.2 程序模块图52.3 主函数设计简要62.4 各函数模块的功能63. 方案实施73.1 程序执行流程图73.2 主函数设计思想74. 结果测试94.1 主函数功能模块测试94.2 主函数功能测试94.3 各功能所执行的操作125. 结论136. 收获与致谢147. 参考文献148. 附件141. 设计背景1.1程序设计内容根据设计要求，利用无向图将学校的景点作为图的顶点，顶点的边作为景点之间的距离进行存储，根据游客的需求，查找各个景点的信息，找出两个景点的最短路径，实现校园的导游目的。1.2程序设计要求用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。1、 景点信息和路径信息保存在文本文件，景点个数不少于20个2、 查询各景点的相关信息；3、 查询图中任意两个景点间的最短路径。4、 查询图中任意两个景点间的所有路径。5、 增加、删除、更新有关景点和道路的信息。6、 求多个景点的最佳（最短）游览路径。2设计方案2.1 景点抽象图校园景点抽象图比较直观的反应的校园景点的总体布局。图中顶点代表校园景点，顶点之间的边代表景点之间的路径，权值代表景点间的距离，两个顶点间没有边，表明两个景点不能直接到达。景点抽象图如图1所示： 图1景点抽象图 2.2 程序模块图图中在初始化阶段对无向图进行初始化，通过查找函数查找各个景点的信息，以及所有景点之间的最短距离，查找景点的位置和此景点在无向图中顶点的编号，最后就能退出程序。程序模块图如图2所示： 2.3 主函数设计简要 在程序的操作要求以及客户的需求下，在主函数设计中首先调用system（“cls”）函数显示第一个界面，此后显示出一个可视化的操作界面，可以为游客提供相关的景点的各种信息，并且提示游客做出最好的选择，便于其在后面的操作过程当中能够快速方便的找到其需要查找的景点。然后就要用到一个switch（）的选择函数，并用此函数实现程序的所有功能：景点信息一览表，景点信息的查询，两个景点之间的最短距离，两个景点之间的所有路径，增加、删除、修改景点信息，一个景点到所有景点的最短路径，清屏和退出程序。完成相关的选择操作后进入到选择的操作界面当中，从而实现所需要的功能。2.4 各函数模块的功能 1、调用无向网的初始化信息实现景点信息的查询以及全部输出 2、用弗洛伊德算法实现两个景点的最短路径的查询 3、用迪杰斯特拉算法实现一个景点到其余所有景点的最短路径的输出 4、用system（“cls”）函数实现清屏功能 5、用exit（）函数实现退出程序的功能。 3. 方案实施3.1 程序执行流程图流程图是算法设计中不可缺少的一部分，通过流程图，可以更加清晰的理解程序算法的过程，清楚算法的进程，使算法一目了然。流程图如图3-1： 图3 程序流程图3.2 主函数设计思想while(1) /无限循环完成程序的循环执行switch(choise)case 0: printall(G);break; /0.所有景点信息一览表 case 1: searchinfo(G); break; /1.景点信息查询 case 2: shortpath(G);break; /2.查询两个顶点间的最短路径 case 3: oubleall(G);break; /3.查询两个景点间所有的路径 case 4: changevex(G);break; /4.增加,删除,更新有关景点的信息 case 5: shortallpath(G);break; /5.一个景点到其他所有景点的 /最短路径（迪杰斯特拉） case 6: system(cls);break; /清屏 case 7: exit(0); /退出程序 default: break; 用一个无限循环实现程序的循环执行，但是死循环是无法自动退出的，因此增加7号功能，调用exit（）函数实现退出程序的操作。主函数采用模块化设计，将函数的功能放在函数中实现，简化主函数。相应的函数模块实现对应的功能1、0号（景点信息一览表）1号功能（查询景点信息）调用无向网的初始化信息实现景点信息的查询以及全部输出 2、2号功能（查询两个景点的最短路径）应用弗洛伊德算法实现两个景点的最短路径的查询3、3号功能（查询两个景点之间的所有路径）应用图的遍历查询两个景点间所有的路径4、4号功能（增加，删除，更新有关景点信息）更改无向网的初始化实现更改景点信息 5、5号功能（一个景点到其他景点的最短路径）实现一个景点到其他所有景点的最短路径（迪杰斯特拉）6、6号功能（清屏）调用system（“cls”）函数实现清屏功能，7、7号功能（退出程序）调用exit（）函数实现退出程序的功能。 4. 结果测试4.1 主函数功能模块测试 主函数的执行界面，测试结果如图4所示图4 主函数界面的运行结果4.2主函数功能测试1、在请选择查询的项目后输入0，按enter键，即完成0号功能测试，0号功能测试结果如图5所示图5 0号功能运行结果 2、在请选择查询的项目后面输入1，按enter键，即完成1号功能测试， 1号功能测试结果如图6所示图6 1号功能运行结果 3、在选择项目后输入2，完成2号功能，2号功能的运行结果如图7所示 图7 2号功能的运行结果 4、在请选择查询的项目后输入3，按enter键，即完成3号功能的测试，3号功能测试结果如图8所示图8 3号功能运行结果 5、在选择查询的项目后输入4，即完成4号功能的测试，4号功能的运行结果如图9所示图9 4号功能的运行结果6、在选择的项目后输入5，即完成5号功能的测试，5号功能的测试结果如图10所示 图10 5号功能的运行结果4.3 各功能所执行的操作 共有8个功能，各个功能所执行的操作如下所示 0号功能：景点信息一览表 1号功能：查询景点信息 2号功能：查询两个景点的最短路径 3号功能：查询两个景点之间的所有路径 4号功能：增加，删除，更新有关景点信息 5号功能：一个景点到其他景点的最短路径 6号功能：清屏 7号功能：退出程序5. 结论 经过这次课程设计，我对程序中算法的概念理解的更加透彻。算法是程序中必不可少的部分，它是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。同时，在选择算法时必须考虑算法的时间复杂度和空间复杂度，这样才能让程序正常，高效的运行。数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机的硬(特别是编码理论、存储装置和存取方法)的研究范围,而且和计算机软件的研究有着更密切的关系,无论是编译程序还是操作系统,都涉及到数据元素在存储器中的分配问题.在研究信息检索时也必须考虑如何组织数据,以便查找和存取数据元素更为方面。因此,可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程.在计算机科学中,数据结构不仅是一般程序设计(特别是非数值计算的程序设计)的基础,而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。6. 收获与致谢首先，在本次作业中，通过运行程序，我对无向图的运用有了更深的理解，对它的方法又加以掌握，为以后的学习增加了基础。小组内成员的分工不同，负责的模块不同，但大家能够齐心协力，共同努力。感谢成员的不懈努力，正有了成员的配合 ，才顺利完成做业。还要感谢孙高飞老师的教导，正因为有他的帮助，有他知识的教育，我们才能够运用无向图将学校景点化，顺利完成作业。7. 参考文献1.谭浩强. C程序设计（第四版)J. 清华大学出版, 20102.严蔚敏，吴伟民. 数据结构 (C语言版)J.清华大学出版社, 20118. 附件指导教师评语：1、课程设计报告：a、内容： 不完整 完整 详细 b、方案设计： 较差 合理 非常合理c、实现： 未