topsort.txt

数据结构的c++实现,源代码全部在C++builder中运行.第六部分

//图类结构体定义与相关操作graph4.h
typedef struct
{char *data;
 int *visited;
 float **edge;
 int max,size;
}Graph;
//初始化图
void SetGraph(Graph *G,int n)
{int i,j;
 G->data=new char[n];
 G->visited=new int[n];
 G->edge=(float **)malloc(n*sizeof(float *));
 for(i=0;i<n;i++)
  G->edge[i]=(float *)malloc(n*sizeof(float));
 for(i=0;i<n;i++) G->visited[i]=0;
 for(i=0;i<n;i++)
  for(j=0;j<n;j++) G->edge[i][j]=0;
 G->max=n;
 G->size=0;
}
//构造图
void MakeGraph(Graph *G,RCW r[],int n,int e)
{float w;int m=0;
 while(m<n)
  {if(G->size==G->max)
   {cout<<"Graph is full!\n";
    exit(1);}
   G->data[G->size]='a'+m;
   G->size++;m++;}
  //插入弧
  for(int p=0;p<e;p++)
  {int i,j,k;
   for(k=0;k<n;k++)
    {if(r[p].w1==G->data[k]) i=k;
     if(r[p].w2==G->data[k]) j=k;}
   G->edge[i][j]=r[p].w;}
}
//拓扑排序topSort.cpp
#include<iostream.h>
#include<iomanip.h>
typedef struct
{char w1,w2;
 float w;
}RCW;
#include"graph4.h"
typedef struct
{int *data;
 int max,top;
}Stack;
void TopSort(Graph *G)
{int i,j,n,d,count=0,*D;
 Stack S;
 if(G->size==0) return;
 n=G->size;
 S.data=new int[n];
 S.max=n;S.top=-1;
 D=new int[n];
 for(j=0;j<n;j++)
  {d=0;
   for(i=0;i<n;i++)
    if(G->edge[i][j]!=0) d++;
    D[j]=d;
    if(d==0)
     {if(S.top==S.max-1)
       {cout<<"Stack is full!\n";exit(1);}
      S.top++;
      S.data[S.top]=j;
     }
  }
 while(!(S.top==-1))
 {if(S.top==-1)
    {cout<<"Pop an empty stack!\n";exit(1);}
  S.top--;
  i=S.data[S.top+1];
  cout<<G->data[i]<<' ';
  count++;
  for(j=0;j<n;j++)
  if(G->edge[i][j]!=0)
  {D[j]--;
   if(D[j]==0)
    {if(S.top==S.max-1)
       {cout<<"Stack is full!\n";exit(1);}
      S.top++;
      S.data[S.top]=j;
 }}}
 if(count<n)
  cout<<"\nThere is a cycle.";
 free(D);
 free(S.data);
}
void main()
{cout<<"topSort.cpp运行结果:\n";
 Graph G;int n=6,e=8;//n为顶点数,e为边数
 RCW rcw[8]={{'a','b',1},{'a','d',1},{'a','e',1},{'b','f',1},
             {'c','b',1},{'c','f',1},{'e','d',1},{'e','f',1}};
 SetGraph(&G,n);
 MakeGraph(&G,rcw,n,e);
 TopSort(&G);
 free(G.data);//释放空间
 free(G.visited);
 for(int i=0;i<G.max;i++) free(G.edge[i]);
 free(G.edge);cin.get();}
topSort.cpp运行结果:
c a e d b f