数据结构学习

拓扑排序是有向图的一种重要的应用。根据拓扑排序，我们能合理的安排活动的先后顺序。

它的算法为：

v (1)在有向图中选一个没有前驱的顶点且输出之 。 v (3)重复上述步骤直至不存在没有前驱的结点为止。 利用拓扑排序我们也可以检测有向图中是否有回路。  v (2)从图中删除该顶点和所有以它为尾的弧。 typedef  struct  TAdjacentVertex ... {    int nVertexNum;    struct TAdjacentVertex* pNextVertex;} TAdjacentVertex; // structure of the Vertex typedef  struct  TVertex ... {    int nInDegree; //number of vertexes pointing to this vertex    int nFlag;    struct TAdjacentVertex* pAdjacentVertex; //pointer of the first adjacent vertex} TVertex; /**/ /**    Function Name        ：CreatGraph_Topo*    function                     ：Creat a Graph and store it in the adjacent vertexes's array*    detail                         ：none*    author                        ：weixiong*    time                             ：2007-2-1*    return type                 ：void*   return description  :  *                         *    function parameters    ：int  NodesNum                             number of all the vertexes*                          *                           */   TVertex *  CreatGraph_Topo( int  NodesNum) ... {    TVertex* pVertexArray = new TVertex [NodesNum + 1];    for (int i = 1; i <= NodesNum; i++)    ...{        cout << "Please enter the in degree of the " << i << " 'th vertex." << endl;        int nIn_Degree = 0;        cin >> nIn_Degree;        pVertexArray[i].nInDegree = nIn_Degree;        pVertexArray[i].nFlag = 0;        int nAmount = 0;        cout << "Please give the number of adjacent nodes of the " << i << " th node" << endl;        cin >> nAmount;        if (0 == nAmount)        ...{            pVertexArray[i].pAdjacentVertex = NULL;        }        else        ...{            TAdjacentVertex* pPreNode = NULL;            for (int j = 1; j <= nAmount; j++)            ...{                TAdjacentVertex* pNewNode = new TAdjacentVertex;                cout << "Please enter the sequence number of the node." << endl;                int nSequenceNum = 0;                cin >> nSequenceNum;                pNewNode->nVertexNum = nSequenceNum;                if (1 == j)                ...{                    pVertexArray[i].pAdjacentVertex = pNewNode;                }                else                ...{                    pPreNode->pNextVertex = pNewNode;                }                pPreNode = pNewNode;                pNewNode->pNextVertex = NULL;            }        }    }    return pVertexArray;} int  CountNoPreNum(TVertex *  pVertexList,  int  nVerterNum) ... {    int nNumofZeroIndegree = 0;    for (int i = 1; i <= nVerterNum; i++)    ...{        if (0 == pVertexList[i].nFlag)        ...{            if (0 == pVertexList[i].nInDegree)            ...{                nNumofZeroIndegree++;            }        }    }    return nNumofZeroIndegree;} int  main() ... { cout << "Please enter the number of all the vertexes: " << endl; int nVertexNum = 0; cin >> nVertexNum; TVertex* pVertexList = CreatGraph_Topo(nVertexNum); int nOutputNum = 0; while (CountNoPreNum(pVertexList, nVertexNum)) ...{  for (int i = 1; i <= nVertexNum; i++)  ...{           if (0 == pVertexList[i].nFlag)             ...{                  if (0 == pVertexList[i].nInDegree)                  ...{       pVertexList[i].nFlag = 1;        cout << i << ' ';      nOutputNum++;      for (TAdjacentVertex* pCurrentVertex = pVertexList[i].pAdjacentVertex; NULL != pCurrentVertex; pCurrentVertex = pCurrentVertex->pNextVertex)        ...{                          pVertexList[pCurrentVertex->nVertexNum].nInDegree--;     }                 }            }  } }    if (nOutputNum < nVertexNum)    ...{        cout << "There have circle in this graph.";    }}

在代码中我用加标志的方法来标注无前驱的结点，实现的拓扑排序的功能。

也可以采用stack来存储无前驱的结点，在出栈的时候将相应结点的入度减一，如果出现了入度为0,即无前驱的结点，则进栈。本来应该在代码中实现，是个缺陷。

 如果配以图片的说明更好些，但是总是上传不了。不知道为什么。

最近整理代码的时间花得少了。