Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритми та структури даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра СКС
Інформація про роботу
Рік:
2012
Тип роботи:
Курсова робота
Предмет:
Програмування частина 4 Технологія системного програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Інститут дистанційного навчання
Кафедра СКС
КУРСОВА РОБОТА
з дисципліни «Програмування»
на тему «Алгоритми та структури даних»
Варіант № 8
Завдання на курсову роботу:
На вході задано масив з N елементів. Використовуючи метод бінарного пошуку знайти заданий елемент і вивести його на екран.
1.1 Ручний ввід даних.
1.2. Ввід даних через файл.
Складіть алгоритм визначення того, що бінарне дерево є:
а) строго бінарне;
б) повне;
г) майже повне.
2.1. Ручний ввід даних.
2.2. Ввід даних через файл.
ЗМІСТ
ВСТУП……………………………………………………………………….
4
1.
ТЕОРЕТИЧНА ЧАСТИНА…………………………………………..
6
1.1
Задача на пошук (Бінарний пошук або пошук діленням на половину)………………………………………………………………..
6
1.2
Задача на бінарне дерево……………………………………………….
6
2.
ОПИС АЛГОРИТМУ………………………………………………….
8
2.1
Схема алгоритму бінарного пошуку………………………………….
8
2.2
Схема алгоритму бінарного дерева……………………………………
10
3.
БЛОК-СХЕМА АЛГОРИТМУ………………………………………
11
4.
РЕЗУЛЬТАТИ ТЕСТУВАННЯ………………………………………
12
4.1
Задача на бінарний пошук………………………………………………
12
5.
ПРАКТИЧНА РЕАЛІЗАЦІЯ ПРОСТИХ МЕТОДІВ СОРТУВАННЯ…………………………………………………………
12
ВИСНОВКИ…………………………………………………………………..
20
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ……………………………..
21
Додаток…………………………………………………………………………
22
ВСТУП
Однією з найпоширеніших мов програмування є мова Pascal. Сучасні її підмножини (останні версії), а також середовище Delphi, що грунтується на мові програмування Object Pascal, широко використовують поряд з мовами С, С++, С++Builder. Вони дають змогу створювати складні програмні продукти, як у галузі системного, так і прикладного програмування. Та все ж незамінною залишається мова програмування Pascal, як інструмент для вивчення основ програмування.
На початкових етапах не було конкретних теоретичних концепцій та технологій програмування. Результат створення програм залежав, головне, від мистецтва програміста й ефективності застосованих ним хитрощів. Такі програми важко налагоджувати, вони мало придатні для вдосконалення. Особливо важко компонувати складні програми з частин, розроблених колективом програмістів.
Як уже зазначено, методологією сучасного програмування є програмування структурне. Дехто вважає, що це просто програмування згідно з чіткими канонами, інші – що це написання підпрограм (модулів) та об’єднання їх у програму, ще інші – що це програмування “без goto ”.
Мета структурного програмування – створювати програми чіткої структури, тобто такі, які можна було б без великих затрат розуміти, супроводжувати і модифікувати без участі авторів.
До структури даних відносяться: список, стек, черга, а також дерева.
Список – це скінченна сукупність даних одного типу, між якими налагоджено зв’язок. Елемент списку складається з двох частин: самого даного (даних) та вказівника на наступний елемент списку.
Стек – це структура даних, у якій елемент, записаний останнім, зчитують (є доступний до опрацювання) першим. Тут виконується принцип “останній прийшов - перший вийшов”.
Черга – це структура даних, у якій елемент, записаний першим, зчитують першим. Тут діє принцип “перший прийшов – перший вийшов”.
Дерево – це не порожня множина елементів, один з яких називається коренем, а решта поділяється на декілька підмножин, що не перетинаються.
На відмінно від структур даних, алгоритм повинен відповідати чітко вираженим діям, а також відповідати певним властивостям.
Алгоритм – це строга і чітка система правил, яка визначає послідовність дій над деякими об’єктами і після скінченого числа кроків приводить до досягнення поставленої мети.
Крім того, що алгоритм - не просто звід кінцевого числа правил, що задають послідовність виконання операцій при рішенні тієї чи іншої специфічної задачі, він має ще п'ять важливих особливостей:
Кінцевість. Алгоритм завжди повинен закінчуватись після кінцевого числа кроків.
Результативність.
Дискретність. Алгоритм повинен мати чіткі кроки.
Детермінованість. Кожний крок алгоритму повинен, бути точно визначеним.
Єфективність.
1. ТЕОРЕТИЧНА ЧАСТИНА
1.1. Задача на пошук (Бінарний пошук або пошук діленням на половину)
Алгоритм бінарного пошуку припустимо використовувати для знаходження заданого елемента тільки у впорядкованих масивах. В завданні я використовую масив, впорядкований по зростанню (Vector[I] <= Vector[I+1]).
Принцип Бінарного пошуку:
Заданий масив ділиться пополам і для порівняння вибирається середній елемент. Якщо він співпадає із шуканим елементом, то пошук припиняється. Якщо ж середній елемент менший шуканого елемента, то всі елементи лівіше його також будуть менші шуканого елемента. Значить їх можна виключити із зони дальшого пошуку, залишивши тільки праву частину масиву. Аналогічно, якщо середній елемент більший шуканого елемента, то відкидається права частина, а залишається ліва.
На другому етапі робляться аналогічні дії над половиною масиву, яка залишилася. В результаті після другого етапу залишається ј частина масиву.
І так далі, поки або елемент буде знайдений, або довжина зони пошуку стане рівна нулю. В інакшому випадку шукає мий елемент не буде знайдений.
1.2. Задача на бінарне дерево
Дерево – це скінчена множина вузлів з одним виділеним вузлом, що називається коренем, а інші вузли розділені на m ( 0 множин В1, В2, ... Вm, які не перетинаються і кожна з яких являє дерево (піддерево). На рисунку 1 зображено дерево з коренем 1 і трьома піддеревами: B1={2}, B2={3,5,6}, B3={4,7}. При графічному поданні будь-який корінь з’єднується з коренями своїх піддерев. На рисунку 1 вузол 1 з’єднується з вузлами 2, 3, 4; корінь 3 з’єднується з 5, 6; вузол 4 – з вузлом 7.
Корінь дерева (попередник, батько) передує кореням своїх піддерев, що є його наступниками (синами). Це співвідношення між вузлами дерев має такі властивості:
існує вузол (корінь дерева) без попередників;
для будь-якого вузла k, окрім кореня w, існує послідовність вузлів k0, k1, … , kn, n ( 1, k0 = w, kn = k, де ki – наступник ki-1, i=2, 3, …, n,що утворює гілку довжини n від w до k = kn (на рис.1 для вузла 6 гілкою є послідовність 1, 3, 6).
Корінь дерева w має m ( 0 синів, що є, в свою чергу, коренями інших піддерев B1, B2, …, Bm. Вузли, які не мають піддерев складають листя дерева, всі інші вузли дерева – внутрішні. Степінь вузла k – це кількість його синів. Найбільший степінь якого-небудь вузла вважають степенем дерева. Дерево степеня n називається повним, якщо степінь всякого вузла дорівнює n або 0. Дерево упорядковане, коли для кожного сина k( вузла k степеня n указано, яким він є: першим, другим, ... , n-м. На рисунку 2 є два повних упорядкованих дерева степеня 2. Можна вважати, що кожне з них зображує одне й теж неупорядковане повне дерево степеня 2.
Рис. 1 Рис. 2
Бінарні дерева – це упорядковане дерево степеня 2, що має додатково дві властивості: 1) воно може бути пустим, не маючи жодного вузла; 2) будь-який вузол може мати другого сина (правого) за відсутності першого (лівого).
Якщо кожен вузол бінарного дерева не є листком, має не порожні праві та ліві піддерева, то таке бінарне дерево називається строго бінарним деревом (рис. 3).
Строго бінарне дерево
Рис. 3
Майже повне бінарне дерево (рис. 4) – це таке дерево, в якому існує невід’ємне ціле к таке, що:
Кожен листок в дереві має рівень к чи к+1;
Якщо вузол дерева має правого нащадка к+1, то всі ліві нащадки, що є листками, мають рівень к+1.
Майже повне і строго бінарне дерево
Рис. 4
2. ОПИС АЛГОРИТМУ
2.1. Схема алгоритму бінарного пошуку
Необхідно знайти елемент Х 14
Вихідний масив Vector
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n=16
1
4
7
11
14
18
20
22
25
29
32
37
41
46
49
53
L=1 R=n=16
i:=(L+R) div 2 = 8
Vector[I] > X
1 2 3 4 5 6 7
1
4
7
11
14
18
20
L=1 R=7 R:= i – 1 = 7
i:= (L+R) div 2 = 4
Vector[I] < X
L:= i + 1 = 5
5 6 7
14
18
20
L=5 R=7
i:= (L+R) div 2 = 6
Vector[i] > X
R:= i – 1 = 5
5
14
L=R=5
i:=(L+R) div 2 = 5
Vector[i] = X
Елемент знайдений на позиції 5
а) Ручний ввід даних.
Вводиться рядок цілочисельних чисел в порядку зростання.
Вводиться шуканий елемент. Шукається індекс середнього елемента. Якщо шуканий елемент менший середнього елемента, то праву частину відкидаємо. І так далі, аж поки не знайдемо шуканого елемента. Якщо серед цього рядку чисел не буде шуканого елемента, то програма видасть повідомлення.
б) Автоматичний ввід даних.
Ця підпрограма працює так само, як і попередня, тільки рядок цілочисельних чисел задається комп’ютером автоматично.
2.2. Схема алгоритму бінарного дерева
а) Ручний ввід даних.
Вводяться вузли бінарного дерева.
Після цього програма перевіряє чи бінарне дерево є строго бінарним, чи не строго бінарне, повним або не повним, майже повним або не є майже повним. Procedure maketree – створює батька бінарного дерева; Procedure setleft – створює лівого сина бінарного дерева; Procedure setright – створює правого сина бінарного дерева; Function StrogoBinDer – перевіряє бінарне дерево чи воно є строго бінарним деревом; Function PovneDer – перевіряє бінарне дерево чи воно є повним; Function MaizhePovneDer - перевіряє бінарне дерево чи воно є майже повним.
В кінці виконання підпрограми виводиться на екран повідомлення про це дерево.
б) Ввід даних через файл.
Ця підпрограма працює так само, як і попередня, тільки вузли бінарного дерева не вводяться, а зчитуються з файлу “Test.txt”
3. БЛОК-СХЕМА АЛГОРИТМУ
Початок
n=20{довжина
масиву}
Ввід елементів
масиву (Vector[I])
Ввід шукаючого
елемента (X)
L:=1; R:=n;
i:=(L+R) div 2
If Vector[I]=X
If Vector[i]<X
Break {Вихід із
цикла пошуку}
L:=I+1
R:=I-1
4. РЕЗУЛЬТАТИ ТЕСТУВАННЯ
4.1. Задача на бінарний пошук
а) Ручний ввід даних.
Запишемо елементи в порядку зростання:
1 3 4 5 7 8 10 14 17 19 23 25 27 38 43 56
Нехай шуканим елементом буде – 17;
Елемент 17 знаходиться на 9 позиції
б) Автоматичний ввід даних.
В файлі є такі числа: 1 2 11 14 17 24 28 30 34 39 40 45
Введіть шуканий елемент: 3
Шуканий елемент не знайдений, бо не входить в заданий діапазон
в) Вихід.
5. ПРАКТИЧНА РЕАЛІЗАЦІЯ ПРОСТИХ МЕТОДІВ СОРТУВАННЯ
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) {
flag=1;
for(j=i; j<N-1-i; j++) {
if (a[j]>a[j+1]) {
swap(a[j], a[j+1]);
flag=0;
}
}
if (flag==0)
for(j=N-2-i; j>i; j--) {
if (a[j-1]>a[j]) {
swap(a[j-1], a[j]);
}
}
i++;
}
}
//++++++++++++++++MergeSort++++++++++++++++++++++++++++++++++
void Merge(tItem * a, int L, int m, int R){
// merge a[L..m] and a[m+1..R]
int i1, i2,i;
tItem * b = new tItem[R-L+1];
for (i=0; i<R-L+1; ++i)
b[i] = a[i+L];
i=L; // index in a;
i1=0; // index in b[0..m-L];
i2=m-L+1; // index in b[m-L+1..R-L];
while (i<=R) {
if ((i1<=m-L) && (i2<=R-L)) {
if (b[i1]<b[i2])
a[i++] = b[i1++];
else
a[i++] = b[i2++];
continue;
}
if ((i1>m-L) && (i2<=R-L)) {
a[i++] = b[i2++];
continue;
}
if ((i1<=m-L) && (i2>R-L)) {
a[i++] = b[i1++];
continue;
}
if ((i1>m-L) && (i2>R-L)) {
cout << "!!!!!!!!!!!!! ";
continue;
}
}
delete [] b;
}
void MergeSort(tItem * a, int L, int R) {
int m,i,j;
tItem x;
//cout << L << " " << R << endl;
if (R<=L) return;
if (R-L==1) {
if (a[L] > a[R])
swap(a[L], a[R]);
return;
}
m = (R+L)/2;
if (L<m) MergeSort(a,L,m);
if (R>m+1) MergeSort(a,m+1,R);
Merge(a, L, m, R);
}
//++++++++++++++++HeapSort++++++++++++++++++++++++++++++++++
void pushdown(tItem * a, int L, int R) {
int i = L;
while (i+1 <= (R+1)/2) {
if (R+1 == 2*(i+1)) {
if (a[i] < a[2*i+1])
swap(a[i], a[2*i+1]);
i = R;
}
else {
if ((a[i] < a[2*i+1]) && (a[2*i+1] >= a[2*(i+1)])) {
swap(a[i], a[2*i+1]);
i = 2*i+1;
}
else {
if ((a[i] < a[2*(i+1)]) && (a[2*(i+1)] > a[2*i+1])) {
swap(a[i], a[2*(i+1)]);
i = 2*(i+1);
}
else {
i = R;
} // if ((a[i] > a[2*i+1]) ...
} // if ((a[i] > a[2*i]) ...
} // if (R == 2*i)
} // while
}
void HeapSort(tItem * a) {
int i;
for (i = (N-1)/2; i>=0; i--) {
pushdown(a, i, N-1);
//print("", a, N, false);
}
//fout << "-----------------------------------" << endl;
for (i = N-1; i>0; i--) {
swap(a[0], a[i]);
//print("Swap:", a, N, false);
pushdown(a, 0, i-1);
//print("pushdown:", a, N, false);
//fout << endl;
}
}
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//
//+++++++++++++++++++ +++++++++++++++++++++++++++//
//+++++++++++++++++++ Main +++++++++++++++++++++++++++//
//+++++++++++++++++++ +++++++++++++++++++++++++++//
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//
int main() {
tItem * a, * b; // Array and it's reserved copy
int i;
clock_t start, finish;
double duration;
bool sorted = true;
a = new tItem[N];
b = new tItem[N];
srand(time(0));
//++++++++++++++++Generation+++++++++++++++++++++++++++++++++
for(i=0; i<N; i++) {
a[i].key = rand();
a[i].data[0] = 'A' + rand() % ('Z'-'A'+1);
a[i].data[1] = 'A' + rand() % ('Z'-'A'+1);
a[i].data[2] = 'A' + rand() % ('Z'-'A'+1);
a[i].data[3] = '\0';
b[i].key=a[i].key;
strcpy(b[i].data,a[i].data);
}
print("Array generated", a, N, !sorted);
//++++++++++++++++Quicksort++++++++++++++++++++++++++++++++++
moves=0; // кількість обмінів (копіювань)
compares=0; // кількість порівнянь ключів елементів
start = clock();
QuickSort(a,0,N-1);
finish = clock();
print("Array sorted by QuickSort", a, N, sorted);
cout<< "Time to sort array of " << N << " elements QuickSort:";
duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout << duration << " seconds" << endl;
fout << endl << "Time to sort array of " << N << " elements QuickSort: "
<< duration << endl;
cout <<compares<<" - compares; "<< moves << " moves \n";
fout <<compares<<" - compares; "<< moves << " moves \n";
//++++++++++++++++ShellSort+++++++++++++++++++++++++++++++++
for(i=0;i<N;i++)
a[i]=b[i];
moves=0; // кількість обмінів (копіювань)
compares=0; // кількість порівнянь ключів елементів
start = clock();
ShellSort(a);
finish = clock();
print("Array sorted by ShellSort", a, N, sorted);
cout<< "Time to sort array of " << N << " elements by ShellSort:";
duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout << duration << " seconds" << endl;
fout << endl << "Time to sort array of " << N << " elements by ShellSort: "
<< duration << endl;
cout <<compares<<" compares; "<< moves << " moves \n";
fout <<compares<<" compares; "<< moves << " moves \n";
//++++++++++++++++ShakerSort+++++++++++++++++++++++++++++++++
for(i=0;i<N;i++)
a[i]=b[i];
moves=0; // кількість обмінів (копіювань)
compares=0; // кількість порівнянь ключів елементів
start = clock();
ShakerSort(a);
finish = clock();
print("Array sorted by ShakerSort", a, N, sorted);
cout<< "Time to sort array of " << N << " elements by ShakerSort:";
duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout << duration << " seconds" << endl;
fout << endl << "Time to sort array of " << N << " elements by ShakerSort: "
<< duration << endl;
cout <<compares<<" compares; "<< moves << " moves \n";
fout <<compares<<" compares; "<< moves << " moves \n";
//++++++++++++++++HeapSort+++++++++++++++++++++++++++++++++
for(i=0;i<N;i++)
a[i]=b[i];
moves=0; // кількість обмінів (копіювань)
compares=0; // кількість порівнянь ключів елементів
start = clock();
HeapSort(a);
finish = clock();
print("Array sorted by HeapSort", a, N, sorted);
cout<< "Time to sort array of " << N << " elements by HeapSort:";
duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout << duration << " seconds" << endl;
fout << endl << "Time to sort array of " << N << " elements by HeapSort: "
<< duration << endl;
cout <<compares<<" compares; "<< moves << " moves \n";
fout <<compares<<" compares; "<< moves << " moves \n";
//++++++++++++++++MergeSort+++++++++++++++++++++++++++++++++
for(i=0;i<N;i++)
a[i]=b[i];
moves=0; // кількість обмінів (копіювань)
compares=0; // кількість порівнянь ключів елементів
start = clock();
MergeSort(a, 0, N-1);
finish = clock();
print("Array sorted by MergeSort", a, N, sorted);
cout<< "Time to sort array of " << N << " elements by MergeSort:";
duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout << duration << " seconds" << endl;
fout << endl << "Time to sort array of " << N << " elements by MergeSort: "
<< duration << endl;
cout <<compares<<" compares; "<< moves << " moves \n";
fout <<compares<<" compares; "<< moves << " moves \n";
delete [] a;
delete [] b; }
ВИСНОВОК
Курсова робота написана на тему “Алгоритми та структури даних”, і складається з кількох частин, в яких наглядно показано використання бінарних дерев, як структури даних та алгоритм бінарного пошуку.
В рамках даної курсової роботи було систематизовано, закріплено і розширено теоретичні і практичні знання з програмування, були застосовані різноманітні структури даних та алгоритми при розв’язуванні конкретних прикладних задач.
Отримані навики оформлення програмної документації.
20.11.2013 19:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора