#include"stdio.h" #include"stdlib.h" #define MAX_VEXTEX_NUM 20 //定义顶点的最大值 #define M 20 #define STACK_INIT_SIZE 100 //定义栈的大小 100 #define STACKINCREMENT 10 //定义栈的增量 10 #define OK 1 #define ERROR 0 typedef int ElemType; //定义栈顶元素类型 typedef struct ArcNode { int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条弧的指针 }ArcNode; //表结点 typedef struct VNode { int data;//顶点信息 ArcNode *firstarc;//表结点的地址。指向该顶点的弧的指针 }VNode,AdjList[MAX_VEXTEX_NUM]; //头结点 typedef struct { AdjList vertices; int vexnum,arcnum;// 图的顶点数和弧数 }ALGraph; typedef struct //建栈 { ElemType *base; //在栈构造之前的指针 ElemType *top;//栈顶指针 int stacksize; //定义所分配的存储空间 }SqStack; //顺序栈 void InitStack(SqStack *S) //初始化栈 { S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S->base) { printf("初始化出错,退出"); exit(1); } S->top=S->base; //空栈之前的指针赋给头指针 S->stacksize=STACK_INIT_SIZE;//栈的空间设为STACK_INIT_SIZE } int Pop(SqStack *S,ElemType *e) //出栈操作 { if(S->top==S->base) //栈空返回OK return ERROR; *e=*--S->top; //删除栈顶元素 return 0; } void Push(SqStack *S,ElemType e) //进栈操作,插入元素e为新的栈顶元素 { if(S->top-S->base >= S->stacksize) //栈满,追加存储空间 { S->base=(ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S->base) //存储分配失败 { printf("进栈出错,退出"); exit(1); } S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; } *S->top++=e; } int StackEmpty(SqStack *S) //判断栈是否为空 { if(S->top == S->base) //若栈不空,则删除S的栈元素,并返回OK,否则返回ERROR return OK; else return ERROR; } void CreatGraph(ALGraph *G) //构建图,用邻接表存储 { int m,n,i; ArcNode *p;//定义临界表指针变量 printf("请输入顶点和弧数:"); scanf("%d%d",&G->vexnum, &G->arcnum); //输入顶点数和弧数 printf("请输入%d个顶点值:",G->vexnum); for(i=1;i<=G->vexnum;i++) //构造顶点向量 { scanf("%d",&G->vertices[i].data); G->vertices[i].firstarc=NULL; } for(i=1;i<=G->arcnum;i++) //输入存在弧的点集合 { printf("请输入存在弧的两个顶点的值:"); scanf("%d%d",&n,&m); while(n >G->vexnum|| m>G->vexnum) { printf("输入的顶点值不正确 ,请重新输入:"); scanf("%d%d",&n,&m); } p=(ArcNode *)malloc(sizeof(ArcNode)); if(p==NULL) { printf("出错,退出"); exit(1); } p->adjvex=m; p->nextarc=G->vertices[n].firstarc; //一次插入进邻接表 G->vertices[n].firstarc=p; } printf("建立的邻接表为:\n"); //输出建立好的邻接表 for(i=1; i<=G->vexnum; i++) { printf("[%d]",G->vertices[i].data); for(p=G->vertices[i].firstarc; p ; p=p->nextarc) printf("-->[%d]",p->adjvex); printf("\n"); } } void FindDegree(ALGraph G,int indegree[]) //求入度操作 { int i; for(i=1;i<=G.vexnum;i++) { indegree[i]=0;//赋初值 } for(i=1;i<=G.vexnum;i++) { while(G.vertices[i].firstarc) { indegree[G.vertices[i].firstarc->adjvex]++; G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc; } } } void TopologicalSort(ALGraph G) //输出拓扑排序函数 { int indegree[M]; int i,j=1,k,n; int count=0; ArcNode *p; SqStack S; FindDegree(G,indegree); //对个顶点求入读 indegree[0...vexnum] InitStack(&S); //初始化栈 for(i=1;i<=G.vexnum;i++) { printf("第%d个点的入读为%d \n",i,indegree[i]); } printf("\n"); for(i=1;i<=G.vexnum;i++) //建0入度顶点栈S { if(!indegree[i]) Push(&S ,i); //入栈为0者进栈 } printf("进行拓扑排序输出顺序为:\n"); while(!StackEmpty(&S)) //栈不空时 { Pop(&S,&n); printf("%4d\n",G.vertices[n].data); count++; //输出i好顶点并计数 for(p=G.vertices[n].firstarc; p!=NULL; p=p->nextarc) { k=p->adjvex; if(!(--indegree[k])) //若入读减为0,则入栈 { Push(&S,k); } } for(i=1;i<=G.vexnum;i++) //输出各顶点入栈是每一趟的入度情况 { printf("第%d趟排序第%d个点的入度%d \n",j,i,indegree[i]); } j++; } printf("\n"); if(count<G.vexnum) //拓扑排序不成功 { printf("出现错误\n"); } else //排序成功 { printf("排序成功\n"); } } void main() { printf("以下是一个拓扑排序算法,请按要求进行输入:\n"); ALGraph G; //定义一个图的变量 CreatGraph(&G); //调用构建函数 TopologicalSort(G); //调用拓扑排序函数 }