PAGE数据结构课程设计设计说明书有向图拓扑排序算法的实现学生姓名樊佳佳学号班级网络工程1301成绩指导教师申静数学与计算机科学学院2016年1月4日课程设计任务书 2015—2016学年第一学期课程设计名称：数据结构课程设计课程设计题目：图的拓扑排序算法的实现完 成 期 限：自 2015年 12月20日至 2016年 1 月 3 日共 2 周设计内容：1、设计任务（1）给出一个有向无环图，遍历所有的节点；（2）能够实现对所有顶点的拓扑；(3)界面友好数据结构拓扑排序算法，可操作性强。2、需求分析对系统的功能及性能要求进行分析，写出需求规格说明书（可行性分析报告、系统的分层DFD图）。3、软件设计软件设计分两个阶段进行：总体设计和详细设计；总体设计：确定系统总体设计方案，完成系统的模块结构图及模块的功能说明；详细设计：对模块内部过程及数据结构进行设计，以及进行数据库设计、用户界面设计等编写出该项目的详细设计报告；4、具体编码编写程序数据结构拓扑排序算法-数据结构课程设计：有向图拓扑排序算法的实现.docx 22页，要求给出详细的注释数据结构拓扑排序算法，包括：模块名、模块功能、中间过程的功能、 变量说明等。同时编写用户使用手册、程序模块说明等文档；5、软件测试所有测试过程要求采用综合测试策略：先作静态分析，再作动态测试。
应事先制订测试计划，并要求保留所有测试用例，完成测试报告。指导教师：申静教研室负责人：申静课程设计评阅评语：指导教师签名：年 月 日摘 要设计了一个对有向图进行拓扑排序的算法，该算法首先用邻接表构造有向图的存储结构，然后对此有向图进行拓扑排序，输出拓扑排序的结果。用VC++作为软件开发环境，以邻接表作为图的存储结构，将图中所有顶点排成一个线性序列，输出拓扑排序结果。拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。关键词：邻接表；有向无环图；拓扑排序目录 TOC o "1-3" u 1 课题描述 h 12 问题分析和任务定义 h 23 逻辑设计 h 33.1程序模块功能图 h 33.2 抽象数据类型 h 34 详细设计 h 44.1 C语言定义的相关数据类型 h 44.2 主要模块的伪码算法 h 44.2.1主函数伪码算法 h 44.2.2邻接表伪码算法 h 44.2.3拓扑排序的伪码算法： h 54.3 主函数流程图 h 65 程序编码 h 76 程序调试与测试 h 137 结果分析 h 168 总结 h 17参考文献 h 18第 PAGE 1 页 共18 页1 课题描述根根据设计要求运用C语言程序设计了一个对有向图进行拓扑排序的算法，该算法首先用邻接表构造有向图的存储结构，然后对此有向图进行拓扑排序，输出拓扑排序的结果。
如给定一个有向无环图如图1.1所示。在此图中，从入度为0的顶点出发，删除此顶点和所有以它为尾的弧；重复直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。 图1.1 有向无环图开发工具： C++ 6.0第 PAGE 18 页 共 18 页2 问题分析和任务定义对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对由某个集合上的一个偏序得到该集合上的一个全序，这个操作就称之为拓扑排序。偏序集合中仅有部分成员之间颗比较，而全序指集合中全体成员之间均可比较，而由偏序定义得到拓扑有序的操作便是拓扑排序。一个表示偏序的有向图可用来表示一个流程图，通过抽象出来就是AOV-网，若从顶点i到顶点j有一条有向路径，则i是j的前驱，j是i的后继。若（i，j）是一条弧，则i是j的直接前驱；j是i的直接后继。在AOV-网中，不应该出现有向环，用拓扑排序就可以判断网中是否有环，若网中所有顶点都在它的拓扑有序序列中，则该AOV-网必定不存在环。3 逻辑设计主函数3.1程序模块功能图主函数拓扑排序节点入度栈的初始化创建邻接表有向图初始化拓扑排序节点入度栈的初始化创建邻接表有向图初始化图3.1程序模块功能图3.2 抽象数据类型ADT ｛数据对象：D={V|V是具有相同特性的数据元素的集合，即顶点集}数据关系：R={|v,w∈V,表示顶点v到顶点w的弧}基本操作P:( *G)初始条件：成对输入顶点集V中的点。
操作结果：构造图G的邻接表。( G, int [])初始条件：图G的邻接表中存在结点V。操作结果：找到图中入度为0结点。()操作结果：完成图形初始化。( G)初始条件：构造的有向图G已初始化。操作结果：对于有向图G根据邻接存储表进行拓扑排序。}4 详细设计4.1 C语言定义的相关数据类型# 20 /宏定义最大顶点个数/# 100 /宏定义栈的存储空间大小/ int ; VNode /邻接表头结点的类型/{int data; /顶点信息,数据域/}VNode, []; /是邻接表类型/ { ; /邻接表/ int , ; /图中顶点数vexn和边数arcn/}; /图的类型/ //构建栈{ base; /数据域/ top; /栈指针域/int ; };4.2 主要模块的伪码算法4.2.1主函数伪码算法：开始{创建及输出邻接表(&G);输出排序后的输出序列(G);}结束4.2.2邻接表伪码算法：# VNode /邻接表头结点的类型/{ int data; /顶点信息,数据域/ ; /指向第一条弧/}VNode, []; /是邻接表类型/ { ; /邻接表/ int , ; /图中顶点数vexn和边数arcn/}; /图的类型/开始{定义一个指针P置i的初值为1邻接表中所有头结点指针置初值当); ("n输入边数:"); scanf("%d",&G->); ("=======================================================");for (i=1; ;i++)/初始化各顶点/ {G->[i].data=i;/编写顶点的位置序号/G->[i].=NULL; }for (i=1;;i++)/记录图中由两点确定的弧/ {("n输入确定弧的两个顶点u，v:");scanf("%d %d",&n,&m);while (nG->||mG->){("输入的顶点序号不正确 请重新输入:");scanf("%d%d",&n,&m);}p=()(()); /开辟新的弧结点来存储用户输入的弧信息/if(p==NULL){("ERROR!");exit(1);}p->=m;/该弧指向位置编号为m的结点/p->=G->[n].;/下一条弧指向的是依附于n的第一条弧/G->[n].=p; }("=======================================================");("n建立的邻接表为:n"); /打印生成的邻接表（以一定的格式）/for(i=1;;i++) {("%d",G->[i].data);for(p=G->[i].;p;p=p->)("-->%d",p->);("n"); }("=======================================================");}// /栈的存储结构/{int base;/栈底指针/int top;/栈顶指针/int ;};//void ( S)/初始化栈/{ S->base=(int )((int)); if(!S->base)/存储分配失败/ {("ERROR!");exit(1); } S->top=S->base; S->=;}//void Push( S,int e)/压入新的元素为栈顶/{ if(S->top-S->base>=S->) {S->base=(int )(S->base,(S->+)(int));/追加新空间/if(!S->base)/存储分配失败/ {("ERROR!");exit(1); }S->top=S->base+S->;S->+=; } S->top++=e;/e作为新的栈顶元素/}//int Pop( S,int e)/弹出栈顶，用e返回/{ if(S->top==S->base)/栈为空/ { false; } e=--S->top; 0;}//int ( S) /判断栈是否为空，为空返回1，不为空返回0/{ if(S->top==S->base) true; else false;}//void ( G, int [])/对各顶点求入度/{int i;for(i=1; ;} }}/*/void ( G) {int [M];int i, k, n;int count=0;/初始化输出计数器/ p; S;(G,);(&S);for(i=1;;if(!(--[k]))/若入度减为零，则再入栈/{Push(&S,k);}}}if(count
文章来源:https://m.book118.com/html/2019/0117/7043146053002002.shtm