Как известно, основными рабочими объектами в программах являются переменные. Имя переменной заменяет адрес области памяти, где при выполнении программы хранится значение этой переменной. Одной из важнейших функций компилятора является назначение адресов памяти всем переменным программы. Такое распределение памяти называют статическим – оно выполняется при компиляции программы на язык машины. Недостатком такого способа распределения памяти является его жесткость – для изменения объема памяти, выделенной под какую-либо переменную необходимо перекомпилировать программу.
Во многих задачах подобная статичность является очень неудобной, поэтому многие языки программирования, в частности С/С++ и Паскаль, реализуют другой способ создания переменных – динамический. Он позволяет создавать переменные в процессе выполнения программы в ответ на вызов специальных стандартных функций. При этом динамически выделяются необходимые области памяти, в которые заносятся значения соответствующих переменных. Когда необходимость в использовании таких переменных исчезает, соответствующие области памяти можно освободить для других целей.
Механизм динамического распределения памяти основан на использовании специальных переменных, которые называют указателями. Переменные-указатели или переменные ссылочного типа - это специальные переменные, значениями которых являются адреса областей памяти. Каждый указатель может адресовать некоторую область памяти, в которой могут находиться любые данные. Чаще всегопод адрес отводится 4 байта. Необходимо четко различать переменную-указатель и адресуемую ею область памяти.
 значение указателя: адрес области памяти 00 00 4А F0
|
| Адресуемые данные (массивы, записи), располагающиеся в памяти начиная с адреса 00 00 4A F0 |
Для описания переменных-указателей необходимо:
· ввести имя переменной
· связать эту переменную с адресуемыми данными, указав их тип или имя с помощью специального символа ^:
var указатель: ^ базовый тип;
Например, указатели на простейшие базовые типы вводятся следующим образом:
pInt: ^ integer; {указатель на отдельное целое число}
pChar: ^ char; {указатель на отдельный символ}
pString1, pStr2: ^ string; {два указателя на символьные строки}
Ссылочные типы можно предварительно ввести в разделе описания типов, а потом объявить соответствующую переменную. Например:
type TpString = ^ string; {ссылочный тип для адресации текстовых строк}
var pStr1, pStr2: TpString; {переменные-указатели на строки}
Можно ввести указатели на структурные типы (массивы, записи), используя для этого предварительно объявленные типы:
type TMyArray = array [1..100] of integer;
var pMyArray1: ^TMyArray; {указатель на начало базового массива}
Необходимо понимать, что объявление переменной-указателя НЕ приводит к выделению памяти для самих адресуемых данных: память выделяется ТОЛЬКО для указателя (например – 4 байта). Поэтому для правильного использования механизма динамического распределения памяти НЕ следует объявлять переменные базового типа (точнее, их объявлять можно, но к динамическому распределению памяти это никакого отношения не имеет).
Например:
type TMyRecord = record
Field1: SomeType1;
Field2: SomeType2;
end;
var MyRec: TMyRecord; {обычная переменная-запись со статическим выделением памяти}
pMyRec: ^TMyRecord; {переменная-указатель на будущую структуру-запись с выделением памяти только для указателя, но не для самой записи!}
Динамическое создание переменных базового типа выполняется вызовом стандартной подпрограммы New с параметром-указателем, связанным с данным базовым типом:
New (pMyRec);
New (pStr1);
Данный вызов выполняет два следующих действия:
· обращается к операционной системе для выделения области памяти, необходимой для размещения переменной базового типа
· устанавливает начальный адрес этой области памяти в качестве значения переменной-указателя
Вызов New можно выполнять в любом месте в теле программы любое число раз, в том числе – циклически. Это позволяет при выполнении программы динамически создавать любое необходимое число переменных базового типа.
После выделения области памяти в неё можно записать необходимое значение, используя ссылочную переменную и символ ^ после ее имени:
pStr1 ^: = ‘Привет’;
pInt^: = 1;
Комбинация имени переменной-указателя и символа ^ превращает указатель в переменную базового типа. С такой переменной можно делать все те операции, которые разрешены для базового типа. Например:
pInt^: = pInt^ + 1;
pChar^: = ‘A’;
ReadLn (pStr1^);
pMyArray^[ i ]: = 10;
pMyRec^.Field1: = соответствующее значение;
Обращаем внимание на последние два присваивания, конструкцию которых можно прокомментировать следующим образом:
· pMyArray и pMyRec – это имена ссылочных переменных
· pMyArray^ и pMyRec^ - это условные обозначения объектов базового типа, т.е. массива и записи соответственно
· pMyArray^[ i ] и pMyRec^.Field1 – это обозначения отдельных элементов базового типа, т.е. i-го элемента массива и поля записи с именем Field1
C переменными ссылочного типа допустимы две операции:
1. Присваивание значения одной ссылочной переменной другой ссылочной переменной того же базового типа:
pInt1: = pInt2;
После этого оба указателя будут адресовать одну и ту же область памяти.
2. Сравнение двух ссылочных переменных на равенство или неравенство:
if pInt2 = pInt1 then …
В практических задачах довольно часто приходится использовать “пустые указатели”, которые никуда не указывают. Для задания такого пустого указателя используется специальное служебное слово nil. Например:
pInt1: = nil; {указатель ничего не адресует}
if pStr1 = nil then...{проверка указателя на пустоту}
Для освобождения динамически распределенной памяти используется вызов Dispose с параметром-указателем:
Dispose (pStr1);
После этого вызова соответствующая переменная-указатель становится неопределенной (НЕ путать с ПУСТЫМ указателем!) и ее нельзя использовать до тех пор, пока она снова не будет инициализирована с помощью вызова New или инструкции присваивания. Использование вызова Dispose может приводить к весьма неприятной ситуации, связанной с появлением так называемых “висячих” указателей: если два указателями адресовали одну и ту же область памяти (а это встречается очень часто), то вызов Dispose с одной из них оставляет в другой переменной адрес уже освобожденной области памяти и повторное использование этой переменной приведет либо к неверному результату, либо к аварийному завершению программы.
1.3. Дополнительные вопросы использования переменных-указателей
Иногда бывает удобно присваивать ссылочной переменной адрес базового объекта, используя для этого непосредственно сам объект. Для этого можно использовать специальный оператор взятия адреса @:
var x: real; {обычная переменная вещественного типа}
pReal: ^ real; {указатель на вещественный тип}
Begin
x:= 1.5; {обычная переменная x получает значение 1.5}
pReal:= @x; {указатель получает адрес размещения числа 1.5}
Write (pReal^: 6: 2); {вывод числа 1.5 с помощью указателя pReal}
end;
Принципиальное отличие данного способа использования указателя от ранее рассмотренного состоит в том, что здесь НЕ используется механизм динамического распределения памяти, т.е. НЕ используются стандартные функции New и Dispose: переменная x является обычной статической переменной, размещаемой в статической области памяти, просто доступ к ней по каким-то причинам организуется не напрямую, а с помощью ссылочной переменной.
Довольно мощным использованием указателей является объединение их в массив. Это можно сделать в силу того, что все переменные-указатели с одним и тем же базовым типом являются однотипными. Массивы указателей можно обрабатывать с помощью циклов. В качестве примера рассмотрим массив указателей на записи некоторой структуры.
type TRec = record {описание базового типа-записи}
x, y: integer;
name: string;
end;
TpRec = ^TRec; {описание ссылочного типа}
var ArrOfPointer: array [1..100] of TpRec;
{объявление массива указателей на записи}
Begin
for i:= 1 to 100 do ArrOfPointer [ i ]^.x: = Random (100);
{цикл установки значений в поле x}
end.
При использовании указателей есть еще одна весьма мощная, но опасная возможность – так называемые нетипизированные указатели, которые не связаны ни с каким базовым типом и поэтому могут адресовать объекты любых типов. Подобные указатели объявляются с помощью служебного слова pointer:
var pAll: pointer;
Распределение и освобождение памяти для нетипизированных указателей производится с помощью специальных стандартных функций GetMem и FreeMem, которые имеют по два параметра – имя нетипизированного указателя и байтовый размер выделяемой области памяти. Для задания этого размера удобно использовать стандартную функцию SizeOf, которая принимает имя типа данных, а возвращает необходимый размер области памяти. Например:
type TRec = record {описание базового типа-записи}
x, y: integer;
name: string;
end;
var p1, p2: pointer; {объявление двух нетипизированных указателей}
Begin
GetMem (p1, SizeOf (TRec)); {распределение памяти под объект-запись}
p1^.name:= ‘Text’;
p2:= p1; {оба указателя адресуют одну и ту же область}
FreeMem (p1, SizeOf (TRec));
{освобождение памяти и деактуализация указателя p1}
end.
В заключение необходимо отметить, что использование динамической памяти требует большой осторожности и может быть причиной трудноуловимых ошибок времени выполнения.
1.4. Контрольные вопросы по теме
1. Что включает в себя понятие структуры данных?
2. Назовите основные линейные структуры данных и их разновидности
3. Назовите основные нелинейные структуры данных и их разновидности
4. В чем состоят отличия статического и динамического распределения памяти?
5. Что такое переменные ссылочного типа (указатели)?
6. Что включает описание переменных-указателей?
7. Приведите примеры описания простых переменных-указателей
8. Как вводится переменная-указатель на текстовые строки (2 способа)?
9. Как вводится переменная-указатель на массив?
10. Как вводится переменная-указатель на структуру-запись?
11. Какая память выделяется транслятором при объявлении переменных-указателей?
12. Какие стандартные подпрограммы используются для динамического выделения и освобождения памяти?
13. Что происходит при выполнении подпрограммы New?
14. Как выполняется установка необходимого значения в динамически выделенную область памяти?
15. Если р – переменная-указатель, то что определяет выражение p^?
16. Если р – переменная-указатель на массив, то как можно определить i-ый элемент массива?
17. Если p – переменная-указатель на запись, то как можно определить некоторое поле этой записи?
18. Какие операции разрешены с переменными-указателями?
19. Что такое “пустой указатель” и как он задается?
20. Что происходит при вызове стандартной подпрограммы Dispose?
21. Какие неприятности могут возникать при использовании подпрограммы Dispose?
22. Как можно переменной-указателю непосредственно присвоить адрес базового объекта?
23. Как задается оператор взятия адреса и для чего он используется?
24. Как задается массив указателей?
25. Если Pointers есть массив указателей, то что определяет выражение Pointers [ j ]^?
26. Что такое нетипизированные указатели и как они описываются?
27. Какие стандартные функции используются для распределения и освобождения памяти с нетипизированными указателями?
28. Приведите пример записи функции для распределения памяти с нетипизированным указателем.
29. Приведите пример записи функции для освобождения памяти с нетипизированным указателем.
Тема 2. Структуры данных “стек” и “очередь”
2.1. Что такое стек и очередь?
Стек – это линейная структура данных, в которую элементы добавляются и удаляются только с одного конца, называемого вершиной стека. Стек работает по принципу “элемент, помещенный в стек последним, извлечен будет первым”. Иногда этот принцип обозначается сокращением LIFO (Last In – First Out, т.е. последним зашел – первым вышел).
Очередь – это линейная структура данных, в которую элементы добавляются с одного конца (конец очереди), а удаляются - с другого (начало очереди). Очередь работает по принципу “элемент, помещенный в очередь первым, извлечен будет тоже первым”. Иногда этот принцип обозначается сокращением FIFO (First In – First Out, т.е. первым зашел – первым вышел). Элементами стеков и очередей могут быть любые однотипные данные. В простейшем случае – целые числа, чаще всего – записи заранее определенной структуры. Стеки и очереди очень широко используются в системных программах, в частности – в операционных системах и компиляторах. Программная реализация стеков и очередей возможна двумя способами:
· статически с помощью массива
· динамически с помощью механизма указателей