Курсовая работа: Анализ алгоритмов нечисленной обработки данных
Данный метод удобен для массивов с большой длиной, но его использование возможно только в упорядоченных массивах.
Анализ сортировки деревом был проведен на примере массива длиной в 16, 128, 512, 1024 элементов.
Результаты представлены в виде нижеследующей таблицы.
Таблица 6. Результаты сортировки
Количество элементов в массиве | 16 | 128 | 512 | 1024 |
Количество перестановок | 18 | 130 | 514 | 1026 |
Ниже приведен график сортировки деревом.
Рисунок 3. График сортировки деревом.
Вывод: Организация массива в виде двоичного дерева требует несколько больших затрат как на организацию массива, так и на поиск в нем нужного элемента, чем это минимально необходимо. Впрочем, это увеличение не столь существенно. Этот метод оптимален по порядку роста трудоемкости поиска в зависимости от размера массива.
Сортировка деревом не является минимальной по памяти, так как на построения дерева необходимы большие затраты памяти, но процесс сортировки с помощью данного метода занимает мало времени.
В процессе выполнения данного курсового проекта изучены и разработаны алгоритмы нечисленной обработки данных: линейный и двоичный поиск заданного элемента, а также упорядочение массива методом сортировки дерева. Был проведен анализ результатов программы, который подтвердил правильность составления и отладки программы. Для наглядности результатов работы программы построены графики и составлены таблицы.
1. Лорин Г. Сортировка и системы сортировки. М.: Наука, 1983г.
2. Лавров С.С, Гончаров Л.И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971г.
3. Попов В.Б. Turbo Pascal. М.: Финансы и статистика, 2007г.
Таблицы идентификаторов
Таблица А.1: Идентификаторы основной программы
Имя параметра | Физический смысл параметра | Тип параметра |
n | Длина исходного массива до 1024 элементов | integer |
i | Счетчик, индекс элемента массива | integer |
j | Счетчик, индекс элемента массива, указатель | integer |
x | Искомое число | integer |
a | Одномерный числовой массив (исходный массив) | mas=array [1..1024] of integer |
b | Двумерный числовой массив, дерево, образованное из исходного массива | mas2=array [1..1024, 1..5] of integer |
b1 | Двумерный числовой массив, сортируемое дерево | mas2=array [1..1024, 1..5] of integer |
F | Текстовый файл для хранения исходного массива | text |
F_1 | Текстовый файл для хранения отсортированного массива, сортируемого массива после каждой перестановки | text |
Таблица А.2: Идентификаторы процедуры VVod
Имя параметра | Физический смысл параметра | Тип параметра |
i | Счетчик, индекс элемента формируемого массива | integer |
n | Длина формируемого массива | integer |
a | Формируемый массив | mas=array [1..1024] of integer |
Таблица А.3: Идентификаторы процедуры Vivod
Имя параметра | Физический смысл параметра | Тип параметра |
i | Счетчик, индекс элемента выводимого на экран массива | integer |
n | Длин массива, выводимого на экран | integer |
a | Выводимый на экран массив | mas=array [1..1024] of integer |
Таблица А.4: Идентификаторы процедуры Save_To_File
Имя параметра | Физический смысл параметра | Тип параметра |
i1 | Счетчик, индекс элемента массива, сохраняемого в файл | integer |
F | Файл, в который необходимо записывать сортируемый массив после каждой перестановки | text |
n | Длина массива | integer |
a | Исходный массив, сохраняемый в файл | mas=array [1..1024] of integer |
m | Количество перестановок | integer |
А.5 Идентификаторы процедуры Lin_Poisk
Имя параметра | Физический смысл параметра | Тип параметра |
i | Счетчик, индекс элемента массива | integer |
k | Количество сравнений | integer |
n | Длина массива | integer |
a | Массив, в котором необходимо найти искомый элемент | mas=array [1..1024] of integer |
x | Искомый элемент | integer |
Таблица А.6 Идентификаторы процедуры Dv_Poisk
Имя параметра | Физический смысл параметра | Тип параметра |
sri | Индекс среднего элемента в массиве | integer |
k | Количество сравнений | integer |
vi | Индекс верхнего элемента в массиве | integer |
ni | Индекс нижнего элемента в массиве | integer |
n | Длина массива | integer |
a | Массив, в котором необходимо найти искомый элемент | mas=array [1..1024] of integer |
x | Искомый элемент | integer |
f | Флаг нахождения искомого элемента в массиве | boolean |
Таблица А.7: Идентификаторы процедуры Tree
Имя параметра | Физический смысл параметра | Тип параметра |
i | Счетчик, индекс элемента массива (строка) | integer |
j | Счетчик, индекс элемента массива (столбец) | integer |
s | Рабочая память, необходимая для хранения значения | integer |
k | Индекс элемента в массиве | integer |
a | Исходный массив, из которого следует построить дерево | mas=array [1..1024] of integer |
n | Длина массива | integer |
b | Дерево, полученное из массива A | mas2=array [1..1024, 1..5] of integer |
Таблица А.8: Идентификаторы процедуры TreeSort
Имя параметра | Физический смысл параметра | Тип параметра |
k | Число вершин дерева | integer |
m | Количество перестановок | integer |
i1 | Счетчик, индекс элемента массива | integer |
b | Дерево, полученное из массива | mas2=array [1..1024, 1..5] of integer |
b1 | Сортируемое дерево | mas2=array [1..1024, 1..5] of integer |
a | Отсортированный массив | mas=array [1..1024] of integer |
Текст программы
Program Fariza_Kurs;
uses crt;
type
mas= array [1..1024] of integer;
mas2= array [1..1024, 1..5] of integer;
var n,i,j,x: integer;
a: mas;
b,b1: mas2;
f, f1: text;
Procedure Vvod(n: integer; Var a: mas);
var i: integer;
begin
if n<=16 then
begin
writeln('Vvedite elementy massiva');
for i:=1 to n do read(A[i]);
end
else
for i:=1 to n do
A[i]:=random(1000);
writeln(f,'Ishodnii masssiv');
for i:=1 to n do write(f,a[i]:4);
end;
Procedure Vivod(n: integer; a: mas);
var i: integer;
begin
for i:=1 to n do write(a[i], ' ');
end;
{zapis v fail}
Procedure Save_To_File(var f:text; n: integer; a: mas; m:integer);
var i1: integer;
begin
if n<=16 then
begin
writeln(f,m,'-yi shag:');
for i1:=1 to n do
write(f,A[i1]:4);
writeln(f);
end;
if (n>16) and (m mod 10=0) then
begin
writeln(f,m,'-yi shag:');
for i1:=1 to n do
write(f,A[i1]:4);
writeln(f);
end;
end;
{metod lineinogo poiska}
Procedure Lin_Poisk(n: integer; a: mas; x: integer);
var i,k: integer;
begin
writeln('Metod lineinogo poiska:');
k:=0;
for i:=1 to n do
if a[i]=x then begin k:=i; break;
end;
if k<>0 then Writeln('Element naiden. Sravnenii - ',k)
else writeln('Element ne naiden');
end;
{========metod dvoichnogo poiska ================}
procedure Dv_Poisk(n:integer;a:mas; x:integer);
var k,ni,vi, sri:integer;
f:boolean;
begin
writeln('Metod dvoichnogo poiska:');
vi:=N;
ni:=1;
k:=0;
f:=FALSE;
repeat
sri:=( (ni+vi) div 2);
k:=k+1;
if a[sri] = X then f:=TRUE
else if X > a[sri] then ni:=sri else vi:=sri;
until (k>trunc(ln(n)/ln(2))) or (f=true);
if f=true then writeln('Element naiden, Index= ', sri,'. Sravnenii ',k)
else writeln('Element ne naiden');
end;
{predstavlenie massiva A v vide dereva}
Procedure Tree(a:mas; n: integer; var b: mas2 );
label l;
var i,j,s,k: integer;
begin
b[1,3]:=0;
b[1,4]:=0;
b[1,5]:=0;
for i:=1 to n do begin
b[i,1]:=a[i];
b[i,2]:=a[i];
end;
for i:=2 to n do
begin
k:=1;
l: if b[i,1]<b[k,1] then j:=3 else j:=4;
s:=b[k,j];
if s<>0 then begin
k:=s;
goto l;
end;
b[k,j]:=i;
b[i,3]:=0;
b[i,4]:=0;
b[i,5]:=k;
end;
end;
{sortirovka derevom}
procedure Tree_Sort(b: mas2; var b1: mas2; n: integer);
label l1,l2,l3;
var k,m,i1: integer;
begin m:=0;
for i:=1 to n do
for j:=1 to 5 do
b1[i,j]:=b[i,j];
i:=1;
k:=0;
l1:
if b[i,3]<>0 then
begin
i:= b[i,3];
goto ll;
end;
m:=m+1;
for i1:=1 to n do A[i1]:=b1[i1,1];
savetofile(f1,n,a,m);
l2:
k:=k+1;
b1[k,1]:=b[i,1];
b1[k,2]:=b[i,2];
if b[i,4]<>0 then
begin
i:=b[i,4];
goto ll;
end;
m:=m+1;
for i1:=1 to n do A[i1]:=b1[i1,1];
savetofile(f1,n,a,m);
l3:
j:=i;
i:=b[i,5];
if i<>0 then
begin
if b[i,1]> b[j,1] then goto lm else goto ln;
end;
m:=m+1;
for i1:=1 to n do A[i1]:=b1[i1,1];
savetofile(f1,n,a,m);
writeln('Otsortirovanii massiv');
Vivod(n,a);
readln;
writeln('Kolichestvo perestanovok=',m);
end;
BEGIN
writeln(' VVedite 4islo elementov massiva N<=1024');
readln(n);
assign (f, 'd:\dan.txt');
rewrite(f);
Vvod(n,a);
close(f);
writeln('Ishodnii massiv:');
Vivod(n,a);
{====================lineinii poisk===============}
writeln;
writeln('Vvedite element dla poiska');
readln(x);
LinPoisk(n,a,x);
{========sortirovka============}
assign (f1, 'd:\res.txt');
rewrite(f1);
tree(a,n,b);
Treesort(b,b1,n);
writeln(f1, 'Otsortirovannyi massiv:');
for i:=1 to n do write(f1, A[i]:4);
close(f1);
{========dvoichnii poisk===========}
DvPoisk(n,a,x);
end.