May 29, 2009

資料結構作業八之二:WINNER TREE(SELECTION TREE)

想不到我竟然會盯著一個方塊盯一個下午.......|||Orz|||
個人史上最強拼裝車....
===========================================

#include<iostream>
#include<time.h>

using namespace std;
///////////////////////////////////////////////////////////////////////////////////
//       Definition  declaration
///////////////////////////////////////////////////////////////////////////////////
#define DataSize 10
#define RunSize 1024

///////////////////////////////////////////////////////////////////////////////////
//       Structure declaration
///////////////////////////////////////////////////////////////////////////////////
typedef struct Node
{
 int RUN, BX;
 int Data;
}Node;
typedef Node *WT;

///////////////////////////////////////////////////////////////////////////////////
//       Global Variable declaration
///////////////////////////////////////////////////////////////////////////////////
int r = 0;

///////////////////////////////////////////////////////////////////////////////////
//       Function declaration
///////////////////////////////////////////////////////////////////////////////////
int GetRandomData(void);
void InsertSort(WT *RunArray, int n);
void WinnerTreeSort(WT *RunArrayX, WT *WinnerTreeX, WT *ResultArrayX, int n);

///////////////////////////////////////////////////////////////////////////////////
//       MAIN START
///////////////////////////////////////////////////////////////////////////////////
void main (void)
{
 int n, qq;
 WT RunArray[RunSize + 1][DataSize + 1];
 WT WinnerTree[256];
 WT ResultArray[256];

 cout << "Input # of RUN(2,4,8,16....2^n):";
 cin >> n;
 for(int i = 1; i <= n; i++)
 {
  for(int j = 1; j <= DataSize; j++)
  {
   qq = GetRandomData();
   RunArray[i][j] = (WT) malloc(sizeof(Node));
   RunArray[i][j]->Data = qq;
   RunArray[i][j]->RUN = i;
   RunArray[i][j]->BX = j;
  }
 }

 for(int i = 1; i <= n * 2 - 1; i++)
 {
  WinnerTree[i] = (WT)malloc(sizeof(Node));
  WinnerTree[i]->RUN = NULL;
  WinnerTree[i]->BX = NULL;
  WinnerTree[i]->Data = NULL;
 }

 for(int i = 1; i <= n * DataSize; i++)
 {
  ResultArray[i] = (WT)malloc(sizeof(Node));
  ResultArray[i]->RUN = NULL;
  ResultArray[i]->BX = NULL;
  ResultArray[i]->Data = NULL;
 }

 cout << "\nOrignal RUN[n] data.\n";
 for(int i = 1; i <= n; i++)
 {
  cout << "RUN[" << i << "]=";
  for(int j=1; j<= DataSize; j++)
  {
   cout <<RunArray[i][j]->Data;
   if(j%DataSize == 0)
    cout << endl;
   else
    cout << ", ";
  }
 }
///////////////////////////////////////////////////////////////////////////////////
 InsertSort(&RunArray[0][0], n);
 cout << "\nAfter First Sorting.\n";
 for(int i = 1; i <= n; i++)
 {
  cout << "RUN[" << i << "]=";
  for(int j=1; j <= DataSize; j++)
  {
   cout << RunArray[i][j]->Data;
   if(j%DataSize == 0)
    cout << endl;
   else
    cout << ", ";
  }
 }
///////////////////////////////////////////////////////////////////////////////////
 WinnerTreeSort(&RunArray[0][0], WinnerTree, ResultArray, n);
  cout << "\nAfter Second Sorting, RESULT[1.." << DataSize * n << "]=\n";
 for(int i = 1; i<= n * DataSize; i++)
 {
  cout << ResultArray[i]->Data;
  if(i % DataSize == 0)
   cout << endl;
  else
   cout << ", ";
 }
 cout << endl;
}
///////////////////////////////////////////////////////////////////////////////////
//       MAIN END
///////////////////////////////////////////////////////////////////////////////////

 


///////////////////////////////////////////////////////////////////////////////////
//       Routine: GetRandomData
///////////////////////////////////////////////////////////////////////////////////
int GetRandomData(void)
{
 int data;
  time_t t;
  tm NOW;

  time(&t);
  localtime_s(&NOW, &t);
  
  data = ((rand()<<15) | rand() * NOW.tm_sec) % 1000;
  return data;
}

///////////////////////////////////////////////////////////////////////////////////
//       Routine: InsertSort
///////////////////////////////////////////////////////////////////////////////////
void InsertSort(WT *RunArrayX, int n)
{
 int p, np, scan, temp, x;
 WT tmp1;
 WT tmp2;

 for(int i = 1; i<= n; i++)
 {

  p = 1;
  np = p+1;
xxx:
  if(np > DataSize)
  {
  } else {
   scan = np;
   p = scan-1;
yyy:
   x = i * (DataSize + 1);
   tmp1 = *(RunArrayX + x + scan);
   tmp2 = *(RunArrayX + x + p);
   if(!(tmp1->Data > tmp2->Data))
   {
    temp = tmp2->Data;
    tmp2->Data = tmp1->Data;
    tmp1->Data = temp;
    scan = scan-1;
    if(scan == 1)
    {
zzz:
     np = np+1;
     goto xxx;
    } else {
     p = scan-1;
     goto yyy;
    }
   }
   goto zzz;
  }
 }
}

///////////////////////////////////////////////////////////////////////////////////
//       Routine: WinnerTreeSort
///////////////////////////////////////////////////////////////////////////////////
void WinnerTreeSort(WT *RunArrayX, WT *WinnerTreeX, WT *ResultArrayX, int n)
{

 int p, nt, i, j, k;
 for(i = n, j = 1, k = 1; i <= n * 2 - 1; i++, j++)
   WinnerTreeX[i] = *(RunArrayX + j * (DataSize + 1) + k);

 p=n;

 do{
  nt=p;
  do{
   if(!(WinnerTreeX[p]->Data > WinnerTreeX[p + 1]->Data))
    WinnerTreeX[p / 2] = WinnerTreeX[p];
   else
    WinnerTreeX[p / 2] = WinnerTreeX[p + 1];
   p = p + 2;
  }while(!(p >= (nt * 2)));
  p = nt / 2;
 }while(!(p == 1));


 int count = 1;
 do{
  ResultArrayX[count]->Data = WinnerTreeX[p]->Data;
  count++;

  if(count > (DataSize * n))
   break;

  if(WinnerTreeX[p]->BX == DataSize)
  {
   WinnerTreeX[p]->Data = 0xFFFF;

   p = WinnerTreeX[p]->RUN+n-1;

   do{
    if(p%2 == 0)
     p=p+1;
    else
     p=p-1;

    if(WinnerTreeX[p]->Data == 0xFFFF)
     p = p-2;

   }while(WinnerTreeX[p]->Data == 0xFFFF);

  } else {
    WinnerTreeX[WinnerTreeX[p]->RUN + n - 1] = *(RunArrayX + (WinnerTreeX[p]->RUN) * (DataSize + 1) + (WinnerTreeX[p]->BX + 1));
    p = WinnerTreeX[p]->RUN + n - 1;
  }

  do{
   if(!(p % 2))
   {
    if(WinnerTreeX[p]->Data > WinnerTreeX[p + 1]->Data)
     WinnerTreeX[p / 2] = WinnerTreeX[p + 1];
    else
     WinnerTreeX[p / 2]=WinnerTreeX[p];

   } else {
    if(WinnerTreeX[p - 1]->Data > WinnerTreeX[p]->Data)
     WinnerTreeX[p / 2] = WinnerTreeX[p];
    else
     WinnerTreeX[p / 2] = WinnerTreeX[p - 1];
   }
   p=p / 2;
  }while(p != 1);
 }while(1);
}

===================================================
Input # of RUN(2,4,8,16....2^n):8

Orignal RUN[n] data.
RUN[1]=591, 364, 604, 214, 696, 965, 967, 143, 262, 452
RUN[2]=396, 621, 446, 636, 163, 126, 34, 520, 711, 198
RUN[3]=399, 137, 744, 283, 452, 308, 409, 303, 841, 514
RUN[4]=191, 274, 378, 110, 912, 177, 325, 622, 473, 484
RUN[5]=339, 154, 408, 272, 292, 171, 767, 858, 778, 529
RUN[6]=343, 218, 522, 338, 802, 813, 728, 521, 465, 536
RUN[7]=474, 356, 619, 30, 860, 550, 284, 166, 3, 165
RUN[8]=891, 395, 665, 854, 988, 130, 670, 600, 723, 155

After First Sorting.
RUN[1]=143, 214, 262, 364, 452, 591, 604, 696, 965, 967
RUN[2]=34, 126, 163, 198, 396, 446, 520, 621, 636, 711
RUN[3]=137, 283, 303, 308, 399, 409, 452, 514, 744, 841
RUN[4]=110, 177, 191, 274, 325, 378, 473, 484, 622, 912
RUN[5]=154, 171, 272, 292, 339, 408, 529, 767, 778, 858
RUN[6]=218, 338, 343, 465, 521, 522, 536, 728, 802, 813
RUN[7]=3, 30, 165, 166, 284, 356, 474, 550, 619, 860
RUN[8]=130, 155, 395, 600, 665, 670, 723, 854, 891, 988

After Second Sorting, RESULT[1..80]=
3, 30, 34, 110, 126, 130, 137, 143, 154, 155
163, 165, 166, 171, 177, 191, 198, 214, 218, 262
272, 274, 283, 284, 292, 303, 308, 325, 338, 339
343, 356, 364, 378, 395, 396, 399, 408, 409, 446
452, 452, 465, 473, 474, 484, 514, 520, 521, 522
529, 536, 550, 591, 600, 604, 619, 621, 622, 636
665, 670, 696, 711, 723, 728, 744, 767, 778, 802
813, 841, 854, 858, 912, 965, 967, 860, 891, 988

請按任意鍵繼續 . . .
===================================================

Today's Visitors: 0 Total Visitors: 125
Personal Category: 台北科技大學 Topic: learning / education / advanced edu.
Previous in This Category: 資料結構作業八之一:QUICK SORT   Next in This Category: 資料結構作業九:(Doubly) Linked list creat and table sort & exchange.
[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