Типичная ошибка программирования 9

Неправильная ссылка на элемент двумерного массива а[х] [у] как а[х,у]. На самом Деле, а[х,у] воспринимается как а[у]. потому что C  оценивает выражение (со - держащее операцию последования — запятую) х, у просто как у (последнее из разделенных запятыми выражений).

Многомернные массивы могут получать начальные значения в своих объявлениях точно так же, как массивы с единственным индексом. Например, двумерный массив Ь[2] [2] можно объявить и дать ему начальные значения таким образом:

int b [2][2] = {{1,2}, {3, 4}};

Значения группируются в строки, заключенные в фигурные скобки. Таким образом, элементы Ь[0] [О] и b[0] [1] получают начальные значения 1 и 2, а элементы Ь[1] [О] и Ь[1] [1] получают начальные значения 3 и 4. Если начальных значений в данной строке не хватает для их присвоения всем элементам строки, то остающимся элементам строки присваиваются нулевые начальные значения. Таким образом, объявление

int b [2 ] [2] = { {1, }, {3, л)};

будет означать что b[0] [О] получает начальное значение 1, b[0] [1] получает начальное значение 0, b[1] [О] получает начальное значение 3 и Ь[1] [1] получает начальное значение 4.

Рисунок 22 демонстрирует присваивание начальных значений двумерным массивам в объявлениях. Программа объявляет три массива, каждый с тремя строками и тремя столбцами. Объявление arrayl имеет шесть начальных значений в двух подсписках. Первый подсписок присваивает начальные значения 1, 2 и 3 элементам первой строки массива; второй подсписок присваивает начальные значения 4, 5 и 6 элементам второй строки массива. Если фигурные скобки вокруг каждого подписка удалить из списка начальных значений arrayl, то компилятор автоматически присвоит первые начальные значения элементам первой строки, а следующие — элементам второй строки.

Объявление аггау2 содержит пять начальных значений. Начальные значения присваиваются первой строке, затем второй строке. Любые элементы, которые не имеют явно заданных начальных значений, автоматически получают нулевые начальные значения, так что элемент аггау[1] [2] получит нулевое начальное значение.

Объявление аггауЗ имеет три начальные значения в двух подсписках. Подсписок для первой строки явно присваивает начальные значения 1 и 2 первым двум элементам первой строки. Третий элемент автоматически получает нулевое начальное значение. Подсписок для второй строки явно присваивает начальное значение 4 первому элементу. Остальные два элемента автоматически получают нулевые начальные значения.

Программа вызывает функцию printArray для вывода элементов каждого массива. Заметим, что описание функции указывает параметр — массив как int а[ ] [3]. Когда мы задаем как аргумент функции одномерный массив, скобки в списке параметров функции пусты. Размерность первого индекса многомерного массива также не требуется, но все последующие размерности индексов необходимы. Компилятор использует размерности этих индексов для определения ячеек в памяти элементов многомерных массивов. В памяти все элементы массива хранятся последовательно, независимо от количества индексов. В двумерном массиве первая строка хранится в памяти перед второй строкой.

Рис.22 – Присваивание начальных значений в многомерных массивах

 

Наличие размерностей индексов в объявлении параметра дает возможность компилятору сообщить функции о том, как расположены элементы в массиве. В двумерном массиве каждая строка по существу является одномерным массивом. Чтобы определить местоположение элемента в некоторой строке, функция должна точно знать, сколько элементов находится в каждой строке, чтобы она смогла пропустить соответствующее количество ячеек памяти при обращении к массиву. Таким образом, при обращении к а[1] [2] функция знает, что для доступа ко второй строке (строка 1) нужно пропустить в памяти три элемента первой строки, а затем обратиться к третьему элементу этой строки (элементу 2).

Многие типовые операции с массивами используют структуру повторения for. Например, следующая структура for обнуляет все элементы третьей строки массива а на рис.21:

for (column = 0; column < 4; column ++)

a [2][column] = 0;

Мы указали третью строку, потому что знаем, что ее первый индекс всегда равен 2 (0 — это первая строка, а 1 — это вторая строка). Цикл for варьирует только второй индекс (т.е. индекс столбца). Предыдущая структура for эквивалентна операторам присваивания:

 а [2] [0] = 0;

а [2] [1] = 0;

а [2 ] [2] = 0;

а [2 ] [3] = 0;

Следующий вложенный цикл for определяет сумму всех элементов массива а:

total = 0;

for (row = 0; row < 3; row++)

  for (column = 0; column < 3; column++)

         total += a[row][column];

Внутренняя структура for суммирует элементы одной строки массива. Внешняя структура for начинает работу с установки row (т.е. индекса строки) в нуль, так что во внутренней структуре for могут быть просуммированы элементы первой строки. Затем внешняя структура for увеличивает row на 1, так что могут быть просуммированы элементы второй строки. Далее внешняя структура for увеличивает row до значения 2, так что могут быть просуммированы элементы третьей строки. После завершения работы вложенной структуры for печатается результат.

Программа на рис.23 выполняет несколько других типовых операций над массивом studentGrades размером 3 на 4. Каждая строка массива представляет студента, а каждый столбец представляет оценку, полученную студентом на одном из четырех экзаменов в течение семестра. Манипуляции с массивом выполняются с помощью четырех функций. Функция minimum определяет наихудшую оценку всех студентов в течение семестра. Функция maximum определяет наилучшую оценку всех студентов в течение семестра. Функция average определяет среднесеместровую оценку отдельного студента. Функция printArray выводит двумерный массив в табличном виде.

Каждая из функций minimum, maximum и printArray получает три аргумента — массив studentGrades (называемый grades в каждой функции), количество студентов (число строк массива) и количество экзаменов (число столбцов массива). Каждая функция циклически обрабатывает массив grades, используя вложенные структуры for. Приведем пример вложенной структуры for из описания функции minimum:

for (i = 0; i < pupils; i++)

for (j = 0; j < tests; j++)

       if (grades[i][j] <

             lowGrade) lowGrade = grades[i ][j ];

Рис.23 – Пример использования двумерного массива (часть 1 из 2)

Рис.23 – Пример использования двумерного массива (часть 2 из 2)

 

Внешняя структура for начинается с установки i (т.е. индекса строки) равным нулю, чтобы элементы первой строки можно было сравнивать с переменной lowGrade в теле внутренней структуры for. Внутренняя структура for циклически обрабатывает четыре оценки каждой строки и сравнивает каждую оценку с lowGrade. Если оценка меньше, чем lowGrade, lowGrade устанавливается равной этой оценке. Затем внешняя структура for увеличивает индекс строки до значения 1. Элементы второй строки сравниваются с переменной lowGrade. Затем внешняя структура for увеличивает индекс строки до значения 2. Элементы третьей строки сравниваются с переменной lowGrade. Когда выполнение вложенной структуры заканчивается, lowGrade содержит наименьшую оценку в двумерном массиве. Функция maximum работает аналогично функции minimum.

Функция average принимает два аргумента — одномерный массив результатов экзаменов для одного студента и количество результатов экзаменов в массиве. При вызове average первый аргумент — это studentGrades[student], который указывает, что в average передается отдельная строка двумерного массива studentGrades. Например, аргумент studentGrades[l] представляет собой четыре значения (одномерный массив оценок), хранимый во второй строке двумерного массива studentGrades. Двумерный массив можно рассматривать как массив с элементами, представляющими собой одномерные массивы. Функция average подсчитывает сумму элементов массива, делит ее на количество результатов экзаменов и возвращает результат в форме с плавающей запятой.

 

Резюме

C++ хранит списки значений в массивах. Массив — это последовательная группа связанных ячеек памяти. Эти ячейки связаны тем, что все они имеют одно и то же имя и один и тот же тип. Чтобы сослаться на отдельную ячейку или элемент массива, нужно указать имя массива и индекс.

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

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

Массивы занимают место в памяти. Чтобы зарезервировать память для 100 элементов массива целых значений b и 27 элементов массива целых значений х, программист пишет int b [100], х [27];

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

Элементам массива можно задавать начальные условия тремя способами: в объявлении, присваиванием или при вводе.

Если в списке инициализации начальных значений меньше, чем элементов массива, остающиеся элементы массива принимают нулевые начальные значения.

C++ не предотвращает ссылок на элементы, находящиеся за пределами массива. • Массиву символов можно задавать начальные условия, используя литеральную константу. • Все строки заканчиваются нулевым символом (’\0’).

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

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

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

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

Чтобы принять аргумент-массив, список параметров функции должен указывать, что передается массив. Размер массива в скобках после имени массива указывать не обязательно.

В C++ имеется спецификация типа const, которая запрещает модификацию значений массива в функции. Когда параметру-массиву предшествует спецификатор const, элементы массива становятся константами в теле функции и любая попытка модифицировать элементы массива внутри тела функции приводит к ошибке трансляции.

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

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

Двоичный поиск исключает половину элементов массива после каждого сравнения. Алгоритм выделяет средний элемент массива и сравнивает его с ключом поиска. Если они равны, ключ поиска найден и возвращается индекс массива этого элемента. В противном случае задача поиска сокращается на половину массива.

В наихудшем случае двоичный поиск в массиве из 1024 элементов потребует всего 10 сравнений.

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

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

Чтобы передать функции одну строку двумерного массива, которая принимается как одномерный массив, просто передается имя массива и вслед за ним первый индекс.

 

Терминология

Упражнения для самопроверки