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

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

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

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) осуществляется перебор строк, тогда как во вложенном цикле осуществляется перебор элементов текущей строки (т. е. проходим по столбцам).
Программа 12.1 Заполнение массива случайными числами и вывод.

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

int main() {
	const int n = 6;
	const int m = 5;
	int mas[n][m];
	default_random_engine rnd(time(0));
	uniform_int_distribution<unsigned> 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, который делает программу гораздо компактнее:
Программа 12.2

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

int main() {
	default_random_engine rnd(time(0));
	uniform_int_distribution<unsigned> 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 для определения количество строк и столбцов. Далее в программе можно обрабатывать элементы массива, например, так:
Программа 12.3

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

int main() {
	default_random_engine rnd(time(0));
	uniform_int_distribution<unsigned> 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). То есть, поставить в зависимость изменение одного индекса, от величины другого. Пример задачи.
Программа 12.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
В этом треугольнике на вершине и по бокам стоят единицы (в программе 3 треугольник "положен на бок" - стороны треугольника: первый столбец и главная диагональ). Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси.
Программа 12.5

#include <iostream>
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++) {
		for (int j = 0; j <= i; j++) {
			cout.width(4);
			cout << pas[i][j];
		}
		cout << '\n';
	}
	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

Вопросы

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 (в результате каждая строка матрицы будет содержать элементы арифметической прогрессии). [/su_list]


    Добавить комментарий