TopoSort

//TopoSort.cpp--Topological Sort Page182
#include < stdio.h > 
#include < stdlib.h > 
#include "myconst.h"
#define MAX_VERTEX_NUM 20 
typedef int VertexType;
typedef int InfoType;
typedef struct ArcNode {
    int adjvex;
    struct ArcNode * nextarc;
    InfoType * info;
}
ArcNode;
typedef struct VNode {
    VertexType data;
    ArcNode * firstarc;
}
VNode,
AdjList[MAX_VERTEX_NUM];
typedef struct {
    AdjList vertices;
    int vexnum,
    arcnum;
}
ALGraph;
typedef int SElemType;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10 typedef struct {
    SElemType * base;
    SElemType * top;
    int stacksize;
}
SqStack;
Status InitStack(SqStack & S);
Status Push(SqStack & S, SElemType e);
Status Pop(SqStack & S, SElemType & e);
Status DestroyStack(SqStack & S);
Status StackEmpty(const SqStack & S);
Status CreateDG(ALGraph & G);
int LocateVex(const ALGraph & G, VertexType u);
Status FindInDegree(const ALGraph & G, int indegree[]);
Status DestroyALGraph(ALGraph & G);
Status TopologicalSort(const ALGraph & G);
int main(void) {
    ALGraph G;
    printf("\n");
    CreateDG(G);
    TopologicalSort(G);
    DestroyALGraph(G);
    return 0;
}
Status TopologicalSort(const ALGraph & G) {
    SqStack S;
    int i;
    int count;
    int indegree[MAX_VERTEX_NUM];
    ArcNode * p;
    int k;
    InitStack(S);
    FindInDegree(G, indegree);
    for (i = 0; i < G.vexnum; i++) if (!indegree) Push(S, i);
    count = 0;
    while (!StackEmpty(S)) {
        Pop(S, i);
        printf("vertex%5d:%5d\n", i, G.vertices.data); ++count;
        for (p = G.vertices.firstarc; p; p = p - >nextarc) {
            k = p - >adjvex;
            if (! (--indegree[k])) Push(S, k);
        }
    }
    DestroyStack(S);
    if (count < G.vexnum) return ERROR;
    else return OK;
}
Status FindInDegree(const ALGraph & G, int indegree[]) {
    int i;
    ArcNode * p;
    for (i = 0; i < G.vexnum; i++) indegree = 0;
    for (i = 0; i < G.vexnum; i++) {
        p = G.vertices.firstarc;
        while (p) {++indegree[p - >adjvex];
            p = p - >nextarc;
        }
    }
    return OK;
}
Status CreateDG(ALGraph & G) {
    int i,
    j,
    k;
    VertexType v1,
    v2;
    InfoType w;
    ArcNode * s;
    printf("Enter vertex number:");
    scanf("%d", &G.vexnum);
    printf("Enter arc number:");
    scanf("%d", &G.arcnum);
    for (i = 0; i < G.vexnum; i++) {
        printf("Enter %d vertex:", i + 1);
        scanf("%d", &G.vertices.data);
        G.vertices.firstarc = NULL;
    }
    for (k = 0; k < G.arcnum; k++) {
        printf("Enter %d arc:\n", k + 1);
        printf("Enter the first vertex:");
        scanf("%d", &v1);
        printf("Enter the second vertex:");
        scanf("%d", &v2);
        printf("Enter the w:");
        scanf("%d", &w);
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        s = (ArcNode * ) malloc(sizeof(ArcNode));
        s - >adjvex = j;
        s - >info = (InfoType * ) malloc(sizeof(InfoType)); * (s - >info) = w;
        s - >nextarc = G.vertices.firstarc;
        G.vertices.firstarc = s;
    }
    return OK;
}
Status DestroyALGraph(ALGraph & G) {
    int i;
    ArcNode * p,
    *q;
    for (i = 0; i < G.vexnum; i++) {
        p = G.vertices.firstarc;
        while (p) {
            q = p;
            p = p - >nextarc;
            free(q - >info);
            free(q);
        }
    }
    return OK;
}
int LocateVex(const ALGraph & G, VertexType u) {
    int i;
    int k = -1;
    for (i = 0; i < G.vexnum; i++) if (G.vertices.data == u) break;
    k = i;
    return k;
}
Status InitStack(SqStack & S) {
    S.base = (SElemType * ) malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (!S.base) exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}
Status Push(SqStack & S, SElemType e) {
    if (S.top - S.base >= S.stacksize) {
        S.base = (SElemType * ) realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
        if (!S.base) exit(OVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    } * S.top++=e;
    return OK;
}
Status Pop(SqStack & S, SElemType & e) {
    if (S.top == S.base) return ERROR;
    e = *--S.top;
    return OK;
}
Status DestroyStack(SqStack & S) {
    if (!S.base) exit(OVERFLOW);
    free(S.base);
    return OK;
}
Status StackEmpty(const SqStack & S) {
    return ! (S.top - S.base);
}