//SqStack.h文件 #ifndef SEQLIST #define SEQLIST const int LIST_INIT_SIZE = 100; const int LISTINCREAM  =  10; template 
     
       class SeqStack{
   protected:         T       *base;//栈底指针         T        *top;//栈顶指针 int stacksize;//栈大小 public:         SeqStack(int _stacksize = 100);         ~SeqStack(); void ClearStack(); bool IsEmpty() const; int GetLength() const;         T *GetTop() const; bool Push(T &elem) ; bool Pop(T &elem); bool StackTraverse(bool (*Visit)(T &elem)) ; }; template 
      
        SeqStack
       
        ::SeqStack(int _stacksize) {
   if(_stacksize<=0) exit(1);     stacksize=_stacksize; base = new T[stacksize]; if(!base) return;     top=base; } template 
        
          SeqStack
         
          ::~SeqStack() {
   if(base)         delete base; } template 
          
            void SeqStack
           
            ::ClearStack() { if(base) top=base; } template 
            
              bool SeqStack
             
              ::IsEmpty() const { return ((top-base)==0)?true:false; } template 
              
                int SeqStack
               
                ::GetLength() const { return top-base; } template 
                
                  T *SeqStack
                 
                  ::GetTop() const { //if(top==base) exit(1); //return *(top-1); return top; } template 
                  
                    bool SeqStack
                   
                    ::Push(T &elem) { if(top-base>=stacksize) { T *newbase = new T[stacksize+LISTINCREAM];//创建新的存储空间 if(!newbase) return false; int length = GetLength(); while(length)//内容复制 { newbase[length-1]=base[length-1]; length--; } delete base; //删除原有的存储空间 base=newbase; top = base +stacksize; //stacksize为原有长度; stacksize+=LISTINCREAM; //大小改变 } *top++=elem; return true; } template 
                    
                      bool SeqStack
                     
                      ::Pop(T &elem) { if(top==base) return false; elem=*--top; return true; } template 
                      
                        bool SeqStack
                       
                        ::StackTraverse(bool (*Visit)(T &elem)) //从栈底到栈顶一次遍历 { T *temp=base; while(temp!=top) { if(!Visit(*temp)) return false; temp++; } return true; } #endif //TSort.h文件 #include "SqStack.h" #include 
                        
                          #ifndef ALGRAPH #define ALGRAPH #define MAX_VERTEX_NUM 20 //最大顶点数 struct ArcNode{ int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条弧的指针(后驱) int *info; //该弧相关信息的指针(权值) }; template 
                         
                           struct VNode{ T data; //顶点信息 ArcNode *firstarc;//指向第一条依附该顶点的指针(前驱) }; template 
                          
                            struct _ALGraph{ VNode
                           
                             vertices[MAX_VERTEX_NUM]; int vexnum; int arcnum; int kind; }; template 
                            
                              class ALGraph{ _ALGraph
                             
                               algraph; bool visited[MAX_VERTEX_NUM]; int ve[MAX_VERTEX_NUM];//各顶点最早发生时间 public: void CreateGraph(); //v是图的顶点集 vr是图的边集 //构造函数 int LocateVex (T u); //图存在，图中存在顶点u 则返回该顶点在图中的位置 void DestroyGraph(); //析构函数销毁图 void DisPlay(); //输出图 void FindInDegree(int indegree[]); //求顶点的入度 bool TopologicalSort(); //若图无回路，则输出图的顶点的一个拓扑序列并返回true，否则返回false bool TopologicalOrder(SeqStack
                              
                                &T); // 求各顶点事件的最早发生时间ve }; template 
                               
                                 int ALGraph
                                
                                 ::LocateVex(T u) { for(int i = 0;i
                                 
                                   void ALGraph
                                  
                                   ::CreateGraph() { int i,j,k; T v1,v2; cout<<"请输入有向图的顶点数，边数: "; cin>>algraph.vexnum>>algraph.arcnum; cout<<"请输入"<
                                   
                                    <<"个顶点的值: "; for(i = 0;i
                                    
                                     >algraph.vertices[i].data; algraph.vertices[i].firstarc = false; } for(k = 0;k
                                     
                                      >v1>>v2; i = LocateVex(v1);//记录存储值的数组的下标 j = LocateVex(v2);//记录存储值的数组的下标 ArcNode *p = new ArcNode; //创建一个新的弧结点 p->adjvex = j; p->nextarc = false; p->info = false; p->nextarc = algraph.vertices[i].firstarc; //插在表头 algraph.vertices[i].firstarc = p; } } template 
                                      
                                        void ALGraph
                                       
                                        ::DestroyGraph() { int i; ArcNode *p,*q; for(i = 0;i
                                        
                                         nextarc; delete p;//删除弧结点 p = q; } } algraph.arcnum = 0; algraph.vexnum = 0; } template 
                                         
                                           void ALGraph
                                          
                                           ::DisPlay() { int i; ArcNode *p; cout<
                                           
                                            <<"个顶点:"<
                                            
                                             "<
                                             
                                              adjvex].data<<'\t'; cout<
                                              
                                               nextarc; } } } /*----------------拓扑排序（图采用邻接表存储结构举例表示）--------------*/ template 
                                               
                                                 void ALGraph
                                                
                                                 ::FindInDegree(int indegree[]) // 求顶点的入度 { int i; ArcNode *p; for(i = 0;i
                                                 
                                                  adjvex]++; p = p->nextarc; } } } template 
                                                  
                                                    bool ALGraph
                                                   
                                                    ::TopologicalSort() // 若图无回路，则输出图的顶点的一个拓扑序列并返回true，否则返回false { int i,k,count=0; // 已输出顶点数，初值为0 int indegree[MAX_VERTEX_NUM]; // 入度数组，存放各顶点当前入度数 SeqStack
                                                    
                                                      S;//创建int型静态栈 ArcNode *p; FindInDegree(indegree); // 对各顶点求入度indegree[] 函数被两个方法公用，所以在ALGraph.h中实现 for(i = 0;i
                                                     
                                                      nextarc) // 对i号顶点的每个邻接顶点 { k = p->adjvex; // 其序号为k if(!(--indegree[k])) // k的入度减1，若减为0，则将k入栈S { S.Push(k); } } } if(count
                                                      
                                                        #include
                                                       
                                                         using namespace std; #include "SqStack.h" #include "TSort.h" void opeshow() { cout<<"* 菜 单 *"<
                                                        
                                                          g; opeshow(); cin>>opekind; while(opekind>0 && opekind<4) { if (opekind==1) { g.CreateGraph(); g.DisPlay(); } else if(opekind==2) g.TopologicalSort(); else { cout<<"程序运行结束，Bye-Bye!"<
                                                         
                                                          >opekind; }//while }//main