Для какой структуры данных выделяется непрерывная область в памяти

Абстрактные структуры данных предназначены для удобного хранения и доступа к информации. Они предоставляют удобный интерфейс для типичных операций с хранимыми объектами, скрывая детали реализации от пользователя. Конечно, это весьма удобно и позволяет добиться большей модульности программы. Абстрактные структуры данных иногда делят на две части: интерфейс, набор операций над объектами, который называют АТД(абстрактный тип данных) и реализацию. Ниже, где возможно, собственно АТД будут отделены от их реализации.

Каждый уже имел дело с простыми абстрактными структурами данных — например, когда оперировал с числами. Языки программирования высокого уровня(Паскаль, Си..) предоставляют удобный интерфейс для чисел: операции +, *, = .. и т.п, но при этом скрывают саму реализацию этих операций, машинные команды.

Статические структуры относятся к разряду непримитивных структур, которые, фактически, представляют собой структурированное множество примитивных, базовых, структур. Например, вектор может быть представлен упорядоченным множеством чисел. Поскольку по определению статические структуры отличаются отсутствием изменчивости, память для них выделяется один раз и ее объем остается неизменным до уничтожения структуры. Слово ‘статический’ относится скорее к реализации структуры, нежели к АТД.

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

Слово ‘массив’ употребляется в различных контекстах:

как АТД, т.е множество с операциями:

Получить элемент с номером N
Записать элемент с номером N

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

В случае реализации массива через такую структуру(языки Паскаль, Си) номер соответствует смещению от начала области. В некоторых языках, например, PHP, массив(здесь АТД!) реализован по-другому.

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

Минус — один, но тоже большой: статичность, неизменность структуры. Одномерный массив иногда называют вектором.

Динамические структуры по определению характеризуются отсутствием физической смежности элементов структуры в памяти непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе ее обработки.

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

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

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

Достоинства связного представления данных — в возможности обеспечения значительной изменчивости структур;

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

Вместе с тем связное представление не лишено и недостатков, основные из которых:

на поля связок расходуется дополнительная память;
доступ к элементам связной структуры может быть менее эффективным по времени.

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

Cписки

Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Длина списка равна числу элементов, содержащихся в списке, список нулевой длины называется пустым списком. Линейные связные списки являются простейшими динамическими структурами данных.

Графически связи в списках удобно изображать с помощью стрелок. Если компонента не связана ни с какой другой, то в поле указателя записывают значение, не указывающее ни на какой элемент. Такая ссылка обозначается специальным именем — nil.

На рис. 1 приведена структура односвязного списка. На нем поле INF — информационное поле, данные, NEXT — указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.

Рис. 1: Представление односвязного списка в памяти

Двусвязный список характеризуется наличием пары указателей в каждом элементе: на предыдущий элемент и на следующий:

Рис. 2: Представление двусвязного списка в памяти

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

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

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

Рис. 3: Структура кольцевого двухсвязного списка

массива: выделяется место под N элементов разом, а затем описываются операции над данным типом данных в терминах операций над элементами массива.
списка: память выделяется и освобождается по мере необходимости.

Cтек

Стек — такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека — магазин и очередь, функционирующая по принципу LIFO (Last — In — First- Out — «последним пришел — первым исключается»). Примеры стека: винтовочный патронный магазин, тупиковый железнодорожный разъезд для сортировки вагонов.

Основные операции над стеком — включение нового элемента (английское название push — заталкивать) и исключение элемента из стека (англ. pop — выскакивать).

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

x:=pop(stack); push(stack,x);

Некоторые авторы рассматривают также операции включения/исключения элементов для середины стека, однако структура, для которой возможны такие операции, не соответствует стеку по определению.

а). пустого;
б-г). после последовательного включения в него элементов с именами ‘A’, ‘B’, ‘C’;
д, е). после последовательного удаления из стека элементов ‘C’ и ‘B’;
ж). после включения в стек элемента ‘D’.

Рис. 4: Включение и исключение элементов из стека

Как видно из рис. С.1, стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое название, например A,B,C,D. Тогда в момент времени, когда на столе книг нет, про стек аналогично можно сказать, что он пуст, т.е. не содержит ни одного элемента. Если же мы начнем последовательно класть книги одну на другую, то получим стопку книг (допустим, из n книг), или получим стек, в котором содержится n элементов, причем вершиной его будет являться элемент n+1. Удаление элементов из стека осуществляется аналогичным образом т. е. удаляется последовательно по одному элементу, начиная с вершины, или по одной книге из стопки.

Очередь FIFO

Очередью FIFO (First — In — First- Out — «первым пришел — первым исключается»). называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение — с другой стороны (называемой началом или головой очереди). Те самые очереди к прилавкам и к кассам, которые мы так не любим, являются типичным бытовым примером очереди FIFO.

Основные операции над очередью — те же, что и над стеком — включение, исключение, определение размера, очистка, неразрушающее чтение.

[Статическая реализация очереди на основе массива]
Динамическая реализация очереди аналогична реализации стека.

Дек

Дек — особый вид очереди. Дек (от англ. deq — double ended queue,т.е очередь с двумя концами) — это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека — дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.

включение элемента справа;
включение элемента слева;
исключение элемента справа;
исключение элемента слева;
определение размера;
очистка.

Физическая структура дека в статической памяти идентична структуре кольцевой очереди. Динамическая реализация является очевидным объединением стека и очереди.

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

Примером дека может быть, например, некий терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек.

Для какой структуры данных выделяется непрерывная область в памяти

5.2.2. Структуры данных

Структуры данных – это абстрактные структуры или классы, которые используются для организации данных и предоставляют пользователям различные операции над этими данными.

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

В любом языке программирования массивы имеют несколько общих свойств:

Содержимое массива хранится в непрерывной области памяти.
Все элементы массива имеют одинаковый тип; поэтому массивы называют однородными (homogeneous) структурами данных.
Существует пряммой доступ к элементам массива. (В случае других структур данных это необязательно так. Например, в структуре данных скип-список (SkipList) для доступа к конкретному элементу скип-списка нужно предварительно осуществить поиск среди других элементов скип-списка, пока не найдется требуемый элемент. В случае с массивами, если необходимо получить доступ к i -му элементу массива, можно сделать это одной операцией: arrayName [ i ].)

Типичные операции для массивов включают:

Выделение элемента(Allocation).
Доступ к элементу (Accessing).
Изменение размеров массива (Redimensioning).

Когда в C# объявляется массив, его значение равняется null . Например, следующая строчка кода просто создает переменную с именем booleanArray , которая равна null : bool [ ] booleanArray .

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

booleanArray = new bool[10],

или более обобщенно:

arrayName = new arrayType [ allocationSize ].

Массивы являются превосходной структурой данных, если требуется хранить коллекцию однородных типов, к которым нужно иметь прямой доступ. Поиск в неотсортированном массиве занимает линейное от размера массива время. Это приемлемо, если мы работаем с маленькими массивами, или когда нам нужно лишь изредка производить поиск внутри массива. Если же приложение хранит большие массивы, в которых часто производится поиск, то существуют структуры данных гораздо лучше приспособленные к таким ситуациям.

Многомерные массивы , как и одномерные требуют постоянного времени для доступа к своим элементам. Время поиска в n-элементном массиве равно O ( n ). Для двумерного массива размером n x n время поиска будет равно O(n 2 ), потому что процедура поиска должна будет просмотреть n 2 элементов. В более общем случае время поиска в k -мерном массиве есть O(n k ).

Несмотря на то, что обычные массивы, безусловно, находят широкое применение, они накладывают определенные ограничения на программиста, поскольку каждый массив может хранить данные только одного типа (однородность) и вдобавок перед использованием массива требуется выделять (allocate) определенное количество элементов.

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

Структура данных ‘стек’. Стеком будем называть последовательность элементов, упорядоченных по времени их поступления. Эта последовательность доступна только с одного конца (вершины стека). Для работы со стеком необходим указатель вершины стека. Основные операции над стеком следующие: «запомнить в стеке» и «извлечь из стека» (причем извлекается последний из занесенных в стек элементов — то есть элемент с вершины стека). Поэтому говорят, что стек – это структура типа LIFO — «Last In — First Out» — «последним зашел — первым вышел».

Для представления стека в программе обычно используется одномерный массив (назовем его B), нумерация элементов которого начинается с нуля. В этом нулевом элементе массива хранится индекс первого свободного места в массиве (т.е. увеличенный на 1 индекс вершины стека). Если массив пуст, то указатель равен 1 (B[0]=1).

Добавление элемента X в стек реализуется очень просто — на первое свободное место (индекс которого хранится в B[0]) помещается X, после чего индекс первого свободного места увеличивается на 1:

Если необходимо извлечь элемент x из стека, то берется последний из занесенных элементов (естественно, только в том случае, если стек непуст), и указатель на первое свободное место уменьшается на 1:

Структура данных ‘список’. Каждый элемент списка имеет указатель на следующий за ним элемент (другими словами – хранит информацию о расположении следующего элемента), а если список двусвязный (двунаправленный), то имеет также указатель и на предшествующий элемент. Кроме того есть переменная, указывающая на первый элемент списка. Например, двунаправленный список может быть реализован с помощью двумерного массива A[1..3, 1..N], где содержимое A[2,i] определяет позицию (индекс, адрес) элемента, предшествующего элементу A[1,i], а содержимое A[3,i] определяет позицию элемента, следующего за A[1,i].

Основные операции над списком следующие: «удалить из списка» и «поместить в список».

Например, помещение в список элемента х после элемента A[1,i] может выглядеть так:

Здесь j — адрес свободной позиции в массиве А.

Структура данных ‘очередь’. Очередь в программировании, как и очередь в магазине, имеет начало и конец. Если приходит новый элемент, то он становится в конец очереди, если необходимо взять элемент из очереди, то он берется из ее начала. Очередь будем представлять в виде массива. Пусть у нас есть индекс первого — BEG и последнего — FIN элементов очереди (если очередь пуста, то BEG=FIN+1; сначала же BEG=1, FIN=0).

Очередь опишем так: var Queue=array[1..MaxQ] of element.

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

type element = record
x: byte;
y: byte;
end;

где element — это запись, состоящая из x-овой и y-овой координаты.

С очередью можно проводить операции: вставка в очередь InQueue, удаление из очереди OutQueue.

Procedure InQueue (x : element);

Procedure OutQueue (var x : element);

Уровни структур данных

Структуры данных могут рассматриваться на разных уровнях. Применяются три уровня структур данных:

1. содержательный,
2. логический,
3. физический.

На содержательном уровне структур данных исследуются конкретные объекты обработки, их свойства и отношения между объектами. На этом уровне важны не только значения, но и смысл данных.

На логическом или абстрактном (логические структуры) уровне структура данных считается машинно-независимым логическим понятием, и выделяются следующие задачи: определение массивов данных как объектов исследования, выделение состава массива, определение структуры данных по заданным требованиям, разработка количественных методов оценки эффективности различных видов структур данных.

Физический уровень (физическая структура). На этом уровне рассматриваются среда хранения данных (память ЭВМ) и представление в ней значений (ячейки, разряды ячеек, их адреса и взаимное расположение значений.), т.е. отображение данных в памяти ЭВМ. В общем случае между логической и соответствующей ей физической структурами существует различие, степень которого зависит от самой структуры и особенностей той физической среды, в которой она должна быть отражена.

Различия между уровнями структур данных могут быть пояснены следующим примером. Пусть требуется выполнить ввод данных в память ЭВМ, используя некоторую буферную область (содержательный уровень). С этой целью удобно использовать кольцевую очередь (логический уровень), которая в работающей программе может быть реализована при помощи одномерного массива как непрерывного блока в памяти или при помощи связного списка, допускающего разнесённое размещение в памяти своих элементов (физический уровень).

Классификация структур данных

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

Наиболее простым и понятным критерием классификации является сложность структур данных.

По уровню сложности структуры данных разделяются на:

1. простые структуры — обычные переменные или константы стандартных для языков программирования типов, а также динамические переменные этих же типов;
2. наборы однотипных данных — массивы одномерные (или векторы), двумерные (матрицы) и многомерные;
3. составные структуры, отличные от массивов — записи и объекты классов и им подобные структуры;
4. динамические структуры с внутренними связями — связные списки, деревья, графы.

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

1. линейные структуры — одномерные массивы (или векторы), линейные списки, линейные очереди,стеки;
2. прямоугольные структуры — двумерные (матрицы) и многомерные массивы;
3. кольцевые структуры — кольцевые списки, кольцевые очереди, некоторые реализации графов;
4. ветвящиеся структуры — деревья различных видов, некоторые реализации графов;
5. сетевые структуры — графы.

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

1. обычные — переменные стандартных типов, обычные (т.е. не динамические) массивы, записи и т.п.;
2. динамические (создаваемые и разрушаемые с помощью специальных операций или процедур динамического выделения и освобождения памяти) — динамические массивы, динамические переменные, связные списки, деревья.

В зависимости от наличия или отсутствия связей между элементами структуры данных различают:

1. несвязные структуры — векторы, массивы, строки, стеки, очереди;
2. связные — списки, деревья, графы.

В зависимости от постоянства во время работы программы различают:

1. статические (неизменяющиеся) структуры — переменные различных типов, записи, массивы, в том числе динамические, а также списки, деревья и графы в тех случаях, когда они являются фиксированными и могут быть построены на основе, например, массива.
2. динамические (изменяющиеся) — списки, деревья, очереди, стеки, в общем случае графы.

Здесь следует обратить внимание на то, что термин «динамические» употребляется в разных смыслах, и структуры, динамические по способу создания, могут быть статическими по своему поведению. Структуры, динамические по поведению, как правило, оказываются динамическими и по способу создания. Также следует обратить внимание на то, что термин «статические» используется и в некоторых языках программирования, например, в Си и Си++, и там его смысл в значительной степени отличается от подразумеваемого в приведённой классификации.

По месту размещения в памяти ЭВМ-.

1. существующие в оперативной памяти (или внутренние) — ими могут быть все ранее рассмотренные примеры структур данных. Кроме того, такие структуры могут размещаться:
- — в регистрах процессора — регистровые, обычно переменные стандартных типов, размер которых не превышает разрядности процессора;
- — в стеке — локальные (в некоторых языках принято обозначение «автоматические»)— любые не статические и не динамические структуры;
- — в свободной (динамически выделяемой) памяти или «куче» — глобальные, локальные статические (для языков Си и Си++) и все динамические структуры.
Следующий критерий классификации справедлив только для некоторых языков программирования, а именно тех, которые допускают несовпадение типов данных в операциях и неявное преобразование типов с созданием временных объектов. Для этого критерия достаточно сложно подобрать название в одном или нескольких словах, поэтому сразу приведём его варианты:
- 1. данные, создаваемые самим программистом (независимо от способа и времени создания), в англоязычной литературе по программированию часто обозначаемые словом persistent — «устойчивый» («постоянный», «постоянно существующий»). Таким являются структуры всех данных, явно созданных программистом при написании программы;
- 2. создаваемые и разрушаемые непосредственно во время работы программы без участия программиста, обычно во вспомогательных целях, например, при несовпадении типов данных в каких-либо операциях. Для них используется термин transient — «временный», «преходящий». Их действительно можно коротко назвать временными, поскольку они обычно уничтожаются сразу после их использования. Как правило, такие структуры данных являются безымянными. В некоторых языках программирования, например, Си++, такими данными могут быть данные любых типов. О временных структурах часто говорят, что они создаются не программистом, а самим компилятором (ещё один вариант — компилятор строит код программы так, чтобы эти данные были созданы и разрушены в нужные моменты работы программы).
Приведём ещё один вариант классификации структур данных [9], совпадающий до некоторой степени с рассмотренным и представленный на рисунках 1.1 — 1.3. При этом необходимо помнить, что любая классификация является достаточно условной и может не во всех случаях отражать реальность. Например, на рисунке 1.3 такие структуры данных как очередь, стек и дек отнесены к односвязным линейным структурам. В реальности они могут быть и двусвязными, и кольцевыми, и даже вообще несвязными.

Рис. 1.1— Простые статические структуры данных

Рис. 1.2 — Составные статические структуры данных

Рис. 1.3 — Динамические структуры данных

Структуры данных и способы их реализации

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

Абстрактное понятие «Структура данных» определяет способ объединения некоторого набора отдельных элементов данных в единое целое и методы обработки этих наборов.

Например, классическая структура МАССИВ есть объединение элементов данных, обладающее следующими свойствами:
- все элементы относятся к одному типу (не обязательно простейшему);
- для хранения элементов массива выделяется непрерывная область памяти;
- каждый элемент имеет порядковый номер-индекс, по которому можно выполнить очень быстрое обращение к данному элементу, независимо от его расположения в массиве.
```
var MyArr : array [ 1 .. 100 ] of integer;
```
```
int MyArr[100] ;
```
С другой стороны, конструкция типа запись/структура характеризуется следующими особенностями: объединять можно элементы данных разных типов; вся структура занимает непрерывную область памяти; каждый элемент объявляется как поле со своим уникальным именем; доступ к элементам выполняется по именам полей.

Пример объявления записи/структуры с тремя полями и переменной соответствующего типа. Паскаль
```
type TMyRec = record field1 : integer; field2 : string; field3 : real; end; var MyRec : TMyRec;
```
```
struct MyStruct < int field1; char field2[80]; float field3; >; struct MyStruct MyStr;
```
Возможное размещение полей такой записи/структуры в памяти:

Обе эти стандартные структуры служат основой построения других важных структур, широко используемых в различных приложениях: стеки, очереди, списки, деревья, графы, хеш-таблицы. Каждая из них имеет свои особенности объединения компонент и их обработки и как следствие — свою область применения.

Основные структуры данных представлены на следующей схеме:

Большинство дополнительных структур данных можно реализовать двумя способами:
- на основе массива (статическая или непрерывная реализация);
- на основе использования специальных адресных переменных и механизма динамического распределения памяти (динамическая или связная реализация).
- статическая реализация применима в случае заранее известного и не меняющегося числа элементов в структуре данных (массив, однако!) и часто обеспечивает более высокую скорость выполнения операций;
- динамическая реализация рассчитана на случай, когда число компонентов в структуре данных может изменяться при выполнении программы в очень широких пределах, и такая реализация позволяет более экономно использовать оперативную память.
Статическая (непрерывная) реализация связана с процессом распределения памяти при компиляции программы. Каждой объявленной переменной компилятор выделяет необходимую по размеру область памяти и связывает адрес этой области с именем переменной.

Например, пусть объявлены следующие три переменные. Паскаль
```
var x, y : real; MyArr : array [ 1 .. 100 ] of integer;
```
```
float x, y; int MyArr[100];
```
Тогда компилятор при обработке этих объявлений распределит память примерно следующим образом (с учетом возможных различий в представлении базовых типов на разных платформах):

Особенность статического распределения памяти – жесткая фиксация выделенных областей, невозможность изменения этого распределения при выполнении программы.

Во многих задачах подобная статичность является слишком неудобной, поэтому многие языки программирования, в частности С/С++ и Паскаль, реализуют и другой способ распределения памяти – динамический. Он позволяет выделять память под значения переменных непосредственно в процессе выполнения программы в ответ на вызов специальных стандартных функций. Когда необходимость в использовании этих значений исчезает,

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

Механизм динамического распределения памяти основан на использовании специальных переменных, которые называют указателями. Переменные-указатели, или переменные ссылочного типа — это специальные переменные, значениями которых являются адреса областей памяти. Каждый указатель может адресовать некоторую область памяти, в которой могут находиться обрабатываемые данные. Чаще всего под адрес отводится 4 байта.

Необходимо четко различать переменную-указатель и адресуемую ею область памяти. Схематично взаимодействие указателей и адресуемых данных можно показать следующим образом:

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

Отличия в использовании обычных переменных и переменных-указателей:
1. Объявление переменной с выделением компилятором для хранения ее значений в необходимой области памяти
2. Занесение в выделенную область самих данных с использованием имени переменной
3. Использование данных через имя переменной
1. Объявление указателя специальным образом БЕЗ выделения компилятором памяти под данные
2. Запрос памяти для адресуемых данных во время выполнения программы
3. Занесение в динамически выделенную область некоторых данных ТОЛЬКО через переменную-указатель
4. Использование данных тоже ТОЛЬКО через переменную-указатель
5. Освобождение памяти, если данные больше не нужны
- ввести имя переменной; хорошая рекомендация – начать имя с латинского символа р (от слова pointer);
- связать эту переменную с адресуемыми данными, указав их тип или имя с помощью специального символа ^ (Паскаль) или * (Си)
Еще раз подчеркнем, что объявление переменной-указателя НЕ приводит к выделению памяти для самих адресуемых данных: память выделяется ТОЛЬКО для указателя (например – 4 байта). Поэтому для правильного использования механизма динамического распределения памяти НЕ следует объявлять переменные базового типа (точнее, их объявлять можно, но к динамическому распределению памяти это никакого отношения не имеет).
```
var MyRec : TMyRec; // обычная переменная-запись со статическим // выделением памяти для полей записи pMyRec : ^TMyRec; // переменная-указатель на структуру-запись с // выделением памяти только для указателя, но не для полей записи!
```
Важное замечание: объявление переменной-указателя – это всего лишь объявление, т.е. никакого адресного значения эта переменная не получает и использовать ее для доступа к данным категорически нельзя!

Для использования указателя ему надо присвоить некоторое значение – адрес области памяти, где должны храниться обрабатываемые данные. Запрос такой области памяти во время работы программы выполняется за счет обращения к специальным стандартным функциям – New (Паскаль) или malloc (Си, сокращение от Memory Allocation). Эти вызовы обеспечивают динамическое выделение памяти для новых данных программы и вместе с переменными-указателями являются основой реализации динамических структур.

К сожалению, синтаксически использование данных вызовов различно.

Вызов New имеет обязательный параметр – имя переменной-указателя, связанной на этапе объявления с адресуемыми данными, а вызов malloc – параметр-размер запрашиваемой области памяти (удобно использовать стандартную функцию sizeof (тип) для автоматического получения размера).

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

Примеры вызовов для ранее объявленных указателей:

Вызовы New и malloc можно выполнять в любом месте программы любое разумное число раз, в том числе – внутри циклов. Это позволяет при выполнении программы динамически создавать достаточно много данных. Ограничением по количеству создаваемых данных является размер так называемой кучи (heap), т.е. области памяти, которая выделяется программе операционной системой для динамически создаваемых данных.

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

указатель^ // Паскаль
*указатель // Си

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

Из всего вышесказанного ясно, что переменные адресного типа – это особые переменные со своим набором операций. Основными являются следующие две операции:

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

pMyArr2 : = pMyArr1; // Паскаль
pMyNewStruct = pMyStruct; // Си
- присваивать можно значения только однотипных указателей, т.е. объявленных с одним и тем же базовым типом (в языке Си при определенных условиях можно
- присваивать указатели разных типов, но пользоваться этой возможностью надо крайне осторожно!);
- указатель в правой части должен иметь некоторое значение;
- после выполнения операции оба указателя будут адресовать одну и ту же область памяти
В частном случае указателю можно присвоить «пустое» (нулевое) значение. Такая переменная считается определенной, но никуда не указывающей. Для этого используются специальные служебные слова nil (Паскаль) или NULL (Си):

pMyNewStruct = NULL;
pMyArr := nil ;

2. Сравнение двух однотипных указательных переменных на равенство или неравенство:
```
if ( pInt2 = pInt1 ) then begin . . . end; if ( pMyNewArr != pMyOldArr ) < . . . >;
```
Особенности операции сравнения: сравнивать можно только однотипные указатели; оба указателя должны быть инициализированы. сравниваются не адресуемые данные, а адресные значения!

С помощью служебных слов nil и NULL можно проверять указатели на пустое значение, что часто приходится делать в операциях обработки динамических структур.

Для освобождения динамически распределенной памяти используются противоположные стандартные вызовы — Dispose (Паскаль) и free (Си). Параметром этих вызовов является указательная переменная, используемая для доступа к данным, которые больше программе не нужны:

Dispose ( pMyArr );
free ( pArrInt );

Важное замечание! После отработки этих вызовов соответствующая переменная-указатель становится неопределенной (НЕ путать с ПУСТЫМ указателем!) и ее НЕЛЬЗЯ использовать до тех пор, пока она снова не будет инициализирована с помощью вызова New/malloc или инструкции присваивания. Это может приводить к весьма неприятной ситуации, связанной с появлением так называемых «висячих» указателей: если два указателя адресовали одну и ту же область памяти (а это встречается весьма часто), то вызов Dispose/free с одной из них в качестве параметра оставляет в другой переменной адрес уже освобожденной области памяти и повторное использование этой переменной для доступа к отсутствующим данным приведет к возникновению ошибки.

Еще один тип ошибок, возникающих при использовании указателей, связан с ситуацией, когда некоторый указатель, адресующий некоторые данные, меняет свое адресное значение и в результате программа теряет доступ к этим данным (если, конечно, они не адресуются другим указателем). Эта ситуация носит название «утечка памяти».

Замечание. В языке С++ вместо пары malloc/free для динамического выделения и освобождения памяти используются вызовы new( ) и delete( ).

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

Автор этого материала — я — Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML — то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.

статьи IT, теория программирования
Похожие публикации: