1.课程设计内容与要求
用字符文件提供数据建立 DAG(有向无环图)合适的存储结构。编写程序,输出所有可
能的拓扑排序序列。要求输出的拓扑排序结果用顶点序号或字母表示。输出结果需存于字符
文件。输出结果中应显示全部拓扑排序序列的数目。如果 DAG 存在环(即拓扑排序失败),
输出结果中应显示拓扑排序序列的数目为 0。
课程设计报告要求给出详细算法描述,在结论部分应分析算法的时间复杂度和空间复杂
度,并给出分析的结果。
2. 程序设计报告
2.1 概述
程序的目的是输出 DAG 所有可能的拓扑排序序列,如果不是 DAG 则输出提示信息。
输入的 DAG 信息在字符文件中,包括顶点序号,顶点的出度和入度以及前驱节点;输出
的拓扑排序用顶点序号表示,输出结果保存在字符文件中,并且输出信息中显示全部拓
扑排序序列的数目。
2.2 数据结构设计与说明
DAG 使用邻接表的存储方式。
// 邻接表节点数据结构
typedef struct node{
int code; // 节点下标
struct node *next; // 节点指针域,指向邻接表的下一个节点
}ArcNode;
3 / 13