做了个拓扑排序的程序,大家看看!!
有是不当的地方欢迎各位高手指教!!!


#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<conio.h>

#define MAX_NUM 20
typedef char Vertype;
typedef struct arcnode{
    int adjvex;
    arcnode *nextarc;
}arcnode;
typedef struct vexnode{
    Vertype vex;
    arcnode *firstarc;
}vexnode,AdjList[MAX_NUM];


typedef struct {
    int vexnum,arcnum;
    AdjList verices;
}ALGraph;

typedef struct degree{
    int adjvex;
    int deg;
}Degree[MAX_NUM];
    


int LocateVex(ALGraph G,Vertype v);
void finddegree(ALGraph G,Degree de);

void CreatDN(ALGraph &G){
    int i,j,k,vexnum,arcnum,weight;
    Vertype v1,v2;
    arcnode *p;
    printf("iput the tow numbers of the vertexnum and the arcnums :");
    scanf("%d%d",&vexnum,&arcnum);
    G.vexnum=vexnum;G.arcnum=arcnum;
    fflush(stdin);
    for(i=0;i<vexnum;i++){
        
        G.verices[i].vex=getchar();
        G.verices[i].firstarc=NULL;
    }
    fflush(stdin);
    for(i=0;i<G.vexnum;i++){
        printf("%c\n",G.verices[i].vex);
    }

    for(i=0;i<arcnum;i++){
        printf("\n请输入第%d个有向关系的两个顶点元素:",i+1);
        v1=getche();printf("----->");
        v2=getche();
        j=LocateVex(G,v1);
        k=LocateVex(G,v2);
        if(j==-1||k==-1){
            printf("the v1 or v2 is not in the vertexs!!");
            exit(0);
        }
        p=(arcnode *)malloc(sizeof(arcnode));
        p->adjvex=k;p->nextarc=G.verices[j].firstarc;
        G.verices[j].firstarc=p;
    }
}


int LocateVex(ALGraph G,Vertype v){
    
    int i;
    for(i=0;i<G.vexnum;i++)
        if(G.verices[i].vex==v) return i;
    return -1;
}
void finddegree(ALGraph G,Degree de){
    int i;
    arcnode *p;
    for(i=0;i<G.vexnum;i++)
        de[i].deg=0;
    for(i=0;i<G.vexnum;i++)
        for(p=G.verices[i].firstarc;p!=NULL;p=p->nextarc)
            de[p->adjvex].deg++;
}


void topscort(ALGraph G,Degree &de){
    int i,top,k,count=0;
    Vertype tops[MAX_NUM];
    arcnode *p;
    finddegree(G,de);
    top=-1;
    for(i=0;i<G.vexnum;i++)
        if(de[i].deg==0){
            de[i].adjvex=top;top=i;
        }
    printf("\n\n\n");
    i=0;
    while(top!=-1){
        tops[i++]=G.verices[top].vex;
        k=top;top=de[top].adjvex;
        for(p=G.verices[k].firstarc;p!=NULL;p=p->nextarc){
            de[p->adjvex].deg--;
            if(de[p->adjvex].deg==0){
                de[p->adjvex].adjvex=top;top=p->adjvex;
            }
        }
    }
    if(i!=G.vexnum)
        printf("图中有环\n");
    else{
        printf("拓扑排序的结果为:\n\t\t\t");
        for(i=0;i<G.vexnum;i++)
            printf("%c  ",tops[i]);
    }
}


void main(){
    ALGraph G;
    Degree de;
    CreatDN(G);
    topscort(G,de);
}