数据结构实验——拓扑排序.zip

#include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 100 #define MAXSIZE 100 #define OK 1 #define TURE 1 #define FALSE 0 #define ERROR 0 typedef char VertexType[MAX_VERTEX_NUM]; typedef int DataType; typedef struct { DataType data[MAXSIZE];//用静态数组存放数据元素 int top;//栈顶元素 } SqStack; //图结构邻接表存储结构 typedef struct ArcNode { int adjvex;//该弧所指向的位置 struct ArcNode *nextarc;//指向下一条弧的指针 } ArcNode; typedef struct VNode { DataType data;//顶点信息 ArcNode *firstarc;//指向第一条依附该顶点的弧的指针 } VNode; typedef struct { VNode vertexs[MAX_VERTEX_NUM];//将顶点位置置于数组中 int vexnum,arcnum;//图的当前顶点数和弧数 } ALGraph; //栈的操作 //初始化空栈 int InitStack(SqStack &S) { S.top=-1; return OK; } //判断栈空 int StackEmpty(SqStack S) { //判断空栈返回为空，否则返回为假 return (S.top==-1?TURE:FALSE); } int StackFull(SqStack S) { //判断栈满时返回为真，反之为假 return (S.top==MAXSIZE-1?TURE:FALSE); } //进栈 int Push(SqStack &S,DataType e) { //将e元素插入到栈中，作为新栈顶 if(StackFull(S)) return ERROR;//栈满 S.top++;//top加1，栈顶位置上移 S.data[S.top]=e;//数据e储存入当前栈顶 return OK; } //出栈 int Pop(SqStack &S,DataType &e) { //若栈不为空则删除栈顶元素 if(StackEmpty(S)) return ERROR;//栈空 e=S.data[S.top];//取出数据放入e所指单元中 S.top--;//top减1，栈顶位置下移 return OK; } //建立图 void CreateGraph(ALGraph *G) { int m,n,i; ArcNode *p; printf("\n---------------有向无环图的建立----------------\n\n"); do { printf("请输入顶点数（大于零）："); scanf("%d",&G->vexnum); } while(G->vexnum<0); do { printf("请输入边数："); scanf("%d",&G->arcnum); } while(G->arcnum<0); //将顶点信息存入数组 for(i=1; i<=G->vexnum; i++) { G->vertexs[i].data=i; G->vertexs[i].firstarc=NULL; } for(i=1; i<=G->arcnum; i++) { //输入存在边的点集合 printf("请输入第%d边的信息（v1，v2）:",i); scanf("%d,%d",&n,&m); while(n<0||n>G->vexnum||m<0||m>G->vexnum) { printf("输入的顶点序号不正确 请重新输入:"); scanf("%d,%d",&n,&m); } p = (ArcNode*)malloc(sizeof(ArcNode));//向系统申请指针类型空间 if (p == NULL) { exit(1); } p->adjvex=m; p->nextarc=G->vertexs[n].firstarc; G->vertexs[n].firstarc=p; } } //求顶点入度 void FindInDegree(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.vertexs[i].firstarc) { indegree[G.vertexs[i].firstarc->adjvex]++; G.vertexs[i].firstarc=G.vertexs[i].firstarc->nextarc; } } } void PrintAL(ALGraph *G) { int i; ArcNode *p; //以邻接表形式输出图 printf("----------------------------------------\n"); printf("\n\n---------------建立邻接表---------------\n"); printf("建立的邻接表为:\n"); //输出邻接表 for(i=1; i<=G->vexnum; i++) { printf("V%d->",G->vertexs[i].data); for(p=G->vertexs[i].firstarc; p; p=p->nextarc) printf("V%d;",p->adjvex); printf("\n"); } printf("----------------------------------------\n"); } /* 进行拓扑排序 有向图G采用邻接表存储结构 */ int ToplogicalSort(ALGraph G) { SqStack S; int count,a,i,m,n,k; ArcNode *p; int indegree[MAX_VERTEX_NUM];//定义用于保存入度的数组 FindInDegree(G,indegree);//求各顶点的入度存放于数组indegree中 InitStack(S);//初始化栈 count=0;//定义count用于记录输出的顶点数 for(i=0; i<G.vexnum; i++) { if(indegree[i]==0) Push(S,i);//将图中所有入度为0的结点入栈 } printf("拓扑排序的结果：\n"); while(!StackEmpty(S)) { Pop(S,n);//取出第一个入度为0的顶点 printf("%3d",G.vertexs[n].data);//输出 count++;//计数 for(p=G.vertexs[n].firstarc; p!=NULL; p=p->nextarc) { k=p->adjvex;//获得p点的后续结点号 if(!(--indegree[k])) //对p点各后续顶点入度减1，如果入度为0则入栈 Push(S,k); } } if(count<G.vexnum) { printf("\n存在环！！！ \n"); } return TURE; } int main() { while(1) { ALGraph G; CreateGraph(&G); PrintAL(&G); ToplogicalSort(G); printf("\n"); } return 1; }