Назад Домой! Дальше Глава 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 г.
При освобождении элементов структуры следует особое внимание уделять сохранению 
необходимых связей, т. к. в противном случае можно потерять часть или даже все оставшиеся 
элементы структуры. В рассмотренном примере для этой цели использовалась переменная Ро.
Rambler's Top100
Hosted by uCoz