C语言实现拓扑排序：详解代码与数据结构

拓扑排序是一种在有向无环图(DAG, Directed Acyclic Graph)中对顶点进行线性排序的方法，确保对于图中的每条有向边(u, v)，节点u的排序位置总是在节点v之前。本文档提供了一个用C语言编写的拓扑排序算法的完整代码实现。 首先，引入必要的头文件，如<stdio.h>、<stdlib.h>、<malloc.h>和<iomanip>，这些库用于基本的输入输出操作、内存管理以及格式化控制。 定义了一些预处理宏，例如TRUE和FALSE常量，表示布尔值，OK和ERROR表示成功和错误的状态，INFEASIBLE和OVERFLOW分别表示不可行和溢出的错误码。 接下来是栈数据结构的声明，使用SqStack结构体，它包含一个动态数组base作为栈底元素，一个指针top指向栈顶，以及一个整型变量stacksize表示当前栈的大小。这里的栈被设计成动态增长，初始容量为STACK_INIT_SIZE，每次扩容时增量为STATCKINCREMENT。 定义了几个基本的数据类型，如SElemType、Boolean、Status、InfoType、VertexType、ArcNode和VNode，它们分别代表元素类型、布尔值、状态、信息类型、顶点类型和弧节点类型。这里还定义了AdjList结构体，用于存储有向图的邻接表，以及ALGraph结构体，用于存储整个图的信息，包括顶点、边的数量和图的类型（有向图或无向图）。 在代码中，AdjList[MAX_VERTEX_NUM]数组用于存储每个顶点的邻接节点，VNode结构体封装了顶点的数据和其第一条弧的指针。MAX_VERTEX_NUM是一个预设的最大顶点数量，MAX20可能是MAX_VERTEX_NUM的一个实例。 最后，文档展示了图的抽象邻接列表表示法以及关键的数据结构定义。在实际的拓扑排序过程中，会使用广度优先搜索(BFS)或深度优先搜索(DFS)算法来遍历图，根据边的方向性确定顶点的排序顺序。算法的关键步骤包括初始化数据结构、添加边信息、构建邻接表、检查图是否有环、执行排序等。 这个C语言实现的核心部分可能会涉及以下几个步骤： 1. 图的输入和结构初始化 2. 遍历图以查找入度（即指向该顶点的边的数量） 3. 使用栈辅助数据结构，从入度为0的顶点开始，将它们依次放入栈中 4. 从栈中弹出顶点并输出，同时递减其他顶点的入度 5. 检查是否有顶点的入度始终为0，以判断图是否为有向无环图 6. 如果图不是有向无环图，说明存在循环，无法进行拓扑排序，返回错误 这篇文档提供了C语言实现的拓扑排序算法，适合对图论基础和数据结构有深入了解的开发人员参考学习和实践。通过理解和实现这段代码，读者可以掌握如何在C语言环境中处理有向无环图的顶点排序问题。