§13 Двумерные массивы (матрицы)

Понятие двумерного массива

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

a11 a12 a13 a14 a15 ... a1m
a21 a22 a23 a24 a25 ... a2m
a31 a32 a33 a34 a35 ... a3m
a41 a42 a43 a44 a45 ... a4m
a51 a52 a53 a54 a55 ... a5m
... ... ... ... ... ... ...
an1 an2 an3 an4 an5 ... anm

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

Определение двумерного С-массива

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

int mas[4][6];

Это определение означает, что объявлен целочисленный массив mas содержащий 4 элемента, каждый из которых содержит 6 элементов. Принято считать, что первая размерность определяет строки, а вторая – столбцы. Таким образом, мы объявили двумерный массив состоящий из 4 строк и 6 столбцов.

Инициализация двумерного C-массива

Поскольку мы имеем дело с массивом массивов, то инициализация производится с помощью вложенных {} как показано в примере ниже:

const int n = 5;
const int m = 4;
int mas[n][m] {
	{1, 0, 1, 0},
	{1, 1, 0, 1},
	{0, 1, 1, 0},
	{1, 0, 1, 1},
	{0, 1, 0, 1}
};

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

int mas[4][5] {{}, {}, {}, {}};

Ввод и вывод двумерного С-массива

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

Программа 9.13.1

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

#include <iostream>
#include <random>
#include <chrono>

using namespace std;
using namespace chrono;

int main() {
	const int n = 6;
	const int m = 5;
	int mas[n][m];
	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 < n; i++)
		for(int j = 0; j < m; j++)
			mas[i][j] = d(rnd);
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cout.width(3);
			cout << mas[i][j];
		}
		cout << '\n';
	}
	return 0;
}

Программа выведет следующее:

 52 68 33 98 70
 31 76 92 40 20
 72 57 41 29 74
 33 16 19 71 40
 86 21 42 54 53
 49 17 20 40 77

Определение и инициализация двумерного массива array

Определение объекта array как двумерный массив состоящего из 7 строк и 5 столбцов выглядит следующим образом:

array<array<int, 5>, 7> mas;

Выражение array<int, 5> является описанием типа вложенных массивов (состоящих из 5 целых элементов) которых, в общей сложности, 7 штук. В программе для ввода и вывода элементов двумерного массива array можно использовать диапазонный цикл for, который делает программу гораздо компактнее:

Программа 9.13.2
#include <iostream>
#include <array>
#include <random>
#include <chrono>

using namespace std;
using namespace chrono;

int main() {
	int seed = system_clock::now().time_since_epoch().count();
	default_random_engine rnd(seed);
	uniform_int_distribution<int> d(10, 99);
	array<array<int, 5>, 7> mas;
	for (auto &r : mas)
		for (auto &j : r)
			j = d(rnd);
	for (auto &r : mas) {
		for (auto &j : r) {
			cout.width(3);
			cout << j;
		}
		cout << "\n";
	}
	return 0;
}

Одномерный массив как двумерный

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

Программа 9.13.3
#include <iostream>
#include <array>
#include <random>
#include <chrono>

using namespace std;
using namespace chrono;

int main() {
	int seed = system_clock::now().time_since_epoch().count();
	default_random_engine rnd(seed);
	uniform_int_distribution<int> d(10, 99);
	const int row = 7;
	const int col = 5;
	array<int, col * row> mas;
	for (int i = 0; i < row * col; i++)
		mas[i] = d(rnd);
	int k = 0;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			cout.width(3);
			cout << mas[k];
			k++;
		}
		cout << "\n";
	}
	return 0;
}

Свойства диагоналей матрицы

Матрица, в которой количество строк и столбцов одинаково, называется – квадратной.
Элементы имеющие равные индексы (i == j) находятся на главной диагонали. Если элемент лежит на побочной диагонали, то индексы связаны с размерностью (n) следующим равенством: i + j == n + 2.
От позиции элемента будет зависеть отношение индексов. Если элемент лежит выше главной диагонали, тогда i < j. В противном случае, i > j. Если элемент лежит выше побочной диагонали, то i + j + 2 < n, в противном случае i + j + 2 > n. Однако, при решении задач обхода матрицы, необходимо избегать (там, где это возможно) применение условной инструкции if. Зачастую, задачу можно реализовать более рационально, путем манипуляции индексами (иначе, переменными цикла i и j). То есть, поставить в зависимость изменение одного индекса, от величины другого. Пример задачи.

Программа 9.13.4

Дана квадратная матрица размера n, элементы которой равны 0. Заполнить элементы, лежащие ниже и на самой главной диагонали единицами.

#include <iostream>
using namespace std;

int main() {
	int n;
	cout << "n = "; cin >> n;
	int mas[n][n];
	// Заполняем нулями
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			mas[i][j] = 0;
	// Реализация
	for(int i = 0; i < n; i++)
		for(int j = 0; j <= i; j++)
			mas[i][j] = 1;
	// Вывод
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cout.width(2);
			cout << mas[i][j];
		}
		cout << '\n';
	}
	return 0;
}
n = 10
 1 0 0 0 0 0 0 0 0 0
 1 1 0 0 0 0 0 0 0 0
 1 1 1 0 0 0 0 0 0 0
 1 1 1 1 0 0 0 0 0 0
 1 1 1 1 1 0 0 0 0 0
 1 1 1 1 1 1 0 0 0 0
 1 1 1 1 1 1 1 0 0 0
 1 1 1 1 1 1 1 1 0 0
 1 1 1 1 1 1 1 1 1 0
 1 1 1 1 1 1 1 1 1 1

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

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

int main() {
	int n;
	cout << "n = "; cin >> n;
	int pas[n][n];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			pas[i][j] = 0;
	pas[0][0] = 1;
	for (int i = 1; i < n; i++) {
		pas[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			pas[i][j] = pas[i - 1][j - 1] + pas[i - 1][j];
		}
	}
	for (int i = 0; i < n; i++) {
		cout << setw(3 * (n - i));
		for (int j = 0; j <= i; j++) {
			cout << pas[i][j] << setw(6);
		}
		cout << endl;
	}
	return 0;
}
n = 12
                                   1
                                1     1
                             1     2     1
                          1     3     3     1
                       1     4     6     4     1
                    1     5    10    10     5     1
                 1     6    15    20    15     6     1
              1     7    21    35    35    21     7     1
           1     8    28    56    70    56    28     8     1
        1     9    36    84   126   126    84    36     9     1
     1    10    45   120   210   252   210   120    45    10     1
  1    11    55   165   330   462   462   330   165    55    11     1

Обратите внимание на то, как осуществляется выравнивание по центру. Выравнивание осуществляется манипулятором setw() во внешнем цикле. Формула получена из упрощения выражения n*6/2-i*6/2, где 6 - это количество знакомест на вывод элемента массива. В библиотеке ios отсутствуют методы выравнивания по центру (к сожалению), поэтому для центровки всегда придется вычислять длину выводимой строки и соотносить её с максимальной шириной вывода (из всех возможных построчных выводов), а уже потом определять отступы для каждой строки, подобно примеру этого алгоритма. Если же вы хотите получить идеальное выравнивание (как на картинке выше), то вам потребуется включение соответствующих библиотек для работы с консольным выводом, поскольку в программе 9.13.5 используется символьное позиционирование, а не геометрия окна.

Вопросы

1. Что представляет собой двумерный массив в C++?
2. Перечислите способы заполнения двумерного массива данными.
3. Какой массив называется квадратной матрицей?
4. Что нужно учитывать при выводе двумерного массива?
5. Что такое главная и побочная диагональ матрицы?

Практические задания

1. Даны целые положительные числа M и N. Сформировать целочисленную матрицу размера M × N, у которой все элементы I-й строки имеют значение 10·I (I = 1, …, M).
2. Даны целые положительные числа M, N и набор из N чисел. Сформировать матрицу размера M × N, у которой в каждой строке содержатся все числа из исходного набора (в том же порядке).
3. Даны целые положительные числа M, N, число D и набор из M чисел. Сформировать матрицу размера M × N, у которой первый столбец совпадает с исходным набором чисел, а элементы каждого следующего столбца равны сумме соответствующего элемента предыдущего столбца и числа D (в результате каждая строка матрицы будет содержать элементы арифметической прогрессии).

Print Friendly, PDF & Email

Comments are closed.