东北大学数据结构课程设计：紧缩图邻接表的拓扑排序

"东北大学信息科学与工程学院数据结构课程设计报告——基于紧缩图的邻接表的拓扑排序" 这篇文档是东北大学信息科学与工程学院计算机科学与技术专业学生的一份课程设计报告，主要关注的是如何实现基于紧缩图的邻接表的拓扑排序。拓扑排序是图论中的一个重要概念，特别是在有向无环图(DAG)中，它能对图的顶点进行线性排序，使得对于每条有向边(u, v)，顶点u的排序位置总是在顶点v之前。 紧缩图的邻接表是一种优化的邻接表表示法，它将图的每个顶点的邻接表紧凑地存储在两个向量`list`和`h`中。向量`list`按顺序存储所有顶点的邻接顶点，而`h[i]`则存储顶点i的邻接表在`list`向量中的起始位置，这样可以更有效地查找和操作邻接关系。 设计要求包括以下几点： 1. 使用STL(Standard Template Library)提供的数据结构，如图和栈。STL是C++标准库的一部分，提供了高效且灵活的数据结构和算法，如`std::vector`（用于向量）、`std::stack`（用于栈）等。 2. 实现一个STL兼容的紧缩邻接表结构图类。这可能涉及到定义一个自定义类，包含`list`和`h`向量以及相关的成员函数，以便于创建、修改和查询图结构。 3. 实现拓扑排序算法，该算法应用于紧缩邻接表结构。拓扑排序通常通过深度优先搜索(DFS)或广度优先搜索(BFS)来实现，对于有向无环图，应该能够得到多个有效的排序结果。 报告的其他部分包括需求分析、方案设计、实现、测试与调试、课题总结等内容。需求分析涉及对问题的调研和用户需求的探讨；方案设计则涵盖了功能规划、数据结构选择、算法设计以及用户界面的考虑；方案实现部分描述了开发工具和关键技术的使用，以及各组员的具体工作；测试与调试部分记录了个人和整体的测试过程，确保程序正确运行；最后，课题总结部分包含了对整个设计过程的反思、团队合作的评估和个人设计的总结。 附录部分提供了详细的分工情况、设计文档、源代码、可执行文件和可能的操作手册，为其他人理解和复用这个项目提供了全面的资源。