资源描述：
《数据结构-拓扑排序-实验报告与代码.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验报告七----拓扑排序一．需求分析1、采用邻接表法的存储结构来定义有向图2、实现有向图的创建、遍历3、实现栈的创建及其基本操作（进栈、退栈、判空）4、求图中顶点的入度二．算法设计本程序中采用的数据模型，用到的抽象数据类型的定义，程序的主要算法流程及各模块之间的层次调用关系拓扑排序的基本思想是以下两点：1、在有向图中选一个没有前驱的顶点且输出之。2、从图中删除该顶点何所有以它为尾的弧。3、查邻接表中入度为零的顶点，并进栈。当栈为空时，进行拓扑排序。（a）退栈，输出栈顶元素V。（b）在邻接表中查找Vj的直接后继Vk，将V
2、k的入度减一，并令入度减至零的顶点进栈。4、重复上述两步，直至全部顶点均已输出。如每输出完，则证明有环。程序基本结构：设定栈的抽象数据类型定义：ADTStack{数据对象：D={
3、∈CharSet，i=1,2,3,…..,n,n>=0;}数据关系：R={<，>
4、，∈D,i=2,…,n}存储结构：(1)表结点typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;(2)链表的存储结构typedefstructVNode{intdata;ArcNode*fi
5、rstarc;}VNode,AdjList[MAX_VEXTEX_NUM];(3)图的存储结构typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;(4)栈的存储结构typedefstruct{ElemType*base;ElemType*top;intstacksize;}SqStack;三．程序设计根据算法设计中给出的有关数据和算法，选定物理结构，详细设计需求分析中所要求的程序。包括：人机界面设计、主要功能的函数设计、函数之间调用关系描述等。1界面设计1）欢迎
6、界面2）输入顶点与边的关系，并得到拓扑排序2主要功能1）初始化栈voidInitStack(SqStack*S)//初始化栈{S->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S->base){printf("memoryallocationfailed,goodbye");exit(1);}S->top=S->base;S->stacksize=STACK_INIT_SIZE;}2）出栈操作intPop(SqStack*S,ElemType*
7、e)//出栈操作{if(S->top==S->base){returnERROR;}*e=*--S->top;return0;}2）进栈操作voidPush(SqStack*S,ElemTypee)//进栈操作{if(S->top-S->base>=S->stacksize){S->base=(ElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S->base){printf("memoryallocationfail
8、ed,goodbye");exit(1);}S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*S->top++=e;}3）判断栈是否为空intStackEmpty(SqStack*S)//判断栈是否为空{if(S->top==S->base)returnOK;elsereturnERROR;}4）构建图与欢迎界面voidCreatGraph(ALGraph*G)//构建图{intm,n,i;ArcNode*p;printf("**************
9、**********************************");printf("欢迎使用拓扑排序");printf("制作者：----");printf("************************************************");printf("请输入顶点数和边数:");scanf("%d%d",&G->vexnum,&G->arcnum);for(i=1;i<=G->vexnum;i++){G->vertices[i].data=i;G->vertices[i].f
10、irstarc=NULL;}for(i=1;i<=G->arcnum;i++)//输入存在边的点集合{printf("请输入存在边的两个顶点的序号:");scanf("%d%d",&n,&m);while(n<0
11、
12、n>G->vexnum
13、
14、m<0
15、
16、m>G->vexnum){printf("输入的顶点序号不正确
