10.Массивы

Массив – это линейная структура данных фиксированного размера с произвольным доступом по индексу т.е. по номеру элемента массива. Обычно массивы хранятся в виде последовательного списка. Каждый элемент массива идентифицируется одним или несколькими индексами. Индекс – целое число значение, которого определяет позицию соответствующего элемента в массиве и используется для доступа к этому элементу. Отдельные элементы массива могут изменяться, т.е. для массива возможен режим корректировки. Общее число элементов массива всегда остается неизменным, следовательно, для массива невозможны операции добавления и удаления. В однородных массивах все элементы являются данными одного и того же типа и имеют одинаковый формат. Массивы, элементами которых являются данные разных типов, называются неоднородными. В зависимости от числа индексов идентифицирующих каждый элемент различают одномерные и многомерные массивы. Одномерный массив называется вектор:A={A(1),A(2),…, A(I),…,A(N)}

Это последовательность элементов (записей) размещенных в смежных ячейках памяти. Для вектора транслятор выделяет область памяти в соответствии с объявлением массива в программе. Адрес первого байта выделенного транслятором для первого элемента вектора называется адресом базы вектора. Адрес любого i-ого элемента вычисляется транслятором по формуле:loc(A_i)=L₀+C(i-1)

L₀ – адрес базы вектора

С – число байтов выделенных под 1 элемент вектора.

При обращении к элементу вектора в программе задается значение индекса (i). Транслятор по формуле определяет адрес хранения ai и читает этот элемент из памяти. Представление вектора в памяти не зависит от того как вектор описывается в языке программирования. Двумерный массив называется матрицей. Каждый элемент матрицы определяется двумя индексами. При хранении в памяти матрица представляется в виде эквивалентного вектора, этот вектор может храниться в памяти как «строка строк» или как «строка столбцов». В первом случае такая матрица

А(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).Адрес матричного элемента A(i,j) вычисляется

loc(A_i,j)=L₀+(i-1)mc+(j-1)c

Такой способ называется еще хранение по строкам. В некоторых языках программирования матрица может храниться как строка столбцов, и ее элементы размещаются по столбцам

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

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

11.Стек.

Стек – это линейная структура данных переменного размера с ограниченным доступом. Особенность стековой структуры состоит в том, что доступ к ее элементам, включение и исключение элементов возможны только с одного конца структуры – с вершины стека. На ячейку находящуюся в вершине стека всегда установлен указатель вершины стека. Записывать новый элемент можно только в вершину стека, в ту ячейку, на которую установлен указатель вершины. Прочитать из стека можно только тот элемент, который так же находится в вершине стека и на который установлен указатель вершины. УВ всегда содержит информацию о позиции текущего элемента в стеке, т.е. элемент на который установлен УВ называется текущим. Элемент, который прочитан, считается исключенным из стека. Информация в стеке обрабатывается по принципу «последний пришел, первый ушел», т.к. первым будет прочитан тот элемент стека, который включался в стек последним. Структуру стека часто называют структурой LIFO – Last In First Out

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

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

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

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

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

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

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