Структуры и алгоритмы обработки данных

 

Задача 1. Методы сортировки

Задание:

Составить программу, реализующую указанный вид сортировки для массива элементов размерности N (N?50) указанного типа сформированного случайным образом. Отчет должен содержать краткое объяснение алгоритма сортировки, листинг программы и результаты работы программы. Для варианта №10: сортировка массива целых чисел алгоритмом линейная вставка.

Решение:

Объяснение алгоритма сортировки «линейная вставка».

Сортировка линейной вставкой - самый простой алгоритм, реализующий ручную сортировку карт при игре в Бридж. Просматривая массив с одного конца до другого, каждый элемент массива ставится в правильную позицию по отношению к уже отсортированным элементам.

Эта сортировка работает со списком неупорядоченных положительных целых чисел, сортируя их в порядке возрастания.

Описание алгоритма:

Сортируется вектор A длиной N

Нач

Для i от 2 до N Цикл

X:= A[i];:= i-1;

Пока (j ³ 1) и (A[j] > X) Цикл[j+1]:= A[j];{сдвиг элементов}:= j - 1;

КЦикл[j+1]:= X;{вставка элемента на свое место}

КЦикл

Кон

На каждой итерации первое число не отсортированного списка удаляется из него и помещается на соответствующее ему место в отсортированном списке. Для этого отсортированный список, просматривается, начиная с наименьшего числа до тех пор, пока не находят соответствующее место для нового числа, то есть пока все числа с меньшими значениями не окажутся впереди него, а все числа с большими значениями - после него.

Покажем работу алгоритма на примере:

412 71 81 59 14 273 87

Итерация 0:

Неотсортированный: 412 71 81 59 14 273 87

Отсортированный: 27

Итерация 1:

Неотсортированный: 412 71 81 59 14 273 87

Отсортированный: 27412

Итерация 2:

Неотсортированный: 71 81 59 14 273 87

Отсортированный: 2771 412

Итерация 3:

Неотсортированный: 81 59 14 273 87

Отсортированный: 2771 81 412

Итерация 4:

Неотсортированный: 59 14 273 87

Отсортированный: 2759 71 81 412

Итерация 5:

Неотсортированный: 14 273 87

Отсортированный: 14 27 59 71 81 412

Итерация 6:

Неотсортированный: 273 87

Отсортированный: 14 27 59 71 81 273 412

Итерация 7:

Неотсортированный: 87

Отсортированный: 14 27 59 71 81 87 273 412

Листинг программы

{сортировка массива целых чисел алгоритмом линейная вставка}

Program Sort1;crt, dos;

const=50; {максимальный размер вектора}

type=array [1..ARRAYSIZE] of integer; {тип вектора}: arrayType; {сортируемый вектор}

n: integer; {количество элементов в векторе}

i,j: integer;: char;

{процедура создания и вывода вектора theArray с размером SIZE}

Procedure Vector (SIZE, MAX: integer; var theArray:arrayType);;i:=1 to SIZE do[i]:=random(MAX);('Исходный массив: ');i:=1 to Size do(theArray[i],' ');;

{процедура сортировки}InsertSort (size: integer; var theArray: arrayType);

var: integer; {начальная позиция вставляемого на место элемента}: integer; {значение вставляемого на место элемента}: integer; {позиция вставляемого в упорядоченном векторе}

beginnewPos:=2 to SIZE do:=theArray [newPos];:=newPos-1;(currentPos>=1) and (theArray[currentPos]>newValue) do[currentPos+1]:=theArray[currentPos];:=currentPos-1;;[currentPos+1]:=newValue;;;

{главная программа}

clrscr;('Введите желаемое количество элементов (до 50)');

Readln(n);(n,ARRAYSIZE,a);(n,a);;('Отсортированный массив: ');i:=1 to n do(' ',a[i]);

Readln;('Будете еще? (да - y; нет - n)');

ch:=ReadKey;(ch='N') or (ch='n');

end.

Задача 2. Исследование методов сортировки

Задание:

Составить алгоритм и разработать программу, реализующую указанный вид сортировки. Исследовать работу программы на сортировке n целых чисел, если они:

расположены случайным образом;

отсортированы;

отсортированы в обратном порядке;

В результате исследований построить графики зависимости tср (время сортировки) от n (количество элементов) для всех 3-х случаев (случайный массив, отсортированный, отсортирован в обратном порядке). Отчет должен содержать краткое объяснение алгоритма сортировки, листинг программы, графики, построенные в результате работы программы, выводы. Для варианта №10: быстрая сортировка (обменная сортировка с разделением).

Решение:

Объяснение алгоритма быстрой сортировки

Это один из лучших алгоритмов сортировки. Основные особенности этого алгоритма покажем на примере сортировки произвольного вектора А:

Выбирается "центральный" элемент массива А - х. Массив делится на две части этим элементом.

Указатель i устанавливаем в начало левой части. Меняем этот указатель до тех пор, пока элемент Аi меньше центрального элемента х (Аi<х).

Указатель j устанавливаем в конец правой части. Меняем этот указатель до тех пор, пока элемент Аj больше центрального элемента х (Аj<х).

Если левый указатель i меньше правого указателя j, то элементы Аi и Аj меняем местами. Процесс продолжается до тех пор, пока произвольно выбранный вначале "центральный" элемент массива не займет свою позицию в массиве, то есть все элементы стоящие слева от этого элемента будут меньше его, а все элементы, стоящие справа - больше, а также все элементы левой части будут меньше каждого правого элемента.

Если слева от выбранного "центра" более одного элемента, то процедура повторяется для левой части массива.

Если справа от выбранного "центра" более одного элемента, то процедура повторяется для правой части массива.

Листинг программы

{сортировка массива целых чисел алгоритмом быстрая сортировка}

Program Sort2;crt, dos;

const=5000; {максимальный размер вектора}

type=array [1..ARRAYSIZE] of integer; {тип вектора}: arrayType; {сортируемый вектор}

n: integer; {количество элементов в векторе}

exp: integer;: byte;: integer;,j,k: integer;: integer;: text;: real;_time:array[1..3] of real;

{процедура создания вектора theArray с размером SIZE}

Procedure Vector (SIZE, MAX: integer; var theArray:arrayType);;i:=1 to SIZE do[i]:=random(MAX);

{Writeln('Исходный массив: ');i:=1 to Size do(theArray[i],' ');};QSort (SIZE:integer; var theArray:arrayType; var time:real);, min, sec, hund: word;_time, finish_time: real;sort (L,R:integer);, Tmp: Integer;:=L;:=R;:=theArray[(L+R) div 2];i<=j dotheArray[i]<B do i:=i+1;B<theArray[j] do j:=j-1;i<=j then:=theArray[i];[i]:=theArray[j];[j]:=Tmp;:=i+1;:=j-1;;;L<j then sort(L,j);i<R then sort(i,R);;(hour,min,sec,hund);_time:=sec+hund*0.01+min*60+hour*3600;(1,Size);(hour,min,sec,hund);_time:=sec+hund*0.01+min*60+hour*3600;:= finish_time - start_time;

end;

{главная программа};

assign (f, 'd:\Work\Ann\tp71\BIN\Serik');

rewrite (f);('Введите необходимое количество точек для построения графики: ');

Readln(point);:=round(ARRAYSIZE/point);

Writeln ('Введите количество экспериментов: ');(exp);(f, ' Среднее время сортировки элементов ');(f, ' кол-во ',' обратно- ',' сортированные');(f, 'элементов сортированные ');

for k:=1 to point do:=step*k;i:=1 to 3 do_time[i]:=0.0;j:=1 to exp do(n,ARRAYSIZE,a);(n,a,t);_time[i]:=aver_time[1]+t;i:=1 to n div 2 do:=a[i];[i]:=a[n-i+1];[n-i+1]:=c;;(n,a,t);_time[2]:=aver_time[2]+t;(n,a,t);_time[3]:=aver_time[3]+t;;i:=1 to 3 do_time[i]:=aver_time[i]/exp;(f,n:7,' ');i:=1 to 3 do(f, aver_time[i]:7:2,' ');(f);;(f);

end.

Задача 3. Циклические списки

Задание:

Описать указанный абстрактный тип данных и основные функции работы с ним на абстрактном уровне. Реализовать процедуры необходимые для вставки, удаления элемента в указанный вид АТД, процедуру печати содержимого АТД, а также дополнительно реализовать процедуру указанную в варианте, на конкретном языке программирования.

Для варианта №10: Однонаправленный циклический список символов. Реализовать процедуру подсчета суммы элементов.

Решение:

Теоретическое введение

Циклически связанный список (сокращенно - циклический список) обладает той особенностью, что связь его последнего узла не равна Л, а идет назад к первому узлу списка. В этом случае можно получить доступ к любому элементу, находящемуся в списке, отправляясь от любой заданной точки; одновременно мы достигаем также полной симметрии, и теперь нам уже не приходится различать в списке "последний" или "первый" узел. Типичная ситуация выглядит следующим образом:

Предположим, в узлах имеется два поля: INFO и LINK. Переменная связи PTR указывает на самый правый узел списка, a LINK (PTR) является адресом самого левого узла.

Рис. 1

Разновидностью рассмотренных видов линейных списков является кольцевой список, который может быть организован на основе как односвязного, так и двухсвязного списков. При этом в односвязном списке указатель последнего элемента должен указывать на первый элемент.

Листинг программыlist;CRT;pt = ^elem;= record: byte;: pt;;getprelastel (list:pt):pt;nextel:pt;(list<>NIL) then (* Если список не пуст *):=list;:=nextel; (* Перейти к следующему элементу списка *)(list^.next<>NIL) then

nextel:=list^.next;(nextel^.next=NIL); (* Пока следующий за данным элемент списка не будет последним *):=list; (* Вернуть найденный элемент *)(* Иначе, если список пуст *):=NIL; (* Вернуть указатель на пустой список *)

end;getlastel (list:pt):pt;(list<>NIL) then (* Если список не пуст, то: *)(list^.next<>NIL) do (*Пока текущий элемент списка не последний*)

list:=list^.next; (*Перейти к следующему элементу *):=list; (* Вернуть найденный элемент *)(* Иначе *):=NIL; (* Вернуть указатель на пустой список *)

end;searchel (list:pt;info:byte):pt;(list<>NIL) then (* Если список не пуст *)((list^.next<>NIL) and (list^.info<>info)) do (* Пока текущий элемент не последний и не искомый *):=list^.next; (* Переходить к следующему элементу списка *)

if (list^.info<>info) then (* если искомый элемент не найден *):=NIL (*вернуть указатель на пустой список *)(* Иначе *):=list; (*Вернуть указатель на этот элемент*)(* Иначе *):=NIL; (* Вернуть указатель на пустой список *)

end;;searchpreel (list:pt;info:byte):pt;nextel:pt;(list<>NIL) then (* Если список не пуст *):=list;:=nextel; (* Переходить к следующему элементу списка *)(list^.next<>NIL) then:=list^.next;((nextel^.next=NIL) or (nextel^.info=info)); (* пока следующий за текущим элемент - не последний или искомый*)

if (nextel^.info<>info) or (nextel=list) then (* Если нужный нам элемент не найден или в списке 1 элемент *):=NIL (* Вернуть указатель на пустой список *)(* Иначе *):=list; (* Вернуть указатель на найденный элемент *)(* Иначе, если список пуст *):=NIL; (* Вернуть указатель на пустой список *)

end;;getelem(elname:string):byte;ret:byte;('Введите ',elname,': ');(ret);:=ret;;addtobegin (var list:pt;info:byte);newelem:pt;(newelem); (* создать в памяти новый элемент *)^.info:=info;^.next:=list; (* Присоединить к этому элементу спиоск *)

list:=newelem; (* Вернуть его, как начало нового списка *)

end;addafter (listel:pt;info:byte);newelem:pt;(listel<>NIL) then (* Если список не пуст *)

begin(newelem); (* Создать в памяти новый элемент *)^.info:=info;^.next:=listel^.next; (*Вставить элемент между заданным элементом и следующим *)

listel^.next:=newelem;;;addtoend (var list:pt;info:byte);(list=NIL) then(*Если список пуст*)

addtobegin(list,info)(*Добавить элемент в начало, создав новый список *)(*Иначе*)(getlastel(list),info); (*Добавить элемент после последнего *)

end;addbefore (listel:pt;info:byte);newelem:pt;(listel<>NIL) then (* Если список не пуст *)

begin(newelem); (* Создать в памяти новый элемент *)^.info:=listel^.info; (*Скопировать в него заданный элемент списка*)^.info:=info; (*Записать в заданный элемент списка после добавленного*)^.next:=listel^.next; (*Вставить заданный элемент списка после добавленного*)

listel^.next:=newelem;;;delfirstel(var list:pt);temp:pt;(list<>NIL) then (*Если список не пуст*)

begin:=list; (*Сохранит в памяти адрес первого элемента*):=list^.next; (*Отрезать от списка первый элемент*)(temp); (*Убрать первый элемент из памяти*)

end;;dellastel(var list:pt);temp:pt;(list<>NIL) then (* Если список не пуст, то *)

if (list^.next=NIL) then (* Если в списке один элемент *)

delfirstel(list) (* Удалить его *)(* иначе *)

temp:=getprelastel(list); (* Найти предпоследний элемент списка*)(temp^.next); (* Удалить следующий за ним *)

temp^.next:=NIL;;;delel(var list:pt;el:pt);temp:pt;((list<>NIL) and (el<>NIL)) then (* Если дан элемент для удаления и список не пуст *)

begin(el^.next=NIL) then (* Если элемент, который нужно удалить - последний в списке *)(list^.next=NIL) then (* И если он еще и единственный *)(list) (* Удалит его, то есть первый элемент*)(* Иначе, если он не единственный *)(list) (*Удалит его, то есть последний элемент*):=el^.next; (* Скопировать в этот элемент следующий за ним *)

el^.info:=temp^.info;^.next:=temp^.next;

dispose(temp); (* Удалить следующий за этим элемент *)

end;;;delbefore(var list:pt;info:byte);temp:pt;(list<>NIL) then (* Если список не пуст *):=searchpreel(list,info); (*Найти элемент, предшествующий искомому *)

delel(list,temp); (* И удалить его *)

end;;delafter(var list:pt;info:byte);temp:pt;(list<>NIL) then (* Если список, не пуст *):=searchel(list,info); (* Найти искомый элемент *)

temp:=temp^.next; (* И удалить следующий за ним *)

delel(list,temp);;printlist (list:pt);;(list=NIL) then (* Если список пуст *)

writeln('Список пуст!') (* Сообщить об этом *)(list<>NIL) do(* Пока текущий элемент списка не последний *)

begin(list^.info); (* Распечатать его *)

list:=list^.next;(* Перецти к следующему элементу *)

if (list<>NIL) then(',')('.');;;;checkel(list:pt;info:byte);(searchel(list,info)<>NIL) then

writeln('Элемент ',info,' существует.')('Элемент ',info,' не существует.');;;

{процедура подсчета summi элементов}

Procedure Col (List: pt; var S:byte);: pt;:=0;

L:= List; {указатель на начало списка}

while L<>nil do begin:=S+L^.info;

L:=L^.next;;('Сумма элементов списка ', S);

ReadKey;;showmenu;;

Writeln('1) Добавить элемент в начало списка');('2) Добавить элемент в конец списка');('3) Распечатать список');('4) Удалить первый элемент из списка');('5) Удалить последний элемент из списка');('6) Найти, существует ли указанный элемент в списке');('7) Удалить указанный элемент из списка');('8) Добавить элемент после указанного');('9) Добавить элемент перед указанного');('10) Удалить после указанного');('11) Удалить перед указанным');('12 Сумма элементов списка');('13) Выход из программы');

Writeln;(' Ваш выбор:');;root: pt;: byte;

Sum:byte;:=NIL;(* Создать пустой список *);(* Показать меню *)(selection);(* Ввести с клавиатуры пункт меню *);selection of(* выполнить действие, затребованное пользователем *)

1: addtobegin(root,getelem('значение элемента'));

: addtoend(root,getelem('значение элемента'));

: printlist(root);

: delfirstel(root);

: dellastel(root);

: checkel(root,getelem('значение искомого элемента'));

7: вудуд(кщщебыуфксруд(кщщебпуеудуь(эзначение элемента для удалениия э)));

: addafter (searchel(root,getelem ('значение искомого элемента')), getelem ('значение элемента для добавления '));

: addbefore (searchel(root,getelem('значение искомого элемента')), getelem ('значение элемента для добавления '));

: delafter(root,getelem('значение искомого элемента'));

: delbefore(root,getelem('значение искомого элемента'));

12: begin(root,Sum);('Сумма элементов списка', Sum);

end;

: clrscr;;selection=13;(* Если пользователь выбрал не выход *).

Задача 4. Деревья

сортировка алгоритм список дерево

Задание:

Описать абстрактный тип данных «дерево» и основные функции работы с ним на абстрактном уровне. Реализовать процедуры необходимые для создания дерева и печати содержимого дерева согласно варианта на конкретном языке программирования. Представить арифметическое выражение, указанное в варианте в виде дерева и вывести его на экран в виде согласно варианту. Для варианта №9: Прямое представление дерева. Арифметическое выражение представить в виде префиксной записи.

/4 - d=¾¾¾¾¾¾*a - 1

Решение:

Теоретическое введение

Дерево - это граф, который характеризуется следующими свойствами:

. Существует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент - и который называется КОРНЕМ.

. Начиная с корня и следуя по определенной цепочке указателей, содержащихся в элементах, можно осуществить доступ к любому элементу структуры.

. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.

Наше выражение: X = (c/4 - d)/(a*a - 1) представляется в виде следующего графа на рис. 2:

Рис. 2 - Выражение, представленное в виде дерева

Существует несколько способов представления абстрактной древовидной структуры. Мы рассмотрим следующие способы представления:

. С помощью средств динамического размещения компонент и указания их с помощью ссылок. Следовательно, дерево на рис.1 состоит из компонент такого типа:node = record

op: char;, right:^node;

end;

. С помощью массива:: array [1..11] of

record :char;, right: integer;

end;

Существует три способа обхода деревьев:

. Сверху вниз: R, A, B;

. Слева направо: A, R, B;

. Снизу вверх: A, B, R.

Преобразование дерева в бинарное (двоичное) дерево

Любое m-арное дерево можно хранить в виде двоичного дерева. Алгоритм преобразования m-арного дерева в двоичное состоит в следующем:

. Первый потомок вершины размещается по вертикали вниз, а его братья - по горизонтали. Эту операцию повторяют для каждой отдельно взятой вершины.

. Полученное дерево разворачивают на 45° и получают дерево, для каждой вершины которого справа находятся братья, а слева потомки.

Рассмотрим предложенный алгоритм на примере:

При последовательном размещении дерева один из указателей отсутствует. При фамильном размещении отсутствует правый указатель. При этом братья, если они есть, всегда находятся рядом. Вместо правого указателя введем логический признак: равный true, если у вершины есть правое поддерево и false - нет. Для хранения дерева можно воспользоваться массивом.

Листинг программы

{$M 65500, 0, 100000}MathExpr; {программа вычисляет математическое выражение, строит дерево }

Uses crt;tr=^rec;=record:string; {Информационное поле}: boolean; {Флаг символа}

zn:real; {Значение переменной}: boolean; {Вспомогательный флаг},r:tr; {Указатели на потомка};root,el: tr; {вершина и узлы дерева}: string; {вспомогательная переменная},j:byte; {},y:integer; {координаты для вывода дерева}:byte; {вспомогательная переменная}: char; {}: integer; {для процедуры VAL}

{процедура преобразования арифметического выражения в бинарное дерево}

{процедура использует рекурсивный нисходящий обход}

Procedure Tree (p:tr);undertree (c:char); {создает поддеревья}Skob; {учитывает скобки}i:=i+1;p^.pole[i]='(' then Skob;:=i+1;p^.pole[i]=')';; {Skob}i:=1 to length(p^.pole) dop^.pole[i]='(' then:=i;;(p^.pole[i+1]<>'+') and (p^.pole[i+1]<>'-')(p^.pole[i+1]<>'*') and (p^.pole[i+1]<>'/')(p^.pole[g-1]<>'*') and (p^.pole[g-1]<>'/')(p^.pole[g-1]<>'-') and (p^.pole[g-1]<>'+')(p^.pole[i+1]<>'^') and (p^.pole[g-1]<>'^')(p^.pole,i,1);(p^.pole,1,1);:=0;;;p^.pole[i]=c then(p^.l);^.l^.l:=nil;^.l^.r:=nil;^.l^.pole:=copy(p^.pole,1,i-1);^.l^.zn:=0;^.l^.sym:=false;(p^.r);^.r^.l:=nil;^.r^.r:=nil;^.r^.pole:=copy(p^.pole, i+1, ord(p^.pole[0]));^.r^.zn:=0;^.r^.sym:=false;:=ord(p^.pole[0]);^.pole:=c;;;; {UnderTree}p<>nil then

{Строятся поддеревья в зависимости от приоритета арифметической операции}

begin('+');('-');('*');('/');('^');(p^.l);(p^.r);;; {Tree}

{Вычисление значения арифметической функции}

{процедура использует рекурсивный нисходящий обход}

Procedure Calc(p:tr);p<>nil then beginp^.l^.sym and p^.r^.sym thenp^.pole[1] of

'+': begin^.zn:=p^.l^.zn+p^.r^.zn;^.sym:=true;;

'-': begin^.zn:=p^.l^.zn-p^.r^.zn;^.sym:=true;;

'*': begin^.zn:=p^.l^.zn*p^.r^.zn;^.sym:=true;;

'/': begin^.zn:=p^.l^.zn/p^.r^.zn;^.sym:=true;;

'^': begin^.zn:=EXP(p^.r^.zn*LN(p^.l^.zn));^.sym:=true;;; {case};(p^.l);(p^.r);

end;;{calc}

{процедура определяет где в дереве переменная или значение, и где

знак операции. Используется рекурсивный нисходящий обход}

Procedure Symb(p:tr);p<>nil thenp^.pole[1] in ['a'..'z'] then^.sym:=true;(p^.pole,'= ');(p^.zn);;p^.pole[1] in ['0'..'9'] then^.sym:=true;(p^.pole,p^.zn,code);;(p^.l);(p^.r);

end;; {Symb}

{процедура выводит на экран, полученное дерево }

{процедура использует рекурсивный нисходящий обход}

Procedure OutTree (pr:tr; f:byte);:=y+2;pr<>nil thenf=1 then:=x-5;;f=2 then:=x+9;

end;(X,Y);

{Если f=0 то выводится корневая вершина}

if f=0 then writeln ('[',pr^.pole,']');

{Если f=1 то выводится левое поддерево}

if f=1 then writeln ('[',pr^.pole,']/');

{Если f=2 то выводится правое поддерево}

if f=2 then writeln ('\[',pr^.pole,']/');(pr^.l,1);(pr^.r,2);;:=y-2;; {OutTree}{главная прога}(1,1,80,25);:=22;:=0;(Blue);;

{Ввод выражения, которое нужно посчитать}('Введите ваше выражение: ');(40,4);('Используйте следующие опреации: ');

GotoXY(50,5);('+, -, *, /, ^ ');(40,7);

Write('Программа применяет деревья для ');(40,8);('вычисления математического выражения: ');(1,2);(st);

{root - концевая вершина/ ее создание}

New(el);^.l:=nil;^.r:=nil;^.pole:=st;^.zn:=0;^.sym:=false;^.rend:=false;:=el;

{end of root}(root); {Создается дерево}

{Ввод значений переменных}('Введите значения: ');

Symb(root);(30,1,80,25);(Blue);(White);;('Дерево выглядет так: ');(root,0);root^.l^.sym and root^.r^.sym(root);^.rend:=true;calc(root);root^.rend;(1,23,29,25);(Red);(Green);;('Результат = ', root^.zn:2:3); {вывод результата}('Еще? (y/n)');(yn);yn='n';

end.

Задача 1. Методы сортировки Задание: Составить программу, реализующую указанный вид сортировки для массива элементов размерности N (N?50) указанного т

Больше работ по теме: