Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Програмного забезпечення (ПЗ)
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми і структури даних
Група:
ПІ
Частина тексту файла (без зображень, графіків і формул):
Міністерство науки і освіти України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
кафедра програмного забезпечення
Звіт з лабораторної роботи № 8
з дисципліни “Алгоритми і структури даних ”
Виконав:
студент групи ПІ – 1
Львів 2008
Тема роботи: Ознайомлення із методами сортування. Алгоритм сортування на деревах.
Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із методом сортування на деревах. Виконати лабораторну роботу використавши здобуті знання з методів сортування, зокрема методу сортування на деревах.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Метод вибірки з дерева.
Послідовність чисел розбивається на пари, які об‘єднуються за принципом «син-батько». Батьком з двох синів стає найбільше число. Процес повторюється, доки не буде виділене одне число, найбільше, яке стане корнем утвореного дерева. У разі відсутності одного числа, батьком стає єдиний нащадок (син). Число, що попало в корінь замінюється на безмежність. Процес повторюється для знаходження наступного найбільшого числа і т.д. З рис. 1 видно, що задана послідовність буде впорядкована у низхід ному порядку за 10-1=9 кроків.
Сумарний час виконання такого сортування приблизно пропорційний величині п log2 n . Існує декілька модифікацій цього алгоритму, які скорочують цей час.
Рис. 1. Схема сортування методом вибірки з дерева:
а - послідовність з десяти чисел для відбору першого найбільшого елемента;
б - вибір другого найбільшого елемента.
Текст програми
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<alloc.h>
#define N 2000
struct S* create(int);
struct S* create(struct S*, struct S*);
void clean(struct S*);
int min(int, int);
/*-Struktura-*/
struct S
{
int a; //Vlasne znachenna
struct S* left; //Vk. na livogo syna
struct S* right; //Vk. na pravogo syna
};
//-----------------------------------
void main()
{
int rez=0;
int mas[N],mas2[N];
/*-Inicializacija-*/
for (int i=0;i<N;i++)
mas[i]=rand();
/*-Pobudova dereva-*/
for (int r=0;r<N;r++)
{
S* pmas[N]; //Vk. na vershyny
int cnt=N; //Kilkist vershyn na rivni
for(int i=0;i<N;i++)
pmas[i]=create(mas[i]);//Budujemo riven structur
while(cnt>1)//Do najvyschogo rivn'a
{
int j=0;
//Perenesenna na vyschyj riven vershyny
//z menshym znachennam
for(int i=0;i<cnt;i+=2)
pmas[j++]= i+1<cnt ? create(pmas[i],pmas[i+1]): pmas[i];
cnt=j;
}
//Perenosymo znachenna korenja
//u zapasnyj masyv
mas2[r]=pmas[0]->a;
//Zamina znajdenogo elementa
//u vyhidnomu masyvi
for (int c=0;c<N;c++)
if(mas[c]==pmas[0]->a)
{mas[c]=32767; break;}
/*-Ochyschenn'a pam'jati-*/
clean(pmas[0]);
}
/*-Perevirka-*/
for(int hi=0;i<N-1;i++)
if (mas2[i]>mas2[i+1])
rez=1;
if(rez==1) puts("Ne posortovano!");
else puts("Posortovano!");
}
//------------------------------------
/*-Stvorenna vershyn nyzchogo rivn'a-*/
struct S* create(int a)
{
struct S* b=(struct S*)malloc(sizeof(struct S));
b->a=a;
b->left=NULL;
b->right=NULL;
return b;
}
/*-Stvorenn'a vershyn vyschyh rivniv-*/
struct S* create(struct S* a, struct S* b)
{
struct S* c=(struct S*)malloc(sizeof(struct S));
c->left=a;
c->right=b;
c->a=min(a->a,b->a);
return c;
}
/*-Ochyschenna pam'jati-*/
void clean(struct S* b)
{
if(b->left!=NULL)
delete(b->left);
if(b->right!=NULL)
delete(b->right);
free(b);
}
/*-Zn. minimal'nogo elementa-*/
int min(int a, int b)
{
return a<=b?a:b;
}
Протокол роботи програми
Висновок: Вивчив та дослідив метод сортування, як один із методів обробки даних. Ознайомився із методом сортування на деревах. Виконав лабораторну роботу використавши здобуті знання з методів сортування, зокрема методу сортування на деревах.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора