21 сентября 2021

Массивы

Массив - это структура данных для работы с коллекцией элементов. Массив Си - это группа элементов одного типа, расположенных в памяти последовательно.

Определить массив целых можно так:

int arr[12];

При этом выделяется память для хранения 12 элементов типа int. Значения элементов массива не инициализируются (т.е. могут быть любыми). Проинициализировать значения элементов можно с помощью цикла for:

for (int i = 0; i < 12; ++i) {
    arr[i] = 0;
}

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

Массив можно инициализировать с помощью списка инициализаторов:

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

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

Пример 1. Гистограмма.

На прошлом занятии вы писали самостоятельную работу. Заведем массив scores с вашими баллами:

int scores[] = {5, 7, 6, 8, 9, 9, 6, 8, 6, 8, 7, 7, 7};

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

int hist[11];
    
for (int i = 0; i < 11; ++i)
    hist[i] = 0;

for (int i = 0; i < 13; ++i)
    ++hist[scores[i]];

Наконец, выведем данные в консоль:

for (int i = 0; i < 11; ++i) {
    printf("%2d: %2d  ", i, hist[i]);
    for (int j = 0; j < hist[i]; ++j)
        putchar('*');
    putchar('\n');
}

Вот результат:

 0:  0  
 1:  0  
 2:  0  
 3:  0  
 4:  0  
 5:  1  *
 6:  3  ***
 7:  4  ****
 8:  3  ***
 9:  2  **
10:  0

Функция putchar из библиотеки stdio.h позволяет выводить один символ в поток вывода (также существует функция getchar, которая получает из потока ввода один символ).

Звездочками (символ *) мы построили гистограмму.

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

Определим функцию, которая принимает массив целых чисел и возводит в квадрат каждый элемент массива:

void array_square(int arr[], size_t size) {
    for (size_t i = 0; i < size; ++i) {
        arr[i] *= arr[i];
    }
}

Вместе с массивом необходимо передавать его размер.

Передача массива в функцию осуществляется по имени массива:

int arr2[] = {1, 2, 3, 4};
array_square(arr2, 4);
for (int i = 0; i < 4; ++i)
    printf("%d%c", arr2[i], i < 3 ? ' ' : '\n');

1 4 9 16

Заметим, что при передачи массива в функцию не происходит копирования, поскольку имя массива - это по сути указатель на его первый элемент. Функция array_square могла бы быть объявлена и так:

void array_square(int *arr, size_t size) {
    for (size_t i = 0; i < size; ++i) {
        arr[i] *= arr[i];
    }
}

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

void print_square(const int arr[], size_t size) {
    for (size_t i = 0; i < size; ++i) {
        printf("%d%c", arr[i], i < 3 ? ' ' : '\n');
    }
}

Задание размера массива во время исполнения программы

До сих пор мы задавали размер массива с помощью констант, известных в момент компиляции. Некоторые компиляторы позволяют задавать размер массива во время исполнения программы. Например:

int size;
scanf("%d", &size);
int arr[size];

Такие массивы называют массивами переменной длины. При этом изменять размер уже существующего массива нельзя.

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

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

Си поддерживает многомерные массивы. Двумерный массив, например, можно определить так:

int matrix[3][2] = {
    {1, 0},
    {0, 1},
    {1, 0}
};

for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 2; ++j) {
        printf("%3d", matrix[i][j]);
    }
    putchar('\n');
}

  1  0
  0  1
  1  0

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

Упражнение 2. Решето Эратосфена. Написать функцию, которая принимает натуральное число n и находит все простые числа в интервале от 0 до n. Для этого предлагается использовать следющий алгорим:

  1. Создаем массив primes для найденных простых чисел.
  2. Создать массив целых чисел sieve размера n и инициализировать его единицами, кроме первых трех: sieve = {0, 0, 0, 1, 1, ...}.
  3. Создать переменную p и проинициализировать ее значением 2.
  4. Для всех значений i * p < n, i = 2, 3, ... устанавливаем значения sieve[i * p] = 0
  5. Находим минимальное индекс q в массиве sieve, для которого sieve[q] не равно нулю. Это наше следующее простое число, добавляем его в массив primes. Присваиваем это значение переменной p и возвращаемся на шаг 3. Если найти индекс q не удалось, то завершаем работу функции.

Упражнение 3. Написать функцию, которая принимает массив типа double и определяет является ли массив отсортированным

Упражнение 4. Сортировка вставками. Написать функцию, которая принимает массив чисел и выполняет его сортировку. Для сортировки использовать алгоритм сортировки вставками:

  1. Дан массив arr размера n. Для индекса i от 0 до n выполнить:
  2. Для индекса j от i + 1 до нуля: если arr[j] < arr[j - 1] выполнить операцию swap(arr[j], arr[j - 1]), иначе выйти из цикла по переменной j.

Следующая анимация (из wikipedia) иллюстрирует алгорим сортировки вставками:

Упражнение 5. Бинарный поиск. Написать функцию, которая принимает отсортированный массив типа int[] и целое число n и находит индекс числа n в массиве. Если числа n нет в массиве, то функция возвращает -1. Количество операций должно быть пропорционально логарифму от количества элементов массива.