14750

Программное обеспечение вычислительной техники и автоматизированных систем. Структуры и алгоритмы обработки данных

Книга

Информатика, кибернетика и программирование

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

Русский

2015-01-15

1.73 MB

140 чел.

PAGE  167

Рекомендовано к печати научно-

      методическим советом ТИСБИ

Автор: А.Н. Козин

Рецензент: профессор В.С. Моисеев

Козин А.Н., 2003

Татарский институт содействия бизнесу, 2003


Оглавление

Введение

Раздел 1. Основные структуры данных

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

1.1. Классификация структур данных

1.2. Переменные-указатели и динамическое распределение памяти

1.3. Дополнительные вопросы использования переменных-указателей

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

2. Структуры данных “стек” и “очередь”

2.1. Что такое стек и очередь?

2.2. Статическая реализация стека

2.3. Динамическая реализация стека

2.4. Статическая реализация очереди

2.5. Динамическая реализация очереди

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

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

3. Основы реализации списковых структур

3.1. Структуры данных типа “линейный список”

3.2. Первый способ статической реализации списка

3.3. Второй способ статической реализации списка

3.4. Управление памятью при статической реализации списка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Реализация поисковых деревьев

6.1. Двоичные деревья поиска

6.2. Добавление вершины в дерево поиска

6.3. Удаление вершины из дерева поиска

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

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

7. Дополнительные вопросы обработки деревьев. Графы.

7.1. Проблемы использования деревьев поиска

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

7.3. Деревья общего вида (не двоичные)

7.4. Представление графов

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

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

Раздел 2. Алгоритмы сортировки и поиска

1. Классификация методов. Простейшие методы сортировки

1.1. Задача оценки и выбора алгоритмов

1.2. Классификация задач сортировки и поиска

1.3. Простейшие методы сортировки: метод обмена

1.4. Простейшие методы сортировки: метод вставок

1.5. Простейшие методы сортировки: метод выбора

1.6. Практическое задание

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

2. Улучшенные методы сортировки массивов

2.1. Метод Шелла

2.2. Метод быстрой сортировки

2.3. Пирамидальная сортировка

2.4. Практическое задание

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

3. Специальные методы сортировки

3.1. Простейшая карманная сортировка

3.2. Карманная сортировка для случая повторяющихся ключей

3.3. Поразрядная сортировка

3.4. Практическое задание

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

4. Поиск с использованием хеш-функций

4.1. Основные понятия

4.2. Разрешение конфликтов: открытое хеширование

4.3. Разрешение конфликтов: внутреннее хеширование

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

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

5. Внешний поиск и внешняя сортировка

5.1. Особенности обработки больших наборов данных

5.2. Организация внешнего поиска с помощью Б-деревьев

5.3. Б-дерево как структура данных

5.4. Поиск элемента в Б-дереве

5.5. Добавление вершины в Б-дерево

5.6. Удаление вершины из Б-дерева

5.7. Внешняя сортировка

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

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

Основные термины и понятия

Литература

Введение

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

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

Материал учебного пособия соответствует содержанию Государственного образовательного стандарта по одноименному учебному курсу для студентов специальности «Программное обеспечение вычислительной техники и автоматизированных систем» и предполагает знание студентами основ классического структурного программирования. Отдельные темы пособия могут быть полезны и для студентов других специальностей, связанных с информационными и компьютерными технологиями.


Раздел 1. Основные структуры данных

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

  1.  Классификация структур данных

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

  •  способом объединения отдельных компонент в единую структуру
  •  способами обработки как отдельных компонент структуры так и всей структуры в целом.

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

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

Большинство дополнительных структур данных можно реализовать двумя способами:

  •  статически на основе массива
  •  динамически с помощью специальных переменных-указателей

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

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

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

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

1.2. Переменные-указатели и динамическое распределение памяти.

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

Во многих задачах подобная статичность является очень неудобной, поэтому многие языки программирования, в частности С/С++ и Паскаль, реализуют другой способ создания переменных – динамический. Он позволяет создавать переменные в процессе выполнения программы в ответ на вызов специальных стандартных функций. При этом динамически выделяются необходимые области памяти, в которые заносятся значения соответствующих переменных. Когда необходимость в использовании таких переменных исчезает, соответствующие области памяти можно освободить для других целей.

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

значение указателя: адрес области памяти 00 00 4А F0

Адресуемые данные (массивы, записи), располагающиеся в памяти начиная с адреса 00 00 4A F0

Для описания переменных-указателей необходимо:

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

var   указатель : ^ базовый тип;

Например, указатели на простейшие базовые типы вводятся следующим образом:

pInt : ^integer;   {указатель на отдельное целое число}

pChar : ^char;   {указатель на отдельный символ}

pString1, pStr2 : ^string;   {два указателя на символьные строки}

Ссылочные типы можно предварительно ввести в разделе описания типов, а  потом объявить соответствующую переменную. Например:

type   TpString = ^string;   {ссылочный тип для адресации текстовых строк}

var   pStr1, pStr2 : TpString;   {переменные-указатели на строки}

Можно ввести указатели на структурные типы (массивы, записи), используя для этого предварительно объявленные типы:

type  TMyArray = array [1..100] of  integer;

var   pMyArray1 : ^TMyArray;   {указатель на начало базового массива}

Необходимо понимать, что объявление переменной-указателя НЕ приводит к выделению памяти для самих адресуемых данных: память выделяется ТОЛЬКО для указателя (например – 4 байта). Поэтому для правильного использования механизма динамического распределения памяти НЕ следует объявлять переменные базового типа (точнее, их объявлять можно, но к динамическому распределению памяти это никакого отношения не имеет).

Например:

type   TMyRecord = record

                                       Field1 : SomeType1;

                                       Field2 : SomeType2;

                                  end;    

var   MyRec : TMyRecord;      {обычная переменная-запись со статическим выделением памяти}

       pMyRec : ^TMyRecord;   {переменная-указатель на будущую структуру-запись с выделением памяти только для указателя, но не для самой записи!}

Динамическое создание переменных базового типа выполняется вызовом стандартной подпрограммы  New  с параметром-указателем, связанным с данным базовым типом:

New ( pMyRec );

New (pStr1 );

Данный вызов выполняет два следующих действия:

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

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

После выделения области памяти в неё можно записать необходимое значение, используя ссылочную переменную и символ  ^  после ее имени:

pStr1^ : =  ‘Привет’;

pInt^  : =  1;

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

pInt^  : =  pInt^ + 1;

pChar^  : =  ‘A’;

ReadLn ( pStr1^);

pMyArray^[ i ]  : =  10;

pMyRec^.Field1 : = соответствующее значение;

Обращаем внимание на последние два присваивания, конструкцию которых можно прокомментировать следующим образом:

  •  pMyArray  и  pMyRec – это имена ссылочных переменных
  •  pMyArray^  и  pMyRec^  - это условные обозначения объектов базового типа, т.е. массива и записи соответственно
  •  pMyArray^[ i ]  и  pMyRec^.Field1 – это обозначения отдельных элементов базового типа, т.е. i-го элемента массива и поля записи с именем Field1

C переменными ссылочного типа допустимы две операции:

1. Присваивание значения одной ссылочной переменной другой ссылочной переменной того же базового типа:

 pInt1 : =  pInt2;

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

2. Сравнение двух ссылочных переменных на равенство или неравенство:

if   pInt2  =  pInt1  then …

В практических задачах довольно часто приходится использовать “пустые указатели”, которые никуда не указывают. Для задания такого пустого указателя используется специальное служебное слово  nil. Например:

pInt1 : =  nil;      {указатель ничего не адресует}

if  pStr1  =  nil  then . . .{проверка указателя на пустоту}

Для освобождения динамически распределенной памяти используется вызов  Dispose  с параметром-указателем:

Dispose ( pStr1 );

После этого вызова соответствующая переменная-указатель становится неопределенной (НЕ путать с ПУСТЫМ указателем!) и ее нельзя использовать до тех пор, пока она снова не будет инициализирована с помощью вызова  New  или инструкции присваивания. Использование вызова  Dispose  может приводить к весьма неприятной ситуации, связанной с появлением так называемых “висячих” указателей: если два указателями адресовали одну и ту же область памяти (а это встречается очень часто), то вызов  Dispose  с одной из них оставляет в другой переменной адрес уже освобожденной области памяти и повторное использование этой переменной приведет либо к неверному результату, либо к аварийному завершению программы.

1.3. Дополнительные вопросы использования переменных-указателей

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

var  x : real; {обычная переменная вещественного типа}

pReal : ^real; {указатель на вещественный тип}

begin

x := 1.5;                         {обычная переменная  x  получает значение 1.5}

pReal  :=  @x;               {указатель получает адрес размещения числа  1.5}

Write(pReal^ : 6 : 2);    {вывод числа 1.5 с помощью указателя  pReal}

end;

Принципиальное отличие данного способа использования указателя от ранее рассмотренного состоит в том, что здесь НЕ используется механизм динамического распределения памяти, т.е. НЕ используются стандартные функции  New  и  Dispose: переменная  x  является обычной статической переменной, размещаемой в статической области памяти, просто доступ к ней по каким-то причинам организуется не напрямую, а с помощью ссылочной переменной.

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

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

                         x, y : integer;

                        name : string;

                      end;

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

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

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

begin

  for  i := 1  to  100  do  ArrOfPointer [ i ]^.x  : =  Random(100);

{цикл установки значений в поле  x}

end.

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

var   pAll : pointer;

Распределение и освобождение памяти для нетипизированных указателей производится с помощью специальных стандартных функций  GetMem  и  FreeMem, которые имеют по два параметра – имя нетипизированного указателя и байтовый размер выделяемой области памяти. Для задания этого размера удобно использовать стандартную функцию  SizeOf, которая принимает имя типа данных, а возвращает необходимый размер области памяти. Например:

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

                  x, y : integer;

                  name : string;

              end;

var   p1, p2 : pointer;           {объявление двух нетипизированных указателей}

begin

  GetMem ( p1,  SizeOf ( TRec ) );     {распределение памяти под объект-запись}

  p1^.name := ‘Text’;

  p2 := p1; {оба указателя адресуют одну и ту же область}

  FreeMem ( p1,  SizeOf ( TRec ) );     

{освобождение памяти и деактуализация указателя  p1}

end.

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

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

  1.  Что включает в себя понятие структуры данных?
  2.  Назовите основные линейные структуры данных и их разновидности
  3.  Назовите основные нелинейные структуры данных и их разновидности
  4.  В чем состоят отличия статического и динамического распределения памяти?
  5.  Что такое переменные ссылочного типа (указатели)?
  6.  Что включает описание переменных-указателей?
  7.  Приведите примеры описания простых переменных-указателей
  8.  Как вводится переменная-указатель на текстовые строки (2 способа)?
  9.  Как вводится переменная-указатель на массив?
  10.   Как вводится переменная-указатель на структуру-запись?
  11.   Какая память выделяется транслятором при объявлении переменных-указателей?
  12.   Какие стандартные подпрограммы используются для динамического выделения и освобождения памяти?
  13.   Что происходит при выполнении подпрограммы  New?
  14.   Как выполняется установка необходимого значения в динамически выделенную область памяти?
  15.   Если  р – переменная-указатель, то что определяет выражение  p^ ?
  16.   Если  р – переменная-указатель на массив, то как можно определить i-ый элемент массива?
  17.   Если  p – переменная-указатель на запись, то как можно определить  некоторое поле этой записи?
  18.   Какие операции разрешены с переменными-указателями?
  19.   Что такое “пустой указатель” и как он задается?
  20.   Что происходит при вызове стандартной подпрограммы  Dispose?
  21.   Какие неприятности могут возникать при использовании подпрограммы  Dispose?
  22.   Как можно переменной-указателю непосредственно присвоить адрес базового объекта?
  23.   Как задается оператор взятия адреса и для чего он используется?
  24.   Как задается массив указателей?
  25.   Если  Pointers  есть массив указателей, то что определяет выражение  Pointers [ j ]^ ?
  26.   Что такое нетипизированные указатели и как они описываются?
  27.   Какие стандартные функции используются для распределения и освобождения памяти с нетипизированными указателями?
  28.   Приведите пример записи функции для распределения памяти с нетипизированным указателем.
  29.   Приведите пример записи функции для освобождения памяти с нетипизированным указателем.

Тема 2. Структуры данных “стек” и “очередь”

2.1. Что такое стек и очередь?

Стек – это линейная структура данных, в которую элементы добавляются и удаляются только с одного конца, называемого вершиной стека. Стек работает по принципу “элемент, помещенный в стек последним, извлечен будет первым”. Иногда этот принцип обозначается сокращением LIFO (Last InFirst Out, т.е. последним зашел – первым вышел).

Очередь – это линейная структура данных, в которую элементы добавляются с одного конца (конец очереди), а удаляются  - с другого (начало очереди). Очередь работает по принципу “элемент, помещенный в очередь первым, извлечен будет тоже первым”. Иногда этот принцип обозначается сокращением FIFO (First InFirst Out, т.е. первым зашел – первым вышел). Элементами стеков и очередей могут быть любые однотипные данные. В простейшем случае – целые числа, чаще всего – записи заранее определенной структуры. Стеки и очереди очень широко используются в системных программах, в частности – в операционных системах и компиляторах. Программная реализация стеков и очередей возможна двумя способами:

  •  статически с помощью массива
  •  динамически с помощью механизма указателей

2.2. Статическая реализация стека

Пусть в стеке требуется сохранять целые числа, причем заранее известно их максимальное количество. Тогда для реализации стека надо объявить массив и одну переменную – указатель вершины стека (SPStack Pointer).Будем считать, что стек-массив заполняется (растет) от первых элементов массива к последним. Тогда указатель SP может определять либо последнюю занятую ячейку массива, либо первую свободную ячейку. Выберем второй способ. Тогда для пустого стека переменная SP = 1 (если индексация элементов массива начинается с 1), и при каждом добавлении нового элемента переменная SP увеличивается на 1, а при удалении – уменьшается на 1. Последовательность операций для массива из пяти элементов показана на следующей схеме

1. Пустой стек: sp=1  

 

2. Добавлено первое число 15,  sp=2

3. Добавлено второе число 33, sp=3

4. Добавлено третье число 07, sp=4

5. Удалено с вершины число 07, sp=3

6. Удалено с вершины число 33, sp=2

Со стеком связываются две основные операции: добавление (вталкивание, PUSH) элемента в стек и удаление (выталкивание, POP) элемента из стека.

Добавление включает в себя:

  •  проверку возможности добавления (стек-массив заполнен полностью?)
  •  размещение нового элемента в ячейке, определяемой значением переменной SP
  •  увеличение SP на 1

Удаление включает в себя:

  •  проверку возможности удаления (стек пустой?)
  •  уменьшение SP на 1
  •  извлечение элемента из ячейки, определяемой значением переменной SP

2.3. Динамическая реализация стека

В отличие от статической реализации на основе массива, при использовании механизма динамического выделения памяти в стек можно занести любое число элементов. Ограничением является только размер области памяти, выделяемой для размещения динамически создаваемых переменных. При динамической реализации элементы стека могут располагаться в ЛЮБЫХ свободных областях памяти, но при этом необходимо как-то связывать соседние элементы друг с другом. Это приводит к необходимости добавления в каждый элемент стека нового связующего поля для хранения адреса соседнего элемента. Тем самым, каждый элемент стека должен представлять собой запись, состоящую из двух компонент:

  •  информационная составляющая с полезной смысловой информацией
  •  связующая составляющая для хранения адреса соседнего элемента

Учитывая специфику стека, указатели должны следовать от последнего элемента (вершина стека) к первому (дно стека).

В этом случае физическое размещение элементов в памяти НЕ обязано всегда соответствовать логическому порядку следования элементов. Логический порядок элементов определяется адресными частями при проходе от последнего элемента к первому. Структура оперативной памяти в этом случае может выглядеть следующим образом:

элем. N-3

элем. N-1

элем. N

элем. N-2

элем. N-4

адрес N-4

адрес N-2

адрес N-1

адрес N-3

адрес N-5

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

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

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

Что должны адресовать эти переменные? Элементы стека, т.е. записи определенного типа. Следовательно, прежде всего надо ввести ссылочный тип, связанный с базовым типом-записью, а затем – описать базовый тип как запись с необходимыми полями, одно из которых должно быть ссылочного типа:

type   pStackItem = ^ TStackItem;           

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

         TStackItem = record          

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

                                    inf :   integer;        {информационная часть}

                           next : pStackItem;    

   {ссылочная часть: поле для адреса следующего элемента}  

                               end;

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

var  sp : pStackItem;

Тогда  конструкция  sp^.inf  будет представлять саму информационную часть, а конструкция   sp^.next  -  адрес предыдущего элемента, который был помещен в стек непосредственно перед текущим.

Кроме того, для прохода по стеку от вершинного элемента к самому первому элементу необходима вспомогательная ссылочная переменная (например – с именем  pCurrent). Она на каждом шаге прохода по стеку должна определять адрес текущего элемента. В самом начале прохода надо установить значение  pCurrent = sp, а затем циклически менять его на значение  pCurrent^.next  до тех пор, пока не будет достигнут первый элемент стека. Очевидно, что для прохода надо использовать цикл с неизвестным числом повторений, а признаком его завершения должно быть получение в поле  pCurrent^.next  пустой ссылки  nil. Отсюда следует, что ссылочное поле самого первого элемента стека должно содержать значение  nil.

Тогда схематично проход по стеку можно представить следующим образом:

pCurrent  : =  sp; {начинаем проход с вершины стека}

While pCurrent <> nil  do

      begin

     Writeln ( pCurrent ^. Inf );         {вывод  инф. части текущего элемента}

           pCurrent : =  pCurrent^.next;     {переход к следующему элементу}

 end;

Как выполняется добавление нового элемента в вершину стека?

Необходимые шаги:

  •  выделить память для размещения нового элемента с помощью вспомогательной ссылочной переменной  pTemp  и стандартной программы new(pTemp); адрес этой области памяти сохраняется как значение переменной  pTemp
  •  заполнить информационную часть нового элемента (например:  ReadLn(pTemp^.inf))
  •  установить адресную часть нового элемента таким образом, чтобы она определяла адрес бывшего вершинного элемента:  pTemp^.next  : = sp;
  •  изменить адрес вершины стека так, чтобы он определял в качестве вершины новый элемент:  sp  : =  pTemp;

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

 

Как выполняется удаление элемента с вершины стека?

Необходимые шаги:

  •  с помощью вспомогательной переменной  рTemp  адресуем удаляемый элемент:

рTemp:= sp;

  •  изменяем значение переменной  sp  на адрес новой вершины стека:

sp  : =  sp^.next;

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

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

2.4. Статическая реализация очереди

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

1. Пустая очередь: First = Last =1

 

2. Добавлено первое число 15,  First = 1, Last = 2

3. Добавлено второе число 33, First = 1, Last = 3

4. Добавлено третье число 07, First = 1, Last = 4

5. Удалено число 15, First = 2, Last = 4

6. Удалено число 33, First = 3 , Last = 4

7. Добавлено число 44, First = 3 , Last = 5

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

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

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

8. Добавлено число 11, First = 3 , Last = 6 (= 1)

  1.   Новое число 22 добавляется в первую ячейку:

First = 3 , Last = 2

10. Добавлено число 99, First = 3 , Last = 3

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

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

Само добавление элемента в очередь выполняется следующим образом:

  •  проверить возможность добавления (в массиве есть свободные ячейки?)
  •  добавить элемент в массив по индексу Last
  •  изменить указатель Last на 1
  •  если Last выходит за пределы массива, то установить Last в 1
  •  увеличить счетчик числа элементов в очереди

Удаление элемента из очереди:

  •  проверить возможность удаления (в очереди есть элементы?)
  •  извлечь элемент из массива по индексу First и выполнить с ним необходимые действия
  •  увеличить указатель First на 1
  •  если First выходит за пределы массива, то установить First в 1
  •  уменьшить счетчик числа элементов в очереди

2.5. Динамическая реализация очереди

Аналогично стеку, каждый элемент очереди должен иметь ссылку на следующий за ним элемент, поэтому элемент очереди объявляется как запись с двумя полями – информационное поле и связующее поле. Но для реализации операций с очередью необходимы уже две переменные: указатель pFirst на начало очереди и  указатель pLast на конец очереди.

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

 . . . . . . . .

Основные операции с динамической очередью:

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

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

В этом случае создание пустой очереди включает в себя:

  •  выделение памяти для заголовка с помощью указателя  pFirst
  •  занесение в ссылочную часть заголовка пустого указателя  nil
  •  установка указателя конца очереди  pLast = pFirst

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

…..

Необходимые описания типов и переменных:

type   pQueueItem = ^ TQueueItem;       

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

  TQueueItem = record                    {базовый тип: структура элемента очереди}

                              inf :   integer;        {информационная часть}

                     next : pQueueItem;          

{ссылочная часть: адрес следующего элемента}  

                           end;

var   pFirst, pLast : pQueueItem;

Тогда условие пустой очереди можно записать следующим образом:

  pFirst^.next = nil

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

  •  ввести вспомогательную ссылочную переменную  pTemp
  •  установить  pTemp  в адрес первого реального элемента: pTemp := pFirst^.next
  •  организовать цикл по условию достижения конца очереди
  •  в цикле обработать очередной элемент с помощью указателя  pTemp  и изменить этот указатель:  pTemp := pTemp^.next

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

  •  выделить память для нового элемента с помощью стандартной функции New и вспомогательной ссылочной переменной pTemp:
  •  заполнить поля нового элемента, в частности в связующую часть установить значение nil:  pTemp^.next := nil
  •  изменить связующую часть бывшего последнего элемента таким образом, чтобы она адресовала новый добавленный элемент:  pLast^.next := pTemp;
  •  изменить значение указателя  pLast так, чтобы он указывал новый последний элемент:  pLast := pTemp;

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

  •  адресуем удаляемый элемент с помощью вспомогательной переменной  pTemp :    pTemp := pFirst^.next;
  •  изменить связующую часть заголовка так, чтобы она указывала на второй элемент очереди, который теперь должен стать первым:  pFirst^.next := pTemp^.next
  •  если после удаления в списке не остаётся реальных элементов, то необходимо изменить указатель pLast:   pLast := pFirst
  •  обработать удаленный элемент, например - освободить занимаемую им память с помощью стандартной подпрограммы  Dispose (pTemp)  или включить его во вспомогательную очередь удаленных элементов

Сравнение двух способов реализации очереди полностью аналогично стеку. Интересной разновидностью очереди являются приоритетные очереди, в которых элементы выстраиваются не только в порядке поступления, но и в соответствии с их приоритетами: сначала идут более приоритетные элементы, потом – все менее приоритетные. Одноприоритетные элементы располагаются в порядке поступления. Это требует изменения процедуры добавления элемента в очередь: надо прежде всего найти место в очереди, куда должен вставиться новый элемент в соответствии с его приоритетом, а потом уже выполнить саму вставку. Фактически, приоритетную очередь можно рассматривать как разновидность упорядоченного линейного списка. Реализация линейных списков подробно рассматривается в следующей теме.

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

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

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

Требования:

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

Задание 2. Реализовать тот же набор действий на основе динамического распределения памяти.

Требования аналогичны заданию 1, за исключением того, что проверку заполненности стека проводить не надо. Пустой стек задается установкой  sp := nil.

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

Задание 4 (дополнительно). Добавить в предыдущую программу следующие возможности:

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

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

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

Требования к программе:

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

Задание 6. Реализовать тот же набор действий на основе динамического распределения памяти.

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

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

Пусть за единицу времени (например – 1 минуту) в очередь либо добавляется, либо удаляется случайное число элементов в количестве от 1 до 3-х. Одновременно добавление и удаление НЕ происходит. Для наглядности элементами пусть являются большие латинские буквы (коды ASCII от 65 до 90), выбираемые случайным образом. Тип операции с очередью (добавление или удаление) также задается случайно. Это приводит к тому, что очередь случайно растет и убывает. Программа должна наглядно показывать состояние очереди в каждый момент времени.

Рекомендации по разработке программы.

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

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

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

  •  после создания пустой очереди, содержащей только заголовок, инициировать датчик псевдослучайных чисел (процедура Randomize) и вывести соответствующее сообщение
  •  организовать цикл с выходом при вводе пользователем какого-либо специального символа (например – буквы q)
  •  сгенерировать случайное число в диапазоне от 1 до 100 и проверить его четность с помощью операции взятия остатка от деления этого числа на 2
  •  если число четное – реализовать операцию добавления, если нечетное – операцию удаления
  •  в том и другом случае выполнить:
    •  генерацию случайного числа добавляемых или удаляемых символов в диапазоне от 1 до 3-х
    •  вывод сообщения о выполняемом действии и количестве добавляемых/удаляемых элементов
    •  выполнение цикла для добавления или удаления заданного числа элементов с вызовом соответствующих процедур работы с очередью, причем при добавлении новый символ должен генерироваться случайно с помощью его кода (диапазон 65 – 90) с последующим преобразованием кода в сам символ с помощью стандартной функции CHR
  •  вывести текущее состояние очереди
  •  запросить у пользователя символ для окончания цикла (при выполнении программы для продолжения работы цикла можно просто дважды нажать клавишу ввода)

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

  •  случайное число добавляемых и удаляемых элементов одинаково (например – от 1 до 3-х)
  •  число добавляемых элементов чуть больше (в среднем!) числа удаляемых (например, добавляется случайное количество элементов в диапазоне от 1 до 4-х, а удаляется – от 1 до 3-х)
  •  число удаляемых элементов чуть больше числа добавляемых

Для каждого случая выполнить программу при достаточно большом числе добавлений/удалений (30-40) и сделать вывод о поведении очереди.

.

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

  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.  Сравните статическую и динамическую реализации очереди.

Тема 3. Основы реализации списковых структур

3.1. Структуры данных типа “линейный список”

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

Стандартный набор операций со списком включает:

  •  добавление нового элемента после заданного или перед заданным элементом с проверкой возможности добавления элемента
  •  удаление заданного элемента
  •  проход по списку от первого элемента к последнему с выполнением заданных действий
  •  поиск в списке заданного элемента

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

3.2. Первый способ статической реализации списка.

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

Элемент 1

Элемент 2

Элемент 3

. . . . . . .

Элемент N

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

Как выполнить вставку нового элемента внутри списка, например – в ячейку с номером i < N ? Для освобождения ячейки  i  все элементы списка начиная с номера  i  и до  N надо сдвинуть вправо на одну ячейку (конечно, если в массиве есть еще хотя бы одна свободная ячейка). Копирование надо начинать с последней ячейки, т.е. N – на место N+1, N-1 – на место N, и.т.д. i – на место  i+1. В освободившуюся ячейку  i  записывается новый элемент.

Аналогично (с точностью до наоборот) выполняется удаление любого внутреннего элемента: освобождается ячейка  i  и все последующие элементы сдвигаются влево на одну ячейку, т.е. i+1 – на место i, i+2 – на место  i+1, и т.д.,  элемент N – в ячейку  N-1.

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

3.3. Второй способ статической реализации списка.

Второй способ реализации списка на основе массива использует принцип указателей (но БЕЗ динамического распределения памяти). В этом случае каждый элемент списка (кроме последнего) должен содержать номер ячейки массива, в которой находится следующий за ним элемент. Это позволяет РАЗЛИЧАТЬ физический и логический порядок следования элементов в списке. Удобно (но НЕ обязательно) в начале массива ввести фиктивный элемент-заголовок, который всегда занимает нулевую ячейку массива, никогда не удаляется и указывает индекс первого реального элемента списка. В этом случае последний элемент списка (где бы он в массиве не располагался) должен в связующей части иметь некоторое специальное значение-признак, например – индекс 0.

Схема физического размещения элементов списка в массиве:

Номер ячейки

0

1

2

3

4

5

Информац. часть

заголовок

Элем. 3

Элем. 1

Элем. 2

Элем. 4

Следующий эл-нт

2

5

4

1

0

Соответствующая схема логического следования элементов списка:

Тогда необходимые объявления могут быть следующими:

Const  N = 100;

Type  TListItem = record

                                  Inf  :  <описание>;

                                  Next  :  integer;

                              end;

Var   StatList  :  array [0 . . N]  of   TListItem;

Рассмотрим реализацию основных списковых операций.

Условие пустоты списка:  StatList [ 0 ].Next = 0;

Проход по списку:

  •  ввести вспомогательную переменную Current для отслеживания текущего элемента списка и установить Current := StatList [ 0 ].Next;
  •  организовать цикл по условию  Current = 0, внутри которого обработать текущий элемент StatList [ Current ].Inf  и изменить указатель  Current  на следующий элемент:  Current := StatList [ Current ].Next

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

Current  :=  StatList [ 0 ].Next;

While (Current <> 0) and (StatList [ Current ].Inf  <> ‘значение’  do

     Current  :=  StatList [ Current ].Next;

If  Current = 0  then  ‘поиск неудачен’  else  ‘элемент найден’;

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

  •  проверка возможности добавления с помощью счетчика текущего числа элементов в списке
  •  определение каким-то образом элемента, после которого надо добавить новый элемент (например – запрос у пользователя)
  •  поиск этого элемента в списке; пусть его индекс есть  i
  •  определение номера свободной ячейки массива для размещения нового элемента (методы определения будут рассмотрены ниже); пусть этот номер равен  j
  •  формирование  связующей части нового элемента, т.е. занесение туда номера ячейки из связующей части элемента  i : StatList [ j ].next  :=  StatList [ i ].next;
  •  изменение связующей части элемента  i  на номер j: StatList [ i ].next  :=  j;
  •  занесение данных в информационную часть нового элемента StatList[j].inf;

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

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

  •  проверка возможности добавления с помощью счетчика текущего числа элементов в списке
  •  определение каким-то образом элемента, перед которым надо добавить новый элемент (например – запрос у пользователя)
  •  поиск этого элемента в списке с одновременным отслеживанием элемента-предшественника; пусть индекс заданного элемента есть  i, а индекс его предшественника - s
  •  определение номера свободной ячейки массива для размещения нового элемента (методы определения будут рассмотрены ниже); пусть этот номер равен  j
  •  формирование  связующей части нового элемента, т.е. занесение туда индекса  i : StatList [ j ].next  :=  i;
  •  изменение связующей части элемента-предшественника с индекса  i  на индекс j: StatList [ s ].next  :=  j;
  •  занесение данных в информационную часть нового элемента StatList[j].inf;

Удаление заданного элемента (естественно, в случае его наличия в списке) также требует изменения связующей части у элемента-предшественника. Это изменение позволяет “обойти” удаляемый элемент и тем самым исключить его из списка.

Необходимые шаги:

  •  определение каким-то образом удаляемого элемента (например – запрос у пользователя)
  •  поиск удаляемого элемента в списке с одновременным отслеживанием элемента-предшественника; пусть индекс удаляемого элемента есть  i, а индекс его предшественника - s
  •  изменение связующей части элемента-предшественника с индекса  i  на индекс-значение связующей части удаляемого элемента  i: StatList [s].next  :=  StatList [ i ].next;
  •  обработка удаляемого элемента (например – вывод информационной части)
  •  включение удаленного элемента во вспомогательный список без его уничтожения или освобождение ячейки  i  с включением ее в список свободных ячеек (методы поддержки свободной памяти рассматриваются ниже)

3.4. Управление памятью при статической реализации списков

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

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

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

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

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

  StatList [ N ]. Next := 0;

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

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

Состояние пустого списка:  StartFree  = 1

0

1

2

3

4

5

6

7

8

9

10

0

2

3

4

5

6

7

8

9

10

0

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

  •  Занятые ячейки массива: 3 – 1 – 2 – 8 – 10 – 5
  •  Свободные ячейки: 6 – 9 – 4 – 7 ,  StartFree  = 6

0

1

2

3

4

5

6

7

8

9

10

Инф.2

Инф.3

Инф.1

Инф.6

Инф.4

Инф.5

3

2

8

1

7

0

9

0

10

4

5

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

  •  Занятые ячейки:  8 – 2 – 5 – 6 – 7 – 10 – 1 – 4 – 3 – 9
  •  Свободных ячеек нет:  StartFree  = -1

0

1

2

3

4

5

6

7

8

9

10

Инф.7

Инф.2

Инф.9

Инф.8

Инф.3

Инф.4

Инф.5

Инф.1

Инф.10

Инф.6

8

4

5

9

3

6

7

10

2

0

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).

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

  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. Реализовать набор подпрограмм для выполнения основных операций со списком списков. Требования аналогичны предыдущему заданию.

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

  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.  Симметричный обход:
  •  рекурсивно обработать левое поддерево текущего поддерева
  •  обработать вершину текущего поддерева
  •  рекурсивно обработать правое поддерево
  1.  Обход в обратном направлении:
  •  рекурсивно обработать левое поддерево текущего поддерева
  •  рекурсивно обработать правое поддерево
  •  затем – вершину текущего поддерева

Прямой обход: A - B - C

Симметричный обход: B - A - C

Обратный обход: B - C - A

В качестве примера по шагам рассмотрим обход следующего ДД с числовыми компонентами (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
  1.   поддерево 4-6-7
  2.   поддерево 6-*-*
  3.   вершина 6
  4.   вершина 4

10. поддерево 7-*-*

  1.   вершина 7
  2.   вершина 0
  3.   поддерево 2-*-5
  4.   вершина 2
  5.   поддерево 5-8-9
  1.   поддерево 8-*-*
  2.   вершина 8
  3.   вершина 5
  4.   поддерево 9-*-*
  5.   вершина 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
  1.  вершина 7
  2.  вершина 4
  3.  вершина 1
  4.  поддерево 2-*-5
  5.  поддерево 5-8-9
  1.  вершина 8
  2.  вершина 9
  3.  вершина 5
  4.  вершина 2
  5.  вершина 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;

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

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

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

  0

         1

                   3

                   4

                                6

                                7

         2

                   5

                                8

                                9

                                     9

                       5

                                     8

            2

 0

                                     7

                       4

                                     6

             1

                       3

                      3

           1

                                     6

                       4

                                     7

  0

            2

                                     8

                        5

                                     9

Прямой обход

Обратно-симметричный

Симметричный проход

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

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

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

Исходное дерево

Вывод в прямом порядке

Вывод в симметричном порядке

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

               10

     15               9

13       22    5       17

10

         15

                   13

                   22

          9

                    5

                   17

                       13

          15

                       22

10                        

                       5        

           9

                       17

                      17

           9

                       5

10

                      22     

          15

                      13       

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  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.  Какие формальные параметры должна иметь рекурсивная подпрограмма построения идеально сбалансированного дерева и для чего они используются?
  33.  Приведите программную реализацию процедуры построения идеально сбалансированного дерева.

Тема 6. Реализация поисковых деревьев

  1.  Двоичные деревья поиска.

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

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

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

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

Например, если идеально сбалансированное ДП имеет 1000 вершин, то даже в наихудшем случае потребуется не более 10 сравнений (2 в степени 10 есть 1024), а если число вершин 1 миллион, то потребуется не более 20 сравнений.

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

Интересно заметить, что обход ДП в симметричном порядке позволяет получить исходный набор данных в соответствии с заданным упорядочиванием, а обход в обратно-симметричном порядке – в обратном порядке.

Алгоритм поиска в ДП очень прост:

Начиная с корневой вершины для каждого текущего поддерева надо выполнить следующие шаги:

  •  сравнить ключ вершины с заданным значением x
  •  если заданное значение меньше ключа вершины, перейти к левому потомку, иначе перейти к правому поддереву.

Поиск прекращается при выполнении одного из двух условий:

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

Интересно, что поиск очень легко можно реализовать простым циклом, без использования рекурсии:

pCurrent := pRoot;     {начинаем поиск с корня дерева}

Stop := false;

While  (pCurrent <> nil)  and  (not  Stop)  do 

    if  x < pCurrent ^.inf   then   pCurrent := pCurrent^.left  else

        if  x > pCurrent ^.inf  then   pCurrent := pCurrent^.right  else  Stop := true;

6.2. Добавление вершины в дерево поиска

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

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

Само добавление включает следующие шаги:

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

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

Procedure AddNode ( var  pCurrent : Tp);

begin

    if  pCurrent = nil  then     {место найдено, создать новую вершину}

    begin

         New ( pCurrent );   {параметр  pCurrent  определяет адрес новой вершины}

         pCurrent^.inf := “необходимое значение”;

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

         “установка значения поля счетчика в 1 “;

    end                              

    else             {просто продолжаем поиск в левом или правом поддереве}

         if   x < pCurrent^.inf   then  AddNode (pCurrent^.left)

            else   if   x > pCurrent^.inf   then  AddNode (pCurrent^.right)

                    else  “увеличить счетчик”    

end;

Запуск процедуры выполняется в главной программе вызовом AddNode(pRoot). Если дерево пустое, т.е.  pRoot = nil, то первый вызов процедуры создаст корневую вершину дерева, к которой потом можно аналогичными вызовами добавить любое число вершин.

Рассмотрим нерекурсивный вариант процедуры добавления вершины в ДП. Необходимо объявить две ссылочные переменные для отслеживания адреса текущей вершины и адреса ее родителя:  

          pCurrent, pParent : Tp;

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

if  pRoot = nil  then

  begin

     New (pRoot);   pRoot^.left := nil;  pRoot^.right := nil;

     “заполнение остальных полей”;

  end

else

  begin

     pCurrent := pRoot;       {начинаем поиск с корня дерева}

     while  (pCurrent <> nil )  do

     begin

        pParent := pCurrent;     {запоминаем адрес родительской вершины}

        if  ( x < pCurrent^.inf) then  pCurrent := pCurrent^.left

            else  if  ( x > pCurrent^.inf)  then  pCurrent := pCurrent^.right

                else  begin     {вершина найдена, добавлять не надо, закончить цикл}

                           pCurrent := nil;

                           “увеличить счетчик”;

                        end;

     end;

     if  ( x < pParent^.inf)  then

     begin                                  {добавляем новую вершину слева от родителя}   

        New (pCurrent);

        “заполнить поля новой вершины”;

        pParent^.left := pCurrent;

     end  

           else

                 if  ( x > pParent^.inf)  then

                     begin                   {добавляем новую вершину справа от родителя}

                         New (pCurrent);

                         “заполнить поля новой вершины”;

                         pParent^.right := pCurrent;

                     end   

  end;

6.3. Удаление вершины из дерева поиска

Теперь рассмотрим удаление вершины из ДП. По сравнению с добавлением удаление реализуется более сложным алгоритмом, поскольку добавляемая вершина всегда является терминальной, а удаляться может ЛЮБАЯ, в том числе и нетерминальная. При этом может возникать несколько различных ситуаций.

Рассмотрим фрагмент ДП с целыми ключами.

Ситуация 1. Удаляемая вершина не имеет ни одного потомка, т.е. является терминальной. Удаление реализуется очень легко обнулением соответствующего указателя у родителя. Например, для удаления вершины с ключом 23 достаточно установить 25.left = nil.

Ситуация 2. Удаляемая вершина имеет только одного потомка. В этом случае удаляемая вершина вместе со своим потомком и родителем образуют фрагмент   линейного списка. Удаление реализуется простым изменением указателя у родительского элемента. Например, для удаления вершины с ключом 20 достаточно установить 30.left = 20.right = 25

Ситуация 3. Пусть удаляемая вершина имеет двух потомков. Этот случай наиболее сложен, поскольку нельзя просто в родительской вершине изменить соответствующее ссылочное поле на адрес одного из потомков удаляемой вершины. Это может нарушить структуру дерева поиска. Например, замена вершины 30 на одного из ее непосредственных потомков 20 или 40 сразу нарушает структуру дерева поиска.

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

  •  либо войти в левое поддерево удаляемой вершины и в этом поддереве спустится как можно глубже, придерживаясь только правых потомков; это позволяет найти в дереве ближайшую меньшую вершину (например, для вершины 30 это будет вершина 25)
  •  либо войти в правое поддерево удаляемой вершины и спустится в нем как можно глубже придерживаясь только левых потомков; это позволяет найти ближайшую бОльшую вершину (например, для той же вершины 30 это будет вершина 33).

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

Procedure  DeleteNode ( var  pCurrent : Tp);

Var  pTemp : Tp;

   Procedure Changer ( var  p : Tp);

        begin

              {реализация рассматривается ниже}    

         end;

begin 

   if  pCurrent = nil  then  “удаляемой вершины нет, ничего не делаем”

   else  

       if  x < pCcurrent^.inf   then  DeleteNode ( pCcurrent^.left)

            else

                if  x > pCurrent^.inf   then  DeleteNode ( pCurrent^.right)

                     else                                    {удаляемая вершина найдена}

                      begin

                           pTemp := pCurrent;

                           if   pTemp^.right = nil  then   pCurrent := pTemp^.left

                             else  

                                 if  pTemp^.left = nil  then  pCurrent := pTemp^.right

                                    else                            {два потомка, ищем заменитель}

                                       Changer ( pCurrent^.left);    { а можно и  pCurrent^.right }

                           Dispose ( pTemp);

                      end;

end;

Схема процедуры  Changer:

begin

    if  p^.right <> nil  then  Changer ( p^.right)

    else                   {правое поддерево пустое, заменитель найден, делаем обмен}

    begin

        pTemp^.inf := p^.inf;    {заменяем информац. часть удаляемой вершины}

        pTemp := p;                   {pTemp теперь определяет вершину-заменитель}

        p := p^.left;       {выходной параметр адресует левого потомка заменителя}

    end;

end;

Дополнительный комментарий к процедурам. Подпрограмма  Changer  в качестве входного значения получает адрес левого (или правого) потомка удаляемой вершины и рекурсивно находит вершину-заменитель. После этого информационная часть удаляемой вершины заменяется содержимым вершины-заменителя, т.е. фактического удаления вершины не происходит. Это позволяет сохранить неизменными обе связи этой вершины с ее потомками. Удаление реализуется относительно вершины-заменителя, для чего ссылка  pTemp  после обмена устанавливается в адрес этой вершины. Кроме того, в самом конце процедуры  Changer  устанавливается новое значение выходного параметра  p: оно равно адресу левого потомка вершины-заменителя. Это необходимо для правильного изменения адресной части вершины-родителя для вершины-заменителя. Само изменение происходит при отработке механизма возвратов из рекурсивных вызовов процедуры  Changer. Когда все эти возвраты отработают, происходит возврат в основную процедуру  DeleteNode, которая освобождает память, занимаемую вершиной-заменителем. Отметим, что приведенная выше реализация процедуры  Changer  ориентирована на поиск в левом поддереве удаляемой вершины и требует симметричного изменения для поиска заменителя в правом поддереве.

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

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

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

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

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

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

                   5(1)  11(2)   19(5)   33(1)   34(4) . . . . .

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

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

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

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

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

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

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

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

  •  в именах используются только строчные (малые) буквы
  •  отсутствуют комментарии
  •  отсутствуют текстовые константы, задаваемые с помощью кавычек ‘’

Например, пусть исходная программа имеет следующий вид:

program test;

var x, y : integer;

      str : string;

begin

  x := 1;

  y := x + 2;

  write(x, y);

end.

Тогда для нее должна быть построена следующая таблица имен и дерево поиска:

begin

4

end

8

integer

2

program

1

str

3

string

3

test

1

var

2

write

7

x

2   5   6   7

y

2   6   7

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

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

  1.  Объявить необходимые глобальные переменные, такие как номер обрабатываемой строки исходного текста и ее длина, номер обрабатываемого символа в строке (счетчик символов), сама текущая строка, текущее формируемое имя, имя исходного файла, файловая переменная, указатель на корень дерева
  2.  Объявить и реализовать рекурсивную подпрограмму добавления вершины в дерево поиска. За основу можно взять рассмотренную в предыдущей работе процедуру добавления, внеся в нее следующие небольшие дополнения:
  •  при вставке новой вершины создать первый (пока единственный!) узел вспомогательного линейного списка, заполнить его поля и поля созданной вершины дерева необходимыми значениями
  •  в случае совпадения текущего имени с ключом одной из вершин дерева добавить в конец вспомогательного списка новый узел с номером строки, где найдено данное имя
  1.  Объявить и реализовать рекурсивную подпрограмму для вывода построенной таблицы в порядке возрастания имен. Основа – обход дерева в симметричном порядке. Дополнительно для каждой вершины выводится список номеров строк, где используется данное имя. Для этого организуется проход по вспомогательному линейному списку от его начала до конца.
  2.  Объявить и реализовать рекурсивную подпрограмму для построчного вывода дерева в обратно-симметричном порядке. Эту подпрограмму без каких-либо изменений можно взять из предыдущей работы.
  3.  Реализовать главную программу, выполняющую основную работу по выделению имен из строк обрабатываемого текста. Формируемое имя объявляется как String, но обрабатывается как массив символов. Основной механизм формирования имени – посимвольная обработка текущей строки. Как только в строке после не-буквенных символов распознается буква, начинается выделение всех последующих буквенно-цифровых символов и формирование очередного имени. Обрабатываемая строка (тип String) рассматривается как массив символов. Удобно перед обработкой строки добавить в ее конце символ пробела. Номер текущего обрабатываемого символа задается переменной-счетчиком. Для отслеживания символов в формируемом имени также необходима переменная-счетчик.

Алгоритм работы главной программы:

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

  1.  Контрольные вопросы по теме
    1.  Какое дерево называется деревом поиска?
      1.  В чем состоит практическая важность использования деревьев поиска?
        1.  Какие преимущества имеет использование деревьев поиска для хранения упорядоченных данных по сравнению с массивами и списками?
          1.  Почему наивысшая эффективность поиска достигается у идеально сбалансированных деревьев?
            1.  Как находится максимально возможное число шагов при поиске в идеально сбалансированном дереве?
            2.  Приведите алгоритм поиска в дереве поиска.
            3.  Как программно реализуется поиск в дереве поиска?
            4.  Как выполняется добавление новой вершины в дерево поиска?
            5.  В чем смысл рекурсивной реализации алгоритма добавления вершины в дерево поиска?
            6.  Какой формальный параметр имеет рекурсивная процедура добавления вершины в дерево поиска и как он используется?
            7.  Приведите программную реализацию рекурсивной процедуры добавления вершины в дерево поиска.
            8.  Какие ссылочные переменные необходимы для нерекурсивной реализации процедуры добавления вершины в дерево поиска?
            9.  Как программно реализуется добавление нерекурсивная процедура добавления вершины в дерево поиска?
            10.  Какие ситуации могут возникать при удалении вершины из дерева поиска?
            11.  Что необходимо выполнить при удалении из дерева поиска вершины, имеющей двух потомков?
            12.  Какие правила существуют для определения вершины-заменителя при удалении из дерева поиска?
            13.  Опишите алгоритм удаления вершины из дерева поиска.
            14.  Приведите программную реализацию алгоритма удаления вершины из дерева поиска.

Тема 7. Дополнительные вопросы обработки деревьев. Графы.

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

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

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

“Хорошая” входная последовательность:

20 – 10 – 30 – 15 – 25 – 5 - 40

“Плохая” входная последовательность:

10 – 15 – 20 – 5 – 25 – 30 - 40

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

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

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

Очевидно, что любое идеально сбалансированное дерево является также и АВЛ-сбалансированным, но не наоборот.

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

и оно же АВЛ-сбалансированное

АВЛ-сбалансированное, но не идеально сбалансированное

Не АВЛ-сбалансированное

(нарушение – для корня)

Для реализации алгоритмов АВЛ-балансировки в каждой вершине дерева удобно хранить так называемый коэффициент балансировки (КБ) как разность высот правого и левого поддеревьев. Для АВЛ-деревьев у всех вершин значение КБ равно  –1,  0  или  +1.

АВЛ-сбалансированное дерево

несбалансированное дерево

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

Type Tp = ^TNode;

  TNode = record

                     Inf : <описание>;

                     Left, right : Tp;

                     Balance : shortInt;

                  end;

        Алгоритм АВЛ-балансировки при добавлении вершины.

  •  выполняется поиск в дереве места для новой добавочной вершины, при этом для каждой вершины высчитывается коэффициент балансировки
  •  если необходимо, то выполняется добавление самой вершины с заполнением всех полей, в том числе и КБ =0 (т.к. потомков у вновь созданной вершины пока нет)
  •  изменяется на 1 коэффициент балансировки у родителя добавленной вершины: КБ = КБ + 1 если добавлен правый потомок, иначе КБ = КБ - 1
  •  проверяем новое значение КБ  у родительской вершины: если он имеет допустимое значение, то переходим еще на уровень выше для изменения и анализа КБ у деда новой вершины и т.д – до корневой вершины (иногда условие балансировки может нарушиться только для корневой вершины, поэтому приходится проверять все вершины на пути от вновь добавленной до корневой)
  •  если у какой либо вершины нарушается условие балансировки, запускается специальный алгоритм перестановки вершин, который восстанавливает АВЛ-балансировку дерева и в то же время сохраняет упорядоченную структуру дерева поиска

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

до балансировки

после балансировки

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

  •  вершина с нарушенным условием балансировки деформирована влево, КБ(30) = -2
  •  ее левый потомок также перевешивает в левую сторону, КБ(15) = -1

Для исправления этой ситуации выполняется однократный поворот вправо:

  •  вершина 15 заменяет вершину 30
  •  левое поддерево вершины 15 не изменяется (15 – 10 – 5)
  •  правое поддерево вершины 15 образуется корневой вершиной 30
  •  у вершины 30 правое поддерево не изменяется (30 – 40)
  •  левое поддерево вершины 30 образуется бывшим правым потомком вершины 15, т.е. 20

Аналогично выполняется однократный поворот влево, если вершина с нарушенным условием балансировки перевешивает вправо (КБ = 2), а ее правый потомок тоже перевешивает вправо (КБ = 1).

Более сложные случаи возникают при несогласованном перевешивании корневой вершины и ее потомков (коэффициенты балансировки имеют разные знаки). Например, рассмотрим случай, когда корневая вершина поддерева с нарушенным условием перевешивает влево (КБ = -2), но ее левый потомок перевешивает вправо (КБ = 1).

до балансировки

после балансировки

Двукратный поворот включает в себя:

  •  вершина 30 заменяется вершиной 20, т.е. правым потомком левого потомка
  •  левый потомок вершины 20 (вершина 17) становится правым потомком вершины 15
  •  левое поддерево с корнем 15 без изменений остается левым поддеревом вершины 20
  •  правое поддерево вершины 20 начинается с вершины 30
  •  правое поддерево вершины 30 не меняется (30 – 40 – 50)
  •  левое поддерево вершины 30 образуется правым поддеревом вершины 20 (25 – 23)

Удаление вершин из АВЛ-дерева выполняется аналогично:

  •  ищется удаляемая вершина
  •  если требуется – определяется вершина-заменитель и выполняется обмен
  •  после удаления вершины пересчитываются КБ и при необходимости производится балансировка точно по таким же правилам

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

Практика использования АВЛ-деревьев показала, что балансировка требуется примерно в половине случаев вставки и удаления вершин.

Общий вывод: учитывая достаточно высокую трудоемкость выполнения балансировки, АВЛ-деревья следует использовать тогда, когда вставка и удаление выполняются значительно реже, чем поиск.

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

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

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

Type  Tp = ^TNode;

          TNode = record

                             Inf : <описание>;

                             Left, right, parent : Tp;

                          end;

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

Недостатками являются:

  •  Увеличение затрат памяти на поддержку в каждой вершине дополнительного указателя (4 байта на вершину), т.е. в каждой вершине 12 байт занимает служебная информация, что при большом числе вершин (сотни тысяч) может стать весьма ощутимым
  •  Увеличивается число операций при добавлении и удалении вершин за счет поддержки дополнительных ссылочных полей

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

7.3. Деревья общего вида (не двоичные).

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

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

Исходное недвоичное дерево

Представление в виде списка списков

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

Type  Tp = ^ TNode;

          TNode = record

                            Inf : <описание>;

                            NextParent,  NextChild : Tp;

                          end;

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

Схематично рассмотрим реализацию основных операций с подобным списковым представлением недвоичных деревьев.

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

PCurrentParent := pRoot;

While  pCurrentParent <> nil do

  begin

     “обработка вершины  pCurrentParent^”;

     pCurrentChild := pCurrentParent^.NextChild;

     while  pCurrentChild <> nil do

        begin

            “обработка вершины  pCurrentChild^”;

            pCurrentChild := pCurrentChild^.NextChild;

        end;

     pCurrentParent := pCurrentParent^.NextParent;

  end;

  1.  Добавление вершины  X  как потомка вершины  Y:
    •  “поиск вершины  Y  обходом всех вершин”;
    •  if  “вершина  Y  найдена в списке родителей”  then  “добавляем  X  в список потомков вершины  Y”;
    •  if  “вершина  Y  найдена в списке потомков”  then
      •  “добавляем  Y  в список родителей”;
      •  “создаем у вершины  Y  список потомков с вершиной  X”;
  2.  Удаление вершины  X, если она не корневая для всего дерева:
  •  “поиск вершины  X  обходом всех вершин”;
  •  if  “вершина  X  найдена в списке родителей”  then
    •  “просмотром всех списков найти родителя вершины  X”;
    •  “удалить  X  из списка потомков”;
    •  “к родителю  X  добавить список всех потомков  X”;
  •  if  “вершина  X  есть только в списке потомков”  then
    •  “удалить  X  из списка потомков”;
    •  if  “список потомков пуст, то удалить родителя из списка родителей”;

  1.   Представление графов

Граф – это множество однотипных объектов (вершин), некоторые из которых связаны друг с другом какими-либо связями (ребрами). Одна связь всегда соединяет только две вершины (иногда – вершину саму с собой). Основные разновидности графов:

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

Примеры графов разных типов:

обычный

ориентированный

взвешенный

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

Для рассмотренных выше примеров матрицы смежности будут следующими:

A

B

C

D

E

A

0

1

1

1

1

B

1

0

0

0

1

C

1

0

0

1

0

D

1

0

1

0

0

E

1

1

0

0

0

A

B

C

D

E

A

0

1

1

0

0

B

1

0

0

0

1

C

0

1

0

1

1

D

1

0

0

0

1

E

0

0

0

0

0

A

B

C

D

E

A

0

15

0

9

0

B

15

0

10

0

0

C

0

10

0

22

6

D

9

0

22

0

19

E

0

0

6

19

0

Недостатки данного способа:

  •  заранее надо знать хотя бы ориентировочное число вершин в графе
  •  для графов с большим числом вершин матрица становится слишком большой (например 1000*1000 = 1 миллион чисел)
  •  при малом числе связующих ребер матрица заполнена в основном нулями

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

 

Описание подобной сложной списковой структуры выполняется обычным образом.

Операции добавления и удаления по сравнению с деревьями имеют следующие варианты:

  •  добавление новой связи (ребра) между заданной парой существующих вершин
  •  добавление новой вершины вместе со всеми необходимыми связями
  •  удаление связи (ребра) между двумя вершинами
  •  удаление вершины вместе со всеми ее связями

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

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

Добавление новой вершины включает в себя:

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

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

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

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

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

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

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

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

Например, для рассмотренного выше обычного графа получим:

  •  пусть стартовая вершина – B
    •  включаем B в список обработанных вершин: список = (В)
      •  помещаем в стек смежные с В вершины, т.е. A и E: стек = (А, Е)
      •  извлекаем из стека вершину E: стек = (А)
      •  т.к. E нет в списке обработанных вершин, то обрабатываем ее и помещаем в список: список = (В, Е)
      •  смежные с E вершины – это A и B, но B уже обработана, поэтому помещаем в стек только вершину А: стек = (А, А)
      •  извлекаем из стека вершину А: стек = (А)
      •  т.к. А нет в списке обработанных вершин, то помещаем ее туда: список = (В, Е, А)
      •  смежные с А вершины – это B, C, D, E, из которых B и E уже обработаны, поэтому помещаем в стек C и D: стек = (A, C, D)
      •  извлекаем из стека вершину D: стек = (A, C)
      •  т.к. D не обработана, то помещаем ее в список: список = (B, E, A, D)
      •  смежные с D вершины – это А и С, из которых А уже обработана, поэтому помещаем в стек вершину С: стек = (А, С, С)
      •  извлекаем из стека вершину С: стек = (А, С)
      •  т.к. С не обработана, помещаем ее в список: список = (B, E, A, D, C)
      •  смежные с С вершины – это A и D, но они обе уже обработаны, поэтому в стек ничего не заносим
      •  извлекаем из стека С, но она уже обработана
      •  извлекаем из стека А, но она тоже уже обработана
      •  т.к. стек стал пустым, то завершаем обход с результатом (B, E, A, D, C)

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

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

Тот же что и раньше пример даст следующий результат:

  •  пусть стартовая вершина – B
    •  включаем B в список обработанных вершин: список = (В)
      •  помещаем в очередь смежные с В вершины, т.е. A и E: очередь = (А, Е)
      •  извлекаем из очереди вершину А: очередь = (Е)
      •  т.к. она не обработана, добавляем ее в список: список = (В, А)
      •  смежные с А вершины – это B, C, D и E, помещаем в очередь вершины C, D и E: очередь = (E, C, D, E)
      •  извлекаем из очереди вершину Е: очередь = (C, D, E)
      •  т.к. Е не обработана, помещаем ее в список: список = (B, A, E), т.е. в первую очередь обработаны обе смежные с В вершины
      •  смежные с Е вершины – это А и В, но обе они уже обработаны, поэтому очередь новыми вершинами не пополняется
      •  извлекаем из очереди вершину С: очередь = (D, E)
      •  т.к. С не обработана, то помещаем ее в список: список = (B, A, E, С)
      •  смежные с С вершины – это А и D, помещаем в очередь только D: очередь = (D, E, D)
      •  извлекаем из очереди вершину D: очередь = (E, D)
      •  т.к. D не обработана, помещаем ее в список: список = (B, A, E, С, D)
      •  смежные с D вершины – это А и С, но обе они обработаны, поэтому очередь не пополняется
      •  извлекаем из очереди вершину Е, но она уже обработана: очередь = (D)
      •  извлекаем из очереди вершину D, но она уже обработана и т.к. очередь становится пустой, то поиск заканчивается с результатом (B, A, E, С, D), что отличается от поиска в глубину.

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

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

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

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

  •  добавление новой вершины как потомка заданной вершины
  •  удаление заданной вершины
  •  вывод всех вершин с указанием родительских связей
  •  поиск заданной вершины

Требования к подпрограммам и главной программе – стандартные.

Задание 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.  Какие шаги включает в себя алгоритм поиска в ширину?

Раздел 2. Алгоритмы сортировки и поиска

Тема 1. Классификация методов. Простейшие методы сортировки

1.1. Задача оценки и выбора алгоритмов

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

  •  точность решения задачи
  •  затраты машинного времени
  •  затраты оперативной памяти

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

  •  минимально возможное число повторов элементарных операций в наилучшем случае
  •  среднее число повторов
  •  максимальное число повторов для наихудшего случая

Например, в задаче поиска в неупорядоченном массиве или списке из n элементов базовой операцией является сравнение заданного значения с ключом элемента массива. Тогда минимальное число сравнений равно 1 (совпадение произошло на первом элементе массива), максимальное равно n (просмотрен весь массив), а среднее - около n/2.

В отличие от этого, двоичный поиск в упорядоченном массиве или в “хорошем” двоичном дереве поиска дает другие оценки: минимум – 1, максимум - log 2 n, среднее – 0,5* (log 2 n).

Получение подобных оценок часто является сложной математической задачей. Наиболее полный анализ методов получения этих оценок для всех основных алгоритмов приводится в фундаментальной многотомной работе Дональда Кнута [1, 2].

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

Для оценивания трудоемкости алгоритмов была введена специальная система обозначений – так называемая О-нотация.  Эта нотация позволяет учитывать в функции f (n) лишь наиболее значимые элементы, отбрасывая второстепенные.

Например, в функции  f (n) = 2n2 + n – 5 при достаточно больших  n  компонента  n2 будет значительно превосходить остальные слагаемые, и поэтому характерное поведение этой функции определяется именно этой компонентой. Остальные компоненты можно отбросить и условно записать, что данная функция имеет оценку поведения (в смысле скорости роста ее значений) вида  О(n2 ).

Аналогично, для функции  f (n) = 2n + 3n3 – 10  начиная с некоторого  n  первое слагаемое будет превосходить второе и поэтому данную функцию можно описать оценкой  О(2n).

Важность О-оценивания состоит в том, что оно позволяет описывать характер поведения функции f(n) с ростом n: насколько быстро или медленно растет эта функция.

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

  1.  постоянные функции типа О(1), которые с ростом n НЕ растут (в оценивании алгоритмов этот случай встречается крайне редко, но все-таки встречается!)
  2.  функции с логарифмической скоростью роста О(log 2 n)
  3.  функции с линейной скоростью роста О(n)
  4.  функции с линейно–логарифмической скоростью роста О(n*log 2 n)
  5.  функции с квадратичной скоростью роста О(n2 )
  6.  функции со степенной скоростью роста  О(na) при а>2
  7.  функции с показательной или экспоненциальной скоростью роста  О(2n)
  8.  функции с факториальной степенью роста  О(n!)

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

Отсюда можно сделать несколько выводов.

  1.  При выборе однотипных алгоритмов предпочтение (при прочих равных условиях) следует отдавать алгоритмам с наименьшей скоростью роста трудоемкости, поскольку они позволят за одно и то же время решить задачи с большей размерностью
  2.  Если заранее известно, что размерность решаемых задач невелика, но зато число их повторений очень большое, имеет смысл рассмотреть возможность использования алгоритмов не с самой лучшей оценкой, поскольку при малых n “лучшие” алгоритмы могут вести себя хуже, чем “плохие” (это можно заметить по графику в области начала координат)
  3.  Алгоритмы класса О(2n) и О(n!) следует использовать с большой осторожностью, учитывая катастрофический рост их трудоемкости уже при n>100. Например, если число базовых операций определяется соотношением 2n, то при n=100 это число будет примерно равно 1030, и если одна базовая операция выполняется за 1 микросекунду, то это потребует около 1024 секунд, т.е. порядка 1016 лет. К сожалению, задачи с подобной трудоемкостью довольно часто встречаются на практике и их точное решение пока невозможно даже на сверхбыстрых суперкомпьютерах!

Как быть с оценкой трудоемкости программы в целом, если в программе используется несколько алгоритмов, решающих свои конкретные задачи? Есть два основных способа взаимодействия алгоритмов – последовательное и вложенное. При последовательном выполнении алгоритмов с оценками O(f1), O(f2), …, O(fk) общая трудоемкость определяется трудоемкостью алгоритма с максимальным значением:

  O (программы) = Max (O(f1), O(f2), . . ., O(fk))

При вложенном выполнении общая трудоемкость есть произведение оценок вложенных друг в друга алгоритмов: O(программы) = O(f1)*O(f2)*O(f3)

1.2. Классификация задач сортировки и поиска

Пусть задано некоторое множество элементов а1 а2, а3, . . ., аn и требуется выстроить эти элементы по порядку в соответствии с заданной функцией предпочтения (например, по алфавиту). Очень часто значения функции предпочтения явно хранятся в исходных элементах в виде специального ключевого поля целого или строкового типа.

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

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

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

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

  •  Универсальные методы, не требующие никакой дополнительной информации об исходных данных и выполняющие сортировку “на месте”, т.е. без использования больших объемов дополнительной памяти (например – для размещения копии исходного массива); такие методы в лучшем случае дают оценку трудоемкости порядка  O(n*log 2 n)
  •  Специальные методы, которые либо за счет некоторой дополнительной информации об исходных данных, либо за счет использования большой дополнительной памяти позволяют получить более высокую производительность сортировки порядка  O(n) (примеры – карманная и поразрядная сортировка)

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

  •  Простейшие методы с трудоемкостью порядка  O(n2): сортировка обменом, сортировка выбором и сортировка вставками
  •  Улучшенные методы с трудоемкостью  O(n*log 2 n): метод Шелла, пирамидальная сортировка, быстрая сортировка

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

Общая классификация методов сортировки приводится на схеме. Описание всех методов приводится далее в пособии.

Аналогично можно провести классификацию методов поиска. Прежде всего – внутренний поиск и внешний поиск. Внутренний поиск – универсальный и специальный. Универсальный – поиск в упорядоченном или неупорядоченном наборе данных. Неупорядоченный набор – метод простого перебора (массив, список, иногда – дерево), упорядоченный – метод двоичного поиска в массиве или дереве. Специальный метод поиска в массиве (хеш-поиск) предполагает особую его организацию и используется при определенных ограничениях (правда, при выполнении этих ограничений данный метод дает потрясающую производительность – одно сравнение для поиска ЛЮБОГО элемента, независимо от объема входных данных!). Внешний поиск реализуется для сверхбольших объемов данных, которые нельзя одновременно разместить в основной памяти и требует использования внешних файлов (один из самых известных методов основан на использовании так называемых B-деревьев). Универсальные методы поиска были рассмотрены ранее, а остальные рассматриваются ниже, после описания методов сортировки.

1.3. Простейшие методы сортировки: метод обмена

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

Пусть имеется n элементов  а1 а2, а3, . . ., аn, расположенных в ячейках массива. Для простоты будем считать, что сам элемент совпадает с его ключом. Алгоритм состоит в повторении  n-1  шага, на каждом из которых в оставшемся необработанном наборе за счет попарного сравнения соседних элементов отыскивается минимальный элемент.

Шаг 1. Сравниваем  аn  с  аn-1 и если аn < аn-1 то меняем их местами, потом сравниваем  аn-1 с  аn-2  и, возможно, переставляем их, сравниваем  аn-2  и  аn-3  и т.д. до сравнения и, возможно, перестановки  а2  и  а1. В результате на первом месте в массиве оказывается самый минимальный элемент, который в дальнейшей сортировке не участвует

Шаг 2. Аналогично сравниваем  аn  с  аn-1,  аn-1  с  аn-2  и т.д.,  а3  с  а2,  в результате чего на месте  а2 оказывается второй наименьший элемент, который вместе с  а1  образует начальную часть упорядоченного массива

Шаг 3. Аналогичными сравнениями и перестановками среди элементов  а3, а4, … , аn  находится наименьший, который занимает место  а3

. . . . .

Шаг n-1. К этому моменту первые  n-2  элемента в массиве уже упорядочены и остается “навести порядок” только между двумя последними элементами  аn-1  и  аn. На этом сортировка заканчивается.

Пример. Дано 6 элементов – целые числа 15, 33, 42, 07, 12, 19.

а1

а2

а3

а4

а5

а6

Выполняемые операции

шаг 1

15

33

42

07

12

19

сравнение 19 и 12, обмена нет

15

33

42

07

12

19

сравнение 12 и 07, обмена нет

15

33

07

42

12

19

сравнение 07 и 42, меняем их

15