ЛАБОРАТОРНАЯ РАБОТА №16 Тема: Разработка алгоритмов и программ с использованием динамических структур данных

Цель:Сформировать умения разрабатывать алгоритмы и программы с использованием динамических структур

Программное обеспечение: TURBO PASCAL 7.1

Оснащение:персональный компьютер, практикум

Время проведения: 2 уч. часа

Литература:

1. Немнюгин С.А. Turbo Pascal. Практикум. 2-е изд. СПб.: Питер, 2007. С. 138-149.

2. Павловская Т.А. Паскаль. Программирование на языке высокого уровня. Учебник для вузов. СПб.: Питер, 2008. С. 130-152.

ВОПРОСЫ ВХОДНОГО КОНТРОЛЯ:

1. Опишите операции с указателями.

2. Приведите примеры динамических переменных.

3. Пиведите пример динамических массивов.

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Динамические структуры данных типа дерево.

Алгоритмы создания и работа с деревьями (добавление, удаление)

Реализация в виде двоичного дерева позволяет эффективно организовать все 3 операции над таблицами. Схематически оно представляется в виде набора вершин, соединенных направленными дугами. В каждую ветвь, кроме корня, входит одна ветвь. Из каждой вершины выходит не более двух ветвей. Вершина, из которой не выходит ни одна ветвь, называется листом. При представлении таблицы в виде двоичного дерева тексты записей хранятся отдельно. Структура элемента:

Type

Text = <тип запись>;

AdrT = ^Text;

AdrZv = ^Zveno;

Zveno = record

K1: <тип ключа>;

Lev, Prav: AdrZv;

Ard: ArdT;

End;

Var

DvDer: AdrZv;

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Принцип построения дерева

1. Первая запись делается корнем дерева.

2. Если ключ первой записи меньше ключа корня, то ей в соответствие ставится левая вершина, иначе – правая.

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

4. В зависимости от сравнения ключа К с ключом в очередной вершине, перемещаемся влево или вправо от нее до тех пор, пока не найдем подходящую вершину, к которой можно присоединить новую вершину с ключом К.

5. В зависимости от результата сравнения ключа вершины с ключом К делаем вновь сформированную вершину левой или правой для найденной вершины.

Включение нового элемента в дерево

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

Пример.

(* считаем, что в дереве нет записи с тем же ключом *)

var

Zap: Text;

S: AdrZv;

T: AdrT;

Q, Root: AdrZv;

K: Integer;

Begin

…

New(T);

T^ := Zap;

New(S);

S^.K1 := K;

S^.AdrT := T;

S.Lev := nil;

L^.Prav := nil;

If Root = nil then Root := S

Else if K < Q^.K1 then Q^.Lev := S else Q^.Prav := S

Удаление записи из дерева

Если соответствующая вершина – лист дерева, или из нее выходит только одна ветвь, то для удаления записи достаточно скорректировать соответствующую ссылку вершины-предшественника. Если из удаляемой вершины выходит две ветви, то нужно найти подходящее звено дерева, которое можно было бы вставить на место удаляемого звена. Таким звеном является:

1. Самый правый элемент левого поддерева (выходящего из удаляемого элемента). Для достижения этого звена необходимо перейти в следующее от удаляемой вершины по левой ветви, а затем переходить в очередные вершины по правой ветви до тех пор, пока очередная ссылка вправо <> nil.

2. Самый левый элемент правого поддерева (выходящего из удаляемого элемента). Для достижения этого звена необходимо перейти в следующее от удаляемой вершины по правой ветви, а затем переходить в очередные вершины по левой ветви до тех пор, пока очередная ссылка вправо <> nil.

При исключении из дерева вершины с заданным ключом необходимо учесть три случая:

1. Звена с заданным ключом в дереве нет.

2. Звено с заданным ключом имеет не более одной ветви.

3. Звено с заданным ключом имеет две ветви.

Пример.

(* рекурсивная процедура исключения вершины с заданным ключом из дерева для варианта 1. Параметры: D – адрес корня дерева, K - ключ *)

procedure UDDer(Var D: AdrZv; K: Integer);

var Q: AdrZv;

procedure UD(Var R: AdrZv); { Рекурсивная процедура реализующая третий случай удаления; Начальное значение R – адрес левой вершины поддерева }

begin

if R^.Prav = nil then {Самая правая}

begin

Q^.K1 := R^.K1; {R – адрес замещающей вершины; Q – адрес замещаемой}

Q^.Adr := R^.Adr; {Ссылка на текст записи}

Q := R;

R := Q^.Lev; {Занесение в поле Prav звена-предшественника содержимого поля Lev из замещающего звена}

End

Else

UD(R^.Prav);

end;

begin

if D = nil then

Writeln(‘Звена нет’)

Else

If K < D^.Kl then

UDDer(D^.Lev, K)

Else

If K > D^.K1 then

UDDer(D^.Prav, K)

Else

Begin

Q := D; {В Q – адрес удаляемого звена}

If Q^.Prav = nil then

D := Q^.Lev {*} {Занесение ссылки на следующее звено}

Else

If Q^.Lev = nil then

D := Q^.Prav {**} {Занесение ссылки на следующее звено}

Else

UD(Q^.Lev); {***}

End;

end;

Для физического удаления удаляемого звена необходимо вместо (*) поставить

Begin

D := Q^.Lev;

Dispose(Q);

End

Аналогично на (**)

Для физического удаления замещающего звена вместо (***) нужно поставить

Dispose(Q);

Однонаправленные списки

Являются аналогами строк переменной длины. В строке каждый следующий элемент занимает ячейку памяти со следующим по порядку адресом. Элементы строки можно разместить произвольно, если каждый элемент снабдить явным указанием месторасположения следующего элемента. Тогда каждый элемент строки будет состоять из двух полей: литера строка и ссылка на следующий элемент.

type

Adr = ^Zveno;

Zveno = record

AdrSled: Adr;

Element: Char;

end;

Недостаток – движение возможно только в одном направлении.

Двунаправленные списки

Позволяют от любого звена двигаться в двух направлениях. Каждое звено содержит 2 поля ссылочного типа: ссылку на следующий и предыдущий элемент. Структура звена:

type

Adr2 = ^Zveno2

Zveno2 = record

AdrSled: Adr2;

AdrPred: Adr2;

Element: <тип элемента списка>;

end;

СОДЕРЖАНИЕ РАБОТЫ: Написать алгоритм и отладить программу, используя условия задания лабораторной работы №15.

Вариант	Задание
№1	― по запросу выдаются сведения об автобусах, находящихся в парке.
№2	― по запросу выдаются сведения об автобусах, находящихся в парке.
№3	― по запросу выдаются сведения об автобусах, находящихся в парке.
№4	― удаляет данные о списанных книгах.
№5	― удаляет данные о списанных книгах.
№6	― удаление заявок в список.
№7	― удаление заявок.
№8	― при выезде каждого автобуса из парка вводится номер автобуса, и программа удаляет данные об этом автобусе из списка автобусов, находящихся в парке.
№9	― при выезде каждого автобуса из парка вводится номер автобуса, и программа удаляет данные об этом автобусе из списка автобусов, находящихся в парке.
№10	― добавление данных о книгах, вновь поступающих в библиотеку.
№11	― добавление данных о книгах, вновь поступающих в библиотеку.
№12	― добавление заявок в список.
№13	― добавление заявок.
№14	― при въезде каждого автобуса в парк вводится номер автобуса, и программа записывает данные об этом автобусе в список автобусов, находящихся в парке.
№15	― при въезде каждого автобуса в парк вводится номер автобуса, и программа записывает данные об этом автобусе в список автобусов, находящихся в парке.
№16	― по запросу выдаются сведения о наличии книг в библиотеке.
№17	― по запросу выдаются сведения о наличии книг в библиотеке.
№18	― вывод всех заявок.