76.2 Динамические структуры данных. Основные виды, способы построения.

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

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

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

Простейшая статическая структура данных – массив (статический).

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

Достоинства:

• легкость вычисления адреса элемента по его индексу (поскольку элементы массива располагаются один за другим);

• одинаковое время доступа ко всем элементам;

• малый размер элементов: они состоят только из информационного поля.

Недостатки:отсутствие динамики, невозможность удаления или добавления элемента без сдвига других.

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

Например:

var m1:array[-2..2] of real;

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

Массив - такая структура данных, которая характеризуется:

фиксированным набором элементов одного и того же типа;

каждый элемент имеет уникальный набор значений индексов;

количество индексов определяют мерность массива, например, два индекса - двумерный массив, три индекса - трехмерный массив, один индекс - одномерный массив или вектор;

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

Синтаксис описания массива представляется в виде:

<Имя> : Array [n1..k1] [n2..k2] ..[nn..kn] of< Тип >.

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

Среди наиболее распространенных динамических структур данных следует выделить следующие:

• связные списки; деревья; стеки; графы.

Главным достоинством динамических структур данных является возможность изменения их размера в процессе выполнения программы. Другими словами мы можем добавлять и удалять новые элементы в структуру по мере надобности.

Работа с динамическими величинами связана с использованием еще одного типа данных — ссылочного типа. Величины, имеющие ссылочный тип, называют указателями.

Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти.

Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом. Величина ссылочного типа (указатель) описывается следующим образом: имя_типа *<идентификатор>;

Вот примеры описания указателей: int *P1; char *P2;

Здесь P1 — указатель на динамическую величину целого типа; P2 — указатель на динамическую величину символьного типа.

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

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

идентификатор = (тип_идентификатора*) malloc (sizeof(тип_идентификатора))

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

<имя динамической величины> = *<указатель>