1.6. Массивы
 

Массивы являются наиболее широко используемыми структурами данных и предусмотрены во всех языках программирования. Массив состоит из элементов одного типа, называемого базовым, поэтому структура массива однородна. Базовый тип может быть как скалярным, так и структурированным, т.е. элементами массива могут быть числа, символы, строки, структуры, в том числе и массивы. Число элементов массива фиксировано, поэтому объем занимаемой массивом памяти, остается неизменным. С каждым элементом массива связан один или несколько индексов. Они однозначно определяют место элемента в массиве и обеспечивают прямой доступ к нему. Индексы массива относятся к определенному порядковому типу, поэтому индексы можно вычислять. Это обеспечивает, с одной стороны, гибкость обработки элементов массива, с другой стороны, создает опасность выхода за пределы массива, если не предусмотрены соответствующие средства контроля.

• числовые массивы в вычислительных задачах;
• матричная алгебра, экстраполяция, интерполяци;
• указатель (адрес) начала списка;
• таблицы — массивы с элементами типа «запись»;
• управляющие и информационные таблицы в операционных системах, трансляторах, системах управления базами данных (СУБД);
• представление других структур: графов, деревьев.

Массив в памяти хранится в виде вектора, т. е. все элементы размещаются в смежных участках памяти подряд, начиная с адреса, соответствующего началу массива. Элементы одномерного массива размещаются в последовательности А₀, А₁, А₂, …,А_n-1. Элементы двухмерного массива размещаются либо по строкам, когда наиболее быстро меняется последний индекс ( в Си, Паскале, ПЛ/1), либо по столбцам, когда наиболее быстро меняется первый индекс (в Фортране).

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

• тип структуры;
• адрес начала массива А_n;
• тип элемента (длина элемента массива L);
• нижняя граница индекса i_n;
• верхняя граница индекса i_k.

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

Этой информации достаточно как для доступа к элементам массива, так и для контроля над тем, чтобы значения индексов не выходили за установленные диапазоны. Доступ к любому i - му элементу в одномерном массиве осуществляется по адресу:
A_i=A_n+(i-i_n)*L=A_n-i_n*L+i*L= A₀+i*L,
где A₀=A_n-i_n*L - Фиктивное начало массива, т. е. адрес нулевого эл-та.

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

Пусть n-мерный массив А, у которого число элементов по I-M измерениям равно m_i, а индексация по всем измерениям начинается с нуля, представлен в динамической памяти в виде вектора В. Тогда элементу А[i₁,i₂, …,i_n] исходного массива будет соответствовать элемент вектора В[к] с индексом, равным
k=((…(i₁*m₂+i₂)*m₃+i₃) *m₄+…+i_n-1)*m_n+i_n.

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

Свободными называют двухмерные массивы, размер каждой из строк которых может быть различным. Поскольку стандарты языка программирования не допускают такого вида массивов, то создается симбиоз массивов: одномерный массив указателей, число элементов n которого равно числу строк переменной длины, и n одномерных массивов различной длины. Таким образом, массив указателей имеет фиксированную длину, значит, фиксировано и число строк свободного массива. Память под каждую строку свободного массива запрашивается динамически.

Следовательно, при создании такого массива требуется (n+1) обращений к ОС для получения динамической памяти. После того как надобность в свободном массиве отпала, необходимо освободить занимаемую им память, что опятьтаки потребует (n+1) обращений к ОС.

На риc. изображена структура хранения свободного массива с п строками. Массив указателей, U имеет п элементов, каждый из которых содержит адреса векторов-строк массива.

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

Такое представление массивов имеет свои преимущества и недостатки. К недостаткам можно отнести потребность в дополнительной памяти под массив указателей и многократное обращение к ОС для получения памяти. К преимуществам можно отнести следующее:
1)при работе с очень большими массивами получение больших сплошных областей может стать невозможным; в то же время получение памяти под каждую строку вполне возможно;
2)появляется возможность обрабатывать большие массивы данных, хранящихся в файлах, размещая в оперативной памяти только те строки, которые совместно обрабатываются в данный момент;
3)применение свободных массивов, имеющих строки различной длины, позволяет более эффективно использовать память;
4)при сортировке массива по строкам (не элементов в строке, а самих строк) вместо перестановок строк в некоторых случаях можно переставлять только элементы массива указателей, в то время как сами строки остаются на месте.

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

Треугольные и разреженные матрицы. Иногда при использовании матриц имеет смысл хранить только какую-либо часть матрицы. К таким матрицам можно отнести треугольные и разреженные матрицы.

В треугольной матрице А_n*n все элементы выше или ниже главной диагонали являются нулевыми. Если нулевыми являются элементы выше диагонали (нижняя треугольная матрица), то ненулевыми будут элементы a₁₁; a₂₁, a₂₂;a₃₁,a_32n;a₃₃;…;a_n1, a_n2,…,a_nn. Такую матрицу целесообразно хранить в виде одномерного массива (вектора) В с числом элементов m=n*(n + 1)/2. Тогда индекс ib в массиве В для исходного элемента а_ij , i = 1,2,...,n, j = 1,2,...,i, определяется по формуле

Если же индексация массивов начинается с нуля, i = 0, 1,...,я-1> j = 0, 1 ,...,i, то индексы нижнего треугольного массива вычисляются по формуле

Если в исходной матрице нулевыми являются элементы, расположенные ниже главной диагонали (верхняя треугольная матрица), то в массиве В ненулевые элементы разместятся в последовательности a₁₁,a₁₂₁,…,a_1n; a₂₂,a₂₃,…,a_2n;…;a_nn, а доступ к элементу a_ij в этом cлучае будет осуществляться по индексу ib, вычисляемому по более сложной формуле

При индексации, начинающейся с нуля, формула преобразуется

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

Первый и наиболее простой способ заключается в следующем. Создается двухмерный массив (n*3), где n — число ненулевых элементов исходной матрицы. Первые два элемента каждой строки содержат индексы строки и столбца ненулевого элемента, а третий — сам ненулевой элемент. Если же значения элементов исходной матрицы нецелого типа, то вместо одного двухмерного массива (n*3) создаются три одномерных массива с n элементами каждый. Обработка таких массивов особых затруднений не вызывает.

Имеется возможность несколько сократить объем требуемой памяти. Создаются три массива: массив STR по числу строк исходной матрицы; массивы STL и ZN по числу ненулевых элементов исходной разреженной матрицы. В массив STL последовательно заносятся индексы столбцов ненулевых элементов исходной матрицы, сначала для первой строки, затем для второй и т.д., т. е. индексы столбцов каждой i-и строки образуют i-ю группу. Каждый i-й элемент массива STR содержит индекс начала i-й группы в массиве STL. В массив ZN заносятся значения соответствующих ненулевых элементов.

Алгоритмы обработки разреженной матрицы при таком представлении несколько усложняются, так как число ненулевых элементов в строках исходной матрицы различно, а массив STL не содержит признаков конца групп. Поэтому для перехода с одной строки матрицы на другую нужно использовать информацию из массива STR.

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

Элемент структуры