資料結構作業八之二: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
請按任意鍵繼續 . . .
===================================================
Previous in This Category: 資料結構作業八之一:QUICK SORT Next in This Category: 資料結構作業九:(Doubly) Linked list creat and table sort & exchange.

