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

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

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

Например, классическая структура МАССИВ есть объединение элементов данных, обладающее следующими свойствами:

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

Пример объявления массива, предназначенного для хранения 100 целых чисел. Паскаль:

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( ).

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