《数据结构》课程设计：弗洛伊德算法与B树实践

在2019-2020学年第三学期的《数据结构》课程设计题目中，针对2018级数理强化班的学生，主要任务围绕数据结构中的关键概念展开。以下是具体内容的详细解读： 1. **弗洛伊德算法求解有向网最短路径** (30分) - **无图形界面基本版** (10分): 学生需编写程序，从文件中读入包含节点和边权重的格式数据（如示例中上海、西安、广州和成都之间的距离），使用弗洛伊德算法计算每对顶点之间的最短路径。程序要求能在Linux系统（CentOS7）上运行，输入和输出文件的格式可以自定义，但要在15个节点和75条有向边的情况下保证运行时间不超过1秒。基本命令格式为`./floyd --input in.dat --output out.txt`。 - **图形界面版本** (20分): 提升难度，要求程序具备跨平台的图形用户界面。数据同样从文件中读取，界面允许用户选择输入和输出文件名。此外，结果不仅要在界面上显示，还需输出到指定文件，且考虑到节点和边的范围限制。 2. **B树的基本操作** (不确定分数，未在部分给出) - 学生需要掌握B树的基本概念，包括B树的定义、插入、删除和查找操作。这部分可能需要实现一个简单的B树数据结构，并进行相应的操作演示。 3. **排序算法演示** (不确定分数，未在部分给出) - 虽然没有具体提及，但学生可能会被要求实现一种或多种排序算法（如冒泡排序、快速排序、归并排序等），并在程序中展示其执行过程和性能。 4. **自定义STL容器** (不确定分数，未在部分给出) - 这部分要求学生模仿C++标准模板库(STL)中的容器（如vector、list、set等），独立实现一个容器类，以加深对数据结构的理解和实践。 在整个课程设计中，学生需要关注的关键点包括算法分析（如时间复杂度）、文件I/O处理、图形界面设计以及数据结构实现的细节。此外，完成项目的同时，还要注意提交测试数据、预期结果以及与其他同学的交流和合作，确保在规定时间内通过所有测试文件的检查。弗洛伊德算法是此项目的核心，它在图论和最优化问题中有着广泛的应用，因此理解和掌握该算法的实现是成功的关键。同时，图形化界面的添加也体现了软件工程中用户体验的重要性。