for i := 1 to N-1 do StatList [ i ]. Next := i + 1;

StatList [ N ]. Next := 0;

Начало вспомогательного списка задается переменной StartFree с начальным значением 1. Удаление элемента из основного списка приводит к изменению связующей части удаленного элемента и изменению значения переменной StartFree на индекс удаленного элемента. При добавлении нового элемента свободная ячейка определяется по значению переменной StartFree с последующим ее изменением.

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

Состояние списка с шестью элементами:

· Занятые ячейки массива: 3 - 1 - 2 - 8 - 10 - 5

Состояние списка со всеми десятью элементами:

· Занятые ячейки: 8 - 2 - 5 - 6 - 7 - 10 - 1 - 4 - 3 - 9

· Свободных ячеек нет: StartFree = -1

3.5 Динамическая реализация линейных списков

Динамическая реализация линейного списка, также как стека и очереди, основана на динамическом выделении и освобождении памяти для элементов списка. Логическая последовательность элементов списка создается ссылочными переменными с адресами последующих элементов (последний элемент имеет пустую ссылку nil). Опять же для удобства реализации будем считать, что список ВСЕГДА содержит хотя бы один элемент-заголовок с адресом первого реального элемента списка. Это позволяет унифицировать процедуры добавления и удаления крайних элементов и устранить некоторые проверки. Адрес элемента-заголовка задается переменной-указателем pHead. Эта переменная устанавливается при первоначальном создании списка и в дальнейшем НЕ изменяется. Для реализации основных действий используются вспомогательные ссылочные переменные. Необходимые объявления:

type pDinItem = ^ TDinItem; {ссылочный тип для адресации элементов списка}

TDinItem = record

{базовый тип, определяющий структуру элемента списка}

inf : <тип информационной части>;

next : pDinItem; {адрес следующего элемента}

end;

var pHead : pDinItem;

Создание пустого списка включает:

· выделение памяти под заголовок: new(pHead);

· установку пустой ссылочной части заголовка: pHead^.next := nil;

Проход по списку от первого элемента к последнему практически не отличается от прохода по очереди.

Поиск заданного элемента включает:

· установку вспомогательного указателя в адрес первого элемента списка

· организацию цикла прохода по списку с завершением либо по совпадению информационной части элемента с заданным значением, либо по достижению конца списка

· после завершения цикла проверить значение вспомогательного указателя и сделать вывод об успешности поиска

pCurrent := pHead^.next;

while (pCurrent <> nil) and (pCurrent^.inf <> `заданное значение')

do pCurrent := pCurrent^.next;

if pCurrent = nil then `Элемента нет' else `элемент найден';

Удаление заданного элемента включает:

· поиск удаляемого элемента с определением адреса элемента-предшественника (для этого вводится еще одна вспомогательная ссылочная переменная pPrev, инициированная адресом заголовка и изменяющая свое значение внутри цикла)

· если удаляемый элемент найден, то изменяется ссылочная часть его предшественника:

pPrev^.next := pCurrent^.next

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

Добавление нового элемента ПОСЛЕ заданного включает:

· поиск заданного элемента с помощью вспомогательного указателя pCurrent

· выделение памяти для нового элемента с помощью еще одного указателя pTemp

· формирование полей нового элемента, в частности - настройка ссылочной части

pTemp^.next := pCurrent^.next;

· изменение ссылочной части текущего элемента на адрес нового элемента

pCurrent^.next := pTemp;

Добавление нового элемента ПЕРЕД заданным включает:

· поиск заданного элемента с одновременным определением элемента-предшественника (используются указатели pCurrent и pPrev)

· выделение памяти для нового элемента с помощью еще одного указателя pTemp

· формирование полей нового элемента, в частности - настройка ссылочной части:

pTemp^.next := pCurrent;

· изменение ссылочной части элемента-предшественника на адрес нового элемента:

pPrev^.next := pTemp;

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

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

3.6 Практические задания

Задание 1. Реализовать программу для простейшего моделирования линейного списка с помощью массива. Должны быть реализованы все основные действия:

· проход по списку с выводом на экран информационных частей элементов

· поиск элемента с заданной информационной частью

· добавление нового элемента после заданного и перед заданным со сдвигом (при необходимости) хвостовой части вправо для освобождения ячейки массива

· удаление заданного элемента со сдвигом (при необходимости) хвостовой части влево для заполнения образовавшейся пустой ячейки.

Выполнение всех операций предусматривает необходимые проверки (наличие в списке хотя бы одного элемента, наличие свободных ячеек, наличие искомого элемента). Все основные операции оформляются как подпрограммы с параметрами. Главная программа создает пустой список, устанавливая счетчик числа элементов в списке в ноль, и организует диалог для реализации всех операций.

Проверить работу программы для небольшого массива (до 10 элементов).

Задание 2. Изменить предыдущую программу для создания упорядоченного списка. Для этого надо изменить логику работы подпрограммы добавления элемента. Подпрограмма должна находить соответствующее место для нового элемента, т.е. поиск должен останавливаться при обнаружении первого элемента, большего заданного. Предусмотреть обработку особых случаев:

· если в списке нет ни одного элемента, вставка производится в первую ячейку массива

· если все элементы меньше заданного, вставка производится в конец списка

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

Задание 3. Реализовать линейный список на базе массива с указателями-индексами. Список должен иметь заголовок (нулевая ячейка массива) с номером первого элемента списка. Набор операций - стандартный. Для отслеживания свободных ячеек использовать простейшую схему - отмечать свободные ячейки специальным значением индекса (-1). Главная программа при создании пустого списка должна отметить все ячейки массива (кроме нулевой) как свободные.

Задание 4. Реализовать линейный динамический список со стандартным набором операций. Пустой список содержит только элемент-заголовок, который создается главной программой в начале работы и содержит значение nil в ссылочной части. У непустого списка в ссылочной части хранится адрес первого реального элемента. Адрес заголовка сохраняется в глобальной ссылочной переменной. Все действия оформляются как подпрограммы.

Подпрограмма для добавления элемента после заданного должна работать и для пустого списка - в этом случае новый (он же первый реальный!) элемент должен добавляться сразу после заголовка.

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

Само добавление выполняется обычным образом.

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

Работа со вспомогательным списком может выполняться по стековому принципу.

В предыдущую программу надо внести следующие изменения:

· добавить глобальную ссылочную переменную для хранения адреса вершины стека

· в начале главной программы создать пустой вспомогательный список (стек)

· в основное меню добавить возможность просмотра вспомогательного списка (стека)

· изменить процедуру удаления элемента из основного списка, заменив операцию освобождения памяти операциями добавления удаленного элемента во вспомогательный список (стек)

· добавить обычную процедуру вывода вспомогательного списка (стека)

Задание 6. Изменить предыдущую программу для поддержки упорядоченных списков (см. задание 2).

Контрольные вопросы по теме

1. В чем состоит отличие списковых структур от стека и очереди?

2. Что включает в себя стандартный набор операций со списком?

3. В чем состоит простейший способ реализации списка с помощью массива?

4. Как выполняется вставка элемента при простейшей реализации списка на базе массива?

5. Как выполняется удаление элемента при простейшей реализации списка на базе массива?

6. В чем состоят преимущества и недостатки простейшего способа реализации списков с помощью массивов?

7. За счет чего можно повысить эффективность простейшей реализации списка с помощью массива?

8. В чем смысл реализации статического списка с указателями-индексами?

9. Какую структуру имеют элементы массива при статической реализации списка?

10. Какие описания необходимы для статической реализации списка?

11. Как выполняется проход по статическому списку?

12. Как выполняется поиск элемента в статическом списке?

13. Какие особые ситуации возможны при статической реализации списка?

14. Что такое пустой статический список?

15. Как выполняется добавление элемента после заданного в статическом списке?

16. Как выполняется добавление элемента перед заданным в статическом списке?

17. Как выполняется удаление элемента в статическом списке?

18. Как в простейшем случае можно отслеживать свободные ячейки массива при реализации статического списка?

19. В чем недостатки простейшего способа отслеживания свободных ячеек при реализации статического списка?

20. Как используется вспомогательный список свободных ячеек при статической реализации списка?

21. Как инициализируется вспомогательный список свободных ячеек при создании пустого статического списка?

22. Что является основой реализации динамических списков?

23. Какую структуру имеют элементы динамического списка?

24. Какие описания необходимы для реализации динамического списка?

25. Какие переменные используются для реализации операций с динамическими списками?

26. Что включает в себя создание пустого динамического списка?

27. Как выполняется проход по динамическому списку?

28. Как выполняется поиск элемента в динамическом списке?

29. Как выполняется удаление элемента в динамическом списке?

30. Как выполняется добавление элемента после заданного в динамическом списке?

31. Как выполняется добавление элемента перед заданным в динамическом списке?

32. Какие особенности возникают при обработке упорядоченных списков?

Тема 4. Усложненные списковые структуры

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

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

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

Аналогично обычным спискам, удобно ввести фиктивный заголовочный элемент, а поскольку двунаправленные списки являются симметричными, удобно сделать их замкнутыми, кольцевыми: правая ссылка последнего элемента указывает на заголовок, а левая ссылка заголовка - на последний элемент. Адрес заголовка определяется указателем pHead.

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

Двунаправленный список можно реализовать как на основе массива (причем - обеими способами), так и динамически.

В последнем случае описание структуры данных выглядит следующим образом:

type pDin2Item = ^ TDin2Item; {ссылочный тип}

TDin2Item = record {базовый тип}

inf : <тип информационной части>;

left, right : pDin2Item; {адреса соседних элементов}

end;

Если pHead есть указатель на заголовок, то пустой список создается так:

· выделяется память под заголовок, адресуемая указателем pHead

· оба ссылочных поля заголовка устанавливаются в адрес самого заголовка: pHead^.left := pHead; pHead^.right := pHead;

(при этом пустая ссылка nil нигде НЕ используется!)

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

· устанавливаем начальное значение указателя текущего элемента на последний элемент списка: pCurrent := pHead^.left;

· организуем цикл прохода до достижения заголовка

while pCurrent <> pHead do pCurrent := pCurrent^.left;

Удаление заданного элемента требует изменения большего числа ссылочных полей. Надо изменить правый указатель у левого соседа удаляемого элемента и левый указатель у правого соседа.

Если удаляемый элемент адресуется указателем pCurrent, то pCurrent^.left определяет адрес левого соседа, а pCurrent^.right - адрес правого соседа. Тогда необходимые изменения реализуются так:

pCurrent^.left^.right := pCurrent^.right;

pCurrent^.right^.left := pCurrent^.left;

Аналогично выполняется добавление нового элемента, например - после заданного указателем pCurrent. Пусть как обычно новый элемент определяется указателем pTemp. Тогда для вставки его в список надо настроить оба его ссылочных поля, изменить правое ссылочное поле у текущего элемента и левое ссылочное поле у его правого соседа.

Необходимые присваивания (порядок следования важен!):

pTemp^.right := pCurrent^.right;

pTemp^.left := pCurrent;

pCurrent^.right^.left := pTemp;

pCurrent^.right := pTemp;

Аналогично реализуется добавление нового элемента перед заданным элементом, только вместо правого соседа обрабатывается левый сосед текущего элемента.

4.2 Комбинированные структуры данных: массивы и списки указателей

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

type TRec = record{описание базового типа-записи}

x, y : integer;

name : string;

end;

TpRec = ^TRec;{описание ссылочного типа}

var ArrOfPointer : array[1..100] of TpRec;

{объявление массива указателей на записи}

Поиск заданного элемента в данном случае реализуется очень просто:

i:= 1;

While ( i <= 100 ) and ( ArrOfPointer [ i ]^.name <> `заданное значение') do i := i + 1;

Добавление нового элемента предполагает выделение памяти для этого элемента и включение в массив ссылок адреса элемента:

ArrOfPointer [ i ] := pTemp;

Массив указателей позволяет быстро и эффективно производить перестановку элементов. Например, для перестановки элементов i и j достаточно выполнить три простых присваивания:

pTemp := ArrOfPointer [ i ];

ArrOfPointer [ i ] := ArrOfPointer [ j ];

ArrOfPointer [ j ] := pTemp;

Эти присваивания переставляют лишь значения адресов в соответствующих элементах, НЕ перемещая сами базовые объекты, которые могут занимать значительные объемы памяти.

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

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

Type pInf = ^TInf; {ссылочный тип для адресации базовых объектов}

TInf = record {тип-базовая структура}

<описание полей базовой структуры данных>

end;

pItem = ^TItem;

{ссылочный тип для адресации элементов списка указателей}

TItem = record {описание структуры элемента списка указателей}

next : pItem; {поле-указатель на соседний элемент списка}

baseObject : pInf; {поле-указатель на базовый объект}

end;

Естественно, что список указателей может иметь заголовок и быть двунаправленным. В любом случае обработка полей базовых объектов выполняется с помощью соответствующих указателей (поле baseObject) в элементах списка. Например, если pCurrent определяет адрес текущего элемента списка, то выражение pCurrent^.baseObject определяет адрес соответствующего базового объекта, а выражение pCurrent^.baseObject^ - сам базовый объект.

Добавление нового элемента требует двукратного выделения памяти: сначала для самого базового объекта (переменная-указатель pTempObject типа pInf), потом - для элемента списка (переменная-указатель pTemp типа pItem). Основные операции:

· new (pTempObject);

· "заполнение полей базовой структуры pTempObject^ ";

· new (pTemp);

· pTemp^.baseObject := pTempObject;

· "добавление элемента в список";

Аналогично, удаление элемента требует двукратного освобождения памяти: сначала - для базового объекта, потом - для элемента списка. Как и в случае использования массива, очень легко производится перестановка двух элементов за счет взаимной замены адресных полей baseObject без перемещения самих базовых объектов.

Пусть pCurrent1 и pCurrent2 - указатели на элементы списка, у которых надо обменять базовые объекты. Тогда сам обмен реализуется с помощью вспомогательной переменной pTempObject типа pInf следующим образом:

pTempObject := pCurrent1^.baseObject;

pCurrent1^.baseObject := pCurrent2^.baseObject;

pCurrent2^.baseObject := pTempObject;

Отметим, что операции перестановки очень часто используются в алгоритмах сортировки массивов и списков.

4.3 Комбинированные структуры данных: массивы и списки списков

Более сложным случаем является использование массива списков или списка списков. Здесь каждый элемент массива или основного списка является началом вспомогательного списка, причем эти вспомогательные списки могут содержать разное число элементов (но, конечно, одного типа).



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

Type pSubList = ^ TSubList;

TSubList = record

<описание информационных полей>;

next : pSubList;

end;

После этого описывается либо основной массив указателей, либо структура элементов основного списка:

Type TMainArray = array [ 1 . . N ] of pSubList;

pMainList = ^ TMainList;

TMainList = record

NextMain : pMainList;

FirstSub : pSubList;

end;

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

pCurrentMain := "адрес первого элемента основного списка";

while pCurrentMain <> nil do

begin

pCurrentSub := pCurrentMain^.FirstSub;

while pCurrentSub <> nil do pCurrentSub := pCurrentSub^.next;

end;

pCurrentMain := pCurrentMain^.NextMain;

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

Иногда удобно в элементах основного списка хранить не только адрес первого элемента вспомогательного списка, но и адрес последнего элемента. Естественно, что при необходимости как основной, так и вспомогательные списки могут быть двунаправленными.

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

4.4 Практические задания

Задание 1. Реализовать линейный динамический двунаправленный список со следующим набором операций:

· просмотр списка в прямом и обратном направлениях

· поиск заданного элемента в прямом и обратном направлениях

· добавление элемента перед или после заданного

· удаление заданного элемента

Список должен иметь заголовок и быть кольцевым. Пустой список содержит только заголовок, оба ссылочных поля которого указывают на сам заголовок. Адрес заголовка задается глобальной ссылочной переменной. Все операции оформляются как подпрограммы. Добавление нового элемента после заданного должно работать и для пустого списка (см. задание 4 из предыдущей темы).

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

· полный проход по всей структуре

· поиск заданного элемента

· добавление нового элемента в массив с пустым связанным списком

· добавление нового элемента в связанный список

· удаление элемента из связанного списка

· удаление элемента из базового массива

Задание 3. Реализовать набор подпрограмм для выполнения основных операций со списком списков. Требования аналогичны предыдущему заданию.

Контрольные вопросы по теме

1. Какие преимущества и недостатки имеют двунаправленные списки?

2. Какую структуру имеют элементы двунаправленных списков?

3. Почему двунаправленные списки чаще всего делают кольцевыми?

4. Как используются ссылочные поля заголовка двунаправленного списка?

5. Какие описания необходимы для динамической реализации двунаправленных списков?

6. Какие переменные используются при реализации операций с динамическими двунаправленными списками?

7. Как создается пустой динамический двунаправленный список?

8. Как реализуется проход в прямом направлении по динамическому двунаправленному списку?

9. Как реализуется проход в обратном направлении по динамическому двунаправленному списку?

10. Как реализуется поиск в прямом направлении по динамическому двунаправленному списку?

11. Как реализуется поиск в обратном направлении по динамическому двунаправленному списку?

12. Как реализуется удаление элемента в динамическом двунаправленном списке?

13. Как реализуется добавление элемента после заданного в динамическом двунаправленном списке?

14. Как реализуется добавление элемента перед заданным в динамическом двунаправленном списке?

15. Как выполняется перестановка элементов в массиве указателей?

16. Какие описания необходимы для реализации списка указателей?

17. Как выполняется добавление элемента в список указателей?

18. Как выполняется удаление элемента из списка указателей?

19. Как выполняется перестановка элементов в списке указателей?

20. Что такое массив списков и как он описывается?

21. Что такое список списков и как он описывается?

22. Как выполняется полный проход по массиву списков?

23. Как выполняется полный проход по списку списков?

24. Как выполняется поиск элемента в массиве списков?

25. Как выполняется поиск элемента в списке списков?

26. Как выполняется удаление элемента из массива списков?

27. Как выполняется удаление элемента из списка списков?

28. Какие особенности имеет операция добавление элемента в массив или список списков?

Тема 5. Основные понятия о древовидных структурах

5.1 Основные определения

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

Дерево является типичным примером рекурсивно определённой структуры данных, поскольку оно определяется в терминах самого себя.

Рекурсивное определение дерева с базовым типом Т - это:

· либо пустое дерево (не содержащее ни одного узла)

· либо некоторая вершина типа Т с конечным числом связанных с ней отдельных деревьев с базовым типом Т, называемых поддеревьями

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

Классификацию деревьев можно провести по разным признакам.

1. По числу возможных потомков у вершин различают двоичные (бинарные) или недвоичные (сильноветвящиеся) деревья.

Двоичное дерево: каждая вершина может иметь не более двух потомков.

Недвоичное дерево: вершины могут иметь любое число потомков.



2. Если в дереве важен порядок следования потомков, то такие деревья называют упорядоченными. Для них вводится понятие левый и правый потомок (для двоичных деревьев) или более левый/правый (для недвоичных деревьев). В этом смысле два следующих простейших упорядоченных дерева с одинаковыми элементами считаются разными:

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

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

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

2. В силу естественной логической разветвленности деревьев (в этом весь их смысл!) и отсутствия единого правила выстраивания вершин в порядке друг за другом, их логическая организация не совпадает с физическим размещением вершин дерева в памяти.

Дерево как абстрактная структура данных должна включать следующий набор операций:

· добавление новой вершины

· удаление некоторой вершины

· обход всех вершин дерева

· поиск заданной вершины

5.2 Двоичные деревья

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

ДД можно реализовать двумя способами:

· на основе массива записей с использованием индексных указателей

· на базе механизма динамического распределения памяти с сохранением в каждой вершине адресов ее потомков (если они есть)

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

Type Tp = ^TNode; {объявление ссылочного типа данных}

TNode = record

Inf : <описание информационной части>;

Left, Right : Tp;

end;

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

Var pRoot : Tp;

Тогда пустое дерево просто определяется установкой переменной pRoot в нулевое значение (например - nil).

Поскольку дерево является нелинейной структурой, то НЕ существует единственной схемы обхода дерева. Классически выделяют три основных схемы:

· обход в прямом направлении

· симметричный обход

· обход в обратном направлении

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

Сами правила обхода носят рекурсивный характер и формулируются следующим образом:

1. Обход в прямом направлении:

· обработать корневую вершину текущего поддерева

· перейти к обработке левого поддерева таким же образом

· обработать правое поддерево таким же образом

2. Симметричный обход:

· рекурсивно обработать левое поддерево текущего поддерева

· обработать вершину текущего поддерева

· рекурсивно обработать правое поддерево

3. Обход в обратном направлении:

· рекурсивно обработать левое поддерево текущего поддерева

· рекурсивно обработать правое поддерево

· затем - вершину текущего поддерева

В качестве примера по шагам рассмотрим обход следующего ДД с числовыми компонентами (10 вершин):

Обход в прямом порядке:

1. Выделяем поддерево 0-1-2

2. обрабатываем его корень - вершину 0

3. переходим к левому потомку и выделяем поддерево 1-3-4

4. обрабатываем его корень - вершину 1

5. выделяем левое поддерево 3-*-* (здесь * обозначает пустую ссылку)

6. обрабатываем его корень - вершину 3

7. т.к. левого потомка нет, обрабатываем правое поддерево

8. т.к. правого поддерева нет, возвращаемся к поддереву 1-3-4

9. выделяем поддерево 4-6-7

10. обрабатываем его корень - вершину 4

11. выделяем левое поддерево 6-*-*

12. обрабатываем его корень - вершину 6

13. т.к. левого потомка нет, обрабатываем правое поддерево

14. т.к. правого потомка нет, то возвращаемся к поддереву 4-6-7

15. выделяем правое поддерево 7-*-*

16. обрабатываем его корень - вершину 7

17. т.к. левого поддерева нет, обрабатываем правое поддерево

18. т.к. правого поддерева нет, то возвращаемся к поддереву 4-6-7

19. т.к. поддерево 4-6-7 обработано, то возвращаемся к поддереву 1-3-4

20. т.к. поддерево 1-3-4 обработано, возвращаемся к поддереву 0-1-2

21. выделяем правое поддерево 2-*-5

22. обрабатываем его корень - вершину 2

23. т.к. левого потомка нет, обрабатываем правого потомка

24. выделяем поддерево 5-8-9

25. обрабатываем его корень - вершину 5

26. выделяем левое поддерево 8-*-*

27. обрабатываем его корень - вершину 8

28. т.к. левого поддерева нет, обрабатываем правое поддерево

29. т.к. правого поддерева нет, то возвращаемся к поддереву 5-8-9

30. выделяем правое поддерево 9-*-*

31. обрабатываем его корень - вершину 9

32. т.к. левого поддерева нет, обрабатываем правое поддерево

33. т.к. правого поддерева нет, то возвращаемся к поддереву 5-8-9

34. т.к. поддерево 5-8-9 обработано, то возвращаемся к поддереву 2-*-5

35. т.к. поддерево 2-*-5 обработано, то возвращаемся к поддереву 0-1-2

36. т.к. поддерево 0-1-2 полностью обработано, то обход закончен

В итоге получаем следующий порядок обхода вершин: 0-1-3-4-6-7-2-5-8-9

В более краткой записи симметричный обход дает следующие результаты:

1. поддерево 0-1-2 2. поддерево 1-3-4 3. поддерево 3-*-* 4. вершина 3 5. вершина 1	6. поддерево 4-6-7 7. поддерево 6-*-* 8. вершина 6 9. вершина 4 10. поддерево 7-*-*	10. вершина 7 11. вершина 0 12. поддерево 2-*-5 13. вершина 2 14. поддерево 5-8-9	15. поддерево 8-*-* 16. вершина 8 17. вершина 5 18. поддерево 9-*-* 19. вершина 9

Итого: 3-1-6-4-7-0-2-8-5-9

Аналогично, обход в обратном порядке дает:

1. поддерево 0-1-2 2. поддерево 1-3-4 3. вершина 3 4. поддерево 4-6-7 5. вершина 6	6. вершина 7 7. вершина 4 8. вершина 1 9. поддерево 2-*-5 10. поддерево 5-8-9	11. вершина 8 12. вершина 9 13. вершина 5 14. вершина 2 15. вершина 0

Итого: 3-6-7-4-1-8-9-5-2-0

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

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

Каждый рекурсивный вызов прежде всего должен проверить переданный ей адрес на nil. Если этот адрес равен nil, то очередное обрабатываемое поддерево является пустым и никакая его обработка не нужна, поэтому просто происходит возврат из рекурсивного вызова. В противном случае в соответствии с реализуемым правилом обхода производится либо обработка вершины, либо рекурсивный вызов для обработки левого или правого поддерева.

Рекурсивная реализация обхода в прямом направлении:

Procedure Forward ( pCurrent : Tp );

Begin

If pCurrent <> nil then

Begin

"обработка корневой вершины pCurrent^ ";

Forward (pCurrent^.Left);

Forward (pCurrent^.Right);

End;

End;

Первоначальный вызов рекурсивной подпрограммы производится в главной программе, в качестве стартовой вершины задаётся адрес корневой вершины дерева: Forward (pRoot).

Остальные две процедуры обхода с именами Symmetric и Back отличаются только порядком следования трех основных инструкций в теле условного оператора.

Для симметричного прохода:

Symmetric (pCurrent^.Left);

"обработка корневой вершины pCurrent^ ";

Symmetric (pCurrent^.Right);

Для обратного прохода:

Back (pCurrent^.Left);

Back (pCurrent^.Right);

"обработка корневой вершины pCurrent^ ";

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

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

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

Схематично нерекурсивный симметричный обход выглядит следующим образом:

pCurrent := pRoot; {начинаем с корневой вершины дерева}

Stop := false; {вспомогательная переменная}

while (not stop) do {основной цикл обхода}

begin

while pCurrent <> nil do {обработка левых потомков}

begin

"занести pCurrent в стек";

pCurrent := pCurrent^.left;

end;

if "стек пуст" then stop:= true {обход закончен}

else

begin

"извлечь из стека адрес и присвоить его pCurrent ";

"обработка узла pCurrent ";

pCurrent := pCurrent^.right;

end;

end;

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

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

Разные правила обхода часто используются для вывода структуры дерева в наглядном графическом виде. Например, для рассмотренного выше дерева с десятью вершинами применение разных правил обхода позволяет получить следующие представления дерева:

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

5.3 Идеально сбалансированные деревья

В заключение данной темы рассмотрим один частный случай ДД - так называемое идеально сбалансированное дерево (ИСД). Как будет отмечено в дальнейшем, эффективное использование деревьев на практике часто требует управления ростом дерева для устранения крайних случаев, когда дерево вырождается в линейный список и тем самым теряет всю свою привлекательность (с вычислительной точки зрения, разумеется).

В этом смысле ИСД полностью оправдывает свое название, поскольку вершины в нем распределяются наиболее равномерно и тем самым ИСД имеет минимально возможную высоту. Более точно, ДД называется идеально сбалансированным, если для каждой вершины число вершин в левом и правом ее поддеревьях отличаются не более чем на единицу. Обратим внимание, что данное условие должно выполняться для всех вершин дерева!

ИСД легко строится, если заранее известно количество вершин N в этом дереве. В этом случае ИСД можно построить с помощью следующего рекурсивного алгоритма:

· взять первую по порядку вершину в качестве корневой

· найти количество вершин в левых и правых поддеревьях:

Nl = N div 2;

Nr = N - Nl - 1;

· построить левое поддерево с Nl вершинами точно таким же образом (пока не получим Nl = 0)

· построить правое поддерево с Nr вершинами точно таким же образом (пока не получим Nr = 0)

Естественно, что реализация рекурсивного алгоритма наиболее просто выполняется в виде рекурсивной подпрограммы. При этом между этой процедурой и процедурами обхода есть одно принципиальное различие: процедуры обхода лишь используют существующую структуру дерева, не изменяя ее, и поэтому их формальные параметры являются лишь входными, тогда как процедура построения ИСД должна СОЗДАВАТЬ вершины и каждый раз возвращать в вызвавшую ее подпрограмму адрес очередной созданной вершины. Поэтому формальный параметр ссылочного типа должен быть объявлен как параметр-переменная. Кроме того, второй формальный параметр-значение принимает число вершин в текущем строящемся поддереве.

procedure AddNodes ( var pСurrent : Tp; aN : integer);

var pTemp : Tp;

Nl, Nr : integer;

begin

if aN = 0 then { вершин для размещения нет }

pCurrent := nil { формируем пустую ссылку }

else

begin

Nl := aN div 2; {сколько вершин будет слева?}

Nr := aN - Nl - 1; {сколько вершин будет справа?}

New ( pTemp ); {создаем корень поддерева}

AddNodes ( pTemp^.left, Nl); {уходим на создание левого поддерева}

AddNodes ( pTemp^.right, Nr);{уходим на создание правого поддерева}

pCurrent := pTemp; {возвращаем адрес созданного корня}

end

end;

Запуск процесса построения как обычно выполняется из главной программы с помощью вызова AddNodes(pRoot, N). В этом вызове фактический параметр N обязательно должен иметь конкретное значение, например - заданное пользователем количество вершин в строящемся ИСД. Однако, первый фактический параметр pRoot, являясь выходным, получит свое значение лишь после отработки всех рекурсивных вызовов, при возврате в главную программу.

Для понимания работы приведенной процедуры целесообразно вручную расписать шаги ее работы для простейшего дерева из трех вершин. Пусть элементами дерева являются символы A, B, C. В результате работы мы должны получить: pRoot -> A, A.left -> B, A.right -> C, B.left -> nil, B.right -> nil, C.left -> nil, C.right -> nil.

Тогда схема построения ИСД будет:

· Главная программа: вызов AddNodes (pRoot, 3)

· П/п 1: Nl = 1, Nr = 1, создание вершины A, вызов AddNodes (A.left, 1)

· П/п 1-2: сохранение в стеке значений Nl = 1, Nr = 1, адреса A

· П/п 1-2: Nl = 0, Nr = 0, создание вершины B, вызов

AddNodes (B.left, 0)

· П/п 1-2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса B

· П/п 1-2-3: aN = 0, pCurrent = nil, возврат к 1-2

· П/п 1-2: восстановление Nl = 0, Nr = 0, вых. параметр B.left = nil

· П/п 1-2: вызов AddNodes (B.right, 0)

· П/п 1-2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса B

· П/п 1-2-3: aN = 0, pCurrent = nil, возврат к 1-2

· П/п 1-2: восстановление Nl = 0, Nr = 0, вых. параметр B.right = nil

· П/п 1-2: pCurrent = адрес B, возврат к 1

· П/п 1: восстановление Nl = 1, Nr = 1, вых. параметр A.left=адрес B

· П/п 1: вызов AddNodes (A.right, 1)

· П/п 1-2: сохранение в стеке значений Nl = 1, Nr = 1, адреса A

· П/п 1-2: Nl = 0, Nr = 0, создание вершины C, вызов

AddNodes (C.left, 0)

· П/п 1-2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса C

· П/п 1-2-3: aN = 0, pCurrent = nil, возврат к 1-2

· П/п 1-2: восстановление Nl = 0, Nr = 0, вых. параметр C.left = nil

· П/п 1-2: вызов AddNodes (C.right, 0)

· П/п 1-2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса C

· П/п 1-2-3: aN = 0, pCurrent = nil, возврат к 1-2

· П/п 1-2: восстановление Nl = 0, Nr = 0, вых. параметр C.right = nil

· П/п 1-2: pCurrent = адрес C, возврат к 1

· П/п 1: восстановление Nl = 1, Nr = 1, вых. параметр A.right=адрес C

· П/п 1: pCurrent = адрес A, возврат в главную программу

· Главная программа: установка выходного параметра pRoot = адрес A

5.4 Практические здания

Задание 1. Построение и обход идеально сбалансированных двоичных деревьев. Реализовать программу, выполняющую следующий набор операций:

построение идеально сбалансированного двоичного дерева с заданным числом вершин

построчный вывод дерева на основе процедуры обхода в прямом порядке

построчный вывод дерева на основе процедуры обхода в симметричном порядке

построчный вывод дерева на основе процедуры обхода в обратно-симметричном порядке

Рекомендации:

для простоты построения дерева можно информационную часть формировать как случайное целое число в интервале от 0 до 99

глобальные переменные: указатель на корень дерева и число вершин

алгоритмы построения ИСД и его обхода оформляются как подпрограммы, вызываемые из главной программы

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

Все процедуры обхода имеют похожую структуру. Например, процедура обхода в прямом направлении должна:

Ш проверить пустоту очередного поддерева

Ш вывести в цикле необходимое число пробелов в соответствии с уровнем вершины

Ш вывести информационную часть текущей вершины

Ш вызвать рекурсивно саму себя для обработки своего левого поддерева с увеличением уровня на 1

Ш вызвать рекурсивно саму себя для обработки своего правого поддерева с увеличением уровня на 1

Сравнение рассмотренных правил вывода двоичного дерева приводится в следующей таблице

Главная программа реализует следующий набор действий:

· запрос числа вершин в дереве

· запуск рекурсивной подпрограммы построения идеально сбалансированного дерева со следующими фактическими параметрами: указатель на корень дерева (при построении дерева этот параметр является выходным!) и заданное число вершин

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

Задание 2. Добавить в программу нерекурсивный вариант процедуры обхода дерева в симметричном порядке.

Замена рекурсии циклом основана на использовании вспомогательного стека для хранения последовательности пройденных вершин от корня до текущей вершины и уровня этих вершин в дереве (напомним, что уровень используется только для задания правильного числа отступов при построчном выводе дерева). Исходя из этого, создаваемая подпрограмма должна объявить необходимые локальные типы данных для динамической реализации вспомогательного стека. Каждый элемент стека должен хранить: указатель на пройденную вершину дерева, уровень вершины, указатель на следующий элемент стека. Для реализации стека, как обычно, требуются две ссылочные переменные: указатель на вершину стека и вспомогательный указатель, используемый при добавлении или удалении элементов в стек.

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

циклическое сохранение очередной вершины в стеке (пока не будет достигнута пустая вершина) следующим образом:

Ш увеличение уровня вершины на 1

Ш создание нового элемента стека, заполнение всех его полей и добавление его в стек

Ш переход к левому потомку текущей вершины

проверка пустоты стека: если стек пуст, то основной цикл следует завершить, а иначе - перейти к обработке вершины

Ш извлечь из стека адрес текущей обрабатываемой вершины и ее уровень

Ш вывести вершину с необходимым числом пробелов

Ш удалить элемент из стека с освобождением памяти

Ш перейти к правому потомку текущей вершины

Для проверки правильности работы подпрограммы сравнить ее результаты с рекурсивным аналогом.

Задание 3. Обработка произвольных двоичных деревьев

Реализовать программу, выполняющую следующий набор операций с двоичными деревьями:

поиск вершины с заданным значением информационной части

добавление левого или правого потомка для заданной вершины

построчный вывод дерева с помощью основных правил обхода

уничтожение всего дерева

Рекомендации:

объявить необходимые глобальные переменные: указатель на корень дерева, указатель на родительскую вершину, признак успешности поиска

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

Ш проверить необходимость продолжения поиска

Ш проверить текущую ссылочную переменную на nil

Ш сравнить информационную часть текущей вершины с заданным значением

Ш если эти величины совпадают, то установить признак окончания поиска и установить адрес родительской переменной в адрес текущей вершины

Ш в противном случае продолжить поиск сначала в левом поддереве текущей вершины, вызвав рекурсивно саму себя с адресом левого потомка, а потом - в правом поддереве, вызвав саму себя с адресом правого потомка

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

Объявить и реализовать подпрограмму добавления новой вершины в дерево как потомка заданной вершины.

Подпрограмма должна:

Ш проверить пустоту дерева: если указатель корня имеет значение nil, то надо создать корень дерева

o выделить память

o запросить значение информационной части корня

o сформировать пустые ссылочные поля на потомков

Ш если дерево не пустое, то организовать поиск родительской вершины:

o запросить искомое значение информационной части родительской вершины

o установить признак поиска и вызвать подпрограмму поиска

o если поиск удачен, то проверить число потомков у найденной родительской вершины

o если вершина-родитель имеет двух потомков, то добавление невозможно

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

o если родительская вершина не имеет ни одного потомка. то запросить тип добавляемой вершины (левый или правый потомок) и выполнить само добавление

Объявить и реализовать рекурсивную подпрограмму для построчного вывода дерева в обратно-симметричном порядке. Эту подпрограмму без каких-либо изменений можно взять из предыдущей работы.

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

Ш вызвать рекурсивно саму себя с адресом левого поддерева

Ш вызвать рекурсивно саму себя с адресом правого поддерева

Ш вывести для контроля сообщение об удаляемой вершине

Ш освободить память с помощью процедуры Dispose и текущего указателя

Главная программа должна:

· создать пустое дерево

· организовать цикл для добавления вершины с вызовом соответствующей подпрограммы и последующим построчным выводом дерева

· предоставить возможность в любой момент вызвать подпрограмму удаления дерева с фактическим параметром, равным адресу корня дерева, что запускает механизм рекурсивного удаления всех вершин, включая и корневую; поскольку после удаления корневой вершины соответствующий указатель становится неопределенным, можно инициировать его пустым значением, что позволит повторно создать дерево с новой корневой вершиной

Контрольные вопросы по теме

1. В чем состоит основное отличие древовидных структур от списковых?

2. Как рекурсивно определяется дерево?

3. Какие типы вершин существуют в деревьях?

4. Какие можно выделить типы деревьев?

5. Какие деревья называются двоичными?

6. Какие деревья называются упорядоченными?

7. Какие основные понятия связываются с деревьями?

8. Какие основные операции характерны при использовании деревьев?

9. Какую структуру имеют вершины двоичного дерева?

10. Почему для деревьев существует несколько правил обхода вершин?

11. Какие правила обхода вершин дерева являются основными?