Массивы

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

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

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

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

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

Вектор А = А(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-мерного массива указывается число размерностей, а также верхняя и нижняя границы диапазона изменения индексов.

Стек

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

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

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

Элемент, на который установлен указатель вершины, называется текущим. Указатель вершины всегда содержит информацию о позиции текущего элемента в стеке. Прочитанный элемент считается удаленным из стека.

Информация в стеке обрабатывается по принципу "последним пришел – первым ушел", так как первым будет прочитан тотэлементстека, который включался в стек последним. Структуру стека часто называют структурой типа LIFO (Last In – First Out).

Для хранения стека можно использовать как последовательное, так и связанное представление данных в памяти.

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

Можно организовать стек с изменяемым указателем вершины или с неизменным указателем вершины.

Рассмотрим стек с изменяемым указателем вершины.

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

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

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

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

Читается из стека текущий элемент. После чтения текущего элемента все остальные элементы стека передвигаются так, чтобы стереть прочитанный элемент, так как этот элемент должен быть исключен из стека. Операцию чтения часто называют «выталкиванием».

На рисунке изображены стек с изменяемым указателем вершины и стек с неизменным указателем вершины.

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

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

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