Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных. Новая версия для Оберона

Глава 4 Динамические структуры данных

4.1. Рекурсивные типы

данных..................................... 168

  • 4.2. Указатели......................... 170
  • 4.3. Линейные списки.............. 175
  • 4.4. Деревья............................ 191
  • 4.5. Сбалансированные

деревья ................................... 210

4.6. Оптимальные деревья

поиска..................................... 220

  • 4.7. Б-деревья (ЕМгеев) .......... 227
  • 4.8. Приоритетные деревья

поиска..................................... 246

Упражнения............................. 250

Литература.............................. 254

4.1. Рекурсивные типы данных

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

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

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

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

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

Выражение состоит из терма, за которым следует знак операции, за которым следует терм. (Два этих терма - операнды операции.) Терм - это либо переменная, представленная идентификатором, либо выражение, заключенное в скобки.

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

TYPE expression = RECORD op: INTEGER;

opdl, opd2:term END

TYPE term = RECORD

IF t: BOOLEAN THEN id: Name ELSE subex: expression END END

Поэтому каждая переменная типа term состоит из двух компонент, а именно поля признака t, а также, если t истинно, поля id, или в противном случае поля subex. Например, рассмотрим следующие четыре выражения:

  • 1. х + у
  • 2. х - (у * z)
  • 3. (х + у) * (z - w)
  • 4. (х/(у + z)) * w

Эти выражения схематически показаны на рис. 4.1, где видна их «матрешечная», рекурсивная структура, а также показано размещение этих выражений в памяти.

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

TYPE ped = RECORD

IF known: BOOLEAN THEN name: Name; father, mother: ped END END

Заметим, что каждая переменная типа ped имеет по крайней мере одну компоненту, а именно поле признака known (известен). Если его значение равно TRUE, то есть еще три поля; в противном случае эти поля отсутствуют. Пример конкретного значения показан ниже в виде выражения с вложениями, а также с помощью диаграммы, показывающей возможное размещение в памяти (см. рис. 4.2).

(Т, Ted, (Т, Fred, (Т, Adam, (F), (F)), (F)), (Т, Mary, (F), (Т, Eva, (F), (F)))

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

Схемы расположения в памяти рекурсивных записевых структур

Рис. 4.1. Схемы расположения в памяти рекурсивных записевых структур

Пример рекурсивной структуры данных

Рис. 4.2. Пример рекурсивной структуры данных

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы