May 13, 2009

資料結構作業六(補充)

void ShowCurrentHeap(int Input, int *Heap, int number)
{
 int n;

 if(EmptyFlag == 0)
 {
  for(n = 1; n <= Input; n++)
   cout << Heap[n]  << " ";
 }
 cout << endl;
}
int InputDataIntoHeap(int Number, int *Heap)
{
 int n;
 int NodeData;
 for(n = 1; n <= Number; n++)
 {
  time_t t;
  tm NOW;

  time(&t);
  localtime_s(&NOW, &t);
  
  NodeData = ((rand()<<15) | rand() * NOW.tm_sec) % 100;
  Heap[n] = NodeData;
 }
 n--;
 return n;
}

int AdjustMinHeap(int Pointer, int *Heap)
{
 if(Pointer)
 {
  Parent = 1;

  while(1) // while#1
  {
   LChild = Parent * 2;

   if(LChild > Pointer) // 00
    break;
   else
   { // 00.N
    RChild = LChild+1;

    if(RChild > Pointer)  // 01
    { // 01, Y
     if(Heap[Parent] >= Heap[LChild]) //02
     {
      SwapHeap(Parent, LChild, Heap);
      Child = Parent;
      
      while(1)
      {
       pParent = Child / 2;
       if(!pParent)
       {
        break;
       } else {
        if(Heap[pParent] > Heap[Child])
        {
         SwapHeap(pParent, Child, Heap);
        }
       }
       Child = pParent;
      }
      break;
     } // End of 02
     break;
    } else { // 01.Y
     if( !(Heap[LChild] >= Heap[RChild])) // 03
     { // 03.N
      if(!(Heap[LChild] > Heap[Parent])) // 04
      { // 04.N
       SwapHeap(Parent, LChild, Heap);
      } // End of 04
     } else { // 03.Y
      if(!(Heap[RChild] > Heap[Parent])) // 05
      { // 05.N
       SwapHeap(Parent, RChild, Heap);
      }  // End of 05
     } //End of 03

     Child = Parent;

     while(1) // while#2
     {
      pParent = Child/2;

      if(pParent == 0) // 06
      { // 06.Y
       Parent++;
       break;
      } else { // 06.N
       if(!(Heap[Child] > Heap[pParent])) // 07
       { // 07.N
        SwapHeap(pParent, Child, Heap);
        Child = pParent;
       } else { // 07.Y
        Parent++;
        break;
       } // End of 07
      } // End of 06
     }  // End of while#2
    } // End of 01
   } // end of 00
  } // End of while#1
 } // End of if(Pointer)
 return Pointer;
} // End of AdjustMinHeap

int SortingHeap(int Pointer, int *Heap, int *TempHeap)
{
 int TempPointer = 1;
 int Counter = 0;

 if(Pointer)
 {
  do{
   Pointer = MinHeap(Pointer, Heap);
   TempHeap[Counter+1] = OutPort;
   Counter++;
  }while(Pointer);

  do {
   Pointer++;
   Heap[Pointer] = TempHeap[TempPointer];
   TempPointer++;
  }while(!(Pointer == Counter));

 } // End of if(!Pointer)
 return Pointer;
}

int MinHeap(int Pointer, int *Heap)
{
 if(Pointer)
 {
  MPointer = 1;
  OutPort = Heap[MPointer];
  Heap[MPointer] = Heap[Pointer];
  Pointer--;
  while(1) // while#1
  {
   LChild = MPointer * 2;
   RChild = LChild +1;
   if(LChild > Pointer)
    break;

   if(RChild > Pointer) // 01
   { // 01.Y
    if(!(Heap[LChild] > Heap[MPointer])) // 02
     SwapHeap(MPointer, LChild, Heap);

    Child = MPointer;

    while(1)
    {
     pParent = Child / 2;

     if(pParent == 0)
     {
      break;
     } else {
      if(Heap[Child] < Heap[pParent])
      {
       SwapHeap(pParent, Child, Heap);
      }
     }
     Child = pParent;
    }
    break;
   } else { // 01.N
    if(!(Heap[LChild] > Heap[RChild])) // 03
    { // 03.N
     if(!(Heap[LChild] > Heap[MPointer])) //04
     { // 04.N
      SwapHeap(MPointer, LChild, Heap);
      MPointer = LChild;
     } else { // 04.Y
      break;
     }// End of 04
    } else { // 03.Y
     if(!(Heap[RChild] > Heap[MPointer])) // 05
     { // 05.N
      SwapHeap(MPointer, RChild, Heap);
      MPointer = RChild;
     } else { //05.Y
      break;
     }// End of 05
    } // End of 03
   } // End of 01
  } // End of while#1
 } else {
  EmptyFlag = 1;
 }  // End of if(Pointer)
 return Pointer;
}

void SwapHeap(int A, int B, int *Heap)
{
 int Temp;
 Temp = Heap[A];
 Heap[A] = Heap[B];
 Heap[B] = Temp;
}
int AddKeyValuetoHeap(int r, int Pointer,  int *Heap)
{
 int TempPointer;
 if(Pointer == 0)
 {
  Pointer++;
  Heap[Pointer] = r;
  return Pointer;
 } else {

  Pointer++;
  TempPointer = Pointer;
  if(TempPointer > MAXHEAP)
  {
   cout << "Heap is full!\n";
   system("pause");
   FullFlag = 1;
   return --Pointer;
  }
  EmptyFlag = 0;

  while(1)
  {
   Parent = TempPointer / 2;
   if(Parent ==0)
   {
    Heap[TempPointer] = r;
    return Pointer;
   } else {
    if (r > Heap[Parent])
    {
     Heap[TempPointer] = r;
     return Pointer;
    } else {
     Heap[TempPointer] = Heap[Parent];
     TempPointer = Parent;
    }
   }
  }
 }
}

Today's Visitors: 0 Total Visitors: 24
[Trackback URL]

Post A Comment









Yes No



Please input the magic number:

( Prevent the annoy garbage messages )
( What if you cannot see the numbers? )
Please input the magic number

誰來收藏
Loading ...
unlog_NVPO 0