Массив – это линейная структура данных фиксированного размера с произвольным доступом по номеру элемента (по индексу). Обычно массивы хранятся в виде последовательного списка.
Каждый элемент массива идентифицируется одним или несколькими индексами. Индекс – это целое число, значение которого определяет позицию соответствующего элемента в массиве и используется для доступа к этому элементу. Отдельные элементы массива могут изменяться, т.е. для массива возможен режим корректировки. Общее число элементов массива всегда остается неизменным, следовательно, для массива не возможны операции добавления и удаления.
В однородных массивах все элементы являются данными одного и того же типа и имеют одинаковый формат. Массивы, элементами которых являются данные различных типов, называются неоднородными.
В зависимости от числа индексов, идентифицирующих каждый элемент, различают одномерные и многомерные массивы.
Одномерный массив называется вектором.
Вектор А = А(1), А(2), ….,А(I),….,А(N) – это последовательность элементов (записей), размещенных в смежных ячейках памяти.
Под вектор транслятор выделяет область памяти в соответствии с объявлением массива в программе. Адрес первого байта, выделенного транслятором для первого элемента вектора, называется адресом базы вектора. Адрес любого i – го элемента вычисляется транслятором по следующей формуле:
Loc (Ai) = L0 + C (i-1)
Здесь loc – от англ. location – определение местоположения, L0 - адрес базы вектора, С – число байтов, выделенных для хранения одного элемента вектора.
При обращении к элементу вектора в программе задается значение его индекса 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 ) = L0 + 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-мерного массива указывается число размерностей, а также верхняя и нижняя границы диапазона изменения индексов.
Стек
Стек – линейная структура данных переменного размера с ограниченным доступом.
Особенность стековой структуры состоит в том, что доступ к его элементам, включение и исключение элементов возможны только с одного конца структуры – с вершины стека. На ячейку, находящуюся в вершине стека, всегда установлен указатель вершины стека.