資料結構作業六(補充)
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;
}
}
}
}
}
Previous in This Category: 資料結構作業六:Heap Creating, Adjusting and Sorting. (Minimum) Next in This Category: 搞死人的資料結構作業七:BST(Add / Del)

