tuopupaixu.zip_visual c

// 输出有向图的一个拓扑序列。实现算法7.12的程序 #include<string.h> #include<ctype.h> #include<malloc.h> // malloc()等 #include<limits.h> // INT_MAX等 #include<stdio.h> // EOF(=^Z或F6),NULL #include<stdlib.h> // atoi() #include<io.h> // eof() #include<math.h> // floor(),ceil(),abs() #include<process.h> // exit() #include<iostream.h> // cout,cin // 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 // #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE #define MAX_NAME 5 // 顶点字符串的最大长度 typedef int InfoType; typedef char VertexType[MAX_NAME]; // 字符串类型 #include"ALGraph.h" // // 邻接表存储结构的基本操作 #include"SqStack.h" // 顺序栈的基本操作 void FindInDegree(ALGraph G,int indegree[]) { // 求顶点的入度，算法7.12、7.13调用 int i; ArcNode *p; for(i=0;i<G.vexnum;i++) indegree[i]=0; // 赋初值 for(i=0;i<G.vexnum;i++) { p=G.vertices[i].firstarc; while(p) { indegree[p->data.adjvex]++; p=p->nextarc; } } } Status TopologicalSort(ALGraph G) { // 有向图G采用邻接表存储结构。若G无回路，则输出G的顶点的一个拓扑序列并返回OK， // 否则返回ERROR。算法7.12 int i,k,count=0; // 已输出顶点数，初值为0 int indegree[MAX_VERTEX_NUM]; // 入度数组，存放各顶点当前入度数 SqStack S; ArcNode *p; FindInDegree(G,indegree); // 对各顶点求入度indegree[]，在func7-1.cpp中 InitStack(S); // 初始化零入度顶点栈S for(i=0;i<G.vexnum;++i) // 对所有顶点i if(!indegree[i]) // 若其入度为0 Push(S,i); // 将i入零入度顶点栈S while(!StackEmpty(S)) // 当零入度顶点栈S不空 { Pop(S,i); // 出栈1个零入度顶点的序号，并将其赋给i printf("%s ",G.vertices[i].data); // 输出i号顶点 ++count; // 已输出顶点数+1 for(p=G.vertices[i].firstarc;p;p=p->nextarc) { // 对i号顶点的每个邻接顶点 k=p->data.adjvex; // 其序号为k if(!(--indegree[k])) // k的入度减1，若减为0，则将k入栈S Push(S,k); } } if(count<G.vexnum) // 零入度顶点栈S已空，图G还有顶点未输出 { printf("此有向图有回路\n"); return ERROR; } else { printf("为一个拓扑序列。\n"); return OK; } } void main() { ALGraph f; printf("请选择有向图\n"); CreateGraph(f); // 构造有向图f，在ALGraph.h中 Display(f); // 输出有向图f，在ALGraph.h中 TopologicalSort(f); // 输出有向图f的1个拓扑序列 }