| Задание
| Краткие теоретические сведения
|
| 1. В правой части приведена программа, реализующая основные работы с бинарной кучей, представленной в виде массива.
Опробовать программу и написать комментарии к программному коду.
.
| | #include <iostream>
using namespace std;
const long int MaxV = 5000;
long int a[MaxV]; long int n,i;
long int heap[MaxV]; long int nheap, tmp;
void InitHeap(void)
{ nheap = 0; }
void MoveUp(long int ind)
{ long int k; k = ind / 2; if(ind > 1)
{ if(heap[ind] < heap[k])
{ tmp = heap[ind]; heap[ind] = heap[k];
heap[k] = tmp; MoveUp(k); } }
}
void MoveDown(long int ind)
{ long int k; k = ind * 2; if(k <= nheap)
{ if((k+1 <= nheap) && (heap[k] > heap[k+1])) k++;
if(heap[ind] > heap[k])
{ tmp = heap[ind]; heap[ind] = heap[k];
heap[k] = tmp; MoveDown(k); } } }
| void HeapAdd(long int x)
{ nheap++; heap[nheap] = x; MoveUp(nheap);
}
long int ExtractMin(void)
{ long int value; value = heap[1];
heap[1] = heap[nheap]; heap[nheap] = 0;
nheap--; MoveDown(1);
return value;
}
void main(void)
{ setlocale(LC_ALL, "Russian"); InitHeap();
cout<<"Введите количество элементов "; cin>>n; for(i=0; i<n; i++){
cout<<"Введите "<<i+1<<" элемент= ";
cin>>tmp; HeapAdd(tmp); }
for(i=0; i<n; i++) { a[i] = ExtractMin(); }
cout<<"Результат= ";
for(i=0; i<n; i++) cout<<a[i]<<' ';
fflush(stdin); getchar();
}
| |
| 2. Пункты 2, 3, 4 содержат программный код проекта, в котором реализована бинарная куча также на основе массива.
В правой части данного пункта представлена главная функция и
Дополнить комментарии к программе.
| | #include "stdafx.h"
#include "Heap.h"
#include <iostream>
#include <fstream>
using namespace std;
heap::CMP cmpAAA(void* a1, void* a2)
//функция сравнения
{
#define A1 ((AAA*)a1)
#define A2 ((AAA*)a2)
heap::CMP rc=heap::EQUAL;
if(A1 -> x > A2 -> x)
rc = heap::GREAT;
else
if (A2 -> x > A1 -> x)
rc = heap::LESS;
return rc;
#undef A2
#undef A1
}
bool BuildHeap(char *FileName, heap::Heap& h)// построение кучи из файла
{ bool rc = true; int n;
ifstream inFile;
inFile.open(FileName, std::ios::out);
if(!inFile)
{ cout<<"Невозможно открыть файл"<<endl; exit(1); }
cout<<" Исходные данные"<<endl;
while (inFile>>n)
{ int *a = new int;
*a = n; h.Insert((void*)a);
cout<<*a<<endl; }
inFile.close();
return rc;
}
/ функция записи одного элемента в файл
// сохранение в файл заданного дерева сверху вниз
void SaveHeap(heap::Heap &h, char *FileName)
{ ofstream outFile(FileName, ios_base::out | ios_base::trunc);
if (!outFile)
{ std::cout<<"Ошибка открытия выходного файла"<<std::endl;
return; }
int *a = new int;
for(int u = 0, y = 0; u < h.Size; u++)
{ a = (int*)h.Storage[u];
outFile<<*a; outFile<<endl; }
outFile.close();
}
| int _tmain(int argc, _TCHAR* argv[])
{
setlocale(LC_ALL,"rus");
int k;
heap::Heap h1=heap::Create(30,cmpAAA);
int choise;
for(;;)
{
cout<<"1 - вывод кучи на экран"<<endl;
cout<<"2 - добавление элемента"<<endl;
cout<<"3 - удаление максимального"<<endl;
cout<<"4 - очистить кучу"<<endl;
cout<<"5 - сохранить в файл"<<endl;
cout<<"6 - загрузить из файла"<<endl;
cout<<"0 - выход"<<endl;
cout<<"сделайте выбор"<<endl;
cin>>choise;
switch(choise)
{
case 0: exit(0);
case 1: h1.Scan(0);
break;
case 2: { AAA *a = new AAA;
cout<<"введите ключ"<<endl;
cin>>k;
a->x=k;
h1.Insert(a); }
break;
case 3: h1.ExtractMax();
break;
case 4: h1.DeleteHeap();
break;
case 5: SaveHeap(h1, "G.txt");
break;
case 6: { h1.DeleteHeap();
BuildHeap("G.txt", h1); }
break;
default:
cout << endl << "Введена неверная команда!"; cout << endl; }
}
return 0;
}
|
|
| 3. В правой части записан программный модуль Heap.cpp.
Написать комментарии к программному коду.
| | #include "stdafx.h"
#include "Heap.h"
#include <iostream>
#include <iomanip>
void AAA::Print(){ std::cout << x; }
int AAA::GetPriority() const {return x;}
namespace heap
{Heap Create(int maxsize, CMP(*f)(void*, void*))
{ return *(new Heap(maxsize, f)); }
int Heap::Left(int ix)
{ return (2*ix+1 >= Size)?-1: (2*ix+1); }
int Heap::Right(int ix)
{ return (2*ix+2>=Size)?-1: (2*ix+2); }
int Heap::Parent(int ix) { return (ix+1)/2-1; }
void Heap::Swap(int i, int j)
{ void* buf=Storage[i]; Storage[i]=Storage[j];
Storage[j]=buf;
}
void Heap::Heapify(int ix)
{ int l = Left(ix), r = Right(ix), irl = ix;
if(l>0)
{ if(isGreat(Storage[l],Storage[ix])) irl = l;
if(r>0&&isGreat(Storage[r],Storage[irl]))
irl = r; if(irl!= ix)
{ Swap(ix, irl); Heapify(irl); } } }
| void Heap::Insert(void* x)
{ int i; if(!isFull())
{ Storage[i=++Size-1] = x;
while(i>0 && isLess(Storage[Parent(i)], Storage[i]))
{ Swap(Parent(i),i); i=Parent(i); } }
}
void* Heap::ExtractMax()
{ void* rc; if(!isEmpty())
{ rc=Storage[0]; Storage[0]=Storage[Size-1];
Size--; Heapify(0); }
return rc; }
//вывод значений элементов на экран
void Heap::Scan(int i) const
{ int prodel = 20; std::cout<<'\n';
if (Size==0) std::cout<<"Куча пуста";
for(int u=0,y=0;u<Size;u++)
{cout<<setw(prodel+10)<<setfill(' ');
((AAA*)Storage[u])->Print();
if(u==y) { cout<<'\n';
if(y==0)y=2; else y+=y*2; } prodel/=2; }
cout<<'\n'; }
void Heap::DeleteHeap()
{ if(!isEmpty())
{ Size = 0; this->~Heap(); } }
}
|
|
| 4. В правой части записан заголовочный файл Heap.h.
Написать комментарии к программному коду.
| | #pragma once
struct AAA
{int x;//приоритет
void Print();
int GetPriority() const;
};
namespace heap
{enum CMP{LESS=-1, EQUAL=0, GREAT=1};
struct Heap
{ int Size; int MaxSize;
void** Storage;
CMP (*Compare)(void*,void*);
Heap(int maxsize,CMP (*f)(void*,void*))
{ Size=0; Storage=new void*[MaxSize=maxsize]; Compare=f; };
Heap(int maxsize,CMP(*f)(void*, void*), void* x[])
{Size=0; Storage=x;
MaxSize=maxsize; Compare=f; };
int Left(int ix); int Right(int ix);
int Parent(int ix);
| bool isFull() const {return (Size>=MaxSize);};
bool isEmpty() const {return (Size<=0);};
bool isLess(void* x1,void* x2) const
{ return Compare(x1,x2)==LESS;};
bool isGreat(void* x1,void* x2) const
{ return Compare(x1,x2)==GREAT;};
bool isEqual(void* x1,void* x2) const
{ return Compare(x1,x2)==EQUAL;};
void Swap(int i,int j);
void Heapify(int ix);
void Insert(void* x);
void* ExtractMax();
void DeleteHeap();
void Scan(int i) const;
};
Heap Create(int maxsize, CMP(*f)(void*, void*));
};
|
|
5. В проект добавить следующие функции: удаление минимального ExtractMin; удаление i-ого элемента ExtractI; вывод значений элементов на экран Scan; объединения Union двух куч в одну. Написать программу со всеми операциями (через меню).
