数据结构课程设计：紧缩图邻接表的拓扑排序实现

"该资源是一份东北大学信息科学与工程学院的数据结构课程设计报告，主要研究基于紧缩图的邻接表实现拓扑排序。报告由宋振带领的小组完成，涉及计算机科学与技术专业，指导教师为杨雷。报告内容包括课题概述、需求分析、方案设计、方案实现、测试与调试、课题总结以及附录，详细阐述了紧缩邻接表的存储方式和拓扑排序的实现方法。" 在数据结构中，拓扑排序是对有向无环图(DAG, Directed Acyclic Graph)进行排序的一种方法，使得对于图中的每一条有向边 (u, v)，u 的排序位置总是在 v 之前。在这个毕业设计中，学生们被要求使用STL的图、栈等数据结构来实现基于紧缩图的邻接表结构的拓扑排序。 紧缩图的邻接表是一种优化的图存储结构，它将每个顶点的邻接顶点存储在一个向量list中，并通过另一个向量h记录邻接表在list中的起始位置。这样的设计可以减少内存空间的浪费，提高查找效率。在实现拓扑排序时，通常会使用深度优先搜索(DFS)或广度优先搜索(BFS)。由于题目要求使用栈，这可能意味着采用了拓扑排序的一种变体，即使用栈进行逆向遍历的算法。 设计要求如下： 1. 使用STL库中的数据结构，如`std::vector`来创建图和栈，这样可以方便地进行动态内存管理和操作。 2. 实现一个STL兼容的紧缩邻接表结构的图类。这个类需要包含构造图、添加边、访问顶点及其邻接顶点等基本操作。 3. 实现拓扑排序算法。这通常涉及遍历图的所有顶点，找出没有前驱（即入度为0）的顶点，将它们加入到栈中，然后不断从栈中取出顶点并处理其邻接顶点，直到所有顶点都被处理。 在报告中，学生们还会进行需求分析、方案设计、实现和测试，确保算法的正确性和效率。测试部分会包括单个组员的个人测试以及整体系统的组装和系统测试，以验证算法的完整性和性能。 总结部分会评估整个项目，包括团队协作和个人贡献，同时可能会提供用户操作手册，帮助用户理解和使用设计的程序。附录中则包含了任务分工、源代码、可执行文件和可能的屏幕演示录像，以便于评审和未来参考。 这份报告详细地展示了如何将理论知识应用于实际编程，对于理解数据结构和算法的实际应用具有重要意义，同时也是对学生综合能力的一次全面锻炼。