10. Массивы

Массив — это линейная структура данных фиксированного размера, реализуемая с использованием последовательного представления дан­ных. Понятие массива как структуры данных не тождественно понятию информационного массива, определяющему совокупность данных, обра­батываемых АИС.

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

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

Одномерный массив называется вектором. Вектор А = {A (1)A (2)... A(I)..A(N)} — это последовательность элементов (записей), размещен­ных в смежных ячейках памяти. Единственный индекс вектора указы­вает позицию каждого элемента в последовательности.

Адрес первого байта, выделенного для первого элемента вектора, называется адресом базы вектора. Вектор в целом определяется адресом базы, размером элементов и их числом или размером элементов и диапа­зоном изменения индекса (рис. 8.1). Если L_o — адрес первого байта в блоке памяти, выделенном для хранения вектора, с - число байтов, выделенное для хранения каждого элемента, то адрес любого 1-го элемен­та будет (loc от англ. location - определение местоположения). Адрес базы L ₀ определяется транслятором в процессе трансляции программы.

Двумерный массив, называется матрицей. Каждый элемент матрицы определен двумя индексами. В общем случае массив может иметь любую размерность, т.е. являться многомерным. Многомерный массив может быть представлен эквивалентным одномерным массивом. Например, матрицу можно рассматривать как вектор, элементы которого, в свою очередь, являются векторами. При этом матрица может рассматриваться и храниться в памяти ЭВМ как "строка строк" и как "строка столбцов". В первом случае матрица представится в виде следующего вектора: А (1, 1)А (1,2) А (1,3)А (2, 1)А (2, 2) А (2,3)А (3, 1)А (3,2)А (3,3)

В другом случае, когда матрица рассматривается как "строка столб­цов", ее элементы разместятся в памяти по столбцам в следующем порядке: А(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), что хорошо поясняется на примере стопки тарелок, где доступной является верхняя тарелка. Структура стека явля­ется структурой данных с ограниченным доступом, так как доступ разрешается только к элементу, находя­щемуся в вершине стека. Этот элемент называется те­кущим. Информацию о пози­ции текущего элемента стека хранит указатель вершины стека (УВС), размещаемый обычно в головной ячейке стека. При использовании последовательного представления необходимо знать предельный размер стека. Под этот предполагаемый предельный размер резервируется блок памяти, внутри которого стек растет и сокра­щается. Первая ячейка блока содержит указатель вершины стека. Когда стек пуст, указатель указывает на самого себя; При включении каждого нового элемента указатель вершины увеличивается на единицу. На рис. 8.2 изображен блок памяти с размещенным в нем исходным стеком, а также стеки с исключенным и включенным элементами,

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

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

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