数据结构课程设计报告公园导游图

沈阳航空航天大学

课 程 设 计 报 告

课程设计名称：数据结构课程设计 课程设计题目：公园导游图

院（系）：计算机学院 专 业：计算机科学与技术

-

- 好好学习，天天向上

目 录

第1章 概要设计 ............................................................................................................ 0 题目的内容与要求 ....................................................................................................... 0 总体结构 ....................................................................................................................... 1 第2章 详细设计 ............................................................................................................ 2 建立无向图模块 ........................................................................................................... 2 寻找最短路径模块 ....................................................................................................... 2 查询和输出结果模块 ................................................................................................... 3 第3章 调试分析 ............................................................................................................ 4 第4章 运行结果 ............................................................................................................ 5 参考文献 .......................................................................................................................... 7

-

- 好好学习，天天向上

第1章 概要设计

题目的内容与要求

内容：给出一张某公园的导游图，游客通过询问终端可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路径，是游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。

要求：

1) 能够提供简单友好的用户操作界面，可以输入公园的景点信息，包括

景点名称、编号、与其他景点之间的距离等。 2) 景点信息能够保存在文件中。

3) 完成系统的设计、编码、和调试。 4) 系统利用C语言实现。

5) 按照课程设计规范书写课程设计报告。

-0

- 好好学习，天天向上

总体结构

本程序主要分为三个模块（主要算法模块图见图）：建立无向图模块、寻找最短路径模块、查询和输出结果模块。建立无向图模块：输入景点信息，包括景点个数、名称、与其他景点之间的距离。寻找最短路径模块：floyd算法-用于实现每一对景点间的最短路径。查询和输出结果模块：输入要查找起始点和终点，输出路径长度和路径始点和终点之间的景点编号。

公园导游图 建立无向图 寻找最短路径 查询和输出结果 图 主要算法模块图

-1

- 好好学习，天天向上

第2章 详细设计

在本次课程设计中，我们用到了图这个重要的数据结构。在实现程序的功能的时候，有很多重要的程序段是涉及图方面的：有定义图的结构，图的建立，图的邻接矩阵等等。重要的程序段如下。

建立无向图模块

本课程设计是通过图为载体来实现程序的功能的，因此图结构的定义和建立是必不可少的。输入公园各景点的信息，如名称、编号、与其他景点之间的的距离。流程图如图所示

图 建立无向图模块流程图

结束 输入景点之间距离 输入景点个数及名称 存入文件 寻找最短路径模块

将为未访问过的景点标记为0，利用for循环访问各个结点，寻找最短路径，记录在pathsum中，全部访问结束后，得到最佳路径。流程图如图所示。

-2

- 好好学习，天天向上

是否访问完全部结点 是

否 如存在最短路径， 将值赋给minpath 开始 将最短路径加入路径总和 结束 图 寻找最短路径模块流程图

查询和输出结果模块

主要是输入要查询的景点，然后输出两景点之间的最短路径长度以及所经过的景点。流程图如图所示。

图 查询和输出结果模块流程图

-3

开始 输入要查询的景点编号 输出最短路径长度以及途径景点 结束 - 好好学习，天天向上

第3章 调试分析

（1）问题：由于输入时的疏忽遗漏了“；”、“}”、“）”等，编译时出现错误。 解决方法：通过编译器的错误提示进行修改，添加一些遗漏的信息。 （2）问题：在运行时提示库函数名为未标识符。

解决方法：通过编译器的错误提示进行修改，缺少头文件，添加所需的头文件。

（3）问题：输入需要查找的景点时输入景点名称后无法显示最短路径等信息。

解决方法：规范输入格式。

-4

- 好好学习，天天向上

第4章 运行结果

运行操作及结果：

（1）显示请输入公园景点的个数。

（2）输入景点个数后，显示请输入景点信息，然后依次输入景点信息。

-5

- 好好学习，天天向上

（3）显示请输入公园的邻接矩阵信息，即各景点之间距离。

（4）显示最佳路径。

-6

- 好好学习，天天向上

参考文献

[1] 严蔚敏,吴伟明.数据结构（C语言版）[M].北京:清华大学出版社,2007 [2] 王敬华，林萍，张清国.C语言程序设计教程[M]（第二版）.北京:清华大学出版社,

[3] 吴海燕,任午令,章志勇.数据结构[M].杭州:浙江大学出版社,

[4] 胡圣荣,周霭如,罗穗萍.数据结构教程与题解[M].北京:清华大学出版社, [5] 谭浩强.C程序设计试题汇编[M].北京:清华大学出版社,

[6] 李兵,崔虹燕,马晓亭.C语言程序设计[M].北京:科学出版社,2011

-7

- 好好学习，天天向上

课程设计总结： 这次数据结构课程设计，从理论到实践，让我对数据结构有了更深刻的认识，也学到了很多东西，不仅巩固了以前所学过的知识，而且还学到了很多书本上所没有的内容。我在此次课程设计中深刻体会到了要写好一个程序必须弄清它的最基本的思路，除此之外要有算法思路，会写一些基本函数。编程不像做其它事，它要求编程人员有非常缜密的思维，很好的整体把握能力和很好的调试程序的能力等，也要特别注重细节。我在编写程序过程中遇到了很多的问题，一些基本的函数应用不熟练，让我发现了自己的知识的匮乏，掌握的不够牢固，懂得了只学书本上的东西是远远不够的，只有把所学的理论知识与实践相结合起来，才能真正的学到东西，才能提高自己的实际动手能力和思考能力。 在程序运行成功的时候，我的心里是非常喜悦的，这些天的努力终于有了回报。在以后的学习过程中要多了解一些基本的函数、算法和编程思想，更要多动手写一些程序，不要怕程序出错，争取在改错的过程中找到自己知识的漏洞和模糊点。虽然我编写的程序离真正可以实际应用还有很长的距离，但程序需要完善，人需要不断的学习，我想，经过日后的不断努力，我一定会编写出真正可以实际应用的程序。最后，我要感谢老师和对我的教导和帮助，在百忙之中抽出时间对我遇到的问题进行解决，使我能够顺利的将程序编写完成，我表示由衷的感激。 指导教师评语： 指导教师(签字)： 年 月 日 课程设计成绩

-8