Основы программирования Динамические массивы. Списки. Ассоциативные массивы. Деревья. Хеш-таблицы. Методические указания для студентов 1 курса факультета математики, механики и компьютерных наук

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Федеральное государственное образовательное учреждение высшего профессионального образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

С.С. Михалкович

Основы программирования Динамические массивы. Списки. Ассоциативные массивы. Деревья. Хеш-таблицы

МЕТОДИЧЕСКИЕ УКАЗАНИЯ для студентов 1 курса факультета математики, механики и компьютерных наук

Ростов-на-Дону 2007 3

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

Печатается в соответствии с решением кафедры алгебры и дискретной математики факультета математики, механики и компьютерных наук ЮФУ, протокол № 3 от 13 ноября 2006 г. 4

1 Класс «Динамический массив» Сформулируем основные требования к классу «Динамический массив». Объекты этого класса должны вести себя как массивы, т.е. представлять собой набор элементов, доступ к которым осуществляется по индексу. Размер такого массива задается при создании объекта и может меняться в процессе работы программы. Договоримся также, что индексация будет производиться с нуля. Как и в случае класса «Очередь», будем обозначать тип элементов динамического масссива через DataType. Например, динамический массив целых поместим в модуль IntArray и положим DataType=integer. Класс динамического массива назовем DynArray. При использовании в программе динамических массивов с элементами разных типов будем уточнять имя типа именем модуля: IntArray.DynArray или RealArray.DynArray. 1.1 Предварительный интерфейс класса «Динамический массив» Составим предварительный вариант интерфейса класса DynArray: type DynArray=class public constructor Create(n: integer); destructor Destroy; procedure Resize(newsize: integer); procedure Reserve(newcap: integer); function Size: integer; function Capacity: integer; procedure Add(x: DataType); procedure TrimToSize; function GetItem(i: integer): DataType; procedure SetItem(i: integer; x: DataType); end; Конструктор Create создает динамический массив с n элементами, индексируемый от нуля, деструктор Destroy разрушает его. Функция Size возвращает количество элементов в массиве, процедура Resize устанавливает количество элементов равным newsize, а процедура Add добавляет элемент x в конец массива, увеличивая размер массива на 1. Функция GetItem(i) возвращает значение i-го элемента массива, а процедура SetItem(i,x) устанавливает значение i-го элемента массива равным x; если индекс i находится вне диапазона 0..Size-1, то генерируется исключение. Как уже говорилось, размер динамического массива может постоянно меняться по ходу работы программы. Например, при добавлении элемента размер увеличивается на 1. Задумаемся, однако, как должен быть реализован метод Re5

size. Рассмотрим два противоположных подхода. Первый подход заключается в следующем: под массив отводится максимально возможная память, а при изменении размера меняется только значение закрытого поля, хранящего текущий размер массива. Это решение – эффективное по скорости, но расточительное по памяти. Второй подход – всякий раз выделяется память, размер которой совпадает с размером массива. Такое решение эффективно по памяти, но крайне неэффективно по скорости работы. Действительно, при каждом изменении размера надо создавать новый участок памяти, копировать в него содержимое старого массива и освобождать старый участок памяти. К примеру, если массив состоит из 1000 элементов, то при добавлении одного элемента необходимо выделить память под 1001 элемент, скопировать 1000 элементов в эту память и освободить старую память. Как известно, истина находится посередине между полярными мнениями. Обычно выбирается следующая стратегия изменения размера динамического массива. В начальный момент времени под массив отводится память, превосходящая его размер. Если при выполнении Resize новый размер не превосходит выделенную память, то просто меняется внутреннее поле, характеризующее размер. В противном случае выделяется новая память, происходит копирование старого содержимого в новую память и старое содержимое освобождается. Размер выделяемой памяти должен превосходить новый размер массива с прицелом на дальнейшее увеличение. Обычно принимают следующую стратегию: выделяют память, в 2 раза превосходящую запрашиваемый размер. Назовем метод, ответственный за выделение памяти, именем Reserve. Отметим, что выделенная память не инициализируется нулями, поэтому за ее инициализацию ответственна клиентская программа. Таким образом, динамический массив характеризуется не только своим размером Count, но и так называемой емкостью Capacity, определяющей количество элементов, под которые выделена память. В любой момент времени Size<=Capacity. Если вызывается Resize(newsize) с newsize<=Capacity, то Size просто устанавливается равным newsize, в противном случае вначале резервируется новая память, в 2 раза превосходящая затребованный размер: Reserve(2*newsize). Заметим, что, согласно нашим договоренностям, при уменьшении размера массива новая память не выделяется. Таким образом, память, отводимая под массив, в течение его существования может только расти. В реальных же задачах нередка ситуация, когда размер массива в начале программы может быть значительным, а в конце – маленьким. Например, в поисковой системе мы вначале отбираем 1000 сайтов, удовлетворяющих запросу, а потом выбираем из них 10 лучших, и потом работаем только с ними. В этой ситуации следует предусмотреть возможность уменьшения объема выделяемой под массив памяти. Наиболее простая реализация заключается в следующем: в интерфейс класса вводят метод 6

TrimToSize, при вызове которого размер выделенной памяти уменьшается до размера массива.

1.2 Реализация класса «Динамический массив» Итак, добавим в интерфейс динамического массива процедуры Reserve(newcap), TrimToSize и функцию Capacity. Для реализации данного интерфейса добавим в закрытую секцию класса поля sz и cap, отвечающие соответственно за размер и емкость массива, а также указатель data на массив элементов типа DataType максимально возможного размера (см.п. …). Приведем реализацию класса «Динамический массив целых», представленную в виде модуля IntArray. unit IntArray; interface type DataType=integer; // может быть изменен на любой другой тип const MaxSize = MaxInt div sizeof(DataType); type Arr = array [0..MaxSize-1] of DataType; PArr = ^Arr; type DynArray = class private data: PArr; sz,cap: integer; public constructor Create(n,cp: integer); overload; constructor Create(n: integer); overload; constructor Create; overload; destructor Destroy; procedure Resize(newsize: integer); procedure Reserve(newcap: integer); function Size: integer; function Capacity: integer; procedure TrimToSize; procedure Add(x: DataType); function GetItem(i: integer): DataType; procedure SetItem(i: integer; x: DataType); end; implementation 7

constructor DynArray.Create(n,cp: integer); begin sz:=n; cap:=cp; if cap<sz then cap:=sz; if cap=0 then cap:=4; GetMem(data,cap*sizeof(DataType)); end; constructor DynArray.Create(n: integer); begin Create(n,n); end; constructor DynArray.Create; begin Create(0); end; destructor Destroy; begin FreeMem(data); data:=nil; sz:=0; cap:=0; end; procedure DynArray.Reserve(newcap: integer); var data1: PIntArr; begin Assert(newcap>0,’Размер резервируемой памяти должен быть >0’); if newcap<=cap then exit; GetMem(data1,newcap*sizeof(DataType)); Move(data,data1,sz*sizeof(DataType)); cap:=newcap; FreeMem(data); data:=data1; end; procedure DynArray.Resize(newsize: integer); begin Assert(newsize>=0,’Размер массива не может быть <0’); if newsize=sz then exit; sz:=newsize; if sz>cap then 8

Reserve(2*sz); end; function DynArray.Size: integer; begin Result:=sz; end; function DynArray.Capacity: integer; begin Result:=cap; end; procedure TrimToSize; var data1: PIntArr; begin cap:=sz; if cap=0 then cap:=4; GetMem(data1,cap*sizeof(DataType)); Move(data,data1,sz*sizeof(DataType)); FreeMem(data); end; procedure Add(x: DataType); begin Resize(Count+1); data^[Count-1]:=x; end; procedure DynArray.SetItem(i: integer; x: DataType); begin Assert((i>=0) and (i<sz), ’Выход за границы массива ’+IntToStr(i)); data^[i]:=x; end; function DynArray.GetItem(i: integer): DataType; begin Assert((i>=0) and (i<sz), ’Выход за границы массива: ’+IntToStr(i)); Result:=data^[i]; end; end. Поясним реализацию некоторых методов. Класс DynArray имеет три перегруженных конструктора, объявленых с использованием зарезервированного слова overload. В первом конструкторе массива указывается его первоначальный 9

размер и емкость. Если емкость меньше размера, то она устанавливается равной размеру, а если размер равен 0, то емкость полагается равной 4 элементам. Второй конструктор с одним параметром создает динамический массив с емкостью, равной размеру. Он предназначен для массивов, для которых маловероятно дальнейшее увеличение размера. Наконец, третий конструктор (без параметров) создает динамический массив с нулевым размером. Предполагается, что размер такого массива станет известен далее при выполнении программы. Следует обратить внимание, что во втором конструкторе первый конструктор вызывается как обычная процедура. Здесь проявляется двойственная природа конструктора: при конструировании объекта он вызывается как функция, возвращающая сконструированный объект, а если объект создан, то конструктор может быть вызван как обычная процедура для выполнения инициализации полей объекта. В методах Resize и TrimToSize под содержимое массива выделяется новая память, и старое содержимое копируется в нее при помощи стандартной процедуры Move. Помимо указанного набора методов, в класс DynArray уместно также включить следующие методы: function ToString: AnsiString; function IndexOf(x: DataType): integer; function LastIndexOf(x: DataType): integer; procedure Sort; procedure Reverse; procedure ForEach(p: Proc); Функция ToString преобразует содержимое массива к строковому представлению. Функции IndexOf и LastIndexOf возвращают соответственно индекс первого и последнего элемента, равного x, а если элемент не найден, то возвращается -1. Процедура Sort сортирует элементы массива по возрастанию, используя для сравнения операцию <, процедура Reverse обращает элементы массива. Процедура ForEach применяет к каждому элементу массива процедуру p типа Proc=procedure (var elem: DataType). Для числовых типов можно также добавить методы, вычисляющие сумму и среднее: function Sum: DataType; function Average: real;

1.3 Свойства классов

10

В Delphi Pascal можно определять так называемые свойства классов. Свойства являются расширениями полей классов. При использовании они имеют тот же синтаксис, что и поля, однако не связаны с конкретной областью памяти. Вместо этого, свойства имеют специальные методы доступа, обеспечивая возможность доступа к приватным полям класса и позволяющие при их чтении или записи производить дополнительные действия. Например, пусть имеется класс MyClass с закрытым полем p типа integer. Для доступа к нему на чтение опишем метод-функцию без параметров, возвращающую тот же тип, что и тип поля: function MyClass.GetP: integer; begin Некоторые дополнительные действия Result:=p; end; Для доступа к нему на запись опишем метод-процедуру с одним параметром того же типа, что и тип поля: procedure MyClass.SetP(value: integer); begin Проверка допустимости значения value if p<>value then begin p:=value; Некоторые дополнительные действия end; end; Назовем свойство, связанное с полем p, именем MyProp. Оно описывается в теле класса следующим образом: type MyClass = class private p: integer; function GetP: integer; procedure SetP(value: integer); public property MyProp: integer read GetP write SetP; end; Такая запись говорит о том, что при доступе к свойству MyProp на чтение вызывается метод GetP, а при доступе на запись – метод SetP. Использование свойств идентично использованию полей классов: var A: MyClass; 11

begin ... A.MyProp:=A.MyProp+1; Здесь при использовании записи A.MyProp в правой части оператора присваивания вызывается метод GetP, а в левой – метод SetP. Таким образом, последнее присваивание эквивалентно следующему: A.SetP(A.GetP+1); Отметим, что свойства нельзя передавать в подпрограмму по ссылке. Например, следующая запись ошибочна: Inc(A.MyProp). Вместо нее следует использовать приведенную выше запись: A.MyProp:=A.MyProp+1. Причина проста: при передаче параметра по ссылке в подпрограмму в действительности передается адрес переменной, а свойство напрямую не представляет объект в памяти и поэтому не имеет адреса. Отметим также, что свойства доступа на чтение и запись обычно являются вспомогательными методами, и их принято помещать в закрытую секцию класса. Отметим также, что при описании свойств либо секция read, либо секция write может отсутствовать. Соответственно мы получим свойства с доступом только на запись или только на чтение. Наконец, если при доступе к полю не требуется проводить никаких дополнительных действий, то при описании свойства вместо соответствующего метода можно указать имя поля, например: property MyProp: integer read p write SetP; В подавляющем большинстве случаев доступ на чтение не требует дополнительных действий, поэтому последняя форма описания свойств – самая распространенная. Дополнительные действия могут проводиться как в начале, так и в конце метода. Обычно в начале метода доступа на запись перед присваиванием закрытому полю производится контроль входного параметра на принадлежность к заданному диапазону и в случае его несоответствия диапазону может либо генерироваться исключение, либо параметр автоматически исправляется для соответствия диапазону. Например: procedure MyClass.SetP(pp: integer); begin if pp<0 then pp:=0; if p<>pp then p:=pp; end; Если класс представляет объект, отображаемый на экране, а свойство – его визуальный параметр, то в конце метода после присваивания закрытому полю выполняются действия по перерисовке объекта, например: type 12

MyDrawClass = class private w: integer; procedure SetWidth(ww: integer); public procedure Draw; property MyProp: integer read w write SetWidth; end; procedure MyDrawClass.SetWidth(ww: integer); begin if w<>ww then begin w:=ww; Draw; end; end; Применим полученные знания к классу DynArray. Заменим метод Size на свойство Size, указав для доступа на чтение поле sz, а для доступа на запись – метод Resize: property Size: integer read sz write Resize; Аналогично можно определить свойство Capacity, представляющее емкость массива: property Capacity: integer read cap write Reserve;

1.4 Индексные свойства классов Индексные свойства являются расширениями полей-массивов. Как и обычные свойства, они не связаны с конкретной областью памяти и через специальные методы обеспечивают доступ к приватным полям на чтение и запись. Описание индексного свойства имеет вид: property ИмяСвойства[CписокОписанийИндексов]: ТипСвойства read GetProp write SetProp; Здесь CписокОписанийИндексов имеет ту же форму, что и список формальных параметров подпрограмм, методы GetProp и SetProp должны иметь следующие заголовки: function GetProp(CписокОписанийИндексов): ТипСвойства; procedure SetProp(CписокОписанийИндексов; x: ТипСвойства); Для класса DynArray создадим индексное свойство Items: property Items[i: integer]: DataType read GetItem write SetItem; 13

После такого описания мы сможем обращаться к элементам массива, используя данное индексное свойство: a.Items[1]:=a.Items[0]+5; Последняя запись эквивалентна следующей: a.SetItem(1,a.GetItems(0)+5); Отметим, что после описания свойства Items методы GetProp и SetProp должны быть помещены в приватную секцию. Класс может иметь несколько индексных свойств. Одно из них может быть сделано свойством по умолчанию, для чего в конце его описания необходимо добавить зарезервированное слово default: property Items[i: integer]: DataType read GetItem write SetItem; default; Индексное свойство по умолчанию может быть использовано без указания его имени: запись a.Items[0] эквивалентна записи a[0], и последнее присваивание может быть записано в виде: a[1]:=a[0]+5; Таким образом, индексные свойства по умолчанию позволяют использовать для объектов класса синтаксис массивов.

1.5 Клиентская программа для динамического массива В следующей программе иллюстрируется большинство возможностей динамических массивов. В массив a заносятся вводимые целые положительные числа, признаком конца ввода является число 0. Далее массив a сортируется по возрастанию и обращается. Затем его содержимое переносится в массив b, и элементы массива b удваиваются. uses IntArray; procedure MultBy2(var i: integer); begin i:=2*i; end; var a,b: DynArray; begin a:=DynArray.Create(0,10); repeat read(x); if x=0 then break; a.Add(x); until False; a.TrimToSize; 14

a.Sort; a.Reverse; writeln(a.ToString); b:=DynArray.Create(a.Count); for i:=0 to a.Count-1 do b[i]:=a[i]; b.ForEach(MultBy2); writeln(b.ToString); b.Destroy; a.Destroy; end. Следует обратить внимание на стратегию создания массивов. Массив a создается вызовом конструктора DynArray.Create(0,10): вначале он имеет нулевой размер и под него резервируется память на 10 элементов. Использование данного конструктора означает, что размер массива будет изменяться по ходу работы программы и в большинстве случаев не превысит 10 элементов. Действительно, мы вводим элементы до нулевого и добавляем их в массив, используя функцию Add, увеличивающую размер массива на 1. Первый раз перераспределение памяти произойдет, если размер массива станет больше 10, второй раз – больше 20 и т.д. По окончании заполнения массива a мы вызываем метод a.TrimToSize, что означает, что размер массива a далее в программе меняться не будет. После этого мы создаем массив b, в который копируем содержимое массива a. Поскольку далее размер массива b меняться не будет, то для его создания мы используем конструктор DynArray.Create(a.Count), выделяющий память, совпадающую с размером массива.

2 Класс «Список» на базе двусвязного списка Сформулируем основные требования к классу «Список». Объекты этого класса представляют собой последовательности элементов. По элементам списка должен обеспечиваться последовательный проход в обоих направлениях – от первого элемента к последнему и от последнего к первому. В отличие от массива, к элементам списка нет доступа по индексу, однако предоставляется возможность вставки и удаления элементов в начале, середине и конце списка. Очевидно, что в качестве реализации списка мы выберем структуру данных «Линейный односвязный список». Напомним, что она состоит из элементов вида type PNode=^Node; Node=record data: DataType; 15

prev,next: PNode; end; где тип DataType определен ранее. Будем далее для определенности считать, что DataType=integer и что все описания производятся в модуле IntList. Отметим, что интерфейс класса «Список» должен предоставлять доступ только к полям данных, но не к полям связей. Будем хранить в классе списка указатели на первый, последний и текущий элемент. Все методы разобьем на четыре группы. К первой группе отнесем основные методы – конструктор, деструктор, проверку списка на пустоту, вставку в начало и конц, удаление из начала и конца. Вторую группу образуют вспомогательные методы: значение первого и последнего элемента, поиск элемента и удаление всех его вхождений, а также преобразование содержимого списка в строку. Третья группа методов управляет указателем на текущий элемент, который принято называть внутренним итератором по той причине, что с его помощью можно производить итерацию (цикл) по элементам списка. Помимо свойства, осуществляющего доступ к значению текущего элемента на чтение и запись, здесь присутствуют методы передвижения внутреннего итератора на следующий и предыдущий элемент, на первый и последний элемент, а также метод проверки итератора на пустоту, которая трактуется как достижение итератором конца списка. Наконец, в последней, четвертой группе находятся методы вставки и удаления элемента в позиции текущего указателя. Далее приводится интерфейс класса «Список». type DataType=integer; PNode=^TNode; TNode=record data: DataType; prev,next: PNode; end; List = class private f: PNode; // указатель на первый узел списка l: PNode; // указатели на последний узел списка cur: PNode; // указатель на текущий узел списка function GetData: DataType; procedure SetData(d: DataType); public // Основные методы constructor Create; destructor Destroy; procedure AddFirst(x: DataType); 16

procedure AddLast(x: DataType); procedure DeleteFirst; procedure DeleteLast; function IsEmpty: boolean; // Вспомогательные методы function First: DataType; // первый элемент function Last: DataType; // последний элемент // преобразование содержимого списка в строку function ToString: Ansistring; function Find(x: DataType): boolean; // есть ли x procedure Remove(x: DataType); // удалить все x // Методы, реализующие внутренний итератор property Current: DataType read GetData write SetData; // значение текущего элемента procedure MoveFirst; // итератор - на начало procedure MoveLast; // итератор - на конец procedure Next; //итератор - на следующий элемент procedure Prev;//итератор - на предыдущий элемент function Eol: boolean; // конец списка? // Если Eol=True, то текущий элемент не определен public // Вставка и удаление в позиции внутреннего итератора // вставка в позиции перед итератором procedure InsertBefore(x: DataType); // вставка в позиции после итератора procedure InsertAfter(x: DataType); procedure Delete; // удаление в позиции итератора end; Действие методов понятно из комментариев. Единственный вопрос, который следует пояснить, – как ведет себя указатель на текущий элемент при операциях вставки и удаления. Этот вопрос может решаться по-разному. В данной реализации принято следующее решение. При любых операциях вставки указатель на текущий элемент не изменяется. При удалении текущего элемента указатель на текущий перемещается на следующий элемент, а если он отсутствует, то на предыдущий. Если же после удаления элемента список становится пустым, то указатель на текущий элемент получает значение nil. Тем самым внутренний итератор продолжает указывать на какой-то элемент списка «до последнего». Отметим, что наш класс имеет «жирный» интерфейс. Это означает, что в его интерфейсе содержится множество методов, которые можно разбить на группы, каждая из которых взаимодействует не со всеми, а лишь с подмножеством полей класса. Например, методы, реализующие внутренний итератор, взаимодействуют только с полем cur и не затрагивают остальные поля. 17

2.1 Клиентские приложения для класса «Список» Задача 1. Заполнить список десятью случайными целыми числами и вывести его. Решение. Достаточно использовать только основные и вспомогательные методы: uses IntList; var L: List; begin Randomize; L:=List.Create; for i:=1 to 10 do L.AddLast(Random(100)); writeln(L.ToString); L.Destroy; end. Задача 2. Дан список целых. После каждого четного элемента вставить элемент, равный удвоенному значению предыдущего элемента. Решение. Воспользуемся перемещением по списку с помощью внутреннего итератора. Приведем решение, считая, что список уже создан и заполнен: L.MoveFirst; while not L.Eol do begin if L.Current mod 2 = 0 then begin L.InsertAfter(2*L.Current); L.Next; // передвинуться на вставленный элемент end; L.Next; end; Задача 3. Дан список целых. Удалить все элементы, стоящие на четных местах. Решение. Будем использовать тот факт, что после удаления элемента внутренний итератор передвигается на следующий элемент: L.MoveFirst; while not L.Eol do begin L.Next; if not L.Eol then L.Delete; end; 18

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

2.2 Реализация методов класса «Список» Приведем реализацию методов класса Список с учетом всех сделанных выше замечаний о поведении внутреннего итератора при операциях вставки и удаления. function NewNode(x: DataType; prev,next: PNode): PNode; begin New(Result); Result.data:=x; Result.prev:=prev; Result.next:=next; end; // Основные методы constructor List.Create; begin f:=nil; l:=nil; сur:=nil; end; destructor List.Destroy; begin while not IsEmpty do DeleteFirst; end; procedure List.AddFirst(x: DataType); begin f:=NewNode(x,nil,f); if f.next<>nil then f.next.prev:=f; if l=nil then l:=f; end; procedure List.AddLast(x: DataType); begin l:=NewNode(x,l,nil); 19

if l.prev<>nil then l.prev.next:=l; if f=nil then f:=l; end; procedure List.DeleteFirst; var v: PNode; begin Assert(not IsEmpty); v:=f; f:=f.next; if cur=v then cur:=f; Dispose(v); if f<>nil then f.prev:=nil else l:=nil; end; procedure List.DeleteLast; var v: PNode; begin Assert(not IsEmpty); v:=l; l:=l.prev; if cur=v then cur:=l; Dispose(v); if l<>nil then l.next:=nil else f:=nil end; function List.IsEmpty: boolean; begin Result:= f=nil; end; // Вспомогательные методы function List.First: DataType; begin Assert(not IsEmpty); Result:=f.data; end; 20

function List.Last: DataType; begin Assert(not IsEmpty); Result:=l.data; end; function List.ToString; var v: PNode; begin v:=f; Result:=''; while v<>nil do begin Result:=Result+IntToStr(v.data)+' '; v:=v.next; end; end; function List.Find(x: DataType): boolean; var v: PNode; begin v:=f; Result:=False; while v<>nil do begin if v.data=x then begin Result:=True; break; end; v:=v.next; end; end; procedure List.Remove(x: DataType); begin MoveFirst; while not Eol do if Current=x then Delete else Next; end; // Методы, реализующие внутренний итератор function List.GetData: DataType; begin 21

Assert(cur<>nil); Result:=cur.data; end; procedure List.SetData(d: integer); begin Assert(cur<>nil); cur.data:=d; end; procedure List.Next; begin Assert(cur<>nil); cur:=cur.next; end; procedure List.Prev; begin Assert(cur<>nil); cur:=cur.prev; end; function List.Eol: boolean; begin Result:= cur=nil; end; procedure List.MoveFirst; begin cur:=f; end; procedure List.MoveLast; begin cur:=l; end; // Методы, осуществляющие вставку и удаление // в позиции внутреннего итератора procedure List.InsertBefore(x: DataType); var v: PNode; begin Assert(cur<>nil); if cur=f then AddFirst(x) else begin v:=NewNode(x,cur.prev,cur); 22

cur.prev.next:=v; cur.prev:=v; end end; procedure List.InsertAfter(x: DataType); var v : PNode; begin Assert(cur<>nil); if cur=l then AddLast(x) else begin v:=NewNode(x,cur,cur.next); cur.next.prev:=v; cur.next:=v; end end; procedure List.Delete; var v: PNode; begin Assert(cur<>nil); if cur=f then DeleteFirst else if cur=l then DeleteLast else begin v:=cur; cur.prev.next:=cur.next; cur.next.prev:=cur.prev; cur:=cur.next; Dispose(v) end end; Сделаем несколько замечаний по реализации. В методе InsertBefore, если осуществляется вставка перед первым элементом, то мы просто вызываем метод AddFirst. Аналогично в методе InsertAfter мы пользуемся уже написанным методом AddLast, если осуществляется вставка в конец. В методе Delete мы также частично пользуемся уже написанными методами: если удаляется первый элемент, мы просто вызываем DeleteFirst, а при удалении последнего – DeleteLast. Наконец, метод Remove целиком состоит из вызовов других методов и не обращается к приватным полям класса List. В реализации Remove следует обратить внимание на то, что метод Delete также продвигает 23

указатель на текущий элемент вперед, поэтому действие Next осуществляется фактически и по ветке then и по ветке else условного оператора. Методы, целиком реализованные с помощью вызова других методов, имеют особый статус. Поскольку такие методы не осуществляют доступа к приватным полям класса, то они могут быть реализованы с помощью внешних подпрограмм. Например, метод Remove может быть реализован следующим образом: procedure Remove(L: List; x: DataType); begin L.MoveFirst; while not L.Eol do if L.Current=x then L.Delete else L.Next; end; Считается, что такая реализация повышает защиту доступа, поскольку уменьшает количество методов, имеющих доступ к приватной секции класса.

2.3 Реализация одного АТД на базе другого. Делегирование Один АТД может быть реализован на базе другого АТД. Для этого в класс, определяющий такой тип данных, помещают приватное поле-объект другого класса, после чего вызовы всех методов переадресуются данному внутреннему объекту. При этом внутренний объект может иметь другие имена методов. Говорят, что объект делегирует выполнение операций своему внутреннему подобъекту, а делегированием называют переадресацию выполнения действий другому объекту. Так, приведенная ниже реализация стека делегирует выполнение всех операций внутреннему объекту класса «Список». type Stack = class private L: List; public constructor Create; destructor Destroy; procedure Push(i: integer); function Pop: integer; function Top: integer; function IsEmpty: boolean; end; constructor Stack.Create; begin 24

L:=List.Create; end; destructor Stack.Destroy; begin L.Destroy; end; procedure Stack.Push(i: integer); begin L.AddLast(i); end; function Stack.Pop: integer; begin Result:=L.Last; L.DeleteLast; end; function Stack.Top: integer; begin Result:=L.Last; end; function Stack.IsEmpty: boolean; begin Result:=L.IsEmpty; end;

2.4 Класс «Список» с внешним итератором Внешний итератор – это некоторый обобщенный указатель на элементы контейнера, реализуемый в виде внешнего класса. Он инициализируется контейнером и при инициализации устанавливается в начало контейнера. Он может передвигаться по элементам контейнера в прямом или обратном порядке. Наконец, в позиции итератора можно вставлять и удалять элементы. Напомним, что интерфейс класса «Список» из предыдущего пункта является «жирным» и содержит группу методов для работы с внутренним итератором, а также для вставки и удаления в позиции итератора. Переместим эти методы во внешний итератор, разбив таким образом класс списка на два более легковесных класса. При этом из класса «Список» в класс итератора списка перейдет приватное поле-указатель на текущий элемент списка. В класс итератора добавим также поле-указатель на список. Кроме этого, переименуем свойство Current в Data (поскольку итератор представляет один элемент списка, его бессмысленно называть Current) и добавим в интерфейс итератора метод Assign(it), копирующий в итератор, вызвавший данный метод, внутренние поля итератора it. 25

Приведем интерфейсы классов «Список» и «Итератор списка»: type List = class private f,l: PNode; public constructor Create; destructor Destroy; procedure AddFirst(x: DataType); procedure AddLast(x: DataType); procedure DeleteFirst; procedure DeleteLast; function IsEmpty: boolean; function ToString: string; function Find(x: DataType): boolean; procedure Remove(x: DataType); end; ListIterator = class private L: List; cur: PNode; function GetData: DataType; procedure SetData(d: integer); public constructor Create(LL: List); procedure Assign(it: ListIterator); procedure MoveFirst; procedure MoveLast; procedure Next; procedure Prev; function Eol: boolean; property Data: DataType read GetData write SetData; procedure InsertBefore(x: DataType); procedure InsertAfter(x: DataType); procedure Delete; end; Таким образом, за вставку и удаление из начала и конца отвечает класс списка, а за вставку и удаление в середине – класс его итератора. Отметим также, что разделение на два класса позволило нам избавиться от основного недостатка предыдущей версии списка – «жирного» интерфейса. 26

Методы в новом варианте класса List реализуются так же, как и одноименные методы в прежнем варианте с внутренним итератором. Необходимо внести лишь два изменения. Во-первых, в телах методов убираются все операторы, содержащие действия с полем cur. Во-вторых, в реализации метода Remove внутренний итератор заменяется на внешний: procedure List.Remove(x: DataType); var it: ListIterator; begin it:=ListIterator.Create(Self); while not it.Eol do if it.Data=x then it.Delete(x) else it.Next; it.Destroy; end; Реализация методов в классе ListIterator также практически идентична реализации одноименных методов списка с внутренним итератором с тем исключением, что все вхождения полей f и l заменяются на L.f и L.l: constructor ListIterator.Create(LL: List); begin L:=LL; cur:=L.f; end; function ListIterator.GetData: DataType; begin Assert(cur<>nil); Result:=cur.data end; procedure ListIterator.SetData(d: integer); begin Assert(cur<>nil); cur.data:=d end; procedure ListIterator.Assign(it: ListIterator); begin cur:=it.cur; L:=it.L; end; procedure ListIterator.Next; begin Assert(cur<>nil); 27

cur:=cur.next end; procedure ListIterator.Prev; begin Assert(cur<>nil); cur:=cur.prev end; function ListIterator.Eol: boolean; begin Result := cur=nil end; procedure ListIterator.MoveFirst; begin cur:=L.f; end; procedure ListIterator.MoveLast; begin cur:=L.l; end; procedure ListIterator.InsertBefore(x: DataType); var v: PNode; begin Assert(cur<>nil); if cur=L.f then L.AddFirst(x) else begin v:=NewNode(x,cur.prev,cur); cur.prev.next:=v; cur.prev:=v; end end; procedure ListIterator.InsertAfter(x: DataType); var v: PNode; begin Assert(cur<>nil); if cur=L.l then L.AddLast(x) else begin v:=NewNode(x,cur,cur.next); 28

cur.next.prev:=v; cur.next:=v; end end; procedure ListIterator.Delete; var v: PNode; begin Assert(cur<>nil); if cur=L.f then begin L.DeleteFirst; cur:=L.f; end else if cur=L.l then begin L.DeleteLast; cur:=L.l; end else begin v:=cur; cur.prev.next:=cur.next; cur.next.prev:=cur.prev; cur:=cur.next; Dispose(v); end end; Отметим небольшое изменение кода в Delete: после L.DeleteFirst вызывается cur:=L.f, а после L.DeleteLast вызывается cur:=L.l (ранее эти действия выполнялись непосредственно внутри DeleteFirst и DeleteLast поскольку итератор был внутренним). Отметим также, что в методах класса ListIterator мы осуществляем доступ к закрытым полям f и l класса List. Напомним, что это возможно, поскольку классы List и ListIterator определены в одном модуле.

29

2.5 Клиентское приложение для списка с внешним итератором Задача. Дан список целых. Найти два наиболее близких элемента. Решение. Для решения заведем два итератора, которые будут пробегать список во вложенных циклах. Чтобы каждый элемент сравнивался с каждым, достаточно, чтобы второй итератор пробегал элементы списка от элемента, следующего за тем, на который указывает первый итератор, до последнего. Обратим внимание, что для этого нам понадобится метод итератора Assign, который присваивает поля L и cur одного итератора соответствующим полям другого итератора: uses IntList; var L: List; it1,it2: ListIterator; a,b,i,s,m: integer; begin L := List.Create; it1 := ListIterator.Create(L); it2 := ListIterator.Create(L); Randomize; for i:=1 to 10 do L.AddFirst(Random(100)); writeln(L1.ToString); m:=MaxInt; while not it1.Eol do begin it2.Assign(it1); it2.Next; while not it2.Eol do begin s:=abs(it1.Data-it2.Data); if s<m then begin m:=s; a:=it1.Data; b:=it2.Data; end; it2.Next; end; it1.Next; end; writeln(a,' ',b); 30

it1.Destroy; it2.Destroy; L.Destroy; end. Данный пример показывает, что реализация списка с внешним итератором является более гибкой. Она не только ликвидирует «жирность» интерфейса класса «Список», но и позволяет решать более сложные задачи, требующие использования нескольких указателей на элементы одного списка. К недостаткам этой реализации отнесем необходимость явного вызова конструкторов и деструкторов для всех итераторов. Отметим также, что если список будет разрушен до разрушения итератора, то последующее использование итератора приведет к аварийному завершению программы.

3 Ассоциативные массивы Ассоциативный массив – это АТД, к объектам которого можно обращаться как к одномерному массиву, индекс которого может иметь произвольный тип (в частности, строковый). Например, для ассоциативного массива zoo, хранящего количество животных каждого вида в зоопарке, допустимо следующее обращение к его элементу: zoo['Крокодил']:=3; Простейший способ хранения ассоциативных массивов – список пар (Ключ, Значение), где Ключ определяет индекс элемента, а Значение – значение элемента с этим индексом. Так, ассоциативный массив zoo, представленный списком пар, хранится в виде: ('Крокодил',3), ('Бегемот',2), ('Удав',1) Когда мы обращаемся к какому-то элементу по индексу (например, zoo['Удав']), то в списке пар ищется пара, у которой ключ совпадает с индексом, после чего возвращается второй элемент пары, представляющий собой значение, соответствующее этому ключу (для zoo['Удав'] возвращается 1). Если при обращении к элементу ассоциативного массива пары с таким ключом нет (например, zoo['Воробей']), то в список пар добавляется пара с таким ключом, а соответствующее значение полагается равным 0: ('Крокодил',3), ('Бегемот',2), ('Удав',1), ('Воробей',0) Приведем реализацию ассоциативного массива на базе списка пар типа (string,integer). Для этого будем считать, что список пар определен в модуле PairsSIList, для которого DataType описан следующим образом: type KeyType=string; 31

ValueType=integer; DataType = record Key: KeyType; Value: ValueType; end; Сам ассоциативный массив определим в модуле с именем AssocArraySI. Если потребуется создать ассоциативный массив с другим типом индексов или значений, то к модулю, в котором он определен, достаточно будет подключить другой модуль, реализующий список пар. В закрытой секции интерфейса класса содержится список пар Pairs, а также внешний итератор it по этому списку и два вспомогательных метода TryFind и Add. Процедура TryFind(Key) пытается найти в списке пар пару с ключом Key, используя итератор it. Если поиск не увенчался успехом, то it.Eol возвратит истину (пройден весь список и данные не найдены), если же поиск успешен, то it.Data представляет найденную пару. Процедура Add(Key,Value) добавляет пару (Key,Value) в конец списка и устанавливает итератор на эту пару. Центральным в открытом интерфейсе класса «Ассоциативный массив» является индексное свойство Items, позволяющее использовать для объектов этого класса синтаксис массива. Его методы доступа на чтение и запись GetItem и SetItem используют для своей реализации методы TryFind и Add, а также итератор it. Метод GetItem(Key) ищет пару с ключом Key, и если такая пара не найдена, то добавляет в конец списка пару (Key,0). После этого в любом случае возвращается значение, соответствующее этому ключу. Таким образом, если значение ключа встретилось впервые, то возвращается 0, иначе возвращается соответствующее данному ключу значение. Метод SetItem(Key,Value) ищет пару с ключом Key и если такая пара не найдена, то добавляет в конец списка пару (Key,Value), в противном случае второму элементу пары с ключом Key присваивается значение Value. Таким образом, в итоге работы метода SetItem в списке пар оказывается пара (Key,Value). Приведем интерфейс и реализацию класса AssocArray, помещенного в модуль AssocArraySI. unit AssocArraySI; interface uses PairsSIList; type AssocArray=class private Pairs: List; it: ListIterator; 32

procedure TryFind(Key: KeyType); procedure Add(Key: KeyType; Value: ValueType); function GetItem(Key: KeyType): ValueType; procedure SetItem(Key: KeyType; Value: ValueType); public constructor Create; destructor Destroy; property Items[Key: KeyType]: ValueType read GetItem write SetItem; default; end; implementation constructor AssocArray.Create; begin Pairs:=List.Create; it:=ListIterator.Create(Pairs); end; destructor AssocArray.Destroy; begin it.Destroy; Pairs.Destroy; end; procedure AssocArray.TryFind(Key: KeyType); begin it.MoveFirst; while not it.Eol do begin if it.Data.Key=Key then exit; it.Next; end; end; procedure AssocArray.Add(Key: KeyType; Value: ValueType); var r: PairsSIList.DataType; begin r.Key:=Key; r.Value:=Value; Pairs.AddLast(r); it.MoveLast; end; 33

function AssocArray.GetItem(Key: KeyType): ValueType; begin TryFind(Key); if it.Eol then Add(Key,0); Result:=it.Data.Value; end; procedure AssocArray.SetItem(Key: KeyType; Value: ValueType); begin TryFind(Key); if it.Eol then Add(Key,Value) else it.Data.Value:=Value; end; end.

4 Деревья Дерево – это совокупность элементов, называемых вершинами, или узлами, связанных между собой отношениями вида «родитель – сын». Отношения отображаются в виде линий, которые называются рёбрами, или ветвями дерева. Узел дерева, не имеющий предков, называется корнем дерева, а узлы, не имеющие потомков, называются листьями дерева. Деревья обычно отображаются по уровням. На нулевом уровне находится корень дерева, на первом – его сыновья, на втором – сыновья этих сыновей и т.д. Уровень каждого элемента называется также его глубиной, а количество уровней в дереве называется глубиной дерева. Дерево называется бинарным (двоичным), если каждый его узел имеет максимум двух сыновей. Приведем ряд примеров деревьев. Пример 1. Дерево глав и пунктов книги.

Пример 2. Дерево папок на диске.

34

Пример 3. Дерево разбора выражения a+b*c.

Дерево, приведенное в примере 3, является бинарным, поскольку операции + и * – бинарные. Каждый узел этого дерева, не являющийся листом, содержит знак операции, а два операнда данной операции являются сыновьями этого узла. Сын является либо листом и тогда представляет переменную, либо корнем поддерева. Например, сыновьями узла, содержащего операцию +, являются операнд a и операнд b*c, который также представляется в виде дерева. Из примеров мы видим, что деревья имеют рекурсивную природу. Действительно, любой узел дерева либо является листом, либо имеет сыновей, каждый из которых является корнем поддерева. Приведем другое, рекурсивное определение дерева: Дерево ::= <пусто> │ Корень СписокПоддеревьев СписокПоддеревьев ::= <пусто> │ Дерево СписокПоддеревьев

4.1 Порядки обхода деревьев Как обойти дерево, посетив каждый его узел один раз? Имеется несколько стандартных вариантов обхода деревьев. Все определения будем давать для произвольного дерева, состоящего из корня К и n поддеревьев Д 1 , Д 2 , ... , Д n , и для бинарного дерева, используя для иллюстрации дерево разбора выражения a+b*c:

Заметим, что все порядки обхода формулируются как рекурсивные процедуры, что отражает рекурсивность определения самого дерева. 1) Инфиксный порядок обхода. Для произвольного дерева. Вначале обходится первое поддерево в инфиксном порядке, затем корень и затем – остальные поддеревья в инфиксном порядке: Д1 K Д2 ... Дn Для бинарного дерева. Левое поддерево в инфиксном порядке, корень, правое поддерево в инфиксном порядке: a + b * c 2) Префиксный порядок обхода. Для произвольного дерева. Вначале обходится корень, а потом все поддеревья в префиксном порядке: 35

К Д1 Д2 ... Дn Для бинарного дерева. Корень, левое поддерево в префиксном порядке, правое поддерево в префиксном порядке: + a * b c 3) Постфиксный порядок обхода. Для произвольного дерева. Вначале обходятся все поддеревья в постфиксном порядке, потом корень: Д1 Д2 ... Дn К Для бинарного дерева. Левое поддерево в постфиксном порядке, правое поддерево в постфиксном порядке, корень: a b c * + Отметим, что порядок обхода бинарного дерева разбора выражения соответствует форме записи этого выражения: при инфиксном обходе дерева получаем инфиксную форму, при префиксном – префиксную, при постфиксном – постфиксную. Имеется несколько важных классов бинарных деревьев. Бинарное дерево называется идеально сбалансированным, если для каждого его узла количество узлов в левом и правом поддеревьях отличается максимум на единицу. Бинарное дерево называется полным, если все его уровни полностью заполнены. Нетрудно подсчитать, что количество узлов в полном бинарном дереве глубины k составляет 2 k +1 − 1 . Приведем примеры идеально сбалансированных деревьев:

Из них полными являются первое, третье и последнее. Для создания бинарного дерева в программе нам потребуется следующая структура, определяющая узел дерева: type PNode=^TNode; TNode=record data: DataType; left,right: PNode; end; Здесь left и right – указатели на левое и правое поддерево, DataType – описанный ранее тип, для которого определены операции сравнения =, >, <. Нам потребуется также функция NewNode, возвращающая узел дерева с заполненными полями: 36

function NewNode(x: DataType; left,right: PNode): PNode; begin New(Result); Result.data:=x; Result.left:=left; Result.right:=right; end; Приведем решения нескольких задач на бинарные деревья. Все они имеют простые рекурсивные решения, что является следствием рекурсивной природы определения дерева. Задача 1. Создать идеально сбалансированное дерево с n узлами, заполненными случайными значениями. Решение. Для решения создадим корень дерева, и рекурсивно создадим его левое и правое поддеревья, которые являются идеально сбалансированными и содержат n div 2 и n - n div 2 – 1 узлов соответстванно. function CreateTree(n: integer): PNode; begin if n=0 then Result:=nil else Result:=NewNode(Random(100), CreateTree(n div 2), CreateTree(n - n div 2 - 1)); end; Очевидно, полученное дерево идеально сбалансировано, поскольку количество узлов в поддеревьях отличается максимум на 1 и поддеревья идеально сбалансированы. Задача 2. Разрушить бинарное дерево. Решение. Если дерево пусто, то оно уже разрушено, в противном случае следует разрушить левое поддерево, затем правое поддерево и, наконец, корень: procedure Destroy(r: PNode); begin if r=nil then exit; Destroy(r.left); Destroy(r.right); Dispose(r); end; Задача 3. Выдать узлы бинарного дерева в инфиксном порядке. Решение. По определению инфиксного обхода, если дерево непустое, то надо вначале обойти его левое поддерево в инфиксном порядке, затем корень и, на37

конец, правое поддерево в инфиксном порядке. При обходе корня следует вывести его поле данных: procedure InfixPrintTree(r: PNode); begin if r=nil then exit; InfixPrintTree(r.left); write(r.data,' '); InfixPrintTree(r.right); end; Очевидно, если в последних трех операторах поместить оператор write на первое место, то мы получим вывод дерева в префиксном порядке, если на последнее, то в постфиксном. Задача 4. Дано бинарное дерево. Найти его глубину. Решение. Глубина дерева на единицу больше максимальной глубины его поддеревьев. Поскольку глубина дерева из одного элемента равна 0, то естественно считать глубину пустого дерева равной -1. function TreeDepth(r: PNode): integer; begin if r=nil then Result:=-1 else Result:=max(TreeDepth(r.left),TreeDepth(r.right))+1; end; Обратим внимание, что во всех задачах глубина рекурсии совпадает с глубиной дерева. Более того, если вызов подпрограммы представлять в виде узла дерева и считать его сыновьями рекурсивные вызовы подпрогрмм, то множество всех рекурсивных вызовов образует дерево. Этот факт подчеркивает тесную связь деревьев и рекурсии.

4.2 Бинарные деревья поиска (БДП) Бинарное дерево называется бинарным деревом поиска (БДП, BST – Binary Search Tree), если значение каждого его узла не меньше значений узлов левого поддерева и не больше значений узлов правого поддерева. Ниже на рисунке изображено полное бинарное дерева поиска глубины 3: 41 17 8 3

73 29

12 27 39

60

90

42 70 81 99

38

БДП обладают одним замечательным свойством: при их обходе в инфиксном порядке мы получаем неубывающую последовательность. Так, инфиксный обход дерева, приведенного на рисунке, даст следующую последовательность: 3 8 12 17 27 29 39 41 42 60 70 73 81 90 99 Основными операциями при работе с БДП являются добавление, удаление и поиск элемента. Все указанные операции реализуются рекурсивно. Добавление элемента в БДП При добавлении элемента в дерево возможно несколько ситуаций. Если дерево пусто, то элемент необходимо добавить в его корень. В противном случае, если значение элемента меньше значения поля данных в корне, элемент необходимо добавить в левое поддерево, а если больше, то в правое поддерево: procedure Add(x: DataType; var r: PNode); begin if r=nil then r:=NewNode(x,nil,nil) else if xr.data then Add(x,r.right) end; Заметим, что после добавления элемента дерево остается деревом поиска. Заметим также, что при таком алгоритме добавления мы получим БДП без повторяющихся элементов. Чтобы получить БДП с повторяющимися элементами, достаточно удалить отрезок кода if x>r.data then. Оценим количество операций при добавлении в БДП. Мы знаем, что в полном дереве с k уровнями количество элементов n = 2 k +1 − 1 . Очевидно, если дерево близко к полному (в частности, если оно идеально сбалансировано), то n ≈ 2 k , следовательно, количество уровней k ≈ log 2 n . Например, при n = 1024 элемента глубина хорошо сбалансированного дерева близка к 10. Поскольку при каждом рекурсивном шаге операции добавления мы спускаемся вниз по дереву на один уровень и делаем одну операцию, глубина рекурсии и количество операций при добавлении равны глубине дерева k, т.е. составляют примерно log 2 n . На алгоритме добавления в БДП основана очень эффективная сортировка деревом. В ней используется свойство БДП выдавать отсортированную последовательность при инфиксном обходе. Алгоритм такой сортировки прост: в первоначально пустое БДП с повторяющимися элементами добавляем все элементы с помощью процедуры Add, после чего выдаем все элементы, обходя дерево в инфиксном порядке. Если в процессе добавления дерево остается сбалансированным, то при добавлении в него n элементов количество операций составляет при39

мерно n ⋅ k ≈ n ⋅ log 2 n . Ровно такая оценка была получена в алгоритме быстрой сортировки; для произвольных данных улучшить эту оценку нельзя. При выводе этой оценки мы исходили из того, что БДП является достаточно сбалансированным. Это не всегда так. Например, при добавлении возрастающей последовательности элементов каждый следующий элемент добавляется в правое поддерево листа и дерево вырождается в список: 3 8 12 ... 99

Это – самый плохой случай: количество операций при вставке имеет порядок n, а не log 2 n , поэтому количество операций в алгоритме сортировки деревом составляет примерно n 2 . Однако в среднем (если данные случайны и добавляются в случайном порядке) количество операций при сортировке деревом составляет примерно n ⋅ log 2 n . Отметим также, что мы получили компактный рекурсивный алгоритм сортировки всего с одним циклом (!), совпадающий по оценке количества операций с одним из самых производительных алгоритмов сортировки – быстрой сортировкой: r:=nil; for i:=1 to 10 do Add(r); InfixPrintTree(r); Поиск элемента в БДП Поиск в БДП осуществляется по той же схеме, что и добавление. Пусть ищется элемент со значением x. Если дерево пусто, то элемент не найден. Если значение x совпадает со значением корневого элемента, то элемент найден. Если значение x меньше значения корневого элемента, то рекурсивно ищем x в левом поддереве, а если больше, то в правом поддереве. В случае успешного поиска будем возвращать указатель на элемент, в противном случае будем возвращать nil: function Search(x: DataType; r: PNode): PNode; begin if r=nil then Result:=nil else if r.data=x then Result:=r else if r.data<x then Result:=Search(x,r.right) 40

else Result:=Search(x,r.left); end; Удаление элемента из БДП Удаление элемента из БДП является самым сложным из рассматриваемых алгоритмов. Возможны три случая. a) Требуется удалить лист. 41

41

22

64

8

34

50

22 77

64

8

50

77

Удаляем лист и указателю, который на него указывал, присваиваем nil. б) Требуется удалить элемент, который имеет только одно поддерево. 41

41

22

64

8

50

64 77

8

50

77

Запоминаем адрес единственного поддерева этого элемента, удаляем сам элемент, после чего указателю, который на него указывал, присваиваем адрес поддерева. Очевидно, при подобном удалении дерево остается БДП. в) Требуется удалить элемент, у которого есть левое и правое поддеревья. Вначале найдем этот элемент, используя рекурсию. Он является корнем некоторого поддерева, и сам имеет левое и правое поддеревья. 41

34

22 8

64 34

50

22 77

8

34

28 26

64 50

77

28 31

26

31

Пусть в дереве, изображенном на рисунке, требуется удалить элемент со значением 41. Вначале найдем элемент, значение которого непосредственно предшествует значению корневого элемента. Таковым является самый правый элемент в левом поддереве корня (на рисунке это элемент со значением 34). Перепишем значение этого элемента в корневой, после чего удалим этот элемент. Заметим, что поскольку он – самый правый в левом поддереве, то у него нет правого под41

дерева. Следовательно, для его удаления достаточно присвоить указателю, ранее указывавшему на него, адрес его левого поддерева. Почему приведенный алгоритм корректен? Для этого достаточно показать, что после его работы дерево остается БДП. Это очевидно, поскольку если представлять элементы дерева как упорядоченную последовательность, то данный алгоритм для удаления элемента переписывает в него значение предыдущего элемента, после чего удаляет этот предыдущий. Поскольку удаление предыдущего выполняется по алгоритму случая а) или б), дерево остается БДП. Данное доказательство дает нам возможность привести еще один, симметричный предыдущему, алгоритм удаления: чтобы удалить элемент с двумя поддеревьями, достаточно найти самый левый элемент в его правом поддереве (значение которого непосредственно следует за данным), и перед удалением переписать его значение в исходный. Приведем рекурсивную процедуру удаления элемента из БДП. procedure Delete(x: DataType; var r: PNode); procedure FindAndDelMostRight(var p: PNode); var v: PNode; begin if p.right<>nil then FindAndDelMostRight(p.right) else begin r.data:=p.data; v:=p; p:=p.left; Dispose(v); end; end; var v: PNode; begin if r=nil then exit; if xr.data then Delete(x,r.right) else if (r.left=nil) and (r.right=nil) then // случай а) begin Dispose(r); r:=nil; end 42

else if r.left=nil then // случай б) begin v:=r; r:=r.right; Dispose(v); end else if r.right=nil then // случай б) begin v:=r; r:=r.left; Dispose(v); end else FindAndDelMostRight(r.left); // случай в) end; Случай в) реализуется здесь локальной процедурой FindAndDelMostRight(p), удаляющей в дереве с корнем p самый правый элемент. Вначале эта процедура рекурсивно ищет такой элемент, опускаясь вправо по ветвям дерева. Если движение вправо уже невозможно, значит, мы нашли самый правый элемент и p является ячейкой, хранящей его адрес (она выделена черным прямоугольником на последнем рисунке). Теперь достаточно присвоить значение найденного элемента корневому, изменить указатель p на левое поддерево удаляемого элемента и удалить элемент, на который указывает p.

4.3 Класс «Множество» на базе бинарного дерева поиска Основные операции при работе с множеством – это добавление, удаление элемента и проверка элемента на принадлежность к множеству. Используем делегирование, реализовав множество с помощью бинарного дерева поиска, соответствующие операции для которого мы рассмотрели в предыдущем пункте. Пусть операции с БДП целых описаны в модуле IntBST. Тогда реализация класса множества DataSet в модуле IntSet имеет вид: unit IntSet; interface uses IntBST; type DataSet = class private root: PNode; public constructor Create; destructor Destroy; procedure Include(x: DataType); // добавить x 43

procedure Exclude(x: DataType); // удалить x // принадлежит ли элемент множеству function Contains(x: DataType): boolean; end; implementation constructor DataSet.Create; begin root:=nil; end; destructor DataSet.Destroy; begin IntBST.Destroy(root); end; procedure DataSet.Include(x: DataType); begin IntBST.Add(x,root); end; procedure DataSet.Exclude(x: DataType); begin IntBST.Delete(x,root); end; function DataSet.Contains(x: DataType): boolean; begin Result := BST.Search(x,root)<>nil; end; end. Указывать имя модуля IntBST перед именем вызываемой функции не обязательно, однако мы это делаем с целью подчеркнуть, что процедуры Add, Delete, Search и Destroy вызываются из другого модуля.

4.4 Ассоциативный массив на базе БДП Ассоциативный массив можно сделать не только на базе списка, но и на базе бинарного дерева поиска. Для этого в TNode для дерева достаточно определить два поля данных вместо одного: Key и Value: type KeyType=string; ValueType=integer; PNode=^TNode; 44

TNode=record Key: KeyType; Value: ValueType; left,right: PNode; end; Интерфейс модуля PairsSIBST, реализующего дерево пар (string,integer), будет выглядеть следующим образом: function NewNode(Key: KeyType; Value: ValueType; left,right: PNode): PNode; procedure Add(Key: KeyType; Value: ValueType; var r: PNode); function Search(Key: KeyType; r: PNode): PNode; procedure Delete(Key: KeyType; var r: PNode); Поиск и сравнение при этом следует проводить только по ключевому полю Key. Для реализации методов SetItems и GetItems не потребуется ни итератора, ни вспомогательных методов. Приведем реализацию SetItems, а реализацию GetItems оставим в качестве упражнения: procedure SetItems(Key: string; Value: integer); var v: Pnode; begin v:=Search(Key,root); if v=nil then Add(Key,Value,root) else v.Value:=Value; end;

4.5 Реализация произвольного дерева Произвольное дерево будем составлять из узлов вида: PTreeNode = ^TreeNode; TreeNode = record data: DataType; leftChild, rightSibling: PTreeNode; end; где тип DataType опрделен ранее. Каждый элемент хранит указатель на своего самого левого сына leftChild и на своего правого брата rightSibling (sibling – родной брат/сестра). У корневого элемента братья отсутствуют. Дерево, изображенное на приведенном ниже рисунке,

45

1 3

2 5

6

7

8

4 9 10 11 12

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

3

4 10

5

8

9

6

7

11

12

Для создания дерева воспользуемся вспомогательной рекурсивной функцией CreateRandomTree, которая создает m уровней дерева и на каждом уровне создает n братьев: function CreateRandomTree0(n,m: integer): PTreeNode; // n - количество сыновей, m - количество уровней var i: integer; begin Result:=nil; if m=0 then exit; for i:=1 to n do Result:=NewNode(Random(100), CreateRandomTree0(n,m-1),Result); end; Функция CreateRandomTree0 работает следующим образом: она создает на данном уровне цепочку из n братьев и привязывает к каждому из них в качестве левого сына указатель на дерево, созданное CreateRandomTree0 с количеством уровней на единицу меньше, чем в исходном дереве. Чтобы на нулевом уровне был только один элемент (корень), создадим его отдельно, привязав к нему в качестве указателя на левого сына структуру, созданную вызовом CreateRandomTree0. В результате получим функцию CreateRandomTree для создания дерева с одним корнем, сделав функцию CreateRandomTree0 локальной:

46

function CreateRandomTree(n,m: integer): PTreeNode; <описание CreateRandomTree0> begin Result:=NewNode(Random(100), CreateRandomTree0(n,m),nil); end; Наконец, для вывода дерева составим рекурсивную процедуру PrintTree: procedure PrintTree(r: pTreeNode); begin while r<>nil do begin write(r.data,' '); PrintTree(r.leftChild); r:=r.rightSibling; end end;

5 Хеширование. Хеш-таблицы Хеширование – это способ хранения данных, обеспечивающий быстрый поиск и добавление элементов. Суть его состоит в следующем. Каждому элементу, для которого осуществляется поиск или добавление, ставится в соответствие целое число, называемое его хеш-значением или хеш-кодом (англ. hash – перемешивание). Тем самым все возможные элементы разбиваются на группы (классы эквивалентности). К одной группе (одному классу эквивалентности) относятся элементы с одним хеш-значением. При поиске вначале вычисляется хеш-значение элемента, после чего этот элемент ищется только среди элементов с тем же самым хеш-значением. Например, при поиске слова в английском словаре мы вначале определяем его первую букву (хеш-значение слова), после чего ищем его только среди слов на эту букву, в результате чего поиск на первом же шаге сокращается примерно в 26 раз (количество букв в латинском алфавите). Добавление осуществляется аналогично: вычисляется хеш-значение добавляемого элемента, после чего он добавляется в группу элементов с таким же хеш-значением. Совокупность элементов, сгруппированных по их хеш-значениям, называется хеш-таблицей. Функция, сопоставляющая элементу его хеш-значение, называется хеш-функцией. Обычно в качестве хеш-функции целого числа x используется следующая функция: Hash(x)=x mod N, где N – число, определяющее количество классов эквивалентности (рекомендуется выбирать N простым числом). Наиболее наглядным способом хранения хеш-таблиц является массив списков. Элементы массива нумеруются от 0 до N-1 и представляют собой списки, при этом i-й список хранит элементы с хеш-значением, равным i. Так организо47

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

N-1

Заметим, что если в списках находится примерно равное количество элементов, то поиск одинаково эффективен для всех возможных значений. Например, пусть N=1001 и в каждом списке максимум 3 элемента, а во всей хеш-таблице – 2048 элементов. Тогда после вычисления хеш-значения элемента последовательный поиск в списке с этим номером потребует максимум три итерации. Бинарный же поиск потребует 11 итераций ( 211 = 2048 ). Если количество элементов в разных списках отличается значительно, то эффективность хеширования падает. Самый плохой случай – если один список содержит все элементы, а остальные списки – пустые. Для поиска в этом случае может потребоваться 2048 итераций. Поэтому следует стремиться к тому, чтобы хеш-функция хорошо перемешивала элементы, заполняя хеш-таблицу как можно более равномерно для любых значений (отсюда и название метода – хеширование, т.е. перемешивание). В частности, именно поэтому число N стремятся выбирать простым. Реализуем хеш-таблицу целых в виде класса на основе динамического массива списков. Поскольку список обеспечивает удаление элемента, наша хештаблица будет также позволять удалять элементы. uses IntList; const sz = MaxInt div sizeof(List); type PArr = ^Arr; Arr = array [0..sz-1] of List; HashTable = class private a: PArr; N: integer; public constructor Create(nn: integer); destructor Destroy; 48

function Hash(x: DataType); integer;//хеш-функция элемента x procedure Include(x: DataType); procedure Exclude(x: DataType); procedure Contains(x: DataType): boolean; end; constructor HashTable.Create(nn: integer); var i: integer; begin N:=nn; GetMem(a,N*sizeof(List)); for i:=0 to N-1 do a^[i]:=List.Create; end; destructor HashTable.Destroy; var i: integer; begin for i:=0 to N-1 do a^[i].Destroy; FreeMem(a); end; function HashTable.Hash(x: integer); integer; begin Result:=x mod N; end; procedure HashTable.Include(x: integer); begin if not Has(x) then a^[Hash(x)].AddLast(x); end; procedure HashTable.Exclude(x: integer); begin a^[Hash(x)].Remove(x); end; function HashTable.Contains(x: integer): boolean; begin Result:=a^[Hash(x)].Find(x); end; Отдельно рассмотрим вопрос о создании хорошей хеш-функции для строкового типа данных. Задача – не такая тривиальная, как может показаться на первый 49

взгляд. Приведем, например, упоминаемую в начале пункта хеш-функцию для английского словаря, вырезающую из любого слова первую букву: function Hash(s: string): integer; begin if Length(s)=0 then Result:=0 else Result:=Ord(s[1]) mod 26; end; Эта хеш-функция неудачна по двум причинам. Во-первых, количество слов, начинающихся на разные буквы, существенно различается, т.е. не соблюдается основной принцип хеширования – перемешивание. Во-вторых, при хранении большого количества строк в хеш-таблице значения N=26 уже недостаточно. Более удачной является хеш-функция, учитывающая все символы строки, например, такая: function Hash(s: string): integer; var i: integer; begin Result:=0; for i:=1 to Length(s) do Result:=(Result*17+Ord(s[i])) mod N; end;

Литература 1. Зеленяк О. Практикум программирования на Turbo Pascal / О. Зеленяк. – М.: DiaSoft, 2002. – 310 с. 2. Ставровский А. Турбо Паскаль 7.0 / А.Ставровский. – Киев: BHV, 2001. – 400 с. 3. Вирт Н. Алгоритмы и структуры данных / Н. Вирт. – М.: Мир, 1989. – 360 с.

50