Структура данных типа «массив»

Массив — последовательность элементов одного типа, называемого базовым. На абстрактном уровне массив представляет собой линейную структуру.

На физическом уровне массив реализован последовательной (прямоугольной) схемой хранения. Располагаться он может в статической или динамической памяти. Размер памяти, выделяемый под массив, зависит от базового типа элемента массива и от количества элементов в массиве и определяется формулой V _мас = V _{эл *} k, где V _мас — объем памяти для массива, V _эл — объем памяти одного элемента (слот), k — количество элементов.

На логическом уровне СД типа массив можно описать следующим образом:

1. typedef T2 t_arr[T1], где T1 — тип индекса, T2 — тип элемента.

t_arr ar;

Массив ar типа t_arr располагается в статической памяти.

2. typedef t_arr *tp_ar;

tp_ar p_ar;

Массив типа tp_ar будет располагаться в динамической памяти после обращения к одной из функций выделения памяти (calloc(), malloc()).

Адрес массива запишется в переменную p_ar.

Массив — это статическая структура. В процессе выполнения программы количество элементов массива не изменяется. Доступ к элементу массива прямой, осуществляется через индекс элемента,

например Ar[i] или *P_ar[i].

Кардинальное число для массива T_ar:

Car(T_ar) = [Car(T2)] ^Car(T1).

Набор допустимых операций для СД типа массив:

1. Операция доступа (доступ к элементам массива — прямой, от размера структуры время выполнения операции не зависит).

2. Операция присваивания.