3. Обработка массивов

3.1. Цель работы

Изучение понятия «массив», представления элементов одномерных и многомерных массивов, порядка индексации элементов и освоение методики проектирования алгоритмов обработки массивов данных.

3.2. Методические указания по подготовке к лабораторной работе

Необходимо изучить понятие «массив», способы описания, инициали­зации, индексации массивов, языковые средства С++ для работы с масси­вами. Повторить материал предыдущего практического занятия по работе с циклами.

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

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

Массив характеризуется типом данных ячеек, размерностью и разме­ром. Размерность массива – это количество его измерений. Массив может быть одномерным (вектор), двухмерным (матрица), трехмерным и т.д. Размер массива – это количество его элементов. Для многомерных массивов каждое измерение имеет свой размер (10х15, 10х5х4 и т.д.). Общий размер массива равен произведению размеров его отдельных измерений (соответственно 150 и 200). Необходимо заметить, что на физическом уровне любой массив хра­нится в памяти как одномерный, т.е. как последовательность подряд прону­мерованных ячеек. Представление массивов в матричном, трехмерном и т.д. виде осуществляется только для удобства пользователя (т.е. программиста). Например, элемент матрицы (размером m*n) с индексами(i,j) хранится в памяти со смещением i*n+j.

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

Для доступа к элементу многомерного массива необходимо указать все его индексы (в соответствии с размерностью). Первый индекс – это номер строки, второй – номер столбца, третий – номер слоя и т.д. Например, выра­жение mas[3][2][1] означает обращение к элементу в третьей строке, втором столбце и первом слое трехмерного массива mas (в математической формуле в этом случае написали бы ). Не забывайте, что в языке С++ нумера­ция элементов массива (по любому из его измерений) начинается с нуля.

Часто при работе с массивами фактический размер не равен точно объявленному максимальному (т.е. заполнены и обрабатываются не все 100 ячеек массива, а, например, только первые 34). В этом случае фактический размер массива необходимо хранить в отдельной переменной.

Для доступа к элементу массива необходимо указать имя массива и индекс элемента. Часто элементы массива обрабатываются последовательно. Для этого удобно использовать цикл for: for(int i=0;i<n;i++) { обработка }. Здесь буквой n обозначен фактический размер массива. Можно аналогичным образом обрабатывать элементы массива и в обратном порядке:

for(int i=n-1;i>=0;i--) { обработка }.

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

При обмене местами двух элементов массива используется так назы­ваемый метод пустого стакана: обмен a[i]a[j] реализуется с помощью трех присваиваний w=a[i]; a[i]=a[j]; a[j]=w.

Частыми операциями с массивами являются вставка и удаление эле­мента массива. Для вставки элемента в середину массива на позицию k необ­ходимо сдвинуть вправо все элементы массива с индексами большими или равными k, для чего используется обратный цикл for (почему?). Для удале­ния элемента с индексом k необходимо сдвинуть влево все элементы массива с индексами большими k.

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

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