§ 2. Одномерные массивы


Ввод и вывод элементов массива

Массив – это структура данных, содержащая совокупность элементов, принадлежащих одному и тому же типу с общим для всех элементов именем. Для хранения массива используется область памяти, в которой элементы хранятся последовательно. Элементы массива пронумерованы индексами. Индексирование элементов начинается с 0:

a[0], a[1], a[2] ... 

Элементы массива называются индексированными переменными. Они могут участвовать в выражениях как обычные переменные:

a[0] = a[1] + a[2];
if (a[0] > a[1]) { ... }
a[0]++;

В C++ для описания базового типа массива используется такое же описание массива, как и в языке С, поэтому такой массив мы будем называть Си-массивом.
Описание массива производится следующим образом:

Тип Имя [Количество элементов]; 

Например:

int mass[20];
float a[5];

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

int ar[10] {5, 4, 11, 9, 0, 10, 3, 8, 2, 13};
float omega[] {1.02, 4.2, 3.7, 2.1};
int alpha[100] {};
Примечание: Количество элементов инициализируемого массива (omega) можно опустить, компилятор сам подсчитает их количество. Элементы массива alpha будут иметь значение 0.

В стандартной библиотеке C++ для массивов определена глобальная функция size() возвращающая специальный беззнаковый целый тип size_t – размер массива. Объем памяти, занятой элементами массива (в байтах), можно определить с помощью операции sizeof(), если в качестве аргумента операции передать имя массива. Или следующим образом:

size_byte = sizeof(type) * size(ar)

где type – это тип данных массива ar.
С-массивы являются статическими. Это массивы фиксированного размера (т. е. размер массива нельзя изменить в программе). Нельзя присваивать значение одного C-массива значению другого массива, обращаясь по имени, например: mass1 = mass2. Подобным образом, нельзя сравнивать C-массивы и производить с ними арифметические операции. Изменять значения элементов массива можно только поэлементно, обращаясь к элементу по имени массива и индексу:

mas[0] = 15;
omega[2] = 0.3;

Поэтому, на практике, элементы обрабатываются всей совокупностью с помощью инструкций циклов. Поскольку количество элементов C-массива известно, то удобно использовать инструкцию цикла for.

Программа 9.1.1

Инициализация и вывод элементов массива

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
	int ar[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
	for (int i = 0; i < 10; i++)
		cout << ar[i] << setw(3);
	return 0;
}

Но, пожалуй, главным недостатком Си-массива является отсутствие контроля выхода за границы массива. Эта задача целиком лежит на совести разработчика. О методах, призванных решить данную проблему, см. в разделе “Для тех, кто хочет знать больше!“.
Если начальные значения элементов массива не определены (не инициализированы), то они вводятся в цикле с помощью потока cin. Ввод элементов можно оформить в виде диалога (в сочетании потоков ввода и вывода), как в программе ниже.

Программа 9.1.2

Клавиатурный ввод элементов массива.

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
	int ar[10];
	// Ввод элементов
	for (int i = 0; i < 10; i++) {
		cout << "ar[" << i <<"] = "; // Реализация
		cin >> ar[i];                // диалога
	}
	// Вывод элементов
	for (int i = 0; i < 10; i++)
		cout << ar[i] << setw(3);
	return 0;
}

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

Для решения задач с массивами, содержащими большое количество элементов (такой массив за реальный промежуток времени заполнить с клавиатуры невозможно), возникает необходимость их быстрого заполнения данными каким-либо способом. Для этих целей используется генератор случайных чисел. Такой генератор реализован в Си-библиотеке cstdlib и библиотеке C++ random. Рассмотрим оба этих подхода.

Си-подход. Функция rand()

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

#include <cstdlib>
#include <ctime>

Библиотека ctime нужна для получения момента времени, который используется как отправная точка для последовательности случайных чисел. Непосредственно случайное число возвращает функция rand(). Значение числа лежит в промежутке от 0 до RAND_MAX (константа со значением максимального целого числа, возвращаемого функцией rand()), включительно.
Чтобы получать значения случайных чисел на определенном промежутке (включающим, возможно, и отрицательные числа) используется выражение:
A + rand() % (B - A + 1),
где А и B – это границы отрезка [A, B], множество значений которого используется для создания последовательности случайных чисел.
Функция rand() выдает машиннозависимую последовательность. На одном и том же компьютере будет генерироваться одна и та же последовательность случайных чисел. Чтобы избежать повторяющегося результата, используют две функции: srand() – инициализирующую генератор начальным значением и time(), которая, с аргументом 0, возвращает количество секунд прошедших с 01.01.70 г. (время UNIX). Это обеспечивает генерацию разных числовых последовательностей, что важно для решения задач. В итоге, код программы, в которой производится заполнение массива случайными числами, будет выглядеть следующим образом:

Программа 9.1.3
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

int main() {
	srand(time(0));
	int ar[100];
	// Ввод элементов
	for (int i = 0; i < 100; i++)
		ar[i] = 10 + rand() % 90; // [10; 99]
	// Вывод элементов
	for (int i = 0; i < 100; i++)
		cout << ar[i] << setw(3);
	return 0;
}
Использование библиотеки random

В библиотеке random определены два типа взаимосвязанных классов:

  • random-number engine – процессоры (генераторы) случайных чисел и
  • random-number distribution – распределения случайных чисел

Мы будем использовать генератор случайных чисел по умолчанию, который называется default_random_engine. Объект генератора может быть проинициализирован начальным значением (в программе ниже – это по прежнему будет момент времени).
Для определения диапазона генерации случайных чисел необходимо использовать распределение случайных чисел.
Таких распределений тоже несколько и все они описываются математическим формулами. Мы будем использовать равномерное распределение случайных величин с помощью uniform_int_distribution (равномерное распределение случайных целых чисел). В качестве аргумента, объекту класса распределения передается промежуток на котором должна построиться последовательность случайных чисел. Эта последовательность, также, как и в предыдущем случае, машиннозависимая. Для создания уникального начального значения можно использовать библиотеку ctime (аналогично предыдущему примеру), но мы будем использовать другую библиотеку STD – chrono. В результате, наша программа будет выглядеть следующим образом:

Программа 9.1.4

Заполнить массив случайными числами из отрезка [10, 99].

#include <iostream>
#include <iomanip>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int main() {
	int ar[100];
	int seed = system_clock::now().time_since_epoch().count();
	default_random_engine rnd(seed);
	uniform_int_distribution<int> d(10, 99);
	for (int i = 0; i < size(ar); i++)
		ar[i] = d(rnd);
	cout << "Элементы массива:" << endl;
	for (int i = 0; i < size(ar); i++)
		cout << ar[i] << setw(3);
	return 0;
}
Более подробные сведения о библиотеке chrono см. здесь.

Решение задач с массивами

Рассмотрим типичные задачи с массивами.

Ввод/вывод элементов

В этом типе задач массив заполняется по какому-либо правилу, а выводится, например, манипуляцией индексами.
Задача 1. Заполнить массив из 20 элементов нечетными числами.

Программа 9.1.5
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
	int ar[20];
	// Ввод элементов
	for (int i = 0; i < 20; i++) {
		ar[i] = 2 * i + 1;
	}
	// Вывод элементов
	for (int i = 0; i < 20; i++)
		cout << ar[i] << setw(3);
	return 0;
}

Задача 2. Дан массив случайных чисел, состоящий из 20 элементов. Вывести сначала только элементы с четными индексами, а затем с нечетными, но в обратном порядке.

Программа 9.1.6
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main() {
    srand(time(0));
    int ar[20];
    // Ввод элементов
    for (int i = 0; i < 20; i++)
        ar[i] = 10 + rand() % 90; // [10; 99]
    cout << "Исходный массив:" << endl;
    for (int i = 0; i < 20; i++)
        cout << ar[i] << " ";
    cout << "\nЧетные индексы:" << endl;
    for (int i = 0; i < 20; i+=2)
        cout << ar[i] << " ";
    cout << "\nНечетные индексы:" << endl;
    for (int i = 19; i > 0; i-=2)
        cout << ar[i] << " ";
    cout << endl;
    return 0;
}
Изменение значений элементов или их позиций. Обмен

Этот тип задач требует дополнительной переменной (буфера) для временного хранения значений элементов.
Задача 3. Дан массив случайных чисел, состоящий из 20 элементов. Произвести циклический сдвиг (ротацию) элементов влево (все элементы, начиная со второго смещяются влево, а первый элемент оказывается на последней позиции).

Программа 9.1.7
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

int main() {
	srand(time(0));
	int ar[100];
	// Ввод элементов
	for (int i = 0; i < 100; i++)
		ar[i] = 10 + rand() % 90;
    // Вывод исходного массива
    for (int i = 0; i < 20; i++)
        cout << ar[i] << setw(3);
    cout << "\nЦиклический сдвиг:" << endl;
    // Запоминаем значение первого элемента
    int c = ar[0];
    for (int i = 0; i < 19; i++)
        ar[i] = ar[i + 1];
    ar[19] = c;
    // Вывод измененного массива
    for (int i = 0; i < 20; i++)
        cout << ar[i] << setw(3);
    cout << endl;
    return 0;
}

Задача 4. Дан массив случайных чисел, состоящий из 20 элементов. Поменять местами элементы стоящие на четных позициях с соседними элементами, стоящими на нечетных позициях. Т. е. 1-й со 2-ым, 3-й с 4-ым и т. д.

Программа 9.1.8
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main() {
	srand(time(0));
	int ar[20];
	// Ввод элементов
	for (int i = 0; i < 20; i++)
		ar[i] = 10 + rand() % 90; // [10; 99]
    // Вывод исходного массива
    for (int i = 0; i < 20; i++)
        cout << ar[i] << " ";
    cout << endl;
    for (int i = 0; i < 19; i+=2) {
        int buf = ar[i];
        ar[i] = ar[i + 1];
        ar[i + 1] = buf;
    }
    // Вывод измененного массива
    for (int i = 0; i < 20; i++)
        cout << ar[i] << " ";
    cout << endl;
    return 0;
}
Поиск min/max или по критерию. Подсчет элементов

В этих задачах в теле цикла используется условная инструкция if.
Задача 5. Дан массив случайных чисел, состоящий из 20 элементов. Определить позицию минимального элемента массива и обменять его с первым элементом.

Программа 9.1.9
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main() {
    srand(time(0));
    int ar[20];
    // Ввод элементов
    for (int i = 0; i < 20; i++)
        ar[i] = 10 + rand() % 90; // [10; 99]
    // Вывод исходного массива
    for (int i = 0; i < 20; i++)
        cout << ar[i] << " ";
    cout << endl;
    int min = ar[0];
    int j = 0;
    for (int i = 1; i < 20; i++)
        if (ar[i] < min) {
            min = ar[i];
            j = i;
        }
    if (j) {
        int buf = ar[0];
        ar[0] = ar[j];
        ar[j] = buf;
    }
    // Вывод измененного массива
    for (int i = 0; i < 20; i++)
        cout << ar[i] << " ";
    cout << endl;
    return 0;
}

Задача 6. Дан массив случайных чисел, состоящий из 20 элементов и число k. Обнулить те его элементы, которые больше k.

Программа 9.1.10
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main() {
    srand(time(0));
    int ar[100];
    // Ввод элементов
    for (int i = 0; i < 100; i++)
        ar[i] = 10 + rand() % 90; // [10; 99]
    // Вывод исходного массива
    for (int i = 0; i < 20; i++)
        cout << ar[i] << " ";
    int k;
    cout << "\nk = ";
    cin >> k;
    for (int i = 0; i < 20; i++)
        if (ar[i] > k)
            ar[i] = 0;
    // Вывод измененного массива
    for (int i = 0; i < 20; i++)
        cout << ar[i] << " ";
    cout << endl;
    return 0;
}
Далее следует материал для углубленного изучения. На базовом уровне может быть пропущен.

Для тех, кто хочет знать больше!

Цикл for основанный на диапазоне

Помимо обычной инструкции for, для работы с массивами используется специальная форма цикла for (range-based for), так называемый цикл for основанный на диапазоне. Такая форма выглядит более лаконичной. Так, например, вывод элементов массива в программе 9.1.2 можно осуществить следующим образом:

for (auto &ar : mass)	 	 
    cout << ar << setw(3);	 	 

В переменной ar перебираются все элементы массива ar. Эта переменная может быть как ссылочного типа (это показано в примере - имя переменной предшествует операция &), так и обычного. Если используется переменная не ссылочного типа, то элементы массива будут копироваться. Изменение копий элементов не повлияет на значения оригинальных элементов! Изменение же ссылки повлечет изменение и самого элемента в массиве.

Итераторы

Итератор (iterator) - это такой объект, который позволяет перебирать элементы массива, переходя от одного элемента - к другому.

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

iter1
Для получения итератора существуют специальные функции begin() и end(). Функция begin() возвращает итератор, указывающий на начало массива (первый элемент), а end() возвращает итератор, указывающий на позицию, следующую за последним элементом. Таким образом, функции begin() и end() определяют полуоткрытый интервал [first, last).
Перед использованием итераторов их необходимо объявить:

auto first = begin(ar);
auto last  = end(ar);

где first и last - имена итераторов, а ar - имя массива.
Для перемещения итератора по элементам массива используется операция ++, применяемая к итератору first (обычно, итератор end не перемещается, но это возможно):

first++

Перемещение итератора по элементам массива можно сравнить с перемещением фишки в настольной игре

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

*first

Эти операции можно объединить (поскольку ассоциативность обеих операций слева-направо):

cout << *first++

Это выражение означает, что сначала будет выведен элемент (операция разыменования), а затем произойдет переход к следующему элементу.
Итераторы удобно использовать для контроля выхода за границы массива (что равносильно ошибке, приводящей к краху приложения). В этом случае, для обхода массива, лучше всего подходит цикл while. Рассмотрим пример использования итераторов в программе. Постановка задачи: Заполнить массив членами арифметической прогрессии, первый член которой равен a, а разность q.

Программа 9.1.11
#include <iostream>
#include <iterator>
using namespace std;

int main() {
    int a, q;
    cout << "a = "; cin >> a;
    cout << "q = "; cin >> q;
    int ar[20];
    // Получаем итераторы
    auto first = begin(ar);
    auto last  = end(ar);
    while (first != last) {
        // Присваиваем элементу массива значение n-го члена прогрессии
        *first = a;
        // увеличиваем значение n-го члена на разность
        a += q;
        // переходим к следующему
        first++;
    }
    // Выводим элементы массива
    for (auto mas : ar)
        cout << mas << " ";
    cout << endl;
    return 0;
}
Контейнер array

В стандартной библиотеке C++ существует шаблонный класс контейнера array, позволяющий создавать объекты подобные статическим С-массивам с равной эффективностью, но более безопасный в работе. Преимуществом использования класса array (по сравнению с C-массивами) является то, что он предоставляет ряд удобных функций (общих для всех встроенных контейнеров), таких как сравнение, присваивание, итераторы и мн. др.
Для создания объекта array необходимо включить одноименный заголовочный файл:

#include <array>

Объект класса array создается следующим образом:

array<тип, размер> имя

Приведем пример работы с объектом класса array.
Постановка задачи: Дан массив. Определить:

  1. среднее арифметическое элементов массива;
  2. количество элементов меньших k.
  3. Поменять местами максимальный и минимальный элементы массива

Программа 9.1.12

#include <iostream>
#include <array>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int main() {
//============================= 1 =============================//
	int seed = system_clock::now().time_since_epoch().count();
    default_random_engine rnd(seed);
    uniform_int_distribution<int> d(10, 99);
    int s = 0, k;
    array<int, 20> ar {};
    cout << "Исходный массив:" << endl;
    for (auto &i : ar) {
        i = d(rnd);
        cout << i << " ";
        s += i;
    }
    cout << "\nСреднее арифметическое => "
         << float(s) / 20 << endl;
//=========================== 2, 3 ===========================//
    cout << "k = "; cin >> k;
    s = 0;
    int max = ar[0], m = 0;
    int min = ar[0], n = 0;
    for (size_t i = 1; i < ar.size(); i++) {
        if (ar[i] < k) s++;
        if (ar[i] > max) {max = ar[i]; m = i;}
        if (ar[i] < min) {min = ar[i]; n = i;}
    }
    cout << "Элементов < " << k
         << " => " << s << endl;
    s = ar[m];
    ar[m] = ar[n];
    ar[n] = s;
    cout << "Измененный массив:" << endl;
    for (auto &i : ar) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}
Исходный массив:
62 21 79 88 51 79 13 86 56 61 72 97 18 79 83 51 71 38 88 32 
Среднее арифметическое => 61.25
k = 20
Элементов < 20 => 2
Измененный массив:
62 21 79 88 51 79 97 86 56 61 72 13 18 79 83 51 71 38 88 32 
Примеры решения задач
Вопросы
Темы сообщений
Задания А
Задания Б
Задания С
Ссылки
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.


Обсуждение закрыто.