Массивы

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

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

В однородных массивах все элементы являются данными одного и того же типа и имеют одинаковый формат. Массивы, элементами которых являются данные различных типов, называются неоднородными.

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

Одномерный массив называется вектором.

Вектор А = А(1), А(2), ….,А(I),….,А(N) – это последовательность элементов (записей), размещенных в смежных ячейках памяти.

Под вектор транслятор выделяет область памяти в соответствии с объявлением массива в программе. Адрес первого байта, выделенного транслятором для первого элемента вектора, называется адресом базы вектора. Адрес любого i – го элемента вычисляется транслятором по следующей формуле:

 

Loc (A_i) = L₀ + C (i-1)

 

Здесь loc – от англ. location – определение местоположения, L₀ - адрес базы вектора, С – число байтов, выделенных для хранения одного элемента вектора.

При обращении к элементу вектора в программе задается значение его индекса i. Транслятор по формуле определяет адрес хранения А(i) и читает этот элемент из памяти.

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

Двумерный массив называется матрицей. Каждый элемент матрицы определяется двумя индексами.

При хранении в памяти матрица представляется в виде эквивалентного вектора. При этом матрица может храниться в памяти как «строка строк» или как «строка столбцов». В первом случае матрица 3*3

А (1,1) А (1,2) А (1,3)

А (2,1) А (2,2) А (2,3)

А (3,1) А (3,2) А (3,3)

 

при размещении в памяти будет представлена в виде следующего вектора:

 

А (1,1) А (1,2) А (1,3) А (2,1) А (2,2) А (2,3) А (3,1) А (3,2) А (3,3)

 

Хранение элементов матрицы в таком виде называется хранениемпострокам. Адрес матричного элемента А (i, j) в этом случае определяется выражением

 

Loc (А _i,j ) = L₀ + c m (i - 1) + c (j - 1),

где m – число столбцов.

Такое размещение принято в языках программирования ПЛ/1, Паскаль.

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

А (1,1) А (2,1) А (3,1) А (1,2) А (2,2) А (3,2) А (1,3) А (2,3) А (3,3)

 

Такое размещение матрицы в памяти принято в Фортране.

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

Стек

Стек – линейная структура данных переменного размера с ограниченным доступом.

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