Динамические структуры данных, указатели

Страницы работы

14 страниц (Word-файл)

Содержание работы

1  ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

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

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

1.1  Указатели

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

Вначале о типизированных указателях. Указатель занимает в памяти двойное слово, в котором хранятся сегмент и смещение. Описание ссылочного типа имеет вид

type

type_ptr = ^type__ID;

где type_ID — это идентификатор базового типа, например

type

Integer_Pointer = ^Integer;

var

Hours. Minutes. Seconds : Integer_Pointer;

В данном случае базовый тип — Integer, а в предложении описания типа определяется тип Integer_Pointer — указатель на Integer.

Встроенный тип Pointer обозначает указатель, который не указывает ни на какой определенный тип.

Ниже приводится пример программы, в которой используются указатели. Пусть необходимо считать текстовый файл, интерпретируя его содержимое как массив строковых значений размером до 3000 элементов. Программа text_file_ read предназначена для решения этой задачи. Кажется естественным определить массив строковых значений, в который и будут записываться данные из файла. Однако при компиляции этой программы выдается сообщение о том, что используемая структура данных слишком велика. Появление такого сообщения связано с тем, что область памяти, отводимая под данные (сегмент данных) в Турбо Паскале не может превышать определенной величины — 64 Кбайт. В нашем же случае, учитывая, что строковая переменная по умолчанию содержит 256 байт, массив таких строк не может содержать более 255 элементов.

Пример. Программа, предназначенная для считывания строковых значений из файла

program text_fiIe_read;

const

max = 3000;

var

MyArray : array[l..max] of String;

NString : Integer;

procedure LoadStringArray;

var

f :  text;

S :  string;

begin

Assign( f,‘strings.txt’ );

Reset(f);

Nstring = 0;

while (not eof(f) or (NString < max) do

begin

inc(NString);

ReadLn(f, s);

MyArray[NString] := s;

end;

close(f);

end;

begin

LoadStringArray;

. . .

end.

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

Пример. Программа, считывающая строковые значения из файла, вариант с динамическими переменными.

program text_file_read;

const

max = 3000;

var

MyArray : array[l..max] of ^string;

NString : Integer;

procedure LoadStringArray;

var

f : text;

S : String;

begin

Assign( f,'strings.txt' );

Reset(f);

NString:= 0;

while(not eof(f)) or (NString < max) do

begin

Inc(NStnng);

Readln(f. s);

GetMem(MyArray[NString]. Succ(Length(s));

MyArray[NString]^ : = s;

end;

close(f);

end;

begin

LoadStringArray;

. . .

end.

Чтобы разобраться в работе этой программы, вспомним основные факты, относящиеся к программированию и использованию динамических переменных. Прежде всего, программа должна разместить в памяти динамическую переменную. Для размещения и освобождения памяти используются стандартные процедуры GetMera и FreeMem. Процедура GetMem( var Р : Pointer; Size : Word) создает динамическую переменную указанного размера (параметр Size — размер в байтах) и присваивает значение адреса переменной Р типа «указатель». Может оказаться, что для размещения переменной свободного места в памяти не хватает. В этом случае при работе программы появится сообщение об ошибке. Процедура FreeMem(var Р : Pointer; Size : Word) освобождает область памяти, отведенную под динамическую переменную. После вызова этой процедуры попытка обращения к указателю приведет к ошибке. Каждый вызов GetMem должен сопровождаться вызовом FreeMem. В нашем примере вызов этой процедуры явно не выписан, он находится где-то среди операторов, обозначенных многоточием.

Имеется и другой способ выделения памяти для динамической переменной — вызов процедуры New(P). Она отводит память в динамически распределяемой области под переменную того типа, на который указывает ее параметр-указатель Р. В результате Р присваивается значение адреса этой переменной, а Р^ становится новой переменной. Получение значения переменной, на которую ссылается данный указатель, называют разыменованием.

Похожие материалы

Информация о работе