1、 数据结构课程设计数据结构课程设计 题题 目目: : 拓扑排序拓扑排序 学学 院：院： 班班 级：级： 学学 生生 姓姓 名：名： 学学 生生 学学 号：号： 指指 导导 教教 师：师： 20122012 年年 1 12 2 月月 0505 日日 课程设计任务书课程设计任务书 姓名 班级 学号 设计题目 拓扑排序 理论要点 拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全 序。更直观地讲，一个偏序是自反的、反对称的，用图表示时每个点 都有环且只有单向边。 设计目标 拓扑排序的任务是在这个偏序上得到一个全序， 即得到一个完成 整个项目的各步骤的序列。 研究方法 步骤 在有向图中选一个没有前
2、驱的顶点且输出之。 从图中删除该顶点和所有以它为尾的弧。 预期结果 直至全部顶点均已输出，或者当前图中不存在无前驱的顶点。 计划与进 步的安排 按时并分部完成任务。 I 摘要摘要 拓扑排序是有向无环图的一种重要应用, 实现算法与数据结构关系密切, 本文以邻接表作为图的存储结构, 详细讨论了拓扑排序算法在计算机上的实现方法, 并对该算法作了必要的 分析。 关键词关键词 拓扑排序，有向无环图，邻接表 II 目录 摘要 错误错误! !未定义书签。未定义书签。 课程设计题目 错误错误! !未定义书签。未定义书签。 1 需求分析 1 2 概要设计 1 3 详细设计 1 4 调试分析 3 5 用户使用说明
3、 3 6 测试结果 8 7 结论 . 10 参考文献 错误错误! !未定义书签。未定义书签。 数据结构课程设计 - 1 - 拓扑排序拓扑排序 1.需求分析需求分析 拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。 更直观地 讲，一个偏序是自反的、反对称的，用图表示时每个点都有环且只有单向边。拓 扑排序的任务是在这个偏序上得到一个全序， 即得到一个完成整个项目的各步骤 的序列。2概要设计：说明本程序中用到的所有抽象数据类型的定义、主程序 的流程以及各程序模块之间的层次(调用)关系。 2.概要设计概要设计 （1）在有向图中选一个没有前驱的顶点且输出之。 （2）从图中删除该顶点和所有以它为
4、尾的弧。 重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点 为止。后一种情况则说明有向图中存在环。具体的算法实现参照源程序。 3.详细设计详细设计 构造邻接表图：typedef struct AdjList vertices; int vexnum,arcnum; Graph;/邻接表图 为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的 顶点： typedef struct stack int *base; int *top; int stacksize; sqstack;/栈的结构，存储图的顶点序号 数据结构课程设计 - 2 - 算法的流程图 开始 设辅助
