24序号：《数据结构》题目拓扑序列学院计算机学院专业计算接科学与技术年级班别12级3班学号3112005895学生姓名朱靖宇指导教师曾孜思路理论设计难度系数代码总成绩2014年7月6日需求分析：1.采用邻接表法的存储结构来定义有向图2.实现有向图的创建和遍历3.求图中顶点的入度设计分析：拓扑排序的过程中要求找到入度为0的顶点，所以采用邻接表来存储有向图，而要得到邻接表，则先定义有向图的邻接矩阵结构，再把邻接矩阵转化成邻接表。在具体实现拓扑排序的函数中，当某个顶点的入度为0（没有前驱顶点）时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，为了避免重复检测入度为0的顶点，设立一个栈St，以存放入度为0的顶点。源程序代码：#include<stdio.h>#include<stdlib.h>#defineMAXV10//最大顶点个数typedefstruct{intedges[MAXV][MAXV];//邻接矩阵的边数组intn;//顶点数}MGraph;typedefstructANode{intadjvex;//该弧的终点位置structANode*nextarc;//指向下一条弧的指针}ArcNode;typedefstruct{intno;//顶点信息intcount;//顶点入度25ArcNode*firstarc;//指向第一条弧}VNode,AdjList[MAXV];typedefstruct{AdjListadjlist;//邻接表intn;//图的顶点数}ALGraph;voidMatTolist(MGraphg,ALGraph*&G){inti,j,n=g.n;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++)for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=n;}voidTopSort(ALGraph*G){inti,j,flag=0,a[MAXV];intSt[MAXV],top=-1;//栈St的指针为topArcNode*p;for(i=0;i<G->n;i++)//入度置初值为0G->adjlist[i].count=0;for(i=0;i<G->n;i++)//求所有顶点的入度{p=G->adjlist[i].firstarc;26while(p!=NULL){G->adjlist[p->adjvex].count++;p=p->nextarc;}}for(i=0;i<G->n;i++)if(G->adjlist[i].count==0)//入度为0的顶点进栈{top++;St[top]=i;}while(top>-1)//栈不为空时循环{i=St[top];top--;//出栈a[flag++]=i;//输出顶点p=G->adjlist[i].firstarc;//找第一个相邻顶点while(p!=NULL){j=p->adjvex;G->adjlist[j].count--;if(G->adjlist[j].count==0){top++;St[top]=j;//入度为0的相邻顶点进栈}p=p->nextarc;//找下一个相邻顶点}}if(flag<G->n)printf("该图存在回路，不存在拓扑序列!\n");else{printf("该图的一个拓扑序列为:");for(i=0;i<flag;i++)printf("%d",a[i]);printf("\n");27}}voidmain(){inti,j;MGraphg;ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));printf("请输入图