1、 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：公园导游图 院（系）：计算机学院 专 业：计算机科学与技术 -I- 目目 录录 第第 1章章 概要设计概要设计 .1 1.1 题目的内容与要求 1 1.2 总体结构 2 第第 2章章 详细设计详细设计 .3 2.1 建立无向图模块 3 2.2 寻找最短路径模块 3 2.3 查询和输出结果模块 4 第第 3章章 调试分析调试分析 .5 第第 4章章 运行结果运行结果 .6 参考文献参考文献 .8 -1- 第 1 章 概要设计 1.1 题目的内容与要求题目的内容与要求 内容：给出一张某公园的导游图，
2、游客通过询问终端可知：从某一景点到另 一景点的最短路径。游客从公园大门进入，选一条最佳路径，是游客可以不重复 地游览各景点，最后回到出口（出口就在入口旁边） 。 要求： 1) 能够提供简单友好的用户操作界面，可以输入公园的景点信息，包括 景点名称、编号、与其他景点之间的距离等。 2) 景点信息能够保存在文件中。 3) 独立完成系统的设计、编码、和调试。 4) 系统利用 C 语言实现。 5) 按照课程设计规范书写课程设计报告。 -2- 1.2 总体结构总体结构 本程序主要分为三个模块（主要算法模块图见图 1.1） ：建立无向图模块、寻 找最短路径模块、查询和输出结果模块。建立无向图模块：输入景点
3、信息，包括 景点个数、名称、与其他景点之间的距离。寻找最短路径模块：floyd 算法-用于 实现每一对景点间的最短路径。 查询和输出结果模块： 输入要查找起始点和终点， 输出路径长度和路径始点和终点之间的景点编号。 图图 1.1 主要算法模块图主要算法模块图 公园导游图 建 立 无 向 图 寻 找 最 短 路 径 查 询 和 输 出 结 果 错误错误!未指定书签。未指定书签。 -3- 第 2 章 详细设计 在本次课程设计中，我们用到了图这个重要的数据结构。在实现程序的功能 的时候，有很多重要的程序段是涉及图方面的：有定义图的结构，图的建立，图 的邻接矩阵等等。重要的程序段如下。 2.1 建立无
4、向图模块建立无向图模块 本课程设计是通过图为载体来实现程序的功能的，因此图结构的定义和建立 是必不可少的。输入公园各景点的信息，如名称、编号、与其他景点之间的的距 离。流程图如图 2.1 所示 图图 2.1 2.1 建立无向图建立无向图模块流程图模块流程图 2.2 寻找最短路径模块寻找最短路径模块 将为未访问过的景点标记为 0，利用 for 循环访问各个结点，寻找最短路径， 记录在 pathsum 中，全部访问结束后，得到最佳路径。流程图如图 2.2 所示。 开始 存入文件 输入景点之间距离 输入景点个数及名称 结束 错误错误!未指定书签。未指定书签。 -4- 是 否否 图图 2.2 2.2
5、寻找最短路径寻找最短路径模块流程图模块流程图 2.3 查询和输出结果模块查询和输出结果模块 主要是输入要查询的景点，然后输出两景点之间的最短路径长度以及所经过 的景点。流程图如图2.2所示。 图图2.3 2.3 查询和输出结果查询和输出结果模块流程图模块流程图 开始 输入要查询的景点编号 输出最短路径长度以 及途径景点 结束 开始 是否访问完全部结点 如存在最短路径， 将值 赋给 minpath 将最短路径加入路径总和 结束 错误错误!未指定书签。未指定书签。 -5- 第 3 章 调试分析 （1）问题：由于输入时的疏忽遗漏了“； ” 、 “” 、 “） ”等，编译时出现错误。 解决方法：通过编
6、译器的错误提示进行修改，添加一些遗漏的信息。 （2）问题：在运行时提示库函数名为未标识符。 解决方法：通过编译器的错误提示进行修改，缺少头文件，添加所需的头 文件。 （3）问题：输入需要查找的景点时输入景点名称后无法显示最短路径等信息。 解决方法：规范输入格式。 错误错误!未指定书签。未指定书签。 -6- 第 4 章 运行结果 运行操作及结果： （1）显示请输入公园景点的个数。 （2）输入景点个数后，显示请输入景点信息，然后依次输入景点信息。 错误错误!未指定书签。未指定书签。 -7- （3）显示请输入公园的邻接矩阵信息，即各景点之间距离。 （4）显示最佳路径。 -8- 参考文献 1 严蔚敏,吴伟明.数据结构（C 语言版）M.北京:清华大学出版社,2007 2 王敬华，林萍，张清国.C 语言程序设计教程M（第二版）.北京:清华大学 出版社,2009.8 3 吴海燕,任午令,章志勇.数据结构M.杭州:浙江大学出版社,2011.6 4 胡圣荣,周霭如,罗穗萍.数据结构教程与题解M.北京:清华大学出版 社,2011.9 5 谭浩强.C
