南京邮电大学数据结构实验三：图的基本操作与最小航班中转次数问题

简介：
本课程为南京邮电大学数据结构系列实验之一，重点讲解图的数据结构及算法实现，并通过求解最小航班中转次数问题来加深学生对图的应用理解。 ### 数据结构实验三知识点概述 #### 一、实验目的与要求 本次实验旨在通过实践操作加深学生对数据结构中“图”这一概念的理解，并能够运用所学知识解决实际问题。具体包括以下几点： 1. **掌握图的基本运算：** 学生需熟练掌握基于邻接矩阵和邻接表两种不同存储结构实现图的基本运算方法。 2. **图的应用问题解决：** 学习如何利用图算法解决实际问题，本实验以飞机换乘次数最少问题为例。 3. **模块设计：** 要求学生能够合理设计模块，使程序结构清晰。 4. **功能实现：** 实现的功能需丰富且满足题目要求。 5. **界面设计：** 提倡友好的用户界面设计，提高用户体验。 6. **程序质量：** 程序需具备较高的执行效率，同时注意内存管理。 #### 二、实验环境配置 - **硬件配置：** 微型计算机。 - **软件配置：** - 操作系统：Windows。 - 编程工具：Microsoft Visual C++6.0。 #### 三、实验内容详解 ##### 1. 图的基本运算 - **邻接矩阵表示** - **数据结构定义：** 定义了邻接矩阵结构体`mGraph`，包含二维数组`a`、顶点数`n`、边数`e`以及无边时的权值`noEdge`。 - **初始化：** 初始化函数为图的邻接矩阵分配空间，并设置初始值。每个元素被赋值为 `noEdge`, 除了自环元素被设为0。 - **插入边：** 插入边函数用于插入一条边，检查参数的有效性后更新邻接矩阵相应位置的值。 - **邻接表表示** - 未给出具体实现细节。通常会包括节点结构体和链表定义。节点结构体包含指向下一个节点的指针以及边权重信息，链表则代表图中一个顶点及其相连的所有边。 - **图的遍历** - 深度优先遍历 (DFS)：从某个顶点出发尽可能深入地搜索分支。 - 广度优先遍历(BFS): 从某一点开始先访问其所有邻居，然后再依次访问这些邻居的邻居。 ##### 2. 飞机最少换乘次数问题 - **问题描述**：给定n个城市和m条航线，找出起点到终点间所需换乘次数最少的飞行路线。 - **数据结构选择**: 使用有向图表示城市之间的关系。每个顶点代表一个城市, 每边代表一条航线且权值为1(一次换乘)。 - **算法选择**：使用Dijkstra算法解决此问题，该算法适用于非负权重加权图的单源最短路径计算。 - **实现要点** - 使用邻接矩阵或邻接表表示图结构； - 应用Dijkstra算法找到从起始点到所有其他顶点的最短路径; - 确保时间复杂度控制在O(n^2)以内，适用于规模较小的问题。 #### 四、实验报告要求 - **设计报告**：应全面反映系统的设计流程，并且合理正确。 - **文档内容**: 要详实, 全面覆盖所有实验细节。 - **文档格式**: 应规范美观便于阅读。 #### 五、实验总结 通过本次实验，学生不仅能深入理解图的基本概念和运算方法, 还能学会利用图算法解决实际问题。此外，还强调了程序设计的规范化及高效性的重要性，有助于提升学生的编程能力和解决问题的能力。