アルゴリズムの導論の第6章のスタックの順序付けの与えた偽のコードの変換の具体的なプログラム
15526 ワード
まず自分で書いたクラスのないC++コードをshowします.
このコードは境界問題を完全に無視しているので、いくつかの間違いをもたらしました.
以下は私がネットユーザーからもらったコードに基づいて変更し、複数の関数の境界/条件を調整した後、クラスの方法で完璧に解決しました.
以下は6.5-3課後の問題の引用の最小の山の問題です
以下はクラスを持たないC++コードです
次はクラス付きC++最小スタックコードです.
#include <iostream>
using namespace std;
const length=100;
int A[length]={1,9,10,2,7,5,6,4,13,3,18,11,100};
int Heap_size(int A[]);// 0 。
int heap_size=Heap_size(A);
int PARENT(int i);//
int LEFT(int i);//
int RIGHT(int i);//
void MAX_HEAPIFY(int A[],int i);//
void BUILD_MAX_HEAP(int A[]);//
void Print(int A[]);
void Print1(int A[]);
void HEAPSORT(int A[]);//
int MAXIMUM(int A[]);
int HEAP_EXTRACT_MAX(int A[]);// 。
void HEAP_INCREASE_KEY(int A[],int i,int key);// i key
void MAX_HEAP_INSERT(int A[],int key);
void main()
{
int A[length]={1,9,10,2,7,5,6,4,13,3,18,11,100};
cout<<" ："<<endl;
Print(A);
cout<<" ："<<endl;
BUILD_MAX_HEAP(A);
Print(A);
cout<<" ："<<endl;
HEAP_EXTRACT_MAX(A);
Print(A);
cout<<" 8 15："<<endl;
HEAP_INCREASE_KEY(A,8,15);
Print(A);
cout<<" 56："<<endl;
MAX_HEAP_INSERT(A,56);
Print(A);
cout<<" ："<<endl;
HEAPSORT(A);
Print1(A);
}
int PARENT(int i)
{
return (i-1)/2;
}
int LEFT(int i)
{
return 2*i+1;
}
int RIGHT(int i)
{
return 2*i+2;
}
void MAX_HEAPIFY(int A[],int i)
{
int largest=0;
int L=LEFT(i);
int R=RIGHT(i);
if (L<heap_size&&A[L]>A[i])
{
largest=L;
}
else largest=i;
if (R<heap_size&&A[R]>A[largest])
{
largest=R;
}
if (largest!=i)
{
swap(A[i],A[largest]);
MAX_HEAPIFY(A,largest);
}
}
void BUILD_MAX_HEAP(int A[])
{
int heap_size=length;
for (int i=length/2;i>=0;i--)
{
MAX_HEAPIFY(A,i);
}
}
void HEAPSORT(int A[])
{
BUILD_MAX_HEAP(A);
for (int i=Heap_size(A)-1;i>=0;i--)
{
swap(A[0],A[i]);
heap_size--;
MAX_HEAPIFY(A,0);
}
}
int MAXIMUM(int A[])
{
return A[0];
}
int HEAP_EXTRACT_MAX(int A[])
{
if (heap_size<0)
{
cout<<"heap underflow"<<endl;
exit(0);
}
int max=A[0];
A[0]=A[heap_size-1];
heap_size--;
MAX_HEAPIFY(A,0);
A[heap_size]=0;
return max;
}
void HEAP_INCREASE_KEY(int A[],int i,int key)
{
if (key<A[i])
{
return ;
}
A[i]=key;
while (i>0&&A[PARENT(i)]<A[i])
{
swap(A[i],A[PARENT(i)]);
i=PARENT(i);
}
}
void MAX_HEAP_INSERT(int A[],int key)
{
heap_size++;
A[heap_size-1]=-0x7fffffff;
HEAP_INCREASE_KEY(A,heap_size-1,key);
}
int Heap_size(int A[])
{
for (int i=length-1;i>=0;i--)
{
if (A[i]>0)
{
return i+1;
}
}
return -1;
}
void Print(int A[])
{
for (int i=0;i<heap_size;i++)
{
if(A[i]>0)
cout<<A[i]<<" ";
}
cout<<endl;
}
void Print1(int A[])
{
for (int i=0;i<length;i++)
{
if(A[i]>0)
cout<<A[i]<<" ";
}
cout<<endl;
}このコードは境界問題を完全に無視しているので、いくつかの間違いをもたらしました.
以下は私がネットユーザーからもらったコードに基づいて変更し、複数の関数の境界/条件を調整した後、クラスの方法で完璧に解決しました.
//
/*#include <iostream>
using namespace std;
//
#define N 1000
#define PARENT(i) (i)>>1
#define LEFT(i) (i)<<1
#define RIGHT(i) ((i)<<1)+1
class Heap
{
public:
//
int A[N+1];
int length;
int heap_size;
//
Heap(){}
Heap(int size):length(size),heap_size(size){}
~Heap(){}
//
void Max_Heapify(int i);
void Build_Max_Heap();
void HeapSort(int A[]);
//
void Heap_Increase_Key(int i, int key);
void Max_Heap_Insert(int key);
int Heap_Maximum();
int Heap_Extract_Max();
void Heap_Delete(int i);
//
void Print();
void Print1();
};
// i ， i ， O(lgn)
//
void Heap::Max_Heapify(int i)
{
//Print();
int l = LEFT(i), r = RIGHT(i), largest;
// i、i 、i
if(l < heap_size && A[l] > A[i])
largest = l;
else largest = i;
if(r < heap_size && A[r] > A[largest])
largest = r;
// ， ，
//
if(largest != i)
{
//
swap(A[i], A[largest]);
// ，
Max_Heapify(largest);
}
}
// ， O(nlgn)
void Heap::Build_Max_Heap()
{
heap_size = length;
// ， ，
for(int i = length / 2; i >= 0; i--)
Max_Heapify(i);
}
// ， O(nlgn)
void Heap::HeapSort(int A[])
{
//
Build_Max_Heap();
// i
for(int i = length-1; i >= 1; i--)
{
// i A[i]
swap(A[0], A[i]);
//
heap_size--;
//
Max_Heapify(0);
}
}
// i key， key>=A[i]
void Heap::Heap_Increase_Key(int i, int key)
{
if(key < A[i])
{
cout<<"new key is smaller than current key"<<endl;
exit(0);
}
A[i] = key;
// ， A[PARENT(i)]<A[i]，
// A[PARENT(i)]<A[i]，
while(A[PARENT(i)] > 0 && A[PARENT(i)] < A[i])
{
swap(A[PARENT(i)], A[i]);
i = PARENT(i);
}
}
// key A
void Heap::Max_Heap_Insert(int key)
{
if(heap_size == N)
{
cout<<"heap is full"<<endl;
exit(0);
}
heap_size++;length++;
A[heap_size-1] = -0x7fffffff;
Heap_Increase_Key(heap_size-1, key);
}
// A ， O(1)
int Heap::Heap_Maximum()
{
return A[0];
}
// A ， O(lgn)
int Heap::Heap_Extract_Max()
{
if(heap_size < 0)
{
cout<<"heap underflow"<<endl;
exit(0);
}
//
int max = A[0];
//
A[0] = A[heap_size-1];
heap_size--;
//
Max_Heapify(0);
//
return max;
}
// i
void Heap::Heap_Delete(int i)
{
if(i > heap_size)
{
cout<<"there's no node i"<<endl;
exit(0);
}
// i
int key = A[heap_size-1];
heap_size--;
// A[i] ，
if(key > A[i])
Heap_Increase_Key(i, key);
else// ，
{
A[i] = key;
Max_Heapify(i);
A[heap_size]=0;
}
}
void Heap::Print()
{
int i;
for(i = 0; i < heap_size; i++)
{
if(i > 0)cout<<',';
else cout<<"==> A = {";
cout<<A[i];
}
cout<<'}'<<endl;
}
void Heap::Print1()
{
int i;
cout<<"==> A = {";
for(i = 0; i < length; i++)
{
if (A[i]>0)
{
cout<<A[i]<<" ";
}
}
cout<<'}'<<endl;
}
void main()
{
Heap a(13);
a.A[0]=1;a.A[1]=9;a.A[2]=10;a.A[3]=2;a.A[4]=7;
a.A[5]=5;a.A[6]=6;a.A[7]=4;a.A[8]=13;a.A[9]=3;
a.A[10]=18;a.A[11]=11;a.A[12]=100;
a.Build_Max_Heap();
a.Print();
a.Heap_Delete(2);
a.Print();
a.Heap_Extract_Max();
a.Print();
a.Heap_Increase_Key(8,15);
a.Print();
a.Max_Heap_Insert(56);
a.Print();
a.HeapSort(a.A);
a.Print1();
}以下は6.5-3課後の問題の引用の最小の山の問題です
以下はクラスを持たないC++コードです
#include <iostream>
using namespace std;
const length=100;
int A[length]={1,9,10,2,7,5,6,4,13,3,18,11,100};
int PARENT(int i);//
int LEFT(int i);//
int RIGHT(int i);//
void MIN_HEAPIFY(int A[],int i);//
void BUILD_MIN_HEAP(int A[]);//
void Print(int A[]);
void Print1(int A[]);
int Heap_size(int A[]);// 0 。void HEAPSORT(int A[]);//
void HEAPSORT(int A[]);
int MINIMUM(int A[]);
int HEAP_EXTRACT_MIN(int A[]);// 。
void HEAP_INCREASE_KEY(int A[],int i,int key);// i key
void MIN_HEAP_INSERT(int A[],int key);
int heap_size=Heap_size(A);
void main()
{
cout<<" ："<<endl;
Print(A);
cout<<" ："<<endl;
BUILD_MIN_HEAP(A);
Print(A);
cout<<" ："<<endl;
HEAP_EXTRACT_MIN(A);
Print(A);
cout<<" 8 15："<<endl;
HEAP_INCREASE_KEY(A,8,15);
Print(A);
cout<<" 56："<<endl;
MIN_HEAP_INSERT(A,56);
Print(A);
cout<<" ："<<endl;
HEAPSORT(A);
Print1(A);
}
int PARENT(int i)
{
return (i-1)/2;
}
int LEFT(int i)
{
return 2*i+1;
}
int RIGHT(int i)
{
return 2*i+2;
}
void MIN_HEAPIFY(int A[],int i)
{
int largest=0;
int L=LEFT(i);
int R=RIGHT(i);
if (L<heap_size&&A[L]<A[i])
{
largest=L;
}
else largest=i;
if (R<heap_size&&A[R]<A[largest])
{
largest=R;
}
if (largest!=i)
{
swap(A[i],A[largest]);
MIN_HEAPIFY(A,largest);
}
}
void BUILD_MIN_HEAP(int A[])
{
int heap_size=length;
for (int i=length/2;i>=0;i--)
{
MIN_HEAPIFY(A,i);
}
}
void HEAPSORT(int A[])
{
BUILD_MIN_HEAP(A);
for (int i=Heap_size(A)-1;i>=1;i--)
{
swap(A[0],A[i]);
heap_size--;
MIN_HEAPIFY(A,0);
}
}
int MINIMUM(int A[])
{
return A[0];
}
int HEAP_EXTRACT_MIN(int A[])
{
if (heap_size<0)
{
cout<<"heap underflow"<<endl;
exit(0);
}
int min=A[0];
A[0]=A[heap_size-1];
heap_size--;
MIN_HEAPIFY(A,0);
A[heap_size]=0;
return min;
}
void HEAP_INCREASE_KEY(int A[],int i,int key)
{
if (key<A[i])
{
return ;
}
A[i]=key;
while (i>0&&A[PARENT(i)]>A[i])
{
swap(A[i],A[PARENT(i)]);
i=PARENT(i);
}
}
void MIN_HEAP_INSERT(int A[],int key)
{
heap_size++;
A[heap_size-1]=-0x7fffffff;
HEAP_INCREASE_KEY(A,heap_size-1,key);
}
int Heap_size(int A[])
{
for (int i=length-1;i>=0;i--)
{
if (A[i]>0)
{
return i+1;
}
}
return -1;
}
void Print(int A[])
{
for (int i=0;i<heap_size;i++)
{
if(A[i]>0)
cout<<A[i]<<" ";
}
cout<<endl;
}
void Print1(int A[])
{
for (int i=0;i<length;i++)
{
if(A[i]>0)
cout<<A[i]<<" ";
}
cout<<endl;
}次はクラス付きC++最小スタックコードです.
//
/*#include <iostream>
using namespace std;
//
#define N 1000
#define PARENT(i) (i)>>1
#define LEFT(i) (i)<<1
#define RIGHT(i) ((i)<<1)+1
class Heap
{
public:
//
int A[N+1];
int length;
int heap_size;
//
Heap(){}
Heap(int size):length(size),heap_size(size){}
~Heap(){}
//
void Min_Heapify(int i);
void Build_Min_Heap();
void HeapSort(int A[]);
//
void Heap_Increase_Key(int i, int key);
void Min_Heap_Insert(int key);
int Heap_Minimum();
int Heap_Extract_Min();
void Heap_Delete(int i);
//
void Print();
void Print1();
};
// i ， i ， O(lgn)
//
void Heap::Min_Heapify(int i)
{
//Print();
int l = LEFT(i), r = RIGHT(i), largest;
// i、i 、i
if(l < heap_size && A[l] < A[i])
largest = l;
else largest = i;
if(r < heap_size && A[r] < A[largest])
largest = r;
// ， ，
//
if(largest != i)
{
//
swap(A[i], A[largest]);
// ，
Min_Heapify(largest);
}
}
// ， O(nlgn)
void Heap::Build_Min_Heap()
{
heap_size = length;
// ， ，
for(int i = length / 2; i >= 0; i--)
Min_Heapify(i);
}
// ， O(nlgn)
void Heap::HeapSort(int A[])
{
//
Build_Min_Heap();
// i
for(int i = length-1; i >= 1; i--)
{
// i A[i]
swap(A[0], A[i]);
//
heap_size--;
//
Min_Heapify(0);
}
}
// i key， key>=A[i]
void Heap::Heap_Increase_Key(int i, int key)
{
if(key < A[i])
{
cout<<"new key is smaller than current key"<<endl;
exit(0);
}
A[i] = key;
// ， A[PARENT(i)]<A[i]，
// A[PARENT(i)]>A[i]，
while(A[PARENT(i)] > 0 && A[PARENT(i)] > A[i])
{
swap(A[PARENT(i)], A[i]);
i = PARENT(i);
}
}
// key A
void Heap::Min_Heap_Insert(int key)
{
if(heap_size == N)
{
cout<<"heap is full"<<endl;
exit(0);
}
heap_size++;length++;
A[heap_size-1] = -0x7fffffff;
Heap_Increase_Key(heap_size-1, key);
}
// A ， O(1)
int Heap::Heap_Minimum()
{
return A[0];
}
// A ， O(lgn)
int Heap::Heap_Extract_Min()
{
if(heap_size < 0)
{
cout<<"heap underflow"<<endl;
exit(0);
}
//
int min = A[0];
//
A[0] = A[heap_size-1];
heap_size--;
//
Min_Heapify(0);
//
return min;
}
// i
void Heap::Heap_Delete(int i)
{
if(i > heap_size)
{
cout<<"there's no node i"<<endl;
exit(0);
}
// i
int key = A[heap_size-1];
heap_size--;
// A[i] ，
if(key < A[i])
Heap_Increase_Key(i, key);
else// ，
{
A[i] = key;
Min_Heapify(i);
A[heap_size]=0;// 0。 HeapSort 。
}
}
void Heap::Print()
{
int i;
for(i = 0; i < heap_size; i++)
{
if(i > 0)cout<<',';
else cout<<"==> A = {";
cout<<A[i];
}
cout<<'}'<<endl;
}
void Heap::Print1()
{
int i;
cout<<"==> A = {";
for(i = 0; i < length; i++)
{
if (A[i]>0)
{
cout<<A[i]<<" ";
}
}
cout<<'}'<<endl;
}
void main()
{
Heap a(13);
a.A[0]=1;a.A[1]=9;a.A[2]=10;a.A[3]=2;a.A[4]=7;
a.A[5]=5;a.A[6]=6;a.A[7]=4;a.A[8]=13;a.A[9]=3;
a.A[10]=18;a.A[11]=11;a.A[12]=100;
a.Build_Min_Heap();
a.Print();
a.Heap_Delete(2);
a.Print();
a.Heap_Extract_Min();
a.Print();
a.Heap_Increase_Key(8,15);
a.Print();
a.Min_Heap_Insert(10);
a.Print();
a.HeapSort(a.A);
a.Print1();// ， ，
}