Deja Vu

要記錄一些自己寫過的程式

以後才會知道寫的多醜= =

這是作業程式所以也沒管他空間效率還什麼的 (Deadline是殘酷的 XD)

要找一天來修改修改

// Kruskal's MST algorithm.
#include <iostream>

using std::cout;
using std::cin;
using std::endl;

#include <iomanip>

using std::setw;

#include <ctime>

// contains prototypes for functions srand and rand
#include <cstdlib>

#define MAX 32768

// structure definition
struct Edge {   
   long node1;
   long node2;
   float weight;
   bool isTreeEdge;
}; // end struct Time

// structure definition
struct Node {   
   long p;
   long rank;
}; // end struct Time

void generateEdges( Edge edges[], long numberOfNodes, long numberOfEdges );
void heapSort( Edge edges[], long numberOfEdges );
void BuildMaxHeap( Edge edges[],long numberOfEdges );
void MaxHeapify( Edge edges[], long i, long heapSize );
long findSet( Node forest[], long numberOfNodes, long x );
void link( Node forest[], long x, long y );

int main()
{
 long numberOfNodes;
 long numberOfEdges;
 long weightUpperBound = 20;
 long i;
 long time1, time2, time3, time4;

 srand( time(0) );

 do
 {
  cout << "How many nodes? (at least 10) ";
  cin >> numberOfNodes;
  cout << "How many edges? (at least 10) ";
  cin >> numberOfEdges;
 }while( numberOfNodes<10 || numberOfEdges<10 );

 Edge *edges = new Edge[ numberOfEdges + 1 ];
 Node *forest = new Node[ numberOfNodes + 1 ];

 time1 = time(0);

 generateEdges( edges, numberOfNodes, numberOfEdges );

 cout<<endl;
 for( i = 1; i <= numberOfEdges; i++ )
 {
  edges[i].isTreeEdge = false;
  edges[i].weight = rand()%weightUpperBound+1;
  cout<<"第"<<i<<"條邊weight: "<<edges[i].weight<<endl;
 }

 time2 = time(0);
 cout << endl << time2 - time1 << " seconds" << endl;

 for( i = 1; i <= numberOfNodes; i++ ) {
  forest[i].p = i;
  forest[i].rank = 0;
 }

 heapSort( edges, numberOfEdges );

 time3 = time(0);
 cout << endl << time3 - time2 << " seconds" << endl;

 for( i = 1; i <= numberOfEdges; i++ )
  cout << "{" << edges[i].node1 << "," << edges[i].node2 << "} : " << edges[i].weight << endl;
 cout << endl;

 long x, y;
 for( i = 1; i <= numberOfEdges; i++ ) {
  x = findSet( forest, numberOfNodes, edges[i].node1 );
  y = findSet( forest, numberOfNodes, edges[i].node2 );
  if( x != y ) {
   edges[i].isTreeEdge = true;
   link( forest, x, y );
  }
 }

 time4 = time(0);
 cout << endl << time4 - time3 << " seconds" << endl << endl;

 cout << "All edges of a minimum spanning tree: \n\n";
 for( i = 1; i <= numberOfEdges; i++ )
  if( edges[i].isTreeEdge )
   cout << "{" << edges[i].node1 << "," << edges[i].node2 << "}" << endl;
 cout << endl;

 delete [] forest;
 delete [] edges;

 system("PAUSE");

 return 0; 

} // end main

void generateEdges( Edge edges[], long numberOfNodes, long numberOfEdges )
{
 long weightUpperBound = 2*numberOfEdges;
 long degree,k;
 long count = 0;
 bool duplicate;

 for( long  i = 1; i <= numberOfEdges; i++ )
 {
  edges[i].node2 = 0;
 }

 if( numberOfEdges % numberOfNodes == 0 )
  degree = numberOfEdges / numberOfNodes;
 else
  degree = numberOfEdges / numberOfNodes + 1;

 for(i = 1; i <= numberOfNodes; i++ )
 {
  degree = numberOfEdges / numberOfNodes + 1;
  for( long j = 1; j <= degree; j++ )
  {
   k = 1;
   duplicate = true;

   if( count < numberOfEdges )
   {
    count++;
    edges[count].node1 = i;

    while(k<count)
    {
     if( edges[k].node1==j && edges[k].node2==i )
     {
      duplicate = false;
      count--;
      degree++;
      break;
     }

     k++;
    }

    if( duplicate==true )
    {
     if(i!=j)
     {
      if(j<=numberOfNodes)
      edges[count].node2 = j;
      else
       count--;
     }
     else
     {
      degree++;
      count--;
     }
    }
   }

  }
 }

 for( i = 1; i <= numberOfEdges; i++ )
 {
  //if( edges[i].node2 != 0 )
  cout<<"第"<<i<<"條邊 ("<<edges[i].node1<<" , "<<edges[i].node2<<" )"<<endl;
 }

}

void MaxHeapify( Edge edges[],long i , long heapsize )
{
 long l,r,largest,buf;

 l = 2*i;
 r = (2*i)+1;

 if( l<=heapsize && edges[l].weight>edges[i].weight )
  largest = l;
 else
  largest = i;
 if( r<=heapsize && edges[r].weight>edges[largest].weight )
  largest = r;

 if( largest!=i )
 {
  buf = edges[i].weight;
  edges[i].weight = edges[largest].weight;
  edges[largest].weight = buf;

  buf = edges[i].node1;
  edges[i].node1 = edges[largest].node1;
  edges[largest].node1 = buf;

  buf = edges[i].node2;
  edges[i].node2 = edges[largest].node2;
  edges[largest].node2 = buf;

  MaxHeapify(edges,largest,heapsize);
 }
}

void BuildMaxHeap( Edge edges[],long numberOfEdges )
{
 long heapsize;

 heapsize = numberOfEdges;

 for(long i = numberOfEdges/2;i>0;i--)
  MaxHeapify(edges,i,heapsize);
}

void heapSort( Edge edges[], long numberOfEdges )
{
 long buf,heapsize;

 heapsize = numberOfEdges;

 BuildMaxHeap(edges,numberOfEdges);

 for(long i = numberOfEdges;i>1;i--)
 {
  buf = edges[1].weight;
  edges[1].weight = edges[i].weight;
  edges[i].weight = buf;

  buf = edges[1].node1;
  edges[1].node1 = edges[i].node1;
  edges[i].node1 = buf;

  buf = edges[1].node2;
  edges[1].node2 = edges[i].node2;
  edges[i].node2 = buf;

  heapsize--;
  MaxHeapify( edges,1,heapsize);

 }
}

long findSet( Node forest[], long numberOfNodes, long x )
{
 if( x != forest[x].p )
  forest[x].p = findSet(forest,numberOfNodes,forest[x].p);

 return forest[x].p;
}

void link( Node forest[], long x, long y )
{
 if( forest[x].rank > forest[y].rank )
  forest[y].p = x;
 else
  forest[x].p = y;

 if( forest[x].rank==forest[y].rank )
  forest[y].rank++;
}