数据结构拓扑排序课程设计

《数据结构拓扑排序课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课题二拓扑排序2．1问题的提出2.1问题的提出任务：编写函数实现图的拓扑排序。程序所实现的功能： 建立对应的邻接表，对该图进行拓扑排序，并显示排序结果。输入：顶点数,边数及各顶点信息(数据格式为整形)输出：拓扑排序结果。2.2概要设计1.拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。更直观地讲，一个偏序是自反的、反对称的，用图表示时每个点都有环且只有单向边。拓扑排序的任务是在这个偏序上得到一个全序，即得到一个完成整个项目的各步骤的序列。2．解决拓扑排序的方法如下：（1）在有向图中选一个没有前驱的顶点且输出之。（2）从图中

2、删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。具体的算法实现参照源程序。3．构造邻接表图：typedefstruct{AdjListvertices;intvexnum,arcnum;}Graph;//邻接表图4.为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点：typedefstructstack{int*base;int*top;intstacksize;}sqstack;//栈的结构，存储图的顶点序号2．3流程图2

3、.根据算法思想，画流程图如下：开始设辅助数组indegree记录图的各顶点的入度值，并将indegree数组各变量赋初值。输入图的顶点数、边数建立一个栈，存储图的顶点的序号用邻接表法建图，并计算出indegree数组中各变量值根据indegree数组将入度为0的顶点入栈count对输出顶点计数0=>count栈不空删除栈顶元素,赋给icount++将与第i个顶点链接的各顶点入度减1输出第i个顶点值顶点入度为0顶点序号入栈count

4、ncludeusingnamespacestd;constintMAX=20;constintSTACK_INIT_SIZE=100;constintERROR=0;typedefstructstack{int*base;int*top;intstacksize;}sqstack;//栈的结构，存储图的顶点序号typedefstructlnode{intadjvex;structlnode*next;}ArcNode;//弧结点typedefstructnode2{chardata;ArcNode*fristar

5、c;}VNode,AdjList[MAX];//顶点数组,fristarc指向与顶点邻接的第一条弧typedefstruct{AdjListvertices;intvexnum,arcnum;}Graph;//邻接表图voidInitstack(sqstack&s){s.base=newint;if(!s.base)exit(0);s.top=s.base;s.stacksize=STACK_INIT_SIZE;}voidPush(sqstack&s,int&e){*s.top++=e;}intEmptystack(sqstack&

6、s){if(s.base==s.top)return1;elsereturn0;}intPop(sqstack&s,int&e){if(s.base==s.top)returnERROR;e=*--s.top;}voidCreatGraph(Graph&G,int*indegree){cout<<"请输入图的顶点数和弧数(且顶点数不能超过"<>G.vexnum>>G.arcnum;cout<<"请输入顶点值:"<

7、cin>>G.vertices[i].data;G.vertices[i].fristarc=NULL;indegree[i]=0;}for(i=0;i>m>>n;p=newArcNode;if(!p)exit(0);indegree[n-1]++;//求每个顶点的入度值p->adjvex=n-1;p->next=G.vertices[m-1].fristarc;G.vert

8、ices[m-1].fristarc=p;}}intToposort(Graph&G,int*indegree){sqstackS;Initstack(S);for(inti=0;i