зачем используют циклы в работе с массивами

Урок 6N: Массивы и Циклы

MainActivity

activity_main.xml

Цикл «for»

Конструкция for управляет циклами. Команда выполняется до тех пор, пока управляющее логическое выражение не станет ложным.

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

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

Как правило, цикл for используют для перебора. В качестве имени первой переменной часто используют i (сокр. от init), но вы можете использовать любое имя.

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

Третье выражение в цикле – шаг, то есть, на какое значение нужно изменить переменную. Строго говоря, в таком виде (x = x + 1) современные программисты не пишут, так как есть укороченная форма записи (x++). Предыдущий пример можно переписать по другому:

Эта запись является классической и правильной, если нам нужно посчитать от 0 до 8. Может возникнуть соблазн написать, например, так:

Результат будет таким же, но такой код нежелателен. Старайтесь писать традиционно. Особенно это проявляется при работе с массивами.

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

Основная разница между ними, что массив может состоять из неупорядоченных чисел, а число элементов может быть разным. К счастью, у массива есть специальное свойство length – длина массива. Первый пример можно переписать следующим образом.

Мы создали массив из чисел от 0 до 9. Затем проходим в цикле, но на этот раз во втором операторе не используем число 9, а вычисляем длину массива. Такой гибкий подход позволят проделывать с массивами разные трюки – упорядочивать, сортировать, переворачивать и т.д.

Источник

10.3 – Массивы и циклы

Рассмотрим случай, когда мы хотим найти средний балл за тест в классе студентов. Используя отдельные переменные:

Это много переменных и много набора текста – и это всего 5 студентов! Представьте, сколько работы нам нужно было бы сделать для 30 или 150 студентов.

Использование массивов предлагает немного лучшее решение:

Это значительно сокращает количество объявляемых переменных, но totalScore по-прежнему требует, чтобы каждый элемент массива был указан отдельно. Как и выше, изменение количества студентов означает, что формулу totalScore необходимо изменить вручную.

Циклы и массивы

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

Вот наш пример выше, модифицированный для использования цикла for :

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

Вот пример использования цикла для поиска в массиве, чтобы определить лучший результат в классе:

Смешивание циклов и массивов

Циклы обычно используются с массивами для выполнения одной из трех задач:

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

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

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

Массивы и ошибки на единицу

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

Проблема с этой программой в том, что условие в цикле for неверно! Объявленный массив имеет 5 элементов, пронумерованных от 0 до 4. Однако этот массив перебирается в цикле от 0 до 5. Следовательно, на последней итерации массив выполнит следующее:

Но элемент scores[5] не определен! Это может вызвать всевозможные проблемы, наиболее вероятно, что scores[5] приведет к мусорному значению. В этом случае вероятный результат – maxScore окажется неверным.

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

Небольшой тест

Вопрос 1

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

Подсказка: чтобы определить длину массива, вы можете использовать std::size (начиная с C++17) или трюк с sizeof() (до C++17).

Вопрос 2

Используя массив из вопроса 1.

Попросите пользователя ввести число от 1 до 9. Если пользователь не вводит число от 1 до 9, повторно запрашивайте целочисленное значение, пока он не введет его. После того, как он ввел число от 1 до 9, распечатайте массив. Затем найдите в массиве значение, введенное пользователем, и напечатайте индекс этого элемента.

Проверить std::cin на недопустимый ввод вы можете, используя следующий код:

Вопрос 3

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

Источник

Массивы и циклы

Кувшинов Д.Р.

Одномерные массивы и циклы

Циклы

Что такое “цикл” уже рассказывалось во введении.

Цикл с предусловием

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

Вечный цикл на основе while:

Например, можно модифицировать пример так, чтобы в случае ввода признака конца файла происходил выход из программы, а ошибки ввода игнорировались как и прежде. Для этого добавим “посередине” комбинацию if-break:

Цикл с постусловием

Цикл с постусловием отличается от цикла с предусловием тем, что условие повторения проверяется после каждой итерации (т.е. является условием продолжения цикла). Соответственно, хотя бы один раз цикл выполнится.

На практике цикл do-while применяется намного реже цикла while.

Цикл for

Цикл for в C является “общим типом” цикла и используется значительно чаще while и do-while.

Например, вечный цикл на основе for записывается следующим образом:

Следующие два цикла эквивалентны:

Общий вид конструкции for следующий:

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

Условие повторения проверяется перед каждой итерацией. Таким образом, цикл for может не выполнить ни одной итерации.

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

Пример простого вложенного цикла for (двойной цикл):

Нередко новички в языке C или C++ пытаются записать подобный двойной цикл одной инструкцией for:

Статические массивы

Слово одномерный означает, что для выбора конкретного значения из группы используется одно целое число — порядковый номер этого значения — его индекс (от лат. index — “указательный палец”). У такого массива единственное измерение, имеющее размер, равный количеству элементов в массиве. Индексы в C и C++ всегда отсчитываются от нуля (первый элемент) до размера измерения – 1 (последний элемент). Размер массива не может быть меньше единицы.

Слово статический означает, что память под массив распределяется компилятором (“статически”). При этом, однако, “статический” массив может размещаться в автоматической памяти и быть локальной переменной функции. Размер статического массива должен быть известен на момент компиляции (константа времени компиляции) и не может быть изменён во время работы программы.

Далее представлен простой пример, демонстрирующий определение статического массива и обращение к его элементам (с помощью оператора [] ).

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

Указатели и массивы

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

Указатели можно вычитать, получая целое число со знаком — смещение offset от одного указателя к другому в элементах массива, на которые указывают эти указатели. Если указатели не указывают на элементы одного массива, то попытка вычислить их разность приводит к неопределённому поведению. И наоборот, к указателю на некоторый элемент массива можно добавить (или вычесть из него) целое число (смещение), чтобы получить указатель на другой элемент массива, отстоящий от первого на заданное смещением число элементов. Полученный указатель может “выходить” на верхнюю границу массива, указывая на несуществующий элемент, который шёл бы сразу за последним элементом массива. Разность между таким указателем и указателем на первый элемент массива (на начало массива) равна размеру массива. Наконец, указатели позволяют обращаться к ним как к массивам, что эквивалентно обращению к смещённому на индекс указателю.

Здесь *dest++ и *src++ передвигают соответствующие указатели на одну позицию вперёд, но так как постинкремент возвращает старое значение переменной, то именно это старое значение указателя подвергается разыменованию, поэтому мы получаем ссылки на символы, стоящие на тех позициях, на которые указывали dest и src до инкремента.

Определение размера массива и передача массива в функцию

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

Синтаксис объявления параметра функции в виде массива на самом деле объявляет передачу адреса массива (указателя на него) и только адреса. Поэтому не важно, какой размер указать там между квадратными скобками — можно не указывать никакого (как в примере). Если этот размер указать, то он может послужить для удобства чтения или в качестве намёка компилятору (с точки зрения оптимизации или предупреждений), но на семантику программы влияния не окажет.

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

В C++17 введена стандартная функция size (определённая в ), которая при применении к статическому массиву возвращает его размер в элементах. Применить её ненароком к указателю не получится — будет ошибка компиляции.

Впрочем, при отсутствии такой стандартной функции, её можно написать самостоятельно. Для этого даже не требуется поддержка компилятором новых стандартов C++. Но требуется использовать такой элемент языка как “шаблон функции” — это материал 2-го семестра.

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

Или просто выводим массив в консоль:

Цикл for для диапазона

Данная форма цикла for была введена в язык C++ в стандарте 2011 года и представляет собой вариант цикла “выполнить для каждого элемента”. Итерация выполняется для каждого элемента обобщённого диапазона. Для этого запись вида

трактуется компилятором приблизительно как следующий код (переменные с префиксом __ не видны из пользовательского кода):

Поэтому, например, вместо

можно было написать

При изменении элементов массива в цикле следует указывать ссылочный тип:

Инициализация массива

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

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

Несколько примеров инициализации (попробуйте запустить этот код).

Начиная с C++11, писать = в инициализаторе массива не обязательно:

есть то же самое, что

Многомерные массивы

Статические массивы

Поддержка многомерных массивов языками C и C++ весьма ограничена. Можно создать статический многомерный массив, который интерпретируется как массив массивов. Например, массив из двух массивов по три элемента типа int:

В памяти такие массивы укладываются последовательно одним блоком, эквивалентным одномерному массиву размера, равного произведению размеров по каждому из измерений. Т.е. в случае приведённого выше примера имеем блок из шести int (24 байта, если int занимает 4 байта), заполненный значениями 1, 2, …, 6 подряд — порядок заполнения в памяти соответствует порядку записи в инициализаторе: первая строка-подмассив из трёх элементов, затем вторая строка-подмассив из трёх элементов.

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

Более того, так как размеры подмассивов известны компилятору (зашиты в тип параметра a ), то можно оперировать ими как обычными статическими массивами. Например, пробегать по ним, используя форму цикла for для диапазонов:

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

При инициализации статических многомерных массивов можно опускать внутренние фигурные скобки. При этом следует помнить, что логика заполнения массива элементами заключается в последовательном копировании заданных значений в массив (от младших адресов в памяти к старшим) и заполнении остатка нулями. Так же как и в случае одномерных массивов, начиная с C++11, можно опускать = в инициализаторе.

Может быть опасно изменять код, удаляя “лишние” скобки в инициализаторе:

Удалив внутренние скобки, получим запись последовательности < 1, 0, 1, 0, 0, 1, 0, 0, 0 >в m[3][3] (интерпретируемом как m[9])

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

Многомерные динамические массивы в C и C++ можно реализовать различными способами. Далее представлено три способа.

Динамические массивы

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

В C++ предусмотрены операторы new[] для создания динамических массивов (оператор возвращает ненулевой указатель на массив, в случае ошибки бросается исключение) и delete[] для их удаления.

Способ 1

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

Недостатком данного способа является множество выделений-освобождений динамической памяти и возможная “разбросанность” подмассивов в памяти. (Если бы все элементы массива шли в памяти подряд, то из этого можно было бы извлечь пользу в плане производительности и удобства кодирования некоторых операций.)

Способ 2

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

Массив с размерностями (d₀, d₁, …, d_r–1) содержит d₀·d₁⋯d_r–1 элементов. Количество размерностей r называют рангом rank массива. При укладке их подряд в памяти в духе статического многомерного массива получаем следующую формулу приведения r-мерного (векторного) индекса (i₀, i₁, …, i_r–1) к одномерному индексу I в блоке:

В общем случае его удобно вычислять методом Горнера (только вместо домножения на x домножаем на следующий индекс).

В примерах ниже именно этот способ используется для представления матриц с произвольными размерами. В двумерном случае приведённая выше формула приобретает простой вид: I = i₁ + i₀ d₁ (массив строк, в каждой строке по d₁ столбцов). Т.е. индекс по первому измерению надо умножить на размер второго измерения и добавить индекс по второму измерению.

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

Недостатки: выделение сразу большого куска памяти может производиться медленно или быть вовсе невозможным из-за фрагментации кучи; простые операции, вроде перестановки строк, невозможно выполнить простой манипуляцией указателями: необходимо либо явно обменивать все элементы строк, либо применять промежуточное преобразование индексов, либо создавать новый изменённый массив.

Способ 3

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

Источник