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

Занятие I. Динамические структуры данных. Статические и динамические переменные. Адреса. Указатели и их объявление.

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

• сама программа пользователя;

• системные программы времени выполнения, которые осуществляют вспомогательные действия при работе программы пользователя;

• определяемые пользователем структуры данных и константы;

• точки возврата для программ;

• временная память для хранения промежуточных результатов при вычислении выражений;

• временная память при передаче параметров;

• буферы ввода-вывода, используемые как временные области памяти, в которых хранятся данные между моментом их реальной физической передачи с внешнего устройства или на него и моментом инициализации в программе операции ввода или вывода;

• различные системные данные (информация о статусе устройств ввода-вывода и др.).

Из этого перечня видно, что управление памятью касается широкого класса объектов.

До сих пор мы использовали простейший способ распределения памяти – статическое распределение, т. е. распределение памяти при трансляции программы. То есть когда Вы объявляете переменную

Var

A: Array[1..100] of integer;

Вы даете указание компилятору выделить память размера, соответствующего заданному типу, т.е. 2*100=200 байт. Если в программе на нужный программный объект мы ссылаемся по имени А[3], то машинный код содержит ссылку на номер ячейки памяти (адрес байта), начиная с которой размещается этот объект.

Адреса задаются двумя 16-тиразрядными словами (тип word) – сегментом и смещением. Каждое из них способно адресовать 216=65536 байт (64 Кбайт). Для адресации пространства размером в 1 Мбайт требуется 20 разрядов. Сегменты адресуют память с точностью до параграфа – фрагмента памяти в 16 байт. Смещение адресует память с точностью до байта, но впределах сегмента. Реальный (абсолютный) адрес складывается из значения сегмента, сдвинутого на 4 разряда влево (умноженного на 16), и смещения. Фрагмент программы вычисления абсолютного адреса в реальном режиме:

Var

Segment, Offset: word;

Address: LongInt;

...

Address: = Segment*16+Offset;

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

Error 49: Data Segment too large{Слишком большой сегмент данных}

При динамическом распределении памяти Вы можете запросить блоки размером до одного сегмента (64 Кбайт) каждый, причем их можно требовать в пределах основной памяти (640 Кбайт) в реальном режиме и без программных ограничений в защищенном.

Бывают такие данные, размер которых выясняется только при выполнении программ. Кроме того, иногда мы не знаем, будет существовать некоторый объект или нет.

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

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

Адресация динамических переменных происходит через указатели. В Паскале можно определить переменные, которые имеют тип указатель, их значения определяют адрес объекта. Для работы с динамическими переменными в программе должны быть предусмотрены:

ü выделение памяти под динамическую переменную;

ü присвоение указателю на динамическую переменную адреса выделенной памяти (инициализация указателя);

ü освобождение памяти после использования динамической переменной.

Программист сам должен резервировать место под переменную, определять значения указателей, освобождать память – удалять динамические переменные. Для использования динамической переменной где-то в статике должен быть указатель на нее. Компилятор предусматривает место под указатель, об инициализации указателя должен заботиться программист.

Вместо любой статической переменной можно использовать динамическую, но без реальной необходимости этого делать не стоит. Переменные простых типов нет смысла размещать в динамической области, поскольку они занимают меньше места, чем указатель на них. Например, указатель на целое занимает 4 байта, само целое – 2 байта. Кроме того, при динамическом распределении памяти удлиняется текст программы, снижаются наглядность и быстродействие. Это объясняется тем, что, во-первых, нужно во время исполнения программы определять значения указателей, а во-вторых, усложняется доступ к значению переменной.

Указатели и их объявление

Для работы с динамическими программными объектами в Паскале предусмотрен ссылочный тип или тип указателей. В переменной ссылочного типа хранится ссылка на программный объект (адрес объекта). Указатель состоит из сегмента и смещения. По правилам Паскаля указатели на разные типы данных имеют различные типы, причем эти типы несовместимы, т.е. указатели на разные типы данных не могут ссылаться на один объект.

Чтобы связать ссылочный тип с определенным типом данных, используется символ ^, помещаемый перед именем типа. Например, имеется тип массив:

Type

A = Array[1..100] of integer;

Тип указателя на такой объект:

Type

tA = ^A;

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

Type

A = Array[1..100] of integer; {Тип массив из 100 целых чисел}

tA = ^A; {Тип указатель на тип А}

Var

B: tA; {Указатель на тип А}

C: ^A; {Указатель на тип А}

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

B^[i]: = i; {i-му элементу массива, на который указывает В, присвоить значение i}

C^[i]: = B^[i]; {i-му элементу массива, на который указывает С, присвоить значение i-го элемента массива, на который указывает В}

После выполнения этого кода i-е элементы массивов, на которые указывают В и С, будут равны.

Указатели могут ссылаться на любой тип данных, кроме файлового.

Разберем простой пример, обратив еще раз внимание на синтаксис:

Var

P: ^integer; {Указатель на целое}

P^ – переменная целого типа, на которую ссылается Р, она может стоять как в левой, так и в правой части выражений:

P^: =16;

x: = x+P^;

Первый оператор присваивает целочисленной переменной, на которую ссылается Р, значение 16, второй прибавляет к значению переменной х значение 16, второй прибавляет к значению переменной х значение 16. Аналогично определяются и используются указатели на переменные любого типа, в том числе и определенного пользователем.

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

Схематически можно представить себе указатель так:

адрес

Указательная переменная Р может быть в трех состояниях.

1. Содержать адрес какой-либо переменной, память под которую уже выделена.

адрес

2. Содержать специальный пустой адрес Nil.

3. Находиться в неопределенном состоянии.

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

Схематически различия между состоянием Nil и неопределенным состоянием можно изобразить так:

Использование имени указателя в программе означает обращение к адресу ячейки памяти, на которую он указывает. Чтобы обратиться к содержимому ячейки, на которую указывает указатель, требуется после его идентификатора поставить символ ^. Эта операция еще называется разыменованием.

Для представления указателя на строку с завершающим нулем в Паскале имеется предопределенный тип PChar. В модуле System этот тип описывается следующим образом:

Type

PChar = ^char;

Паскаль поддерживает набор расширенных правил, позволяющих работать со строками с завершающим нулем, используя тип PChar.

Иногда связи между ссылкой и переменной не существует по смыслу задачи, в этом случае с указателем нельзя связать никакой объект, а ссылка должна быть пустой. Зарезервированное слово Nil обозначает константу со значением указателя, который ни на что не указывает. После присвоения

P: = Nil;

указатель не будет указывать ни на какой объект. Значение Nil совместимо с любым ссылочным типом.

Операции " =" и " < > " могут использоваться для сравнения операндов типа указатель. Два указателя равны только в том случае, если они ссылаются на один и тот же объект.

Занятие 2. Присвоение значений указателю. Оператор @ с переменной. Оператор @ с параметром процедуры, переданным по значению. Оператор @ с параметром процедуры, переданным по ссылке.

Переменной-указателю можно присвоисть значение другого указателя того же типа. В языке существует универсальный тип указателя, его имя – pointer. Используя тип pointer как промежуточный, можно присвоить значение одного указателя другому и при несовпадении их типов.

Для инициализации указателей в Паскале предусмотрены специальные процедуры и функции.

Переменной-указателю можно присвоить значение с помощью процедуры new, операции @ или функции Ptr.

Процедура new отводит блок памяти в области для динамических переменных и сохраняет адрес этого блока в указателе.

Операция @ ориентирует переменную-указатель на область памяти, содержащую уже существующую переменную. Ее можно применять к статическим переменным, динамическим переменным, процедурам и функциям.

Функция Ptr ориетирует переменную-указатель на определенный адрес в памяти. Тип результата – указатель того же типа, что и Nil, т.е. он может быть назначен любой переменной-указателю.

@ – это унарный оператор. Тип значения указателя управляется через директуву компилятора $T. Если переключателшь отключен, то результатом является нетипизированный указатель, если включен, – то тип указателя соответствует типу объекта. Если оператор @ применяется к процедуре, функции или методу, то результатом всегда будет указатель типа pointer, независимо от состояния опции $T.

Оператор @ с переменной

Использование @ с обычной переменной (не параметром процедуры) несложно.

Например, можно задать декларацию

Type

A = Array [0..99] of char; {Тип массива символов}

Var

X: Array [0..49] of integer; {Массив целых чисел}

pA: ^A; {Указатель на массив символов}

Объявлены переменные двух разных типов: массива целых из 50 элементов и ссылочного на тип А (массив из 100 символов). Чтобы указатель рА указывал на массив Х, надо присвоить ему адрес Х:

рА: = @Х; {Указатель на массив целых чисел}

Теперь pA^ ссылается на массив целых, но по своей природе он указатель на массив символов, поэтому при обращении pA^[i] мы получаем содержимое отдельных байтов массива Х в символьной форме.

Пример. Компонентам массива целых присваиваются сдвинутые на 65 значения индекса, печатается массив целых. Переменной-указателю на символьный массив присваивается адрес массива целых. Снова распечатывается массив, но по адресам значений. Вместо последовательности чисел будет напечатана последовательность ASCII символов от А до z с пробелами.

Program ReInterpretation;

{Интерпретация массива целых чисел как массива из символов}

Uses

Crt;

Type

A = Array [0..99] of char; {Тип A – массив 100 символов}

Var

X: Array [0..49] of integer; {Массив целых чисел}

pA: ^A; {Указатель на массив символов}

i: integer;

Begin

ClrScr;

for i: = 0 to 49 do

begin

X[i]: = 65+i {65 – код буквы А}

write(X[i], ' '); {Печать чисел}

End;

pA: = @X; {Указателю на А присваивается адрес массива целых чисел}

writeln;

for i: = 0 to 99 do

write(pA^[i], ' '); {Печать символов}

End.

Попытка исполнить последний оператор до оператора pA: = @X привела бы к ошибке, поскольку указатель на массив был бы не опpеделен. Массив Х имеет значения 65..114, которые не выходят за пределы младшего байта двухбайтовых элементов типа word. В старших байтах этой переменной – нули. При побайтной печати массива младшие байты выводятся как буквы алфавита, а старшие – как символ #0, который процедурой write интерпретируется как пробел.

Задание. Наберите программу, откомпилируйте ее и проверьте действие.

Оператор @ с параметром процедуры, переданным по значению

Применение @ к формальному параметру процедуры означает то же, что ссылка на фактический параметр, находящийся в стеке.

Например, пусть Х – формальный параметр процедуры, а рХ – указатель на него. Если в процедуре выполнено назначение

рХ: = @Х;

то рХ^ указывает на значение Х, которое хранится в стеке.

Пример. Процедура Test присваивает локальному параметру р его адрес и выводит значение адреса в формате сегмент: смещение. Основная программа обращается к процедуре с фактическим параметром Р и выводит адрес фактического параметра.

Program FormalParam;

{Определение адреса формального параметра}

Uses

Crt;

Var

P: pointer;

Procedure Test(p: pointer);

Begin

p: = @P; {Определение адреса локального параметра}

writeln ('', Seg(p^), ': ', Ofs(p^));

End;

Begin

ClrScr;

Test(P); {Вызов процедуры}

writeln('', Seg(p^), ': ', Ofs(p^));

End.

На экран будет выведен результат исполнения программы:

В процедуре Р=1103: 16378

В основной программе Р=0: 0

Задание. Наберите программу, откомпилируйте ее и проверьте действие.

Оператор @ с параметром процедуры, переданным по ссылке

Применение оператора @ к формальному переменному параметру процедуры приводит к указанию на действительный параметр процедуры (указатель берется из стека).

Например, пусть

Х – формальный переменный параметр процедуры;

а – переменная, передаваемая в процедуру как действительный параметр;

рХ – ссылочная переменная.

Если процедура, как в предыдущем примере, выполняет присвоение

pХ: = @X;

то pХ – указатель на а, а pX^ – ссылка на само значение а.

Задание. Чтобы проверить выше сказанное, модифицируйте в предыдущем примере единственную строчку, передав указатель в процедуру по ссылке:

Procedure Test(Var p: pointer);

Значение указателя в основной программе изменится и будет равно значению указателя в подпрограмме. Результат:

В процедуре Р=1119: 98

В основной программе Р=1119: 98

Задание. Используя одну из созданных Вами программ в теме " Процедуры и функции", модифицируйте ее, применив знания этого занятия.

⇐ Предыдущая34353637383940414243Следующая ⇒

Поделиться: