Процедуры работы с динамическими структурами данных

Лекция 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«. Запомнить несложно: чтобы создать указатель ставим галочку (^) перед типом, чтобы разыменовать — после имени.

Взятие адреса

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

Мы можем получить адрес абсолютно всего, главное знать, для чего это нужно и каким образом можно с этим работать. Можно даже получить адрес какого либо участка кода и выполнить его. И, естественно, можно получить адреса любых данных в программе. Для этих целей в языке существует специальный оператор – @. Его надо ставить перед именем того объекта, адрес которого нам нужен.

…myPointer_1 := @myIntegerVariable;myPointer_2 := @myStringVariable;myPointer_3 := @myObject;myPointer_4 := @nameOfMyFunction;…

Имена объектов и переменных в этом коде говорят о типе этих объектов. Здесь мы получили адреса переменных (первые 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.

Односвязный список | Динамические структуры данных #1


Похожие статьи.

Понравилась статья? Поделиться с друзьями: