Основы C++. Массивы в C++

14-09-19 root C/C++ 1

Продолжаем изучение основ C++. В этой статье мы рассмотрим массивы.

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

Введение в массивы

Визуализировать массив можно следующим образом:

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

Card1 = getRandomCard();
Card2 = getRandomCard();
Card3 = getRandomCard();
Card4 = getRandomCard();
Card5 = getRandomCard();

к такой

for ( int i = 0; i < 5; i++ )
{
    card[i] = getRandomCard();
}

А теперь представьте разницу, если переменных 100!

Синтаксис

Для объявления массива необходимо указать две вещи (помимо имени): тип и размер массива:

int my_array[ 6 ];

Данная строка объявляет массив из шести целочисленных значений. Обратите внимание, что размер массива заключен в квадратные скобки после имени массива.

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

my_array[ 3 ];

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

my_array ссылается на весь массив целиком, в то время как my_array[0] только на первый элемент, my_array[3] — на четвертый. Обратите внимание, что индексация элементов в массиве начинается с 0. Таким образом Обращение к элементам массива всегда будет происходить со смещением, например:

int my_array[ 4 ]; // объявление массива
my_array[ 2 ] = 2; // установить значение третьего (именно третьего!) равным 2

Объявление многомерных массивов в C++

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

Для объявления двумерного массива необходимо указать размерность двух измерений:

int tic_tac_toe_board[3][3];

Визуализация массива с индексами его элементов:

Для доступа к элементам такого массива потребуется два индекса — один для строки второй для столбца. На изображении показаны нужные индексы для доступа к каждому из элементов.

Использование массивов

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

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

#include <iostream>
using namespace std;

int main() {
    int array[8][8]; // Объявляем массив, который выглядит как шахматная доска
    for (int i = 0; i < 8; i++) {

        for (int j = 0; j < 8; j++) {
            array[i][j] = i * j; // Задаем значения каждого элемента
        }
    }
    cout << "Multiplication table:\n";
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cout << "[ " << i << " ][ " << j << "] = ";
            cout << array[i][j] << " ";
            cout << "\n";
        }
    }
}

Передаем массивы в функции

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

Чтобы передать массив в функцию достаточно просто указать его имя:

int values[ 10 ];
sum_array( values );

А при объявлении функции указать массив в качестве аргумента:

int sum_array (int values[]);

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

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

int sumArray(int values[], int size) {
    int sum = 0;
    for (int i = 0; i < size; i++) {
        sum += values[ i ];
    }
    return sum;
}

Когда мы передаем многомерные массивы, надо указывать все размерности, за исключением первой:

int check_tic_tac_toe (int board[][3]);

Вы, конечно, можете указать первую размерность, но она будет проигнорирована.

Подробнее эта тема будет раскрыта в статье про указатели.

А пока напишем функцию, которая вычисляет сумму элементов массива:

#include <iostream>
using namespace std;

int sumArray(int values[], int size) {
    int sum = 0;
    // цикл остановится когда i == size, потому что индекс последнего элемента = size - 1 
    for (int i = 0; i < size; i++) {
        sum += values[i];
    }
    return sum;
}

int main() {
    int values[10];
    for (int i = 0; i < 10; i++) {
        cout << "Enter value " << i << ": ";
        cin >> values[i];
    }
    cout << sumArray(values, 10) << endl;
}

Сортировка массива

Решим задачу сортировки массива из 100 чисел, которые ввел пользователь:

#include <iostream>
using namespace std;

int main() {
    int values[ 100 ];
    for (int i = 0; i < 100; i++) {
        cout << "Enter value " << i << ": ";
        cin >> values[ i ];
    }
}

Готово, осталось только отсортировать этот массив 🙂 Как обычно люди сортируют массивы? Они ищут самый маленький элемент в нем и ставят его в начало списка. Затем они ищут следующее минимальное значение и ставят его сразу после первого и т.д.

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

void sort(int array[], int size) {
    for (int i = 0; i < size; i++) {
        int index = findSmallestRemainingElement(array, size, i);
        swap(array, i, index);
    }
}

Теперь можно подумать о реализации двух вспомогательных методов findSmallestRemainingElement и swap. Метод findSmallestRemainingElement должен пробегать по массиву и находить минимальный элемент, начиная с индекса i:

int findSmallestRemainingElement(int array[], int size, int index) {
    int index_of_smallest_value = index;
    for (int i = index + 1; i < size; i++) {
        if (array[ i ] < array[ index_of_smallest_value ]) {
            index_of_smallest_value = I;
        }
    }
    return index_of_smallest_value;
}

Наконец, нам надо реализовать функцию swap. Так как функция изменит оригинальный массив, нам просто надо поменять значения местами, используя временную переменную:

void swap(int array[], int first_index, int second_index) {
    int temp = array[ first_index ];
    array[ first_index ] = array[ second_index ];
    array[ second_index ] = temp;
}

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

#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

int findSmallestRemainingElement(int array[], int size, int index);
void swap(int array[], int first_index, int second_index);

void sort(int array[], int size) {
    for (int i = 0; i < size; i++) {
        int index = findSmallestRemainingElement(array, size, i);
        swap(array, i, index);
    }

}

int findSmallestRemainingElement(int array[], int size, int index) {
    int index_of_smallest_value = index;
    for (int i = index + 1; i < size; i++) {
        if (array[ i ] < array[ index_of_smallest_value ]) {
            index_of_smallest_value = i;
        }
    }
    return index_of_smallest_value;
}

void swap(int array[], int first_index, int second_index) {
    int temp = array[ first_index ];
    array[ first_index ] = array[ second_index ];
    array[ second_index ] = temp;
}

// вспомогательная функция для вывода массива
void displayArray(int array[], int size) {
    cout << "{";
    for (int i = 0; i < size; i++) {
        // если элемент не первый выведем запятую
        if (i != 0) {
            cout << ", ";
        }
        cout << array[ i ];
    }
    cout << "}";
}

int main() {
    int array[ 10 ];
    srand(time(NULL));
    for (int i = 0; i < 10; i++) {
        array[ i ] = rand() % 100;
    }
    cout << "Original array: ";
    displayArray(array, 10);
    cout << '\n';
    sort(array, 10);
    cout << "Sorted array: ";
    displayArray(array, 10);
    cout << '\n';
}

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

На этом всё.