2.2.2 Функция для перестроения пирамиды
Функция предназначена для просеивания всех оставшихся элементов после перестановки местами первого и последнего элемента. Функция работает с двумя входными параметрами:
a[] – массив цифр, требующий преобразования после перестановки местами граничных элементов.
k – переменная указывающая номер элемента с которого начинается выполнение алгоритма.
n – переменная указывающая до которого момента выполняется алгоритм.
void downHeap(int a[], long k, long n)
{
// процедура просеивания следующего элемента
// До процедуры: a[k+1]...a[n] - пирамида
// После: a[k]...a[n] - пирамида
int new_elem;
long child;
new_elem = a[k];
while(k <= n/2) // пока у a[k] есть дети
{
child = 2*k;
if( child < n && a[child] < a[child+1] ) // выбираем большего сына
child++;
if( new_elem >= a[child] )
break;
// иначе
a[k] = a[child]; // переносим сына наверх
k = child;
}
a[k] = new_elem;
}
2.2.3 Главная функция программы
Эта функция отвечает за реализацию диалога с пользователем, защиту от неправильного ввода и последовательный вызов функций в зависимости от действий пользователя.
void main( )
{
int ,key;
//выделяем память под массив
int *arr=new int [10];
//вывод информации для пользователя
cout<<” Vvesti massiv. Otsortirovat' massiv pri pomoshi algoritma \n”;
cout<<” Piramidal'noy sortirivku.\n”;
cout<<endl;
//выбираем способ заполнения массива
cout<<" Vibirite sposob vvoda:"<<endl;
cout<<endl;
cout<<"1 S klaviaturi"<<endl;
cout<<"2 Sluhaynie hisla"<<endl;
//проверка на правильность ввода ключа
do{
cin>>key;
if(key==1||key==2) break;
else cout<<" Ne pravil'niy vvod. Povtorite"<<endl;
}while(1);
//подключаем генератор случайных чисел
randomize();
//функция выбора решения по ключу
switch(key){
case 1:
cout<<"Ishodniy massiv: "<<endl;
for (int i=0;i<10;i++)
{
//заполняем массив
cin>>arr[i];
//проверка правильности ввода чисел
if(cin.fail( )){
do {
cout<<" Ne pravil'niy vvod. Povtorite"<<endl;
cin.clear();
cin.ignore();
cin>>arr[i];
}while(cin.fail());
}
}
cout<<endl;
break;
case 2:
cout<<"Sluchainiy massiv: "<<endl;
for (int i=0;i<10;i++)
{
//заполняем массив
arr[i]=random(20)-10;
//выводим его
cout<<arr[i]<<" ";
}
cout<<endl;
break;
}
heapSort(arr, size);
cout<<endl<<"Utogoviy massiv: "<<endl;
for (int i=0; i < 10; i++) {
cout<<arr[i]<<" ";
}
cout<<endl;
delete arr;
getch();
}
Описание работы программного комплекса
Инструкция по работе с программным комплексом
После запуска программы на экране пользователя появляется окно (см.рис.1), в котором будет выведены: номер варианта задания, формулировка задания и список команды выполняемых программой.
Рис.6 Приглашение программы
Каждую команду можно активировать, нажав соответствующую клавишу на клавиатуре («1» - Вручную ввести дерево, «2» - Автоматически сгенерировать дерево).
В случае ввода символа, для которого не предусмотрена никакая команда, программа предложит повторить ввод.
Выбрав команду «2», программа автоматически сгенерирует массив и отсортирует его пирамидальной сортировкой (см.рис.2).
Рис. 2 Пример автоматической генерации массива
Команда
«1» позволит пользователю самостоятельно
заполнить массив элементами в диалоговом
режиме (см.рис.3).
Рис. 3 Ручной ввод элементов массива
При некорректном вводе программа сообщит пользователю о ошибке и предложит повторить ввод (см. рис. 4)
Рис. 4 Сообщения о ошибках