拓扑排序 整体 拓扑排序

#include <iostream.h> #include <VCL.h> String topo; template<class T> class Stack{ public: T* Array; int top; int MaxSize; void doubleArray(int Max); Stack(); ~Stack(){ delete [ ] Array; } void push(const T info); void pop(); void clear(){top = -1;} bool empty() const { if(top==-1) return true; else return false; } bool full() const {return top == MaxSize-1;} T getTop()const; void output()const; }; template<class T> Stack<T>::Stack() { top=-1; MaxSize=1000; Array=new T[MaxSize]; } template<class T> void Stack<T>::push(const T info) { if(full()) doubleArray(3); Array[++top]=info; } template<class T> void Stack<T>::pop() { if(top==-1) { //cout<<"Stack is empty!"<<endl; } else { top--; } } template<class T> T Stack<T>::getTop()const { return Array[top]; } template<class T> void Stack<T>::output()const { if(top==-1) cout<<"Stack is empty!"<<endl; else{ for(int k=0;k<=top;k++) cout<<Array[k]<<" "; cout<<endl; } } template<class T> void Stack<T>::doubleArray(int Max) { T* ptr; ptr=new T[MaxSize+Max]; MaxSize=MaxSize+Max; for(int k=0;k<MaxSize;k++) ptr[k]=Array[k]; Array=ptr; } //定义节点 struct GraphNode { unsigned int Vertex; GraphNode *Next; bool Visited; GraphNode() { Vertex=0; Visited=false; Next=NULL; } }; //定义节点 struct Head { unsigned int Vertex; int NextNumber;//后继个数 int BeforeNumber;//前驱个数 bool Visited; GraphNode *Index; Head() { Vertex=0; BeforeNumber=0; NextNumber=0; Index=NULL; Visited=false; } }; //图类定义 class GraphType { public: GraphType() {} ~GraphType(); void Clear(); Head *AdjacencyList; unsigned int VertexNumber; }; GraphType::~GraphType() { GraphNode *P,*Q; unsigned int i; for (i=1;i<=VertexNumber;i++) { P=AdjacencyList[i].Index; while (P!=NULL) { Q=P; P=P->Next; delete Q; } } delete []AdjacencyList; } void GraphType::Clear() //清除访问标志 { unsigned int i; for (i=1;i<=VertexNumber;i++) AdjacencyList[i].Visited=false; } // //邻接矩阵 int M[81][81]; //矩阵初始化 void ReNewM() { int a,b; for(a=0;a<81;a++) { for(b=0;b<81;b++) { M[a][b]=0; } } } //插入边 void insert(int i,int j) { M[j][i]+=1; } //后驱计数 int NextNodeDegree(int a) { int value=0; int jishu=0; for(jishu=0;jishu<80;jishu++) { value+=M[jishu][a]; } return value; } //前驱计数 int BeforeNodeDegree(int a) { int value=0; int jishu=0; for(jishu=0;jishu<80;jishu++) { value+=M[a][jishu]; } return value; } //邻接矩阵转邻接表 void NewGraph(GraphType &Graph) { GraphNode *P; for (int i=1;i<=81;i++) { //cout<<"!!!!!!"<<endl; Graph.AdjacencyList[i].Vertex=i; Graph.AdjacencyList[i].NextNumber=NextNodeDegree(i); Graph.AdjacencyList[i].BeforeNumber=BeforeNodeDegree(i); Graph.AdjacencyList[i].Visited=false; Graph.AdjacencyList[i].Index=new(GraphNode); P=Graph.AdjacencyList[i].Index; //cout<<"#####"<<endl; for(int ii=1;ii<81;ii++) { //cout<<"$$$$$"<<endl; int m=M[i][ii]; if(m>=1) { for(int iii=0;iii<10;iii++) { //cout<<"*****"<<endl; P->Next=new(GraphNode); P=P->Next; P->Vertex=ii; P->Next=NULL; } } } } } //判断前驱个数是否为0 int IsBeforeEmpty(int i,GraphType &Graph) { if(Graph.AdjacencyList[i].BeforeNumber==0) { return 1; } else { return 0; } } //判断后继个数是否为0 int IsNextEmpty(int i,GraphType &Graph) { if(Graph.AdjacencyList[i].NextNumber==0) { return 1; } else { return 0; } } //Stack <int> L2; //堆栈计数器 //堆栈动态选择 /* Stack <int> Choose(int i) { if(i%2==1) { return L1; } else { return L2; } } */ //节点计数 int NodeSum() { int value2=0; int jishu3=0; for(jishu3=0;jishu3<81;jishu3++) { if(NextNodeDegree(jishu3)+BeforeNodeDegree(jishu3)>0) { value2++; } } return value2; } //删除后继结点 void DeleteNext(int i) { int pp; for(pp=0;pp<82;pp++) { M[pp][i]=0; } } int leave[20]; void chushihualeave() { for(int u=0;u<20;u++) { leave[u]=0; } } void printleave() { cout<<"OK!"<<endl; for(int u=0;u<20;u++) { if(leave[u]>0) { cout<<leave[u]; } } } String a=""; //拓扑排序 void ToPoSorting(Stack<int> &L1,GraphType &Graph,int &StackCount,String &a,,TMemo *Memo3) { int i,j,k; topo="第"; topo+=StackCount; topo+="批输出为: "; topo+=a; a=""; for(i=1;i<82;i++) { if(Graph.AdjacencyList[i].BeforeNumber==0&&Graph.AdjacencyList[i].NextNumber!=0) { L1.push(i); } } while(L1.top>-1) { topo+=L1.getTop(); topo+=" "; for(int io=0;io<82;io++) { if(M[io][L1.getTop()]>0&&Graph.AdjacencyList[io].NextNumber==0&&Graph.AdjacencyList[io].BeforeNumber==1) { a+=io; a+=" "; } } DeleteNext(L1.getTop()); L1.pop(); } cout<<endl; Memo3->Lines->Add(topo); StackCount++; } void main() { int StackCount=1; int aaa; ReNewM(); GraphType Graph; Graph.AdjacencyList=new(Head[82]); Stack<int> L1; insert(1,2); insert(1,4); insert(1,3); insert(3,5); NewGraph(Graph); while(NodeSum()>=1||leave[0]!=0) { ToPoSorting(L1,Graph,StackCount,a); NewGraph(Graph); } cout<<a; cin>>aaa; }