1、 课课 程程 设设 计计 说说 明明 书书 课程名称 数据结构课程设计 设计课题 校园导游程序 专 业 计算机科学与技术 班 级 学 号 姓 名 完成日期 课课 程程 设设 计计 任任 务务 书书 设计题目：设计题目： 校园导游程序校园导游程序 设计内容与要求：设计内容与要求： 问题描述 用无向网表示你所在学校的校园景点平面图， 图中顶点表示主要景 点，存放景点的编号、名称、简介等信息， 图中的边表示景点间的道路， 存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 基本要求 （1） 查询各景点的相关信息； （2） 查询图中任意两个景点间的最短路径。 （3） 查询图中任意两个景点间
2、的所有路径。 （4） 增加、删除、更新有关景点和道路的信息。 指导教师： 2016 年 12 月 20 日 课课 程程 设设 计计 评评 语语 成绩：成绩： 指导教师：_ 年 月 日 目录目录 一、 问题描述 1 二、 基本要求 . 1 三、 测试数据 . 2 四、算法思想 3 五、 模块划分 . 4 5.1 应用函数 4 5.2.1 主函数 5 5.2.2 查询景点信息函数 . 6 5.2.3 查询两景点之间最短路径函数 . 6 5.2.4 查询两景点之间所有路径函数 . 7 5.2.6 删除已有的顶点和路径 . 8 5.2.7 修改已有的顶点和路径 . 9 六、 数据结构 10 七、 测试
3、 11 八、 心得 19 九、 源程序 20 1 一、一、 问题描述问题描述 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放 景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等 信息。要求能够回答有关景点介绍、游览路径等问题。 二、二、 基本要求基本要求 （1） 查询各景点的相关信息； （2） 查询图中任意两个景点间的最短路径。 （3） 查询图中任意两个景点间的所有路径。 （4） 增加、删除、更新有关景点和道路的信息。 2 三三、 测试数据测试数据 菜单函数：依次输入：1，2，3，4，5，6，0 分别对应景点信息查询，最短路径查询，所有路径查询，添加景点
4、及路径 信息，删除景点及路径信息，修改景点及路径信息，退出。 查询景点信息：输入：1，2 分别对应按编号查询，按景点名称查询 按编号查询：输入编号：1 按景点名称查询：输入名称：大明桥 最短路径查询：输入起始景点和终点景点编号：1，7 所有路径查询：输入起始景点和终点景点编号：2，8 添加景点及路径信息：输入新景点序号：9 输入新景点名称：南门 输入新景点相关信息：充满古韵的门，适合拍照 输入到其余各景点的距离：50，100，20 删除景点及路径信息：输入：1，2 分别对应按编号查询，按景点名称查询 按编号查询：输入需要删除的景点编号：8 修改景点及路径信息：输入：1，2 分别对应修改景点信息
5、，修改道路信息 修改景点信息：输入 1，2 分别对应修改景点名称，修改景点描述 修改景点信息：输入修改序号：1 输入修改后的名称：图书馆 123 3 四四、算法思想、算法思想 先利用 CreateUDN 创建初始无向网，通过 main 主函数调用显示，操作功能 的选择通过 Menu 函数输出，根据游客需求选择景点信息查询、景点之间最短路 径查询、景点之间所有路径查询、添加景点信息、删除景点信息或者修改信息。 如果是景点信息查询， 在 search 中完成，再调用 SearchMenu 选择是按照景点 编号或者景点名称查询，游客输入相应内容。如果是景点之间最短路径查询或是 景点之间所有路径查询则
6、游客输入起始景点和结束景点；最短路径是用 ShortestPath 实现，其中运用了迪杰斯特拉算法；所有路径由 Searchpath1 调 用 disppath 再调用 path，在 path 中通过递归算法实现寻找每一条路并输出。 如果是添加景点信息调用 Addnewsight 函数，游客按照提示依次输入信息内容。 如果是删除景点信息，选择按照名称删除或是按照序号删除，再调用 Deletesight 函数，游客输入相应内容进行删除。如果是修改信息，调用 Changesight，Changemenu 两个函数，游客按提示选择修改景点信息或者道路信 息， 再按提示输入修改后得内容。 输出使用调用的相应函数。 信息保存于文件中。 校园导游图 添加景点 和路径 查询所有 路径 查询最短 路径 修改景点 和路径 修 改 路 径 修 改
