数据结构课程设计实例探讨之校园导航设计

2022-11-19

数据结构课程设计是数据结构课程中的重要教学环节, 是锻炼学生理论联系实际的重要手段。通过数据结构课程设计要求学生掌握数据结构与算法的设计方法, 具备初步的独立分析和设计能力;初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;提高综合运用所学的理论知识和方法独立分析和解决问题的能力;训练用系统的观点和软件开发一般规范进行软件开发, 培养软件工作者所应具备的科学的工作方法和作风。

1 问题的提出及设计所要实现的功能

现代社会, 新兴科技日新月异, 信息千变万化, 人们在渴望得到最多最广的信息的同时又渴望得到信息的路径能越来越简单, 易操作, 而且能在简易的操作中得到更多的信息。这就要求信息咨询系统的开发者在开发之时能尽可能的全面理解客户的想法要求, 而且在开发的时候能更简易的操作和更新, 这种思想都符程序设计的开发思想。本次设计其实就是数据结构中图类的问题。将校园景点作为图的结点, 将景点间的路径作为图的边, 路径距离作为边的权值。这样一来, 求两景点间最短路径的问题就抽象成了求图中一结点到另一结点的问题。

以图的邻接表表示法表示校园平面图, 在此基础上实现求校园任意两点的最短路径。要求设计类 (或类模板) 来描述图, 包含必要的构造函数和析构函数, 以及其他能够完成如下功能的成员函数: (1) 输入图、输出图; (2) 查询给定建筑信息; (3) 求校园平面图中任意两点的最短路径, 并输出路径及路径长度; (4) 任意输入两点, 查询出该两点是否存在最短路径;最后, 设计主函数测试该类 (或类模板) 。

2 涉及到的知识内容

显然, 这需要利用数据结构中图的相关知识来解决此次设计。需要选取一种图的存储结构 (比如邻接表) 来存放校园各个建筑所代表的顶点, 以及建筑之间的距离;要实现以上功能就需要理解并应用相关算法:构造图、图的遍历 (深度优先或广度优先) 、最短路径的算法、栈或者队列的相关算法。程序实现拟用面向对象的设计思想, 用C++完成编程。

3 方案的确定及功能模块说明

校园导航系统要求实现诸多功能, 可将软件设计任务划分成许多容易解决的小的子任务, 即分解出许多子功能模块进行设计。本程序经过分析可划分出9个子模块: (1) 建立图的信息:按邻接表存储输入图的信息。 (2) 从文件中读取图的信息:把文件中的原有信息读入, 为程序使用。 (3) 输入并保存景点简介信息:重新输入图的景点或是建筑信息并保存到文件中。 (4) 读取并查找简介信息:在文件中读入信息, 查找指定建筑的简介信息。 (5) 输出图邻接表:输出图的邻接表信息。 (6) 按广度优先遍历图:按广度优先规则遍历并输出遍历结果。 (7) 输出结点间的距离:输入一个节点输出所有节点到它的距离。 (8) 输出结点间的路径:输入一个节点输出所有节点到它的距离及其具体路径。 (9) 书写文件信息:书写有关文件信息。如:景点或是建筑简介、图的邻接表信息、密码。

4 类的定义及说明

为使程序更具有普遍性, 为此我们采用模板来设计数据类型和类:

以上为类模板的声明, 其中包含数据成员与函数成员的声明, 各个函数成员用以实现前期分析中所定义的各个功能模块。限于篇幅, 详细程序不再详述。

5 结语

校园导航设计是计算机代替人工的一个实例, 也是软件工程必不可少的基础。通过学生生活中具体的实例来设计数据结构课程设计题目, 可以让学生更容易产生学习的兴趣, 从而调动探索问题、解决问题的积极性, 使得学生们更容易的体会课程中的理论知识在具体实践中的应用与指导;通过用C++实现数据结构的课程设计, 在使学生理解加深数据结构知识的同时也能进一步体会面向对象的程序设计思想

摘要：数据结构课程设计是数据结构课程中的重要教学环节;本次设计其实就是数据结构中图类的问题。将校园建筑作为图的顶点, 将建筑间的路径作为图的边, 路径距离作为边的权值。这样, 求两建筑间最短路径的问题就抽象成了求图中一顶点到另一顶点的问题。

关键词：数据结构,图,路径,距离