Массивы в C++ на практике

21 комментерий

Как показала практика, у начинающих кодеров возникает множество вопросов при решении задач по теме «Массивы». В данной статье затронуты вопросы, относящиеся только к массивам в классическом понимании. Работа с контейнерами STL — это отдельная тема.

Как правило, задачи сводятся к следующему: заполнить массив, произвести некие операции с элементами массива, распечатать результат. Уже в постановке задачи угадываются логические блоки её решения. Далее я постараюсь показать типовые «кирпичики», из которых можно сложить решение задачи — т. е. программу.

Организация массива

Память под массив может выделяться автоматически или динамически.

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

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

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

Глобальные автоматические массивы в плане переполнения стека безопасны. Но они будут видны во всём коде, лексикографически расположенному после объявления массивов, что может спровоцировать их использование напрямую, минуя их передачу в функции через параметры. Это приведёт к возникновению побочных эффектов работы функций, что затрудняет отладку и делает программы менее надёжными. Такого использования глобальных массивов следует избегать.

Для массивов, использующих динамическое выделение памяти, память распределяется из «кучи» (heap). Куча — это память, выделяемая программе операционной системой, для использования этой программой. Размер кучи, как правило, значительно больше размера стека, а для ОС, поддерживающих парадигму виртуальной памяти, размер кучи теоретически может ограничиваться только разрядностью приложения.

Использование автоматических массивов

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

Размер массива в коде настоятельно рекомендуется указывать с помощью именованной константы. Это полезно по нескольким соображениям:

  1. имя константы должно указывать на область её применения — самодокументирование кода;
  2. при необходимости изменить в коде размер массива потребуется внести правку только в одном месте;
  3. размер массива, как правило, используется в циклах прохода по массиву, проверки границы и пр., поэтому использование символического имени избавит от необходимости тщательной проверки и правки всего кода при изменении размера массива.

Тип константного выражения для определения размера (количество элементов) автоматического массива должен быть целочисленный: char, int, unsigned int, long, etc.

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

Пример определения глобального автоматического массива длиной 10 элементов типа int:

const unsigned int ARRSIZE = 10;

int ary[ARRSIZE];

int main(void) { ... }

Пример определения локального автоматического массива длиной 10 элементов типа int:

const unsigned int ARRSIZE = 10;

int main(void) {
    int ary[ARRSIZE];
    ...
}

Использование массивов с динамическим выделением памяти

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

Память для массива выделяется оператором new в форме new тип[количество_элементов].

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

Когда работа с массивом закончена, память, выделенную под массив необходимо освободить. Это делается с помощью оператора delete в форме delete [] имя_переменной. После того, как память освобождена, работать с массивом нельзя.

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

int main(void) {

    unsigned int arr_size;

    // здесь должно быть получение размера массива arr_size

    int *ary = new int[arr_size];

    // ...

    delete [] ary;

    // ...
}

Заполнение массива значениями

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

Заполнение массива случайными числами

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

#include <cstdlib>

using namespace std;

// функция генерации случайного числа из диапазона от range_min до range_max включительно
int rrand(int range_min, int range_max) {
    return rand() % (range_max - range_min + 1) + range_min;
}

Однако без дополнительных телодвижений стандартная функция rand() будет при каждом запуске программы генерировать одинаковую последовательность случайных чисел (кстати, это очень удобно при отладке!). Для того, что бы при каждом запуске программы получать уникальную последовательность случайных чисел, функцию rand() надо «разогнать» начальным случайным значением. Это делается с помощью функций srand() и time().

Заполнение массива значениями, естественно, делаем в цикле. Помним, что элементы массива в C/C++ нумеруются с 0. Следовательно последний элемент массива имеет индекс на единицу меньший, чем размер массива.

В примере показано заполнение глобального автоматического массива из 10 элементов типа int случайными значения из диапазона от −100 до 100 включительно:

#include <cstdlib>
#include <time.h>

using namespace std;

// функция генерации случайного числа из диапазона от range_min до range_max включительно
int rrand(int range_min, int range_max) {
    return rand() % (range_max - range_min + 1) + range_min;
}

const unsigned int ARRSIZE = 10;
const int ABSLIMIT = 100;

int ary[ARRSIZE];

int main(void) {

    srand(static_cast<unsigned int>(time(NULL)));

    // инициализация массива случайными значениями из диапазона -ABSLIMIT..ABSLIMIT
    for (unsigned int i = 0; i < ARRSIZE; i++) {
        ary[i] = rrand(-ABSLIMIT, ABSLIMIT);
    }
    return 0;
}

Обратите внимание на включение заголовочных файлов!

Заполнение массива числами, введёнными пользователем

Как ни странно, это более сложный случай. Дело в том, что во-первых, наличие человека всегда может приводить к некорректному вводу данных (ошибкам), во-вторых, для человека необходимо обеспечить какой-никакой интерфейс, а в-третьих, система потокового ввода-вывода STL имеет свои неприятные особенности.

Итак, пользуясь предыдущим примером, попробуем написать фрагмент, отвечающий за ввод значений массива с клавиатуры. Добавим в начало кода заголовочный файл #include <iostream>, а вместо инициализации массива случайными значениями напишем что-то типа:

for (unsigned int i = 0; i < ARRSIZE; i++) {
    cout << "Введите значение для элемента массива " << i << ": ";
    cin >> ary[i];
}

Оно как бы работает, но если вы попытаетесь в качестве числа (конечно случайно!) ввести 1111111111111111111111111111111111 или 11q, то, в зависимости от компилятора, сможете наблюдать некоторые интересные эффекты работы вашей программы.

Поэтому приходится писать более сложный код:

// инициализация массива вводом из cin
bool fail = false;
for (unsigned int i = 0; i < ARRSIZE; i++) {
    do {
        fail = false;
        cout << "Введите значение для элемента массива " << i << ": ";
        cin >> ary[i];
        if (cin.fail()) {
            cout << "*** Введено некорректное значение. Повторите ввод." << endl;
            fail = true;
        }
        cin.clear();
        cin.ignore();
    } while (fail);

}

Подробный разбор данного фрагмента выходит за рамки данной статьи. Но интересующиеся могут его разобрать, вооружившись, например, известной книгой Г. Шилдта.

Вывод на консоль значений из массива

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

// вывод в cout значений элементов массива
for (unsigned int i = 0; i < ARRSIZE; i++) {
    cout << "Значение элемента массива [" << i << "] = " << ary[i] << endl;
}

Работа со значениями из массива

Всё, о чём было написано выше, это были как бы вспомогательные элементы программы. Далее разберём несколько примеров обработки массивов.

Поиск максимального/максимального значения в массиве

Ниже приведён полный код программы поиска минимального значения в массиве и его индекса. В программе используется глобальный автоматический массив. Значения массива получаются посредством генератора случайных чисел.

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

// функция генерации случайного числа из диапазона от range_min до range_max включительно
int rrand(int range_min, int range_max) {
    return rand() % (range_max - range_min + 1) + range_min;
}

const unsigned int ARRSIZE = 10;
const int ABSLIMIT = 100;

int ary[ARRSIZE];

int main(void) {

    setlocale(LC_ALL, "Russian");

    srand(static_cast<unsigned int>(time(NULL)));

    // инициализация массива случайными значениями из диапазона -ABSLIMIT..ABSLIMIT
    for (unsigned int i = 0; i < ARRSIZE; i++) {
        ary[i] = rrand(-ABSLIMIT, ABSLIMIT);
    }

    // вывод в cout значений элементов массива
    for (unsigned int i = 0; i < ARRSIZE; i++) {
        cout << "Значение элемента массива [" << i << "] = " << ary[i] << endl;
    }


    // поиск максимального значения в массиве и его индекса
    // при наличии нескольких минимальных значений находится первое
    int min_val = ary[0];
    unsigned int min_idx = 0;
    for (unsigned int i = 1; i < ARRSIZE; i++) {
        if (min_val > ary[i]) {
            min_val = ary[i];
            min_idx = i;
        }
    }
    cout << "Минимальное значение " << min_val << ", индекс элемента " << min_idx << endl;

    system("pause");
    return 0;
}

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

Как видно из комментариев, за поиск минимального значения и его индекса отвечает последний фрагмент программы.

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

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

Поиск определённого значения в массиве

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

Задачи на поиск в массиве могут быть в двух формах:

  1. найти первое (последнее) вхождение искомого значения
  2. найти все вхождения

Поиск первого вхождения:

// поиск в массиве первого вхождения определённого значения
int pattern = 8;  // искомое значение
unsigned int i;
for (i = 0; i < ARRSIZE; i++) {
    if (ary[i] == pattern) {
        break;
    }
}
if (i >= ARRSIZE) {
    cout << "Искомый элемент не найден" << endl;
}
else {
    cout << "Индекс первого вхождения искомого значения: " << i << endl;
}

Поиск последнего вхождения:


// поиск в массиве последнего вхождения определённого значения
int pattern = 8;  // искомое значение
int i;
for (i = ARRSIZE - 1; i >= 0; i--) {
    if (ary[i] == pattern) {
        break;
    }
}
if (i < 0) {
    cout << "Искомый элемент не найден" << endl;
}
else {
    cout << "Индекс последнего вхождения искомого значения: " << i << endl;
}

Обратите внимание на следующие моменты.

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

  2. Если искомый элемент найден, то цикл завершается досрочно оператором break: просматривать остальную часть массива не имеет смысла — задача уже выполнена.

  3. Во втором случае переменная i имеет знаковый тип int. Отрицательное значение используется в качестве флага, что весь массив просмотрен, и значение не найдено.

Поиск всех вхождений:

// поиск в массиве всех вхождений определённого значения
int pattern = 2;  // искомое значение
unsigned int i;
bool found = false;
for (i = 0; i < ARRSIZE; i++) {
    if (ary[i] == pattern) {
        cout << "Индекс найденного элемента: " << i << endl;
        found = true;
    }
}
if (!found) {
    cout << "Искомый элемент не найден" << endl;
}

Здесь цикл не прерывается. Массив просматривается полностью.

Сумма/произведение отрицательных элементов массива

// Сумма отрицательных элементов массива
long sum = 0;
for (unsigned int i = 0; i < ARRSIZE; i++) {
    if (ary[i] < 0) {
        sum += ary[i];
    }
}
cout << "Сумма отрицательных элементов массива равна " << sum << endl;
// Произведение отрицательных элементов массива
long product = 1;
for (unsigned int i = 0; i < ARRSIZE; i++) {
    if (ary[i] < 0) {
        product *= ary[i];
    }
}
cout << "Произведение отрицательных элементов массива равно " << product << endl;

Сумма элементов массива с чётными/нечётными индексами

// Сумма элементов массива с чётными индексами
long sum = 0;
for (unsigned int i = 0; i < ARRSIZE; i += 2) {
    sum += ary[i];
}
cout << "Сумма элементов массива с чётными индексами равна " << sum << endl;
// Сумма элементов массива с нечётными индексами
long sum = 0;
for (unsigned int i = 1; i < ARRSIZE; i += 2) {
    sum += ary[i];
}
cout << "Сумма элементов массива с нечётными индексами равна " << sum << endl;

Работа с массивами с применением функций

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

Массив передаётся в функцию как указатель. Причём неважно, какой это массив: автоматический или массив с динамическим выделением памяти. Также обычно в функцию необходимо передать размер массива (количество элементов), поскольку в общем случае, имея только указатель, невозможно определить размер массива. (Есть частные случаи, когда размер определить можно, используя значение-маркер. Например, строки в C&#x2011;стиле должны заканчиваться нулевым символом).

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

// функция генерации случайного числа из диапазона от range_min до range_max включительно
int rrand(int range_min, int range_max) {
    return rand() % (range_max - range_min + 1) + range_min;
}

const unsigned int ARRSIZE = 12;
const int ABSLIMIT = 5;

void set_random_values(int *ar, unsigned int ar_size) {
    // инициализация массива случайными значениями из диапазона -ABSLIMIT..ABSLIMIT
    for (unsigned int i = 0; i < ar_size; i++) {
        ar[i] = rrand(-ABSLIMIT, ABSLIMIT);
    }
}

void print_values(int *ar, unsigned int ar_size) {
    for (unsigned int i = 0; i < ar_size; i++) {
        cout << "Значение элемента массива [" << i << "] = " << ar[i] << endl;
    }
}

long summ_even(int *ar, unsigned int ar_size) {
    // Сумма элементов массива с чётными индексами
    long sum = 0;
    for (unsigned int i = 0; i < ar_size; i += 2) {
        sum += ar[i];
    }
    return sum;
}

int main(void) {

    setlocale(LC_ALL, "Russian");

    int *ary = new int[ARRSIZE];        // выделяем память под массив

    set_random_values(ary, ARRSIZE);
    print_values(ary, ARRSIZE);
    cout << "Сумма элементов массива с чётными индексами равна " << summ_even(ary, ARRSIZE) << endl;

    delete [] ary;                // освобождение памяти

    system("pause");
    return 0;
}

Обратите внимание, что выделение памяти под массив и её освобождение происходит в одной функции (в данном случае, в main()). Выделять память в одной функции, а освобождать в другой — плохая идея, чреватая ошибками.

Заключение

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

Да пребудет с вами святой Бьярн и апостолы его! ;-)

Автор статьи: Череп.

→.

После регистрации реклама на сайте отображаться не будет.
Обсудите статью на форуме.

Комментарии к статье: 21

Подождите, загружаются комментарии...

Оставить комментарий

Если не хотите больше вводить капчу — создайте аккаунт.

Предпросмотр комментария

Ваш комментарий пуст.