Лекция 1.2
Динамические структуры данных. Указатели
Основные понятия и определения
Формирование динамических объектов осуществляется с помощью стандартных процедур и функций языка Паскаль.
При разработке программ часто возникает проблема, связанная с тем, что размер обрабатываемой информации может быть определен только в процессе работы программы. Например, размер файла можно определить только после того, как он будет открыт (после выполнения в программе оператора Reset).
Все объявления данных в разделе их описания (раздел var) требуют точного значения размерности (например, …array[ 1..10 ] of …), так как компилятор "распределяет" память для используемой информации до начала выполнения программы и может получить эту размерность только из текста программы (в частности из раздела описания переменных). Такое распределение памяти, до начала выполнения программы, называют статическим.
Распределение памяти в процессе работы программы называют динамическим. Для получения памяти в этом случае в программе необходимо выполнить запрос к операционной системе (ОС). По этому запросу ОС выделяет память в динамической области оперативной памяти компьютера – "куче" (heap) и возвращает программе начальный адрес, выделенного участка оперативной памяти. Доступ к данным, значения которых расположены в выделенной динамической области памяти, требует использования в программе переменной, значением которой и будет возвращаемый ОС адрес. Такая переменная имеет специальный, ссылочный тип данных – указатель.
Формат:
Type
<имя типа> = pointer;
<имя типа> = ^<идентификатор типа>;
Например:
Type
T = pointer; { указатель не связан с определенным типом данных }
T1 = ^integer; { указатель связан с данными целого типа }
Var
{ переменные типа указатель}
ptr1: T;
ptr2: T1;
Для правильной работы с указателями очень важно четко различать два понятия:
· значение самого указателя – адрес динамической памяти.
В приведенном примере это значение переменных ptr1, ptr2
· значение по адресу – значение данных, адрескоторых является значением указателя на эти данные. В программе такие значения обозначаются:
<имя переменной типа указатель>^
Для данного примера значения по адресу обозначаются так: ptr1^, ptr2^.
Чтобы "почувствовать разницу" между значением указателя и значением данных, адресуемых этим указателем, рассмотрим следующую схему (рисунок):
Рисунок
После выполнения операции ptrY:= ptrX изменяется значение указателя ptrY и доступ к данным по предыдущему значению этого указателя потерян (данные превращаются в "мусор")!
После выполнения операции ptrY^:= ptrX^ изменяется значение данных по указателю ptrY. Значение указателя ptrY не изменяется!
В конце работы программы необходимо освободить выделенную память, то есть сообщить ОС, что динамическая область памяти, выделенная программе, может использоваться для других программ или в целях самой ОС.
Состояния указателей
Указатели могут иметь 3 состояния:
1. Инициированный указатель. Указатель указывающий на какие-то данные.
2. Пустой указатель. Указатель содержащий пустое значение – NIL. В C/C++ это NULL, уж не знаю почему тут его так назвали. ВАЖНО! Значением NIL нельзя инициировать переменные других типов (не указатели), это приведет к ошибке при компиляции так как само значение NIL имеет тип Pointer!
3. Мусорный указатель. Очень опасный тип указателя. Он содержит какое-то значение, но не указывает никуда. Указатель оказывается в таком состоянии сразу после объявления и после того как память, на которую он указывает, уже освободили. Ошибки, основанные на попытках использования мусорных указателей, доставляют больше всего хлопот. Поэтому рекомендуется своевременно устанавливать неиспользуемым указателям значение NIL и проверять их при использовании на это значение.
Разыменование
Хорошо, указатели указателями, но как использовать данные адресуемые ими? Для этой цели используется операция разыменования — операция обратная объявлению указателя.
…myInt: ^integer;…myInt^:= 1; // присвоим ячейки памяти на которую указывает myInt значение 1 // (не самому указателю!)inc(myInt^); // увеличим значение в ячейке с адресом myInt…Выражение myInt^ дословно означает следующее: «значение по адресу myInt«. Запомнить несложно: чтобы создать указатель ставим галочку (^) перед типом, чтобы разыменовать — после имени.
Взятие адреса
Важно понимать, что указатель всегда указывает на какой-то байт в памяти, а не на объект (если точнее — на первый байт объекта). И для того, чтобы производить какие-либо действия над объектами или переменными определенных типов, адресуемых указателем, мы должны явно сообщить компилятору тип этих данных.
Мы можем получить адрес абсолютно всего, главное знать, для чего это нужно и каким образом можно с этим работать. Можно даже получить адрес какого либо участка кода и выполнить его. И, естественно, можно получить адреса любых данных в программе. Для этих целей в языке существует специальный оператор – @. Его надо ставить перед именем того объекта, адрес которого нам нужен.
Имена объектов и переменных в этом коде говорят о типе этих объектов. Здесь мы получили адреса переменных (первые 2 строки), объекта какого-то класса (3я строка), какой-то функции (4я строка). Обратите внимание, чтобы получить адрес функции, надо указать её имя без параметров и поставить перед ним @.
Приведение типов
Второй очень важной возможностью, является приведение типов. Приведение типов — это указание компилятору каким образом работать с переменной, непосредственно при её использовании.
Необходимо понимать один очень важный момент: приводить к типу нужно именно данные, адресуемые указателем, а не сам указатель. Пример:
…myPointer: pointer;myVar: integer;…// пусть myPointer указывает на какое-то целое число (4 байта), тогдаmyVar:= integer(myPointer);…Этот код отлично скомпилируется, но он содержит ошибку. Дело в том, что здесь мы привели сам указатель к целому знаковому числу. Результат в итоге будет не предсказуем. Нужно помнить, что указатель, это тоже переменная в стеке, а операция типа @myPointer вполне легальна. Более того, мы можем использовать в качестве указателя любую переменную размером 4 байта. (pointer(myDwordValue)) вполне может послужить указателем. Чтобы приводить именно данные, адресуемые этим указателем необходимо воспользоваться разыменованием:
…myPointer: pointer;myVar: integer;…// пусть myPointer указывает на какое-то целое число (4 байта), тогдаmyVar:= integer(myPointer^); // указатель разыменован…Этот код сделает то, что нам нужно.
Ошибки
Об ошибках связанных с использованием указателей, в кругах программистов ходят легенды. На самом деле все не так страшно. Основной принцип, при работе с указателями — не надеяться на компилятор. Вы должны всегда знать, на что указывает ваш указатель. Если возникают хоть какие-то сомнения, лучше переписать этот участок. Так же стоит всегда держать неиспользуемые указатели инициированными значением NIL и проверять их перед использованием.
Основными ошибками, связанными с использованием указателей, являются утечки памяти, попытки использования неинициированных, пустых или мусорных указателей.
Утечки памяти происходят в том случае если, программист забывает освобождать выделенную память. Также не стоит смешивать разные методы выделения и освобождения динамической памяти. Например, если выделить память средствами Delphi, а затем освободить её уже средствами API, могут возникнуть проблемы.
Неинициированные или мусорные указатели появляются тогда, когда программист создает указатель или освобождает память, на которую они указывают и не заботится об установке этих указателей в NIL. Еще один момент, часто приводящий к появлению указателей такого типа — это создание двух и более указателей, адресующих одну и ту же область памяти. При освобождении такой памяти, часто, «сбрасываются» не все указатели.
Процедуры работы с динамическими структурами данных
Процедуры New и Dispose
В этих процедурах размер запрашиваемой и освобождаемой памяти явно не указывается в процедуре и определяется типом данных. Поэтому описание указателя должно быть только такого вида: ^<имя типа данных>.
New(P) – выделить память, размер которой определяется типом данных указателя P. После выделения памяти значением переменной P становится начальный адрес выделенный области памяти.
Выделяемая процедурой New память не инициализируется каким-либо значением.
Dispose(P) – освободить память, начальный адрес, который определяется значением указателя P. Размер освобождаемой памяти определяется типом данных указателя P.