Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Статичні та динамічні структури даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра СКС
Інформація про роботу
Рік:
2012
Тип роботи:
Курсова робота
Предмет:
Програмування частина 4 Технологія системного програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Інститут дистанційного навчання
Кафедра СКС
КУРСОВА РОБОТА
з дисципліни «Програмування»
на тему «Статичні та динамічні структури даних»
Варіант № 1
Завдання на курсову роботу:
1. Провести огляд методів структур даних: списків, стеків, стеків, черг, що широко застосовуються у програмуванні. Розглянути їх властивості і практичне значення.
2. Згенерувати три масиви з випадковими елементами типу Integer довжиною 100, 1000 та 10000 елементів, відповідно.
3. Відсортувати одержані масиви за збільшенням елементів, визначивши при цьому такі параметри:
кількість порівнянь;
кількість обмінів;
фактичний час роботи,
необхідні кожній з програм (простий та один з довершених методів), щоби відсортувати кожен з трьох масивів.
ЗМІСТ
1.
СПИСКИ. СОРТУВАННЯ СПИСКІВ, ПОШУК У СПИСКАХ……...
4
2.
СТЕКИ……………………………………………………………………
11
3.
ЧЕРГИ ПРОСТІ ТА ЦИКЛІЧНІ………………………………………..
15
3.1
Прості черги……………………………………………………………..
15
3.2
Циклічні черги…………………………………………………………..
19
4.
ПРАКТИЧНА РЕАЛІЗАЦІЯ ПРОСТИХ МЕТОДІВ СОРТУВАННЯ.
24
ВИСНОВКИ……………………………………………………………………
31
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ…………………………………
32
1. СПИСКИ. СОРТУВАННЯ СПИСКІВ, ПОШУК У СПИСКАХ
Список – це сукупність елементів, кількість яких може змінюватись в ході виконання програми. При цьому пам’ять для розміщення нового елементу виділяється і вивільняється динамічно по мірі необхідності. Зрозуміло, що для реалізації такого типу даних необхідно використовувати покажчики. Списки можуть реалізовуватись за допомогою одинарних або подвійних зв’язків. В списку з одинарними зв’язками кожен елемент містить покажчик на наступний елемент списку. В списку з подвійними зв’язками кожен елемент містить покажчики на попередній і наступний елемент списку.
На сьогоднішній день найбільш часто використовуються списки з подвійними зв’язками. Це визвано тим, що список з подвійними зв’язками можна читати в обох напрямках, такий список легше відновлювати при пошкодженні і при використанні таких списків операції обробки інформації реалізуються простіше. Виходячи із сказаного ми будемо розглядати лише списки з подвійними зв’язками.
Основними операціями при роботі з списками є:
- додавання елементу до списку;
- вилучення елементу із списку;
- сортування елементів списку;
- пошук елемента списку, що відповідає заданому критерію пошуку.
Розглянемо ці операції на прикладі.
#include <stdio.h>
#include <iostream.h>
#include <conio.h>
//Шаблон класу список
template <class T> class my_list
{
private:
//Покажчик на наступний елемент списку
my_list *next;
48
//Покажчик на попередній елемент списку
my_list *prev;
//Поле даних елементу списку
T info;
//Поточна кількість елементів, занесених до списку
int list_size;
public:
//Функція визначення адреси наступного елементу списку
my_list<T> * get_next() {return next;}
//Функція визначення адреси попереднього елементу списку
my_list<T> * get_prev() {return prev;}
//Функція запису адреси наступного елементу списку
my_list<T> * set_next(my_list<T> *a) {return next=a;}
//Функція запису адреси попереднього елементу списку
my_list<T> * set_prev(my_list<T> *a) {return prev=a;}
//Функція додавання елементу до списку
void add_elem(my_list<T> *first,T inf);
//Функція вилучення елементу із списку
void del_elem(my_list<T> *first);
//Функція сортування елементів списку за зростанням
void sort_elements(my_list<T> *first);
//Функція зчитування даних, збережених в елементі списку
T get_info() {return info;}
//Функція запису даних до елементу списку
void set_info(T c) {info=c;return;}
//Функція запису розміру списку
void set_size(int c) {list_size=c;return;}
//Функція зчитування розміру списку
int get_size() {return list_size;}
//Функція відображення інформаційних полів списку на екрані
void print_list(my_list<T> *first);
//Функція пошуку заданого значення у списку
int b_search(my_list<T> *first,T key);
}
//Реалізація функції видалення елементу із списку
template<class T> void my_list<T>::del_elem(my_list<T> *first)
{
my_list<T> *tmp;
tmp=first->next;
first->list_size--;
first->next=first->next->next;
delete tmp;
return;
}
49
//Реалізація функції відображення списку на екрані
template<class T> void my_list<T>::print_list(my_list<T> *first)
{
int i;
my_list<T> *tmp;
tmp=first;
for(i=0;i< first->get_size();i++)
{
cout << tmp->get_info() << endl;
tmp=tmp->get_next();
}
}
//Реалізація функції сортування елементів списку
template<class T> void my_list<T>::sort_elements(my_list<T> *first)
{
my_list<T> *tmp_ptr;
T tmp_elem_value;
int i,j,d,size;
tmp_ptr=first;
size=first->list_size;
d=size;
for(i=0;i<size-1;i++)
{
for(j=0;j<d-1;j++)
{
tmp_elem_value=tmp_ptr->info;
if(tmp_ptr->info>tmp_ptr->next->info)
{
tmp_elem_value=tmp_ptr->info;
tmp_ptr->info=tmp_ptr->next->info;
tmp_ptr->next->info=tmp_elem_value;
}
tmp_ptr=tmp_ptr->next;
}
d--;
tmp_ptr=first;
}
return;
}
//Реалізація функції додавання елементу до списку
template <class T> void my_list<T>::add_elem(my_list<T> *first,T inf)
{
my_list<T> *tmp;// тимчасовий покажчик для елемента
tmp=new my_list<T>;//виділення пам’яті під елемент
tmp->set_info(inf);//запис інформації до елементу
50
tmp->next=first->next;//додавання до початку списку
tmp->prev=first;
first->prev=NULL;
first->next=tmp;
first->list_size++;
return;
}
//Реалізація функції пошуку значення у списку (бінарний пошук)
template<class T> int my_list<T>::b_search(my_list<T> *first,T key)
{
my_list<T> *tmp,*tmp_beg;
int beg,mid,end,i,num;
if(first->info==key) return 1;//перевірка першого елементу
tmp_beg=tmp=first;
num=1;//налаштування початкових
beg=1;//параметрів списку
end=first->list_size;
while(beg<end)//цикл пошуку
{
mid=(end+beg)/2;//знаходження середини списку
for(i=beg;i<mid;i++)//
{
tmp=tmp->next;//перехід до центрального елементу
}
if(tmp->info==key)//закінчити пошук, якщо знайдено
{
num=mid;
return num;
}
if(tmp->info>key) //вибір потрібної для пошуку частини
{
end=mid;
tmp=tmp_beg;
num=beg;
}
else
{
tmp_beg=tmp;
num=mid;
beg=mid;
}
if (mid == (beg+end)/2) break;
}
tmp=first->next;
51
for(i=2;i<first->list_size;i++)
{
tmp=tmp->next;
}
if(tmp->info==key) return first->list_size;//повернути значення
return -1;//якщо не знайдено повернути код помилки
}
//Головна функція
void main(void)
{
int i;
my_list <int> *first,*last,*tmp;
//Очистка екрану
clrscr();
//Створення списку
first=new my_list<int>;
last= new my_list<int>;
tmp= new my_list<int>;
first->set_next(NULL);
first->set_prev(NULL);
first->set_info(0);
first->set_size(1);
last->set_next(NULL);
last->set_prev(NULL);
tmp=first;
//Додавання чотирьох елементів до списку
for(i=1;i<5;i++)
{
tmp->add_elem(first,i);
}
//Відображення списку
first->print_list(first);
//Сортування списку
first->sort_elements(first);
//Відображення списку
first->print_list(first);
//Пошук елементу із значенням 3
cout << endl << first->b_search(first,3)<<endl<<endl;
//Видалення всіх елементів списку, що знаходяться між першим і останнім
for(i=0;i<3;i++)
{
first->del_elem(first);
}
52
//Відображення списку на екрані
first->print_list(first);
return;
}
З прикладу видно, що навіть елементарні операції із списками потребують досить високої кваліфікації, але вони дають змогу оптимально використовувати пам’ять.
В даному прикладі продемонстровано сортування списку методом обміну. Для простоти в прикладі було опущено ряд необхідних дій, таких як контроль виходу за межі списку, обробка помилок і т.і. Приклад добре прокоментовано, що спрощує розбір прикладу.
Для кращого засвоєння матеріалу рекомендується самостійно реалізувати сортування списку методом включення та методом прямого вибору.
Для пошуку елементів списку, що відповідають заданому критерію пошуку використовують ті ж методи, що і для масивів. В наведеному прикладі розглянуто бінарний пошук.
2. СТЕКИ
Стек – одна з найбільш корисних та найчастіше використовуваних стандартних структур даних. Він використовується для збереження змінних при визові процедур, для збереження змінних при виконанні переривань, для збереження даних про стан екрану при розробці інтерфейсу з користувачем на основі багаторівневого меню тощо. Доступ до елементів стеку здійснюється за принципом LIFO (last in, first out –„останнім зайшов, першим вийшов”).
Концептуально цей тип даних дозволяє виконувати вставку та зчитування даних лише в одному елементі – вершині стеку. Елементи зчитуються у зворотному напрямі – першим зчитується елемент, що був записаний до стеку останнім. Довільний доступ до елементів стеку не допускається.
Стек може бути реалізований на основі масиву або на основі списку. Реалізація на основі масиву більш проста, але має ряд недоліків: обмежену кількість елементів, неефективне використання пам’яті та інші. Реалізація на основі списку більш складна, але позбавлена вказаних недоліків, тому в практичному програмуванні частіше реалізують стеки на основі списків.
Саме тому ми будемо розглядати лише стеки на основі списків.
Стек повинен реалізовувати наступні операції:
- додавання елементу даних до вершини стеку (метод push);
- зчитування та вилучення елементу даних із вершини стеку (метод pop);
- визначення чи є в стеку дані.
Розглянемо ці операції на прикладі простого стеку на основі списку з подвійними зв’язками.
Приклад:
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
54
//Шаблон класу стек
template <class T> class user_stack
{
private:
//Розмір стеку
int stack_size;
//Елемент даних стеку
T data;
//Покажчик на попередній елемент стеку
user_stack *prev;
//Покажчик на наступний елемент стеку
user_stack *next;
public:
//Конструктор стеку
user_stack();
//Функція, що перевіряє чи є в стеку елементи даних
int empty(){if (stack_size>0) return 0; else return -1;};
//Функція, що дозволяє прочитати елемент даних стеку
//Дана функція потрібна лише для відладки програми
T get_data(){return data;};
//Функція, що дозволяє отримати адресу попереднього елементу стеку
user_stack<T> * get_prev(){return prev;};
//Функція, що дозволяє додати елемент до стеку (метод push)
user_stack<T> * push(T var);
//Функція, що дозволяє видалати елемент стеку(метод pop)
T pop();
}
//Реалізація конструктора
template<class T> user_stack<T>::user_stack()
{
stack_size=0;
data=NULL;
prev=NULL;
next=NULL;
}
//Реалізація методу push
template <class T> user_stack<T> * user_stack<T>::push(T var)
{
this->next=new user_stack<T>;
this->next->prev=this;
this->next->data=var;
this->next->stack_size=this->stack_size+1;
return this->next;
}
55
//Реалізація методу pop
template <class T> user_stack<T>::pop()
{
T dat;
dat=this->next->data;
delete this->next;
this->next=NULL;
return dat;
}
void main(void)
{
user_stack<int> *my_stack;
int my_data;
//Створення стеку
my_stack=new user_stack<int>;
//Очистка екрану
clrscr();
//Активація генератора випадкових чисел
randomize();
//Присвоення змінній випадкового значення
my_data=random(10)+5;
//Відображення значення змінної на екрані
cout << "data="<<my_data << endl;
//Запис значення змінної в стек
my_stack=my_stack->push(my_data);
//Відображення на екрані даних записаних у стек
cout << "In stack stored - " << my_stack->get_data() << endl;
//Зміна значення змінної
my_data+=20;
//Відображення нового значення змінної
cout << "Changing data. Now data ="<<my_data << endl;
//Відновлення старого значення змінної із стеку
my_stack=my_stack->get_prev();
my_data=my_stack->pop();
//Відображення відновленого значення змінної на екрані
cout << "After popping data="<<my_data << endl;
return;
}
3. ЧЕРГИ ПРОСТІ ТА ЦИКЛІЧНІ
Черга являє собою лінійний список, доступ до елементів якої здійснюється за принципом FIFO (first in, first out – „першим зайшов, першим вийшов”). Таким чином, першим із черги видаляється елемент, який був записаний до черги першим, потім – елемент, що був записаний до черги другим, і т. д. Для черги такий метод доступу і збереження даних являється єдиним. Довільний доступ до вказаного елементу не допускається. Черги можуть бути простими та циклічними.
3.1. Прості черги
Черги мають досить широке використання на практиці. Наприклад при моделюванні процесів реального часу, для диспетчеризації завдань операційної системи або для буферизації операцій вводу-виводу. Черга повинна реалізовувати наступні операції:
- додавання елементу даних у кінець черги;
- зчитування та вилучення елементу даних з початку черги.
Розглянемо приклад, що демонструє методи роботи з чергами.
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
//Шаблон класу черга
template <class T> class queue
{
private:
//Покажчик на динамічний масив, в якому розміщаються дані
T *q;
//Номер позиції, з якої будуть зчитуватись дані
int read_loc;
//Номер позиції, у яку будуть записуватись дані
int write_loc;
//Розмір черги – максимальна кількість елементів,
//що може бути розміщено у черзі
57
int length;
public:
//Функція – конструктор, що створює чергу заданого розміру
queue(int size);
//Функція – деструктор, що знищує чергу
~queue() {delete [] q;};
//Функція, що записує елемент даних до черги
void write_data(T data);
//Функція, що зчитує елемент даних з черги
T read_data();
}
//Реалізація функції – конструктора
template <class T> queue<T>::queue (int size)
{
//Виділення пам’яті під чергу
q=new T[size];
//Якщо вільної пам’яті нема, то вивести на екран
//повідомлення про помилку
if(!q)
{
cout << "Error! Can't create turn." << endl;
exit(1);
}
//Встановлення розміру черги
length=size;
//Переведення індексів зчитування та запису в початок черги
read_loc=write_loc=0;
}
//Реалізація функції, що записує елемент даних до черги
template <class T> void queue<T>::write_data(T data)
{
//Перевірка наявності вільного місця у черзі і при його відсутності
//виведення повідомлення про помилку
if (write_loc==length)
{
cout << "Error! Turn is full." << endl;
return;
}
//Запис елементу даних у чергу при наявності вільного місця
q[write_loc++]=data;
}
//Реалізація функції, що зчитує елемент даних до черги
template <class T> T queue<T>::read_data()
{
58
//Перевірка наявності незчитаних елементів у черзі та
//відображення повідомлення про помилку у разі їх відсутності
if (write_loc==read_loc)
{
if(read_loc==length){ read_loc=write_loc=0;}
cout << "Error! Turn is empty." << endl;
return NULL;
}
//Повернення зчитаних даних як результату функції
return q[read_loc++];
}
//Головна функція
void main()
{
//Створюємо чергу цілих чисел, величиною 5 елементів
queue<int> a(5);
int turn_data;
//Очищуємо екран
clrscr();
//Записуємо 5 елементів даних до черги
a.write_data(1);
a.write_data(2);
a.write_data(3);
a.write_data(4);
a.write_data(5);
//Записуємо 6-ий елемент даних до заповненої черги.
//На екрані з’явиться повідомлення про помилку
a.write_data(6);
//Зчитуємо елементи даних черги, поки не вичерпаємо їх.
//Після того, як черга стане пустою, при наступному зчитуванні на екрані
//з’явиться повідомлення про помилку
while((turn_data=a.read_data())!=NULL)
{
cout << turn_data << endl;
}
return;
}
Як видно з прикладу – черга досить просто реалізується на основі динамічного масиву.
Така черга називається простою чергою. Однак така черга має деякі недоліки, а саме: фіксований розмір, який не можна змінити в процесі роботи з чергою, можливість втрати даних при переповненні черги, оскільки не можна продовжувати запис даних до заповненої черги, поки не будуть прочитані всі елементи. Лише після того, як буде прочитаний останній елемент черги, до неї можна знов записувати дані, починаючи з першого елементу. Цього можна уникнути, створюючи, в разі необхідності, нові черги в динамічному режимі. Але при такому підході не досить ефективно використовується пам’ять. Можна розробити безрозмірну чергу на основі списку. Однак це – досить складне завдання, розгляд якого виходить за рамки даного посібника. Деяким компромісним варіантом, що покращує використання пам’яті і, при цьому, досить просто реалізується є використання циклічних черг.
3.2. Циклічні черги
Циклічні черги мають таку ж саму структуру, як і прості черги з однією відмінністю. Ця відмінність полягає в тому, що після заповнення черги запис знов починається з першого елементу черги при умові, що цей елемент уже зчитано. Далі запис продовжується, як і в звичайній черзі при умові, що ідповідні елементи черги уже прочитані. При правильному підборі розміру черги з урахуванням швидкості запису й зчитування даних практично можна уникнути проблем з переповненням черги.
Розглянемо приклад практичної реалізації циклічної черги.
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
//Шаблон класу циклічна черга
template <class T> class queue
{
private:
//Покажчик на адресу, за якою починається черга
T *q;
//Змінна, що вказує на елемент, який буде зчитано при черговому зчитуванні
int read_loc;
60
//Змінна, що вказує куди буде записано елемент при черговому записі
int write_loc;
//Розмір черги (максимальна кількість елементів, що можуть
//розміститись в черзі одночасно)
int length;
//Кількість елементів, розміщених в черзі
int elem_nums;
public:
//Конструктор черги
queue(int size);
//Деструктор черги
~queue() {delete [] q;};
//Функція, що записує елемент до черги
void write_data(T data);
//Функція, що зчитує елемент із черги
T read_data();
}
//Реалізація конструктора
template <class T> queue<T>::queue (int size)
{
//Виділення пам’яті під чергу
q=new T[size];
//Повідомлення про помилку в разі невдачі
if(!q)
{
cout << "Error! Can't create turn." << endl;
exit(1);
}
//Активація нулем кількості записаних до черги елементів
elem_nums=0;
//Встановлення розміру черги
length=size;
//Встановлення індексів зчитування та запису в початкову позицію
read_loc=write_loc=0;
}
//Реалізація функції, що записує елемент даних до черги
template <class T> void queue<T>::write_data(T data)
{
//Перевірка наявності вільного місця у черзі і відображення повідомлення про
//помилку вразі відсутності вільного місця
if (elem_nums==length)
{
cout << "Error! Turn is full." << endl;
return;
61
}
//Запис даних до черги при наявності вільного місця
//та збільшення індексу запису
q[write_loc++]=data;
//Якщо досягнуто кінець черги, то перевести індекс запису у початок
if (write_loc>=length) {write_loc=0;}
//Збільшення числа зайнятих елементів на одиницю
elem_nums++;
}
//Реалізація функції зчитування елементу даних із черги
template <class T> T queue<T>::read_data()
{
//Перевірка на наявність незчитаних елементів
//та відображення повідомлення про помилку при їх відсутності
if (elem_nums==0)
{
if(read_loc==length){ read_loc=write_loc=0;}
cout << "Error! Turn is empty." << endl;
return NULL;
}
//Зменшення числа незчитаних елементів на одиницю
elem_nums--;
//Зчитування елементу даних у тимчасову змінну та збільшення
// індексу зчитування на одиницю
tmp=q[read_loc++];
//Якщо досягнуто кінець черги, то перевести
//індекс зчитування у початок черги
if (read_loc>=length) { read_loc=0;}
//Повернути прочитане значення, як результат роботи функції
return tmp;
}
//Головна функція програми
void main()
{
//Створення черги з п’яти елементів
queue<int> a(5);
//Оголошення змінної для тимчасового зберігання елементу даних,
//зчитаних з черги
int turn_data;
//Очистка екрану
clrscr();
//Заповнення черги до кінця елементами даних
a.write_data(1);
62
a.write_data(2);
a.write_data(3);
a.write_data(4);
a.write_data(5);
//Спроба записати дані в заповнену чергу.
//На екрані відобразиться повідомлення про помилку
a.write_data(6);
//Зчитування елементу черги і вивільнення місця під один елемент даних
turn_data=a.read_data();
//Відображення зчитаних даних на екрані
cout << turn_data << endl;
//Запис нового елемнту даних до черги на звільнене місце
a.write_data(6);
//Зчитування всіх елементів даних черги
//при досягненні кінця черги на екрані відобразиться
//повідомлення про помилку
while((turn_data=a.read_data())!=NULL)
{
cout << turn_data << endl;
}
//Повторне заповнення черги даними
a.write_data(1);
a.write_data(2);
a.write_data(3);
a.write_data(4);
a.write_data(5);
//Зчитування першого елементу черги
turn_data=a.read_data();
//Запис ще одного елемента даних на звільнене місце
a.write_data(6);
//Зчитування всіх елементів даних черги
//при досягненні кінця черги на екрані відобразиться
//повідомлення про помилку
while((turn_data=a.read_data())!=NULL)
{
cout << turn_data << endl;
}
return;
}
4. ПРАКТИЧНА РЕАЛІЗАЦІЯ ПРОСТИХ МЕТОДІВ СОРТУВАННЯ
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
20.11.2013 19:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора