Глава 7. ДИНАМИЧЕСКИЕ
СТРУКТУРЫ ДАННЫХ
Рассматриваемые до сих пор параметры программы обладали тем свойством, что под них
выделяется вполне определенный размер памяти и между отдельными объектами
устанавливаются связи еще на этапе компиляции и ком¬поновки. Во время работы
программы вносить изменения в выделенный размер памяти или установленные связи
не удается. Порой это бывает неудобно. Например, программа работает с различным
количеством целых чисел. Естественно разместить их в каком-то массиве. Размер
массива должен быть определен заранее, и, если программа должна быть универсальной,
при определении масси¬ва необходимо учитывать случай максимального количества
таких чисел. Однако это приведет к неэффективному использованию оперативной памяти.
В языке Паскаль есть возможность по ходу выполнения программы выделять и
освобождать необходимую память для размещения в ней различных данных.
Таким образом можно организовывать динамические, т. е. изменяющие размеры,
структуры данных. Оперативная память при этом используется наиболее эффективным
образом. Такая возможность связана с наличием в языке особых типов данных -
указателей. Область оперативной памяти, где можно выделять отдельные участки для
размещения данных и освобождать их, будем называть динамической областью памяти
или динамической памятью.
Использование указателей является единственной возможностью увеличения объема
глобальных параметров программы (см. п. 10) свыше 64 Кбайт.
7.1. Указатель
Указатель в Turbo Pascal дает адрес объекта определенного типа, называемого
базовым типом. При определении типа-указателя используется этот базовый тип, перед
которым ставится признак указателя ^.
Пример.
type
Mas = array [1..10] of Real; {базовый тип}
Point = ^Mas; {тип-указатель на массив из 10
вещественных чисел}
Переменная типа-указателя, которая в дальнейшем будет называться просто указателем,
является физическим носителем адреса величины базового типа. Она занимает 4 байта
памяти (2 слова). Первое слово дает смещение адреса, а второе - адрес сегмента.
Значение этой переменной можно задать процедурой New или GetMem, использованием
адресного оператора @, а также присваиванием ей значения другой переменной этого
же типа. Переменной типа-указателя можно также присвоить значение nil, означающее
отсутствие ссылки на какой-либо объект (фактически в этом случае переменной
присваивается значение 0).
Пример.
type
Complex = record {базовый тип}
Re,Im: Real
end;
Point = ^Complex; [тип-указатель)
Adrlnt = ^Integer; (тип-указатель)
var
X: Complex;
P1, P2, P3, P4: Point;
Ad1: Adrlnt;
begin
. . .
New(P1); (выделение нового элемента типа Complex}
Р2 := @Х; {определение адреса переменной X}
Р3 := Р1; {присвоение значения другого указателя}
Р4 := nil; {присвоение значения nil}
New(Adl); {выделение нового элемента типа Integer}
Следует иметь в виду, что указатели, ссылающиеся на объекты разных типов,
сами являются объектами разных типов и для них недопустима операция присваивания
значений друг другу. Указатели одного и того же типа можно сравнивать с помощью
операций = и <>.
Чтобы получить значение элемента, с которым связан указатель, следует взять имя
указателя и после него поставить знак ^.
Пример.
X := Р1^; {переменной X присваивается значение
элемента, на который указывает Р1}
Р3^ := X; {элементу, на, который указывает РЗ,
присваивается значение переменной X}
Стандартный тип-указатель Pointer дает указатель, не связанный ни с каким конкретным
базовым типом. Этот тип совместим с любым другим типом-указателем, однако следует иметь
в виду, что использование знака ^ после параметра типа Pointer дает параметр без типа
(см. п. 10.3.4).
В Turbo Pascal существует операция получения адреса объекта - @, например
X:=@Y; {X - адрес параметра Y}
Полученный адрес в версии 7.0 может иметь конкретный тип или быть совместимым с любым
указателем. Эти возможности зависят от использования ключа компилятора
{$Т+/-} (см. п. 17.7.1).
7.2. Работа с динамической памятью
Использование указателей совместно с процедурами New и Dispose позволяет осуществлять
динамическое распределение памяти.
Процедура New(P), где Р - указатель, позволяет выделить область памяти такого размера,
в котором можно разместить величину базового типа. Указатель принимает значение адреса
выделенной области.
Процедура Dispose(P), где Р - указатель, позволяет освободить область памяти, на которую
указывает указатель Р, для последующего использования. После выполнения процедуры
значение указателя Р становится неопределённым.
Пример. Ввести в память машины 500 вещественных чисел, а затем вывести их в обратном
порядке.
program EXAMPLE14;
type
Mas = array [1..500] of Real;
Point = ^Mas;
var
P: Point;. {указатель}
i: Word;
begin
New(P); {выделение области памяти для 500 чисел}
WriteLn('Введите 500 чисел');
for i := 1 to 500 do Read(P^[i]):
for i := 500 downto 1 do
WriteLn(P^[i]);
Dispose(P) {освобождение этой области памяти}
end.
Существует и другая возможность работать с динамической памятью - использовать процедуры
GetMem и FreeMem.
Процедура GetMem(P,Size), где Р - переменная типа указатель (в том числе и типа Pointer),
a Size - размер выделяемой область памяти в байтах; позволяет выделить в динамической
памяти область необходимого размера, при этом адрес выделенной области присваивается
переменной Р.
Процедура FreeMem(P,Size) - здесь параметры те же, что и в процедуре GetMem, - освобождает
занятую область памяти с адресом, задаваемым перемен¬ной Р и размером Size байтов. Эта
область становится свободной для повторного использования, а указатель Р становится
неопределенным.
Наконец, для управления динамической памятью существует еще две процедуры: Mark и Release.
Процедура Mark(P), где Р - переменная типа Pointer, фиксирует текущее состояние
динамической памяти, записывая в переменную Р значение указателя на начало свободной
область динамической памяти.
Процедура Release (Р), где Р - переменная типа Pointer, позволяет вернуться к состоянию
динамической памяти, определяемому переменной Р, которой было присвоено значение
процедурой Mark. При этом динамическая память, занятая после выполнения процедуры Mark
с адресами больше адреса, зафиксированного в указателе Р, освобождается.
Во избежание ситуаций, приводящих к неправильной работе с динамической памятью,
нежелательно использовать процедуру Release попеременно с процедурами Dispose и FreeMem.
7.3. Работа со структурами данных
Возможность выделения и освобождения области памяти позволяет создавать структуры данных
с переменным числом элементов - динамические структуры. Чаще всего используют т. н.
связанные структуры, когда среди элементов устанавливается некоторая иерархия, например
наподобие генеалогического дерева. Среди таких структур наибольшее распространение в
различных практических приложениях получили линейные структуры (списки) и
структуры-деревья (более подробно о разнообразии структур см., например, [6,7]).
В связных структурах обычно используются однотипные элементы. Каждый элемент имеет две
различные части:
- информационную часть - та часть, которая содержит всю информацию о том или ином
объекте (например, если это структура целых чисел, то значение конкретного числа);
- ссылку на соседний элемент (соседние элементы) в конкретной иерархии элементов
(например, если структура является списком, то ссылка на элемент, стоящий в списке
непосредственно за данным элементом, а может быть, и на предыдущий элемент).
Наиболее удобно для фиксации такой информации использовать тип-запись. Однако при
задании такого типа элемента возникает определенная трудность, связанная с тем, что
этот тип должен содержать тип-указатель на элемент структуры, который, в свою очередь,
нельзя определить, пока не определен тип элемента. При этом, в какой бы
последовательности ни определялись эти типы, будет нарушено правило, гласящее, что
использовать можно только те элементы программы, которые определены ранее. Для
устранения этого препятствия в языке Паскаль сделано исключение из указанного правила
по отношению к двум типам данных, один из которых является типом: указатель на объект
второго типа.
Пример. Тип элемента структуры, содержащего символьную информацию в
виде строки.
type
pPoint = ^Е1еm; {указатель на элемент}
Elem = record
Info: string[80];
Point: pPoint
end; {тип элемента структуры}
При работе с динамическими структурами данных выполняются следующие основные операции:
- добавление элемента структуры;
- исключение элемента структуры;
- поиск элементов структуры по какому-то признаку.
В разных структурах эти операции выполняются по-своему. В качестве примера рассмотрим
добавление и исключение элементов из линейного списка, называемого очередью, - структуры,
в которой добавление элементов осуществляется с одной стороны, а исключение - с другой
стороны списка.
Пусть элемент структуры имеет информационную часть, представляющую собой одно целое
число. Тогда тип такого элемента может выглядеть следующим образом:
type
pPoint= ^Еlеш;
Elem = record
Info: Integer;
Point: pPoint
end;
Для работы с очередью введем следующие переменные:
var
Ро, РоВ, РоЕ: pPoint;
X: Integer;
Предположим, что вначале в очереди нет элементов - очередь пуста. Этот факт можно
зафиксировать следующим образом (рис. 1 а):
РоB := nil;
РоЕ := nil;
Введем в очередь первый элемент. Для этого можно выполнить следующие действия:
Read(X); {чтение значения первого элемента.}
New(Po); {выделение области под элемент}
Po^.Info := X; {заполнить информационную часть элемента}
Ро^. Point := nil; {нет следующего элемента т.е. признак конца списка}
РoВ := Ро; {указатель начала очереди - теперь указывает на созданный элемент}
РоЕ := Ро; {указатель конца очереди - теперь указывает на созданный элемент}
После выполнения этих операторов возникнет ситуация, изображенная на рис. 1 б. На этом
рисунке прямоугольником указан элемент очереди. Левая часть прямоугольника представляет
собой информационную часть, а правая - ссылку на следующий элемент. Стрелками изображены
указатели.
Для добавления следующего элемента можно записать:
Read(X);
New(Po);
Ро^.Info := X;
Ро^.Point := nil;
РоB.Point := Ро; {установление связей}
РоЕ := Ро;
Полученная ситуация изображена на рис I в.
Рассмотренные выше две последовательности операторов по добавлению элементов похожи друг
на друга и могут выполняться в цикле (с небольшой модернизацией).
Посмотрим теперь, как удалить первый элемент из очереди. Для этого можно выполнить
следующие действия:
if PoB <> nil then
begin
Ро := РоВ^.Point; {указатель на второй элемент}
Dispose(PoB); {освобождение области, выделенной для 1-го элемента)
РоВ := Ро {теперь бывший 2-й элемент становится 1-м }
end;
Полученная ситуация изображена на рис. 1 г.
При освобождении элементов структуры следует особое внимание уделять сохранению
необходимых связей, т. к. в противном случае можно потерять часть или даже все оставшиеся
элементы структуры. В рассмотренном примере для этой цели использовалась переменная Ро.
