1、洛 阳 理 工 学 院课 程 设 计 说 明 书课程名称 数据结构课程设计 设计课题 校园导游程序 专 业 计算机科学与技术 班 级 学 号 姓 名 完成日期 课 程 设 计 任 务 书设计题目： 校园导游程序 设计内容与要求：问题描述 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。基本要求 （1） 查询各景点的相关信息；（2） 查询图中任意两个景点间的最短路径。（3） 查询图中任意两个景点间的所有路径。（4） 增加、删除、更新有关景点和道路的信息。指导教师
2、： 2016 年 12 月 20 日课 程 设 计 评 语成绩：指导教师：_年 月 日目录一、 问题描述 .1二、 基本要求 .1三、 测试数据 .2四、算法思想 .3五、 模块划分 .45.1 应用函数 .45.2.1 主函数 .55.2.2 查询景点信息函数 .65.2.3 查询两景点之间最短路径函数 .65.2.4 查询两景点之间所有路径函数 .75.2.6 删除已有的顶点和路径 .85.2.7 修改已有的顶点和路径 .9六、 数据结构 .10七、 测试 .11八、 心得 .19九、 源程序 .201一、 问题描述用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编
3、号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。二、 基本要求（1） 查询各景点的相关信息；（2） 查询图中任意两个景点间的最短路径。（3） 查询图中任意两个景点间的所有路径。（4） 增加、删除、更新有关景点和道路的信息。2三、 测试数据菜单函数：依次输入：1，2，3，4，5，6，0 分别对应景点信息查询，最短路径查询，所有路径查询，添加景点及路径信息，删除景点及路径信息，修改景点及路径信息，退出。查询景点信息：输入：1，2分别对应按编号查询，按景点名称查询按编号查询：输入编号：1按景点名称查询：输入名称：大明桥最短路径查询：输入起
4、始景点和终点景点编号：1，7所有路径查询：输入起始景点和终点景点编号：2，8添加景点及路径信息：输入新景点序号：9输入新景点名称：南门输入新景点相关信息：充满古韵的门，适合拍照输入到其余各景点的距离：50，100，20删除景点及路径信息：输入：1，2分别对应按编号查询，按景点名称查询按编号查询：输入需要删除的景点编号：8修改景点及路径信息：输入：1，2分别对应修改景点信息，修改道路信息修改景点信息：输入 1，2分别对应修改景点名称，修改景点描述修改景点信息：输入修改序号：1输入修改后的名称：图书馆 1233四、算法思想先利用 CreateUDN 创建初始无向网，通过 main 主函数调用显示，
5、操作功能的选择通过 Menu 函数输出，根据游客需求选择景点信息查询、景点之间最短路径查询、景点之间所有路径查询、添加景点信息、删除景点信息或者修改信息。如果是景点信息查询， 在 search 中完成，再调用 SearchMenu 选择是按照景点编号或者景点名称查询，游客输入相应内容。如果是景点之间最短路径查询或是景点之间所有路径查询则游客输入起始景点和结束景点；最短路径是用ShortestPath 实现，其中运用了迪杰斯特拉算法；所有路径由 Searchpath1 调用 disppath 再调用 path，在 path 中通过递归算法实现寻找每一条路并输出。如果是添加景点信息调用 Addne
6、wsight 函数，游客按照提示依次输入信息内容。如果是删除景点信息，选择按照名称删除或是按照序号删除，再调用Deletesight 函数，游客输入相应内容进行删除。如果是修改信息，调用Changesight，Changemenu 两个函数，游客按提示选择修改景点信息或者道路信息，再按提示输入修改后得内容。输出使用调用的相应函数。信息保存于文件中。校园导游图添加景点和路径查询所有路径查询最短路径修改景点和路径修改路径修改景点删除景点和路径按编号按名称查询景点信息按编号按名称修改名称修改描述4五、 模块划分5.1 应用函数void CreateUDN(int v,int a); /* 造图函数
7、*/void narrate(); /*说明函数*/void ShortestPath(int num); /*最短路径函数*/void output(int sight1,int sight2); /*输出函数*/int Menu(); /* 主菜单 */void search(); /* 查询景点信息 */int SearchMenu(); /* 查询子菜单 */void HaMiTonian(int); /* 图的遍历 */void Searchpath1(MGraph g); /*查询两个景点间的所有路径*/void disppath(MGraph g,int i,int j);voi
8、d path(MGraph g,int i,int j,int k);/*确定路径上第 k+1 个顶点的序号*/void NextValue(int); void display(); /* 显示遍历结果 */int Addnewsight(int n); /*添加新的景点和路径*/int Deletesight(); /*删除景点和路径*/void Changesight(); /*修改景点和路径*/int Changemenu(); /*修改路径或顶点的选择菜单*/int Sightmenu(); /*选择需该景点的菜单*/55.2.1 主函数1.功能：初始图通过 main 主函数调用显示
9、，操作功能的选择通过 Menu 函数输出，显示为菜单形式提醒用户进行操作，用户选择后在 main 主函数中调用各个函数实现各种功能。2.流程图：61014321 51输入相应序号结束开始查询信息 删除信息所有路径 添加信息最短路径 修改信息退出景点信息和操作目录65.2.2 查询景点信息函数1.功能：在 main 主函数中调用 search,打开存储了信息的文件，在显示界面显示已有的景点名称和序号，游客按需求进行序号查询或者名称查询，输入需要查询的序号或者名称后会显示该景点的名称及简介，而后按任意键返回上级菜单选择继续查询或者返回主界面，在查询景点信息函数中实现。2.流程图：5.2.3 查询两景点之间最短路径函数1.功能：在 main 函数中调用 narrate 函数，打开存储了信息的文件，游客输入起点编号或者终点编号，利用迪杰斯特拉算法 由 ShortestPath 最短路径函数 选择一条两点之间的最短路径展示给游客，关闭文件。noyes21开始按编号查询 按景点查询结束输入相关信息是否有此景点？没有找到！ 输出景点信息
