拓扑排序

今天刚刚做完有向图拓扑排序的实验，分享一下，希望各位大虾指点（可以编译）

#include<stdlib.h>
#include<iostream>
using namespace std;

#define  MAX_VERTEX_NUM  20
#define  STACK_INIT_SIZE 100
#define  STACKINCREMENT  10
#define  OK  1
#define  ERROR  0
#define  OVERFLOW 0
#define  NULL   0

typedef struct ArcNode{
        int                              adjvex;   //该弧所指向的顶点的位置
        struct ArcNode  *nextarc;  //指向下一条弧的指针
}ArcNode;
typedef struct VNode{
        int            indegree;           //顶点入度
        char       data;                   //顶点信息
        ArcNode    *fisrtarc;      //指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
        AdjList    vertices;
        int                vexnum, arcnum;
}ALGraph;

typedef struct{                            //构造栈用来存放入度为0的顶点
        char  *base;
        char  *top;
        int   stacksize;
}SqStack;

int InitStack(SqStack &S)
{//构造一个空栈S
        S.base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
        if(!S.base)      exit (OVERFLOW);
        S.top = S.base;
        S.stacksize = STACK_INIT_SIZE;
        return  OK;
}

int StackEmpty(SqStack S)
{
        if(S.top == S.base)
                return ERROR;
        else
                return OK;
}
int Push(SqStack &S, int e)
{
        if(S.top - S.base >= S.stacksize)
        {
                S.base = (char *)realloc(S.base,
                        (S.stacksize + STACKINCREMENT) * sizeof(char));
                if(!S.base) exit (OVERFLOW);
                S.top = S.base + S.stacksize;
                S.stacksize += STACKINCREMENT;
        }
        *S.top++ = e;
        return OK;
}//Push

int Pop(SqStack &S,int &e)
{
        if(S.top == S.base)
                return ERROR;
        e = * --S.top;
        return e;
}//Pop

int CreatGraph(ALGraph &G)
{
        int i, j;
        int v1, v2;
        ArcNode *q;
        cout<<"请输入顶点个数:";
        cin>>G.vexnum;
        for(i=0;i<G.vexnum;i++)
        {
                G.vertices[i].indegree = 0;
                G.vertices[i].fisrtarc = NULL;
        }
        cout<<"请分别输入顶点：\n";
        for(i=1;i<=G.vexnum;i++)
        {
                cout<<"第"<<i<<"个顶点:";
                cin>>G.vertices[i-1].data;
        }
        cout<<"请输入边数：";
        cin>>G.arcnum;
        cout<<"请分别输入边的信息\n";
        for(j=1;j<=G.arcnum;j++)
        {
                cout<<"第"<<j<<"条边的起点v1和终点v2(数字)";
                cin>>v1>>v2;
                G.vertices[v2].indegree++;
                q = (ArcNode *)malloc(sizeof(ArcNode));
                q->nextarc = NULL;
                q->adjvex  = v2;
                q->nextarc = G.vertices[v1].fisrtarc;
                G.vertices[v1].fisrtarc = q;
        }
        for(i=0;i<G.vexnum;i++)
                cout<<"第"<<i<<"个顶点的入度："<<G.vertices[i].indegree<<endl;
        cout<<endl;
        return OK;
}


int TopologicalSort(ALGraph G)
{//有向图采用邻接矩阵存储结构
 //若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR.
        int i, k, count;
        int e;
        SqStack S;
        ArcNode *p ;
        InitStack(S);
        for(i=0;i<G.vexnum;i++)                              //入度为0者进栈
        {
                if(!G.vertices[i].indegree) 
                        Push(S,i);
        }
        count = 0;                                                      //对输出顶点计数

        cout<<"输出拓扑序列"<<endl;
        while(StackEmpty(S))
        {
                Pop(S,e);
                cout<<G.vertices[e].data<<" ";
                ++count;                                                //输出i号顶点并计数

                        for(p=G.vertices[e].fisrtarc; p ;p=p->nextarc)
                        {
                                k = p->adjvex;
                                if(!(--G.vertices[k].indegree)){ Push(S,k);}
                        }       
        }//while
        if(count < G.vexnum)
                return  ERROR;                                  //该有向图有回路
        else return OK;
}//TopologicalSort


void main()
{
        ALGraph H;
        CreatGraph(H);
        TopologicalSort(H);
}