tu.h

大二半年的数据结构上机实验。包括链表

#include <iostream.h>
#include <conio.h>
#include <iomanip.h>
const int MaxVertices=10;
const int MaxWeight=1000;
struct MinSpanTree              
{  int begin,end;              
    int length;                 
};

template<class T>
class  Graph
{ private:
	  int  Vertices[10];                    
	  int  Edge[MaxVertices][MaxVertices];   
	  int  numE;                             
      int  numV;                             
public:
  Graph();      			
  void  Creat(int n,int e);
  void  PrintOut();
  void  Prim() ;
  int InsertEdge(int v1,int v2,int v3);
  int DeleteEdge(int v1,int v2);
};

template<class T>
Graph<T>::Graph()        
{ for ( int i=0; i<MaxVertices; i++ )
      for ( int j=0; j<MaxVertices; j++ )
      	{ if( i==j )  Edge[i][j]=0;
        	else   Edge[i][j]=MaxWeight; 
        }
  numE=0;                      
  numV=0;
}

template<class T>
int Graph<T>::InsertEdge(int v1,int v2,int v3)
{

	if(v1<0||v1>numV||v2<0||v2>numV)
		return 0;
        Edge[v1-1][v2-1]=v3;
	    Edge[v2-1][v1-1]=v3;
        numE++;
	    return 1;
}

template<class T>
int Graph<T>::DeleteEdge(int v1,int v2)
{   
	
	if(v1<0||v1>numV||v2<0||v2>numV)
	 return 0;
	 Edge[v1-1][v2-1]=1000;
	 Edge[v2-1][v1-1]=1000;
	 numE--;
	 return 1;
}

template<class T>
void  Graph<T>::Creat(int n,int e)
{ int vi,vj,w;
 numE=e;   numV=n;
 cout<<"\n  输入顶点的信息（整型）：" ;
 for (int i=0; i<numV; i++ )
    { cout<<"\n "<<i+1<<": ";
        cin>>Vertices[i];
    }
 for ( int a=0; a<numE; a++ )
    { cout<<"\n  输入边的信息（vi,vj,W）：(边的权值应小于1000）";
      cin>>vi>>vj>>w;
      Edge[vi-1][vj-1]=w; Edge[vj-1][vi-1]=w; 
    }
 }
 
template<class T>
void Graph<T>::PrintOut()
{ cout<<"\n  输出顶点的信息（整型）：\n";
  for ( int i=0; i<numV; i++ )cout<<Vertices[i]<<"  ";
  cout<<"\n  输出邻接矩阵 ：" ;
  for (int b=0; b<numV; b++ )
       { cout<<"\n "<<b+1<<": ";
         for ( int j=0; j<numV ;j++ )
         cout<<Edge[b][j]<<"  ";
         cout<<endl;
       }
 }
 
template<class T>
void  Graph<T>::Prim ()
{  int  n=numV,m,v;                      
   MinSpanTree e, mintree[MaxVertices];        
   for (int j=1; j<n; j++)                
     { mintree[j-1].begin=1;            
       mintree[j-1].end=j+1;
       mintree[j-1].length=Edge[0][j];   
    }
  for (int k=0; k<n-1; k++)              
   { int min=MaxWeight;
     for (int j=k; j<n-1; j++)
     if (mintree[j].length<min )  {min=mintree[j].length;  m=j;}
     e=mintree[m]; mintree[m]=mintree[k];  mintree[k]=e;
     v=mintree[k].end;              
     for (int c=k+1;  c<n-1;  c++)      
      { int d=Edge[v-1][mintree[c].end-1];
        if (d<mintree[c].length)  {  mintree[c].length=d;
                                     mintree[c].begin=v;
                                   }
     } //for j
    }// for k
  for (int d=0;d<n-1; d++)
cout<<"\n"<<"起点："<<mintree[d].begin<<"     终点："<<
mintree[d].end<<"    权值："<<mintree[d].length;
  }