Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией
 Скачать 2.67 Mb.
|
Глава 4Литература .............................. 254 Динамические структуры данных 168 4.1. Рекурсивные типы данных В главе 1 массивы, записи и множества были введены в качестве фундаменталь% ных структур данных. Мы назвали их фундаментальными, так как они являются строительными блоками, из которых формируются более сложные структуры, а также потому, что на практике они встречаются чаще всего. Смысл определения типа данных, а затем определения переменных, имеющих этот тип, состоит в том, чтобы раз и навсегда фиксировать диапазон значений этих переменных, а значит, и способ их размещения в памяти. Поэтому такие переменные называют стати ческими. Однако есть много задач, где нужны более сложные структуры данных. Для таких задач характерно, что не только значения, но и структура переменных меняется во время вычисления. Поэтому их называют динамическими структура ми. Естественно, компоненты таких структур – на определенном уровне разреше% ния – являются статическими, то есть принадлежат одному из фундаментальных типов данных. Эта глава посвящена построению, анализу и работе с динамиче% скими структурами данных. Надо заметить, что существуют близкие аналогии между методами структури% рования алгоритмов и данных. Эта аналогия, как и любая другая, не является пол% ной, тем не менее сравнение методов структурирования программ и данных по% учительно. Элементарный неделимый оператор – присваивание значения некоторой пе% ременной. Соответствующий член семейства структур данных – скалярный, не% структурированный тип. Эта пара представляет собой неделимые строительные блоки для составных операторов и для типов данных. Простейшие структуры, получаемые посредством перечисления, суть последовательность операторов и запись. И та, и другая состоят из конечного (обычно небольшого) числа явно пе% речисленных компонент, которые все могут быть различными. Если все компо% ненты идентичны, то их не обязательно выписывать по отдельности: в этом случае используют оператор for и массив, чтобы указать известное, конечное число по% вторений. Выбор между двумя или более элементами выражается условным опе% ратором и расширением записевых типов соответственно. И наконец, повторение с заранее неизвестным (и потенциально бесконечным) числом шагов выражается операторами while и repeat . Соответствующая структура данных – последова% тельность (файл) – это простейшее средство для построения типов с бесконечной мощностью. Возникает вопрос: существует ли структура данных, которая аналогичным образом соответствовала бы оператору процедуры? Естественно, в этом отно% шении самым интересным и новым свойством процедур является рекурсия. Значения такого рекурсивного типа данных должны содержать одну или более компонент, принадлежащих этому же типу, подобно тому как процедура может содержать один или более вызовов самой себя. Как и процедуры, определения ти% пов данных могли бы быть явно или косвенно рекурсивными. Простой пример объекта, который весьма уместно представлять рекурсивно определенным типом, – арифметическое выражение, имеющееся в языках про% 169 граммирования. Рекурсия используется, чтобы отразить возможность вложений, то есть использования подвыражений в скобках в качестве операндов выражений. Поэтому дадим следующее неформальное определение выражения: Выражение состоит из терма, за которым следует знак операции, за которым следует терм. (Два этих терма – операнды операции.) Терм – это либо перемен% ная, представленная идентификатором, либо выражение, заключенное в скобки. Тип данных, значениями которого представляются такие выражения, может быть легко описан, если использовать уже имеющиеся средства, добавив к ним рекурсию: TYPE expression = RECORD op: INTEGER; opd1, opd2: term END TYPE term = RECORD IF t: BOOLEAN THEN id: Name ELSE subex: expression END END Поэтому каждая переменная типа term состоит из двух компонент, а именно поля признака t , а также, если t истинно, поля id , или в противном случае поля subex . Например, рассмотрим следующие четыре выражения: 1. x + y 2. x – (y * z) 3. (x + y) * (z – w) 4. (x/(y + 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). (T, Ted, (T, Fred, (T, Adam, (F), (F)), (F)), (T, Mary, (F), (T, Eva, (F), (F))) Понятно, почему важны условия в таких определениях: это единственное средство ограничить рекурсивную структуру данных, поэтому они обязательно Рекурсивные типы данных Динамические структуры данных 170 Рис. 4.1. Схемы расположения в памяти рекурсивных записевых структур Рис. 4.2. Пример рекурсивной структуры данных сопровождают каждое рекурсивное определе% ние. Здесь особенно четко видна аналогия между структурированием программ и данных. Услов% ный оператор (или оператор выбора) обяза% тельно должен быть частью каждой рекурсивной процедуры, чтобы обеспечить завершение ее вы% полнения. На практике динамические структу% ры используют ссылки или указатели на свои элементы, а идея альтернативы (для завершения рекурсии) реализуется в понятии указателя, как объясняется в следующем разделе. 4.2. Указатели Характерное свойство рекурсивных структур, четко отличающее их от фундаментальных струк% тур (массивов, записей, множеств), – это их спо% собность менять свой размер. Поэтому невозмож% но выделить фиксированный участок памяти для размещения рекурсивно определенной структу% ры, и, как следствие, компилятор не может свя% зать конкретные адреса с компонентами таких переменных. Метод, чаще всего применяемый для решения этой проблемы, состоит в динами 171 ческом распределении памяти (dynamic allocation of storage), то есть распределе% нии памяти отдельным компонентам в тот момент, когда они возникают при вы% полнения программы, а не во время трансляции. При этом компилятор отводит фиксированный объем памяти для хранения адреса динамически размещаемой компоненты вместо самой компоненты. Например, родословная, показанная на рис. 4.2, будет представлена отдельными – вполне возможно, несмежными – за% писями, по одной на каждого индивида. Эти записи для отдельных людей связаны с помощью адресов, записанных в соответствующие поля father (отец) и mother (мать). Графически это лучше всего выразить с помощью стрелок или указателей (рис. 4.3). Рис. 4.3. Структура данных, связанная указателями Важно подчеркнуть, что использование указателей для реализации рекурсив% ных структур – это всего лишь технический прием. Программисту не обязательно знать об их существовании. Память может распределяться автоматически в тот момент, когда в первый раз используется ссылка на новую компоненту. Но если явно разрешается использование указателей, то можно построить и более общие структуры данных, чем те, которые можно описать с помощью рекурсивных опре% делений. В частности, тогда можно определять потенциально бесконечные или циклические структуры (графы) и указывать, что некоторые структуры исполь% зуются совместно. Поэтому в развитых языках программирования принято разре% шать явные манипуляции не только с данными, но и со ссылками на них. Это тре% бует проведения четкого различия на уровне обозначений между данными и ссылками на данные, а также необходимость иметь типы данных, значениями ко% торых являются указатели (ссылки) на другие данные. Мы будем использовать следующую нотацию для этой цели: TYPE T = POINTER TO T0 Такое определение типа означает, что значения типа T – это указатели на дан% ные типа T0 . Принципиально важно, что тип элементов, на которые ссылается Указатели Динамические структуры данных 172 указатель, очевиден из определения T . Мы говорим, что T связан с T0 . Эта связь отличает указатели в языках высокого уровня от адресов в машинном языке и яв% ляется весьма важным средством повышения безопасности в программировании посредством отражения семантики программы синтаксическими средствами. Значения указательных типов порождаются при каждом динамическом разме% щении элемента данных. Мы будет придерживаться правила, что такое событие всегда должно описываться явно, в противоположность механизму автоматичес% кого размещения элемента данных при первой ссылке на него. С этой целью вве% дем процедуру NEW . Если дана указательная переменная p типа T , то оператор NEW(p) размещает где%то в памяти переменную типа T0 , а указатель на эту новую переменную записывает в переменную p (см. рис. 4.4). Сослаться в программе на само указательное значение теперь можно с помощью p (то есть это значение ука% зательной переменной p ). При этом переменная, на которую ссылается p , обозна% чается как p^ . Обычно используют ссылки на записи. Если у записи, на которую ссылается указатель p , есть, например, поле x , то оно обозначается как p^.x . По% скольку ясно, что полями обладает не указатель, а только запись p^ , то мы допус% каем сокращенную нотацию p.x вместо p^.x Рис. 4.4. Динамическое размещение переменной p^ Выше указывалось, что в каждом рекурсивном типе необходима компонента, позволяющая различать возможные варианты, чтобы можно было обеспечить ко% нечность рекурсивных структур. Пример семейной родословной показывает весь% ма часто встречающуюся ситуацию, когда в одном из двух случаев другие компо% ненты отсутствуют. Это выражается следующим схематическим определением: TYPE T = RECORD IF nonterminal: BOOLEAN THEN S(T) END END S(T) обозначает последовательность определений полей, среди которых есть одно или более полей типа T , чем и обеспечивается рекурсивность. Все структуры типа, определенного по этой схеме, имеют древесное (или списковое) строение, подобное показанному на рис. 4.3. Его особенность – наличие указателей на ком% поненты данных, состоящие только из поля признака, то есть не несущие другой полезной информации. Метод реализации с явными укзателями подсказывает простой способ сэкономить память, разрешив включать информацию о поле при% 173 знака в само указательное значение. Обычно для этого расширяют диапазон значе% ний всех указательных типов единственным значением, которое вообще не являет% ся ссылкой ни на какой элемент. Обозначим это значение специальным символом NIL и постулируем, что все переменные указательных типов могут принимать зна% чение NIL . Вследствие такого расширения диапазона указательных значений ко% нечные структуры могут порождаться при отсутствии вариантов (условий) в их (рекурсивных) определениях. Ниже даются новые формулировки объявленных ранее явно рекурсивных ти% пов данных с использованием указателей. Заметим, что здесь уже нет поля known , так как p.known теперь выражается посредством p = NIL . Переименование типа ped в Person (индивид) отражает изменение точки зрения, произошедшее благо% даря введению явных указательных значений. Теперь вместо того, чтобы сначала рассматривать данную структуру целиком и уже потом исследовать ее подструк% туры и компоненты, внимание сосредоточивается прежде всего на компонентах, а их взаимная связь (представленная указателями) не фиксирована никаким яв% ным определением. TYPE term = POINTER TO TermDescriptor; TYPE exp = POINTER TO ExpDescriptor; TYPE ExpDescriptor = RECORD op: INTEGER; opd1, opd2: term END; TYPE TermDescriptor = RECORD id: ARRAY 32 OF CHAR END TYPE Person = POINTER TO RECORD name: ARRAY 32 OF CHAR; father, mother: Person END Замечание. Тип Person соответствует указателям на записи безымянного типа ( PersonDescriptor ). Структура данных, представляющая родословную и показанная на рис. 4.2 и 4.3, снова показана на рис. 4.5, где указатели на неизвестных лиц обозначены констан% той NIL . Получающаяся экономия памяти очевидна. В контексте рис. 4.5 предположим, что Fred и Mary – брат и сестра, то есть у них общие отец и мать. Эту ситуацию легко выразить заменой двух значений NIL в соответствующих полях двух записей. Реализация, которая скрывает указатели Рис. 4.5. Структура данных с указателями, имеющими значение NIL Указатели Динамические структуры данных 174 или использует другие приемы работы с памятью, заставила бы программиста представить записи для родителей, то есть Adam и Eva , дважды. Хотя для чтения данных не важно, одной или двумя записями представлены два отца (или две ма% тери), разница становится существенной, когда разрешено частичное изменение данных. Трактовка указателей как явных элементов данных, а не как скрытых средств реализации, позволяет программисту четко указать, где нужно совмес% тить используемые блоки памяти, а где – нет. Другое следствие явных указателей – возможность определять и манипулиро% вать циклическими структурами данных. Разумеется, такая дополнительная гиб% кость не только предоставляет дополнительные возможности, но и требует от программиста повышенного внимания, поскольку работа с циклическими струк% турами данных легко может привести к бесконечным процессам. Эта тесная связь мощи и гибкости средств с опасностью их неправильного использования хорошо известна в программировании и заставляет вспомнить оператор GOTO . В самом деле, если продолжить аналогию между структурами программ и данных, то чисто рекурсивные структуры данных можно сопоста% вить с процедурами, а введение указателей сравнимо с операторами GOTO . Ибо как оператор GOTO позволяет строить любые программные схемы (включая циклы), так и указатели позволяют строить любые структуры данных (включая кольцевые). [Однако в отличие от операторов GOTO , типизированные указатели не нарушают структурированности соответствующих записей – прим. перев.] Параллели между структурами управления и структурами данных суммирова% ны в табл. 4.1. Таблица 4.1. Таблица 4.1. Таблица 4.1. Таблица 4.1. Таблица 4.1. Соответствия структур управления и структур данных Схема построения Схема построения Схема построения Схема построения Схема построения Оператор программы Оператор программы Оператор программы Оператор программы Оператор программы Тип данных Тип данных Тип данных Тип данных Тип данных Неделимый элемент Присваивание Скалярный тип Перечисление Операторная Запись последовательность Повторение (число Оператор for Массив повторений известно) Выбор Условный оператор Объединение типов (запись с вариантами) Повторение Оператор while или Последовательностный тип repeat Рекурсия Процедура Рекурсивный тип данных Общий граф Оператор перехода Структура, связанная указателями В главе 3 мы видели, что итерация является частным случаем рекурсии и что вы% зов рекурсивной процедуры P , определенной в соответствии со следующей схемой, PROCEDURE P; BEGIN IF B THEN P0; P END END 175 где оператор P0 не включает в себя P и может быть заменен на эквивалентный опе% ратор цикла WHILE B DO P0 END Аналогии, представленные в табл. 4.1, подсказывают, что похожая связь долж% на иметь место между рекурсивными типами данных и последовательностью. В самом деле, рекурсивный тип, определенный в соответствии со схемой TYPE T = RECORD IF b: BOOLEAN THEN t0: T0; t: T END END где тип T0 не имеет отношения к T , может быть заменен на эквивалентную после% довательность элементов типа T0 Остальная часть этой главы посвящена созданию и работе со структурами дан% ных, компоненты которых связаны с помощью явных указателей. Особое внима% ние уделяется конкретным простым схемам; из них можно понять, как работать с более сложными структурами. Такими простыми схемами являются линейный список (простейший случай) и деревья. Внимание, которое мы уделяем этим средствам структурирования данных, не означает, что на практике не встречают% ся более сложные структуры. Следующий рассказ, опубликованный в цюрихской газете в июле 1922 г., доказывает, что странности могут встречаться даже в тех случаях, которые обычно служат образцами регулярных структур, таких как (генеа% логические) деревья. Мужчина жалуется на свою жизнь следующим образом: Я женился на вдове, у которой была взрослая дочь. Мой отец, который часто нас навещал, влюбился в мою приемную дочь и женился на ней. Таким образом, мой отец стал моим зятем, а моя приемная дочь стала моей мачехой. Через несколько месяцев моя жена родила сына, который стал сводным братом моему отцу и моим дядей. Жена моего отца, то есть моя приемная дочь, тоже родила сына, который стал мне братом и одновременно внуком. Моя жена стала мне бабушкой, так как она мать моей мачехи. Следовательно, я муж моей жены и в то же время ее прием ный внук; другими словами, я сам себе дедушка. |