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

Контрольная работа - Компьютеры, программирование

Другие контрольные работы по предмету Компьютеры, программирование

°лит его, то есть первый элемент*)(* Иначе, если он не единственный *)(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}

{п