拓扑排序（Topological）

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<stdlib.h>

#include<stack>

using namespace std;

#define MAX 20

typedef struct node

{

    struct node * nextarc;

    char Info;

}ArcNode, *pArcNode;

typedef struct

{

    int VerCount;//顶点数目

    int ArcCount;    //弧的数目

    pArcNode Adj;

}AdjList, *pAdjList;

void CreatAdj(pAdjList myAdjList,int *sign)

{

    int i, j;

    char tail;

    pArcNode p, q;

    printf("Please input the num of Vertex:");//顶点个数

    scanf("%d", &myAdjList->VerCount);

    printf("Pleaase input the num of Arc");//弧的个数

    scanf("%d", &myAdjList->ArcCount);

    myAdjList->Adj = (pArcNode)malloc(myAdjList->VerCount  *sizeof(ArcNode));

    for (i = ; i < myAdjList->VerCount; i++)

        myAdjList->Adj[i].nextarc = NULL;

    printf("Please input the Graph: \n");

    printf("Please input all of the vertex:\n");

    fflush(stdin);

    for (i = ; i < myAdjList->VerCount; i++)

    {

        scanf("%c", &myAdjList->Adj[i].Info);

        fflush(stdin);

    }

    printf("Please input the Ver:\n");

    for (i = ; i < myAdjList->ArcCount; i++)

    {

        printf("Please input tail of Arc%d :", i);

        scanf("%c", &tail);

        p = (pArcNode)malloc(sizeof(ArcNode));

        p->nextarc = NULL;

        fflush(stdin);

        printf("Please input head of Arc%d :", i);

        scanf("%c", &p->Info);

        getchar();

        for (j = ; j < myAdjList->VerCount; j++)

            if (myAdjList->Adj[j].Info == p->Info)

                    sign[j]++;

        for (j = ; j < myAdjList->VerCount; j++)

        {

            if (myAdjList->Adj[j].Info == tail)

            {

                q = &myAdjList->Adj[j];

                while (q->nextarc != NULL)

                    q = q->nextarc;

                q->nextarc = p;

            }

        }

    }

}

void TopologicalSort(pAdjList myAdjList, int *sign)

{

    stack <ArcNode> S;

    ArcNode *temp;

    int s[];

    int i, j;

    for (i = ; i < myAdjList->VerCount; i++)

        s[i] = sign[i];

    for (i = ; i < myAdjList->VerCount; i++)

    {

        if (s[i] == )

        {

            S.push(myAdjList->Adj[i]);

            s[i] = -;

        }

    }

    while (!S.empty())

    {

        for (i = ; i < myAdjList->VerCount; i++)

            if (myAdjList->Adj[i].Info == S.top().Info)

                temp = &myAdjList->Adj[i];

        S.pop();

        printf("%c", temp->Info);

        while (temp->nextarc != NULL)

        {

            for ( j = ; j < myAdjList->VerCount; j++)

            {

                if (myAdjList->Adj[j].Info == temp->nextarc->Info)

                {

                    s[j]--;

                    if (s[j] == )

                    {

                        S.push(myAdjList->Adj[j]);

                        s[j] = -;

                    }

                }

            }

            temp = temp->nextarc;

        }

    }

}

int main()

{

    AdjList myAdjList;

    int sign[];

    for (int i = ; i < ; i++)

        sign[i] = ;

    CreatAdj(&myAdjList,sign);

    TopologicalSort(&myAdjList, sign);

    system("pause");

    return ;

}

栈操作。