Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Класи. Бінарні дерева
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра СКС
Інформація про роботу
Рік:
2012
Тип роботи:
Курсова робота
Предмет:
Програмування частина 4 Технологія системного програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Інститут дистанційного навчання
Кафедра СКС
КУРСОВА РОБОТА
з дисципліни «Програмування»
на тему «Класи. Бінарні дерева»
Варіант № 23
Завдання на курсову роботу:
Провести огляд класів, доступу до полів та методів класу, статичних членів класу, реалізації механізмів успадкування та поліморфізму в С++, доступу до базових класів, друзів класу, шаблонів класів, перевантаження операторів для класів, а також бінарних дерев, що широко застосовуються у програмуванні. Розглянути їх властивості і практичне значення.
Згенерувати три масиви з випадковими елементами типу Integer довжиною 100, 1000 та 10000 елементів, відповідно.
Відсортувати одержані масиви за збільшенням елементів, визначивши при цьому такі параметри:
кількість порівнянь;
кількість обмінів;
фактичний час роботи,
необхідні кожній з програм (простий та один з довершених методів), щоби відсортувати кожен з трьох масивів.
ЗМІСТ
1.
Динамічний розподіл пам’яті…………………………………………...
4
2.
Доступ до полів та методів класу. Статичні члени класу…………….
5
3.
Реалізація механізмів успадкування та поліморфізму в С++. Доступ до базових класів………………………………………………………..
7
4.
Друзі класу……………………………………………………………….
10
5.
Шаблони класів………………………………………………………….
12
6.
Перевантаження операторів для класів………………………………...
14
7.
Бінарні дерева……………………………………………………………
15
8.
Практична реалізація простих методів сортування…………………..
22
Висновки……………………………………………………………………….
29
Список використаної літератури……………………………………………..
30
1. ДИНАМІЧНИЙ РОЗПОДІЛ ПАМ’ЯТІ
Для більш ефективного використання пам’яті часто доводиться розроблювати класи, в яких розмір об’єкту залежить від даних, що в ньому зберігаються. В таких структурах часто об’єм потрібної пам’яті стає відомим лише безпосередньо перед ініціалізацією конкретного об’єкта даного класу. Це призводить до необхідності динамічного керування пам’яттю. Для цих цілей в С++ передбачено два оператори new та delete. Оператор new дозволяє виділити пам’ять об’єкту, оператор delete дозволяє звільнити пам’ять Динамічний розподіл пам’яті вимагає використання покажчиків.
Розглянемо приклади.
Динамічне виділення пам’яті під одновимірний масив
float* y;
y=new float [5];
Очищення пам’яті, виділеної динамічно під одновимірний масив
delete y;
Динамічне виділення пам’яті під двовимірний масив
float** y;
y=new float* [5];
for(i=0;i<5;i++) {y[i]= new float[5] };
Очищення пам’яті, виділеної динамічно під двовимірний масив
for(i=0;i<5;i++) {delete y[i] };
delete y;
Зрозуміло, що оператор new використовується в конструкторі, а оператор delete в деструкторі. Розглянемо приклад.
Нехай нам потрібен клас одновимірний вектор, розмір якого визначається у момент ініціалізації. Такий клас повинен мати конструктор з параметром, що вказує на розмір вектора та конструктор за замовчуванням, щоб не виникали аварійні ситуації при ініціалізації без параметрів. Будемо вважати, що за замовчуванням наш вектор буде тривимірним. Щоб не ускладнювати приклад в описі класу покажемо лише конструктори та деструктори, а інші необхідні методи не показуватимемо.
class MyVector
{
private:
float *v;
int size;
public:
MyVector(){size=3; v= new float[size];}; //конструктор за замовчуванням
MyVector(int a) {size= a; v= new float[size];}; //конструктор з параметром
~MyVector(){delete[] v;};//деструктор
...
};
2. ДОСТУП ДО ПОЛІВ ТА МЕТОДІВ КЛАСУ.
СТАТИЧНІ ЧЛЕНИ КЛАСУ
Доступ до відкритих полів та методів класу здійснюється прямим зверненням, з використанням операторів прямого і непрямого вибору, як в структурах і об'єднаннях.
Оператор прямого вибору – це точка „.”. Оператор непрямого вибору – це спеціальний символ, що складається з мінуса та знаку більше „->”. Оператор прямого вибору використовується тоді, коли доступ до об’єкту класу у рограмі виконується безпосередньо. Оператор непрямого (опосередкованого) вибору використовується, коли доступ до об’єкту класу у програмі виконується опосередковано через покажчик на об’єкт.
Доступ до закритих та захищених методів та полів здійснюється лише за допомогою відкритих методів класу або за допомогою друзів класу. Доступ за допомогою друзів класу буде розглядатись пізніше, а зараз розглянемо приклад без використання друзів класу.
class MyClass
{
int i; //закрите поле класу
public:
//відкриті методи класу
MyClass(){i=0};//конструктор
inline int get_i(){ return i; };
inline void set_i(int) { i=x; return; };
};
...
void main()
{
MyClass obj;//об’явлення об’єкту
MyClass * obj_ptr=&obj;// об’явлення покажчика на об’єкт
obj. set_i(5) ; //встановлюємо нове значення закритого поля i
//шляхом безпосереднього звернення до відкритого методу
obj_ptr-> set_i(6) ; // встановлюємо нове значення закритого поля i
//шляхом опосередкованого (через покажчик об’єкт) звернення
//до відкритого методу
}
Як зазначалось раніше клас – це тип даних, інформаційна структура, а не об'єкт даних. Кожен об'єкт класу містить свою власну копію полів цього класу. Проте деякі типи найелегантніше реалізуються, якщо всі об'єкти цього типу можуть спільно використовувати (розділяти) деякі дані. При цьому бажано, щоб такі дані , що розділяються, були описані як частина даного класу. Наприклад для управління завданнями в операційній системі використовують список всіх завдань, або при створенні об'єктів класу необхідно, щоб ці об'єкти могли контролювати кількість створених об'єктів даного класу і т.д.
Для реалізації цих властивостей в С++ передбачено використання статичних полів класу. Статичні поля описуються за допомогою ключового слова static. Оскільки статичні члени класу використовуються всіма об’єктами класу, то бажано перед використанням такі поля завжди ініціалізувати при описі класу.
Наведемо приклад.
class MyClassStatic
{
int i;
static int count; //статичне поле класу
public:
MyClassStatic(int a=0){i=a;};//конструктор
int inc_count(){++count; return 0;}; //метод доступу до статичного поля
int get_i(){return i;};//метод доступу до звичайного закритого поля
int get_count(){return count;}; //метод доступу до статичного поля
};
int MyClassStatic::count=0; //ініціалізація статичного поля
3. РЕАЛІЗАЦІЯ МЕХАНІЗМІВ УСПАДКУВАННЯ ТА ПОЛІМОРФІЗМУ В С++. ДОСТУП ДО ЧЛЕНІВ БАЗОВИХ КЛАСІВ
Як уже зазначалося, успадкування і поліморфізм – відносяться до найважливіших механізмів ООП. З їх допомогою можна розробляти дуже складні класи, просуваючись від загального до приватного, а також "нарощувати" вже створені, одержуючи з них нові класи з необхідними властивостями. Основною відмінністю реалізації успадкування і поліморфізму в С++ є можливість успадкування від кількох класів одночасно – множинне успадкування.
Приступаючи до проектування складного класу необхідно з'ясувати, які найбільш загальні властивості повинні бути притаманними даному класу, і чи немає вже готового класу, який би можна було "доробити". Знайшовши такий клас, потрібно успадкувати необхідні властивості і додати нові(або змінити деякі з тих, що вже існують). При цьому потрібно пам'ятати, що в С++ можливе множинне успадкування.
Для ілюстрації вищесказаного наведемо приклад створення нового об'єкту на основі двох базових об'єктів з використанням успадкування їх членів і перевизначенням двох функцій членів, а саме конструктора і функції для виведення вмісту об'єкту на екран.
Настійно рекомендую звернути увагу на визначення конструктора результуючого класу і на звернення до конструкторів базових класів, а так само на використання оператора дозволу області видимості ”::”.
#include <iostream.h>
#include <string.h>
class human //перший базовий клас
{
char* name;
char* surname;
public:
human(char* h_name="anybody", char* h_surname="anybody");//конструктор
~human(){delete name; delete surname;return;};//деструктор
24
void get_info()//метод get_info першого базового класу
{cout <<"\n name - " << name << "\n surname - "<< surname <<"\n"; return ;};
};
//конструктор першого базового класу
human::human(char* h_name, char* h_surname)
{
name = new char[strlen(h_name)+1];
strcpy(name,h_name);
surname = new char[strlen(h_surname)+1];
strcpy(surname,h_surname);
return;
};
//другий базовий клас
class qualification
{
char* trade;
int time;
public:
qualification(char* q_trade="NO", int q_time=0);//конструктор
~qualification(){delete trade;return;}//деструктор
void get_info()//метод get_info другого базового класу
{cout<<"\nmy trade is - "<<trade<<"\ni work in my trade - "<<time<<"-year(s)\n";
return;}
};
//конструктор другого базового класу
qualification::qualification(char* q_trade, int q_time)
{
trade=new char[strlen(q_trade)+1];
strcpy(trade,q_trade);
time=q_time;
return;
}
//клас породжений від двох базових
//базові класи вказуються через кому після символа двокрапки
class employee: human, qualification
{
employee(char* h_name, char* h_surname, char* q_trade, int q_time);
//метод get_info об’єднаного класу виконує лише коректний визов
//методів get_info базових класів
void get_info(){human::get_info();qualification::get_info();return;}
};
//конструктор породженого класу
//у даному випадку виконує лише коректний визов
//конструкторів базових класів, передаючи їм відповідні аргументи
employee::employee(char* h_name, char* h_surname, char* q_trade, int q_time):
human(h_name,h_surname), qualification(q_trade,q_time)
{
//тіло конструктора породженого класу
//тут при необхідності можна виконувати додаткові дії
return;
}
4. ДРУЗІ КЛАСУ
Іноді виникає необхідність, щоб якась функція, що не є членом класу мала доступ до закритих та захищених полів об'єктів даного класу. У С++ є така можливість. Для цього необхідно і достатньо оголосити дану функцію другом цього класу. Зробити це можна за допомогою ключового слова “friend”. Розглянемо це на прикладі.
class friend_prob
{
private:
int status;
public:
int get_status(){return status;}
void set_status(int x){ status=x; return;}
//функція prob_friend оголошується другом класу
void friend prob_friend(friend_prob &obj );
};
void prob_friend( friend_prob &obj)
{
//функція друг здійснює доступ до закритого члена
//класу шляхом прямого звертання.
obj.status++;
return;
}
У даному прикладі функція prob_friend (friend_prob &obj) описана, як друг класу friend_prob. Це дозволяє їй дістати доступ до закритого поля даного класу status. Зверніть увагу на те, що, оскільки в програмі може існувати одночасно декілька об'ектів даного класу, такій функції необхідно як параметр передавати покажчик на об'єкт, з яким вона повинна працювати в даний момент.
Аналогічним чином можна описати метод іншого класу або навіть цілий клас, як друг даного класу. Наприклад, можна визначити клас а, як друг класу b. Тоді методи об'єктів класа а отримають доступ до закритих та захищених полів об'єктів класу b.
Розглянемо приклад.
class MyClass1;//випереджуючий неповний опис класу MyClass1
class MyClass2
{
private://розділ закритих полів класу
int status;
public://розділ відкритих методів класу
int get_status(){return status;}
void set_status(int x){status=x;return;}
friend MyClass1;//об’являємо клас MyClass1 другом класу MyClass2
};
class MyClass1
{
public:
//метод set_status класу MyClass1 модифікує закрите
//поле status класу MyClass2 шляхом прямого звернення
void set_status(MyClass2& obj,int x){obj.status=x;return;}
};
У даному прикладі клас MyClass1 оголошується як друг класу
MyClass. Це дозволяє методу set_status класу MyClass1 звертатися до
закритого поля status класу MyClass2.
Зверніть увагу на те, що, для забезпечення можливості зробити це оголошення, довелося застосувати випереджуючий неповний опис класу MyClass1. Без такого опису компілятор видав би помилку. Крім того методу set_status класу MyClass1 для реалізації доступу до конкретного об'єкту необхідно знати адресу цього об'єкту, тому, як один з аргументів, йому передається покажчик на об'єкт класу MyClass2.
Наявність механізму установлення дружніх відносин між класами дозволяє моделювати досить складні відносини між класами, що значно полегшує створення програм для вирішення складних практичних завдань.
5. ШАБЛОНИ КЛАСІВ
Досить часто при використанні ООП виникає необхідність введення великої кількості класів, які виконують однакові дії і відрізняються лише типами даних, по відношенню до яких ці дії застосовуються. Для спрощення виконання цієї задачі в С++ передбачені шаблони класів. Шаблони класів це елементи мови програмування, які дозволяють визначити структуру сімейства класів, за якою компілятор самостійно створює потрібні класи, ґрунтуючись на параметрах настройки, що задаються. Цей механізм аналогічний механізму шаблонів функцій.
Найбільш типовий приклад використання шаблонів класів – це створення контейнерних класів, наприклад, векторів для розміщення об'єктів довільних типів.
Приклад:
template <class T>//шаблон класу вектор
class Vector
{
private:
T *elements;
int size;
public:
Vector(int razm=0); //конструктор, його реалізація має особливості
//деструктор, його реалізація також може мати особливості
~Vector(){delete elements;}
//перевантажений оператор для класу
T& operator[](int i){return elements[i];}//перевантажений оператор-метод
//метод, його реалізація має особливості
void print_contents();
};
//конструктор, його реалізація має особливості
template <class T>
Vector<T>::Vector(int razm)
{
elements=new T[razm];
for(int i=0; i< razm; elements[i]=(T) 0 i++);
size=razm;
};
29
//метод, реалізація якого має особливості
template <class T>
void Vector<T>::print_contents()
{
cout << "elements num-"<<size<<"\n";
for(int i=0; i<size; i++)
cout <<"el["<<i<<"]="<<elements[i] <<"\n";
}
//головна функція
//зверніть увагу на визначення типу для кожного об’єкту
int main()
{
int razmer=10;
Vector <int> i(razmer);
Vector <float> x(razmer);
Vector <char> з(razmer);
…
return 0;
}
Заголовок шаблону класу починається з ключового слова template і містить вказівку на те, що тип наперед невідомий і повинен вказуватись при об’вленні об’єкту <class T>. Замість літери Т може бути використана інша літера. Головне, щоб у всіх методах і полях класу, де буде оброблюватись інформація даного типу стояла та ж сама літера. Це дасть змогу компілятору правильно сформувати об’єкт класу для заданого типу. При розробці шаблонів класів часто виникає проблема перевантаження операторів. Це пов’язано з тим, що з одного боку для розроблених програмістом класів, як правило, немає стандартних операторів, а з іншого боку дуже зручно, коли аналогічні операції для різних типів позначаються у програмі однаковими операторами.
6. ПЕРЕВАНТАЖЕННЯ ОПЕРАТОРІВ ДЛЯ КЛАСІВ
При розробці шаблонів класів часто виникає проблема перевантаження операторів. Це пов’язано з тим, що з одного боку для розроблених програмістом класів, як правило, немає стандартних операторів, а з іншого боку дуже зручно, коли аналогічні операції для різних типів позначаються у програмі однаковими операторами.
Навіть у попередньому прикладі нам довелося перевантажувати оператор індексу, щоб можна було звертатись до елемента вектора таким же чином, як до елемента масиву.
Перевантажувати оператори для класів можна або описуючи оператори як методи класу (дивись попередній приклад), або використовуючи дружню функцію. Розглянемо приклад використання дружньої функцію для перевантаження оператора складання. Перевантажимо цей оператор для складання двох об'єктів класу complex, що моделює комплексне число.
class complex
{
private:
float re,im;
public:
void set_value(float x,float у){re=x;im=y;return ;}
float get_re(){return re;}
float get_im(){return im;}
friend complex operator+(complex&,complex&);//перевантажений оператор „+”
};
complex operator+(complex& а complex& b)//реалізація алгоритму оператора
{
complex с;
с.re=a.re+b.re;
с.im=a.im+b.im;
return с;
}
7. БІНАРНІ ДЕРЕВА
Остання структура даних, яку ми вивчимо в даному курсі – це дерево. Фактично дерево – це різновид динамічного списку. Існує багато типів дерев, але ми розглянемо лише бінарні дерева. Це визвано тим, що такий тип дерев є значно простішим і найбільш зручним у використанні, порівняно з іншими типами дерев.
Бінарне дерево – це структура даних, кожен елемент якої окрім самих даних містить покажчики на два наступних елементи структури. Один з цих наступних елементів умовно називається лівим, а інший правим.
Кожен елемент дерева називається вузлом або листом дерева. Перший вузол дерева (з якого дерево власне починається) називається коренем. Фрагмент дерева разом з вузлом, від якого він починається, називається піддеревом або віткою.
Множина всіх вузлів, рівновіддалених від кореня, називається рівнем. Вузол, з якого не починається жодна вітка, називається кінцевим або термінальним вузлом.
Оскільки дерево бінарне, кожен вузол може породжувати два вузли наступного рівня. Породжені вузли є дочірніми по відношенню до вузла, що їх породив. Породжуючий вузол є батьківським по відношенню до своїх дочірніх вузлів. Батьківський вузол разом із своїми дочірніми складає ланку. Сумарна кількість рівнів дерева називається висотою дерева.
Доступ до елементів дерева. Сортування бінарних дерев. Пошук у бінарних деревах
Основними операціями при роботі з деревами є:
- додавання елемента до дерева;
- пошук елемента дерева, що відповідає заданому критерію пошуку;
- сортування елементів дерева;
- вилучення елемента дерева.
Процес доступу до елементів дерева називається проходженням дерева. Існує три способи проходження дерев: послідовний, низхідний та висхідний. При послідовному методі доступу до елементів дерева порядок проходження дерева наступний: спочатку розглядається самий лівий відносно кореня елемент, потім його батьківський вузол, потім правий елемент даної ланки, потім переходять до елемента попереднього рівня, що є батьківським по відношенню до батьківського вузла даної ланки і т. д. Вверх до кореня, а потім від кореня вниз до самого правого елемента. При низхідному проходженні дерева порядок обходу елементів зверху-вниз та зліва-направо. Тобто спочатку проходиться корінь, потім його лівий елемент, а потім правий і т.д.
При висхідному проходженні порядок проходження зліва-направо та знизу-вверх. Тобто спочатку проходиться лівий вузол найнижчої ланки, потім правий вузол цієї ланки, а потім їх батьківський вузол і т.д. Розглянемо приклад. В прикладі будемо використовувати послідовний метод проходження дерева.
Для простоти вважатимемо, що дерево упорядковано (відсортовано) за зростанням відповідно до прямого порядку проходження. При такому упорядкуванні ліва вітка породжена вузлом містить значення менші за значення цього вузла, а права вітка, породжена даним вузлом, містить значення більші за значення цього вузла. Сам процес упорядкування виконуватимемо методом вставки під час формування дерева. Операції видалення елемента не розглядатимемо, оскільки вона досить складна. Бажаючі можуть знайти потрібну інформацію у літературі вказаній у списку використаної літератури.
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
66
//клас бінарне дерево
template <class T> class tree
{
T info; //поле, що містить інформацію
tree * left; //покажчик на лівий елемент ланки
tree * right; //покажчик на правий елемент ланки
public:
tree * root;//покажчик на корінь дерева
tree(){root=NULL;};//конструктор
//функція, що будує дерево
void stree(tree<T> *r, tree<T> *previous, T info);
//функція, що відображає дерево на екрані
void print_tree(tree *r, int l);
//функція пошуку елемента дерева
tree<T> *search_tree(tree<T> *r, T key);
}
//реалізація функції, що будує дерево
template <class T> void tree<T>::stree(tree<T> *r, tree<T> *previous, T info)
{
if (!r)
{
r=new tree<T>; //виділення пам’яті під елемент дерева
if (!r)//якщо не вдалося виділити пам’ять під елемент
{
cout << "Out of memory." << endl;//повідомляємо про це
exit(1);//і виходимо з процедури
}
//ініціалізуємо елемент
r->left=NULL;
r->right=NULL;
r->info=info;
if(!root) //якщо треба робимо його коренем дерева
{
root=r;
}
else//в противному випадку робимо його звичайним вузлом
{
if(info < previous->info) //якщо елемент менший за попередній, то
{
previous->left=r;//переходимо до лівої гілки
}
else
{
67
previous->right=r;//інакше до правого
}
}
return;
}//коли дійшли до потрібного термінального листа, то розміщуємо елемент.
if (info<r->info) Якщо елемент менший за попередній, то
{
stree(r->left,r,info); //розміщуємо його в лівому листі
}
else
{
stree(r->right,r,info); // інакше розміщуємо його в правому листі
}
return;
};
//реалізація процедури відображення дерева
//відображуємо відповідно до порядку послідовного проходження дерева
template <class T> void tree<T>::print_tree(tree<T> *r, int l)
{
int i;
if(!r)
{
return; //якщо нема батьківського вузла, то це корінь і процедуру закінчено
}
print_tree(r->right,l+1); //друкуємо елементи правої гілки
for(i=0;i<l;++i)
{
cout << " ";
}
cout << r->info << endl;
print_tree(r->left,l+1); //друкуємо елементи лівої гілки
}
//реалізація процедури пошуку елемента
template <class T> tree<T> *tree<T>::search_tree(tree<T> *r, T key)
{
if(!r)
{
return r; //якщо нема батьківського вузла, то це корінь і процедуру закінчено
}
68
//перевіряємо елементи дерева поки не знайдемо шукане
//або не досягнемо кінця
while(r->info!=key)
{
if(key<r->info)
{
r=r->left; //перевіряємо елементи лівої гілки
}
else
{
r=r->right; //перевіряємо елементи правої гілки
if(r==NULL){break;}
}
}
return r;
}
//основна програма
void main()
{
char s[80], key;
tree<char> chTree; //створюємо об’єкт класу бінарне дерево
clrscr(); //очищуємо екран
do //вводимо елементи дерева
{
cout << "Input character (. - for stopping):";
cin >> s;
if(*s!='.')
{
chTree.stree(chTree.root,NULL,*s);
}
} while(*s!='.'); //для закінчення вводу натискаємо крапку
chTree.print_tree(chTree.root,0); //друкуємо дерево на екрані
getch(); // затримуємо зображення, щоб побачити результат
cout << "input character for searching-";
cin >> key; //отримуємо значення для пошуку елемента
chTree.print_tree(chTree.search_tree(chTree.root,key),0); //виконуємо пошук
getch();// затримуємо зображення, щоб побачити результат
return; //закінчуємо програму
}
Як бачимо бінарне дерево – досить складна структура даних. Фактично це ускладнений варіант списку. Деякі операції реалізуються значно складніше ніж у списку. Однак операції пошуку у відсортованому бінарному дереві виконуються значно ефективніше ніж у списку, тому бінарні дерева використовуються на практиці досить часто.
Зверніть увагу на те, що майже всі методи класу бінарне дерево є рекурсивними, оскільки така реалізація при роботі з бінарним деревом –більш ефективна.
8. ПРАКТИЧНА РЕАЛІЗАЦІЯ ПРОСТИХ МЕТОДІВ СОРТУВАННЯ
1. Написати програму, що реалізує один з простих методів сортування: пpоцедуpи соpтування методами Шелла, пірамідального та швидкого соpтування мiстяться у файлах.
2. Згенерувати три масиви з випадковими елементами типу Integer довжиною 100, 1000 та 10000 елементів, відповідно.
3. Відсортувати одержані масиви за збільшенням елементів, визначивши при цьому такі параметри:
кількість порівнянь;
кількість обмінів;
фактичний час роботи,
необхідні кожній з програм (простий та один з довершених методів), щоби відсортувати кожен з трьох масивів. Швидкодія сучасних ЕОМ може привести до того, що час роботи процедури буде дорівнювати нулеві з точністю, яку забезпечує системний таймер. Тоді варто запустити її багато разів у циклі, а потім усереднити результат.
Текст програми
#include <stdlib.h> // div_t rand
#include <conio.h> // clrscr()
#include <math.h>
#include <iostream> // cin, cout
#include <fstream> // ofstream
#include <time.h>
using namespace std;
const long int
N=1000, // Array dimension
M=int(log((double)N)/log((double)2)+1); // Parameter for ShellSort. Never change it !
unsigned long moves, compares;
struct tItem {
int key;
char data[4];
friend bool operator < (tItem x, tItem y) { return (x.key < y.key); }
friend bool operator <= (tItem x, tItem y) { return (x.key <= y.key);}
friend bool operator > (tItem x, tItem y) { return (x.key > y.key); }
friend bool operator >= (tItem x, tItem y) { return (x.key >= y.key);}
friend void swap(tItem& a, tItem& b);
friend void copy(tItem& a, tItem& b);
tItem& operator = (tItem& y) { copy(*this, y); return *this; };
};
void swap(tItem& x, tItem& y) {
int k = x.key; x.key = y.key; y.key = k;
char s[4];
strcpy(s, x.data); strcpy(x.data, y.data); strcpy(y.data, s);
};
void copy(tItem& x, tItem& y) {
x.key = y.key;
strcpy(x.data, y.data);
};
ofstream fout("sort.txt");
void print(char * text, tItem * a, int N, bool sorted) {
fout << endl << text;
if (N<101 && !sorted) {
fout << endl;
for(int i=0;i<N;i++) {
fout << a[i].key << " " << a[i].data << " ";
if ((i+1)%10==0) fout << endl;
}
}
if (sorted)
for(int i=0;i<N;i++) {
if (i>0 && a[i-1] > a[i]) {
fout << a[i-1].key << "(" << a[i-1].data << ") > " << a[i].key << "(" << a[i].data << ") ! " << endl;
}
}
}
//++++++++++++++++Quicksort++++++++++++++++++++++++++++++++++
void QuickSort(tItem * a, int L, int R) {
int m,i,j;
tItem x;
i = L;
j = R;
m=(L+R)/2;
x = a[m];
while (i<=j) {
while (a[i]<x) { i++; }
while (x<a[j]) { j--; }
if (i<=j) {
if (i<j) {
swap(a[i], a[j]);
//c = a[i];
//a[i] = a[j];
//a[j] = c;
}
i++; j--;
}
}
if (L<j) {QuickSort(a,L,j);}
if (i<R) {QuickSort(a,i,R);}
}
//++++++++++++++++ShellSort++++++++++++++++++++++++++++++++++
void ShellSort(tItem * a) {
int i,t,k,m,l,j;
int * h = new int[M];
tItem x;
t = (int) (log((double)N)/log((double)2)-1);
h[t-1]=1;
for (k=t-2; k>=0; k--) {
h[k] = 2*h[k+1] + 1;
}
for (m=0; m<t; m++) { // Global iteration No
k = h[m]; // Step
for (l=0; l<=k-1; l++) { // SubArray No
for (i=1; i<=(N-1)/k; i++) {
if (l+i*k < N) {
x=a[l+i*k];
j=l+(i-1)*k;
while ((j>=0) && (x<a[j])) {
a[j+k] = a[j];
j = j-k;
} // while ((j>=0)
a[j+k] = x;
} // if (l+i*k
} // for (i=1;
} // SubArray
} // Global iteration
delete [] h;
}
//++++++++++++++++ShakerSort+++++++++++++++++++++++++++++++++
void ShakerSort(tItem * a) {
int i=0,j,flag=0;
while (flag==0) {
21.11.2013 11:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора