Структуры и алгоритмы обработки данных
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
°лит его, то есть первый элемент*)(* Иначе, если он не единственный *)(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 (listNIL) 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}
{п