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

Любой массив характеризуется именем, размером, числом измерений (размерностью) и типом элементов. Размер массива соответствует количеству его элементов. Размерность массива, или число измерений, определяет количество индексов, необходимых для однозначного доступа к элементам массива. Говорят, что число индексов характеризует размерность массива.

До сих пор мы рассматривали одномерные массивы, в которых доступ к элементу массива определяется одним индексом. Каждый элемент такого массива имеет номер или индекс, определяющий его местоположение в массиве. С точки зрения структуры данных одномерный массив является линейной структурой и соответствует понятию вектора в математике.

Часто данные могут быть организованы в виде таблицы, где расположение каждого элемента определяется двумя параметрами. Например, место в зрительном зале задается указанием номера ряда и номером места в этом ряду. С точки зрения структуры данных – это таблица, что соответствует в математике понятию – матрица. Примером матрицы может быть таблица Пифагора (таблица умножения), состоящая из 10 строк и 10 столбцов, в которой каждый элемент определяется формулой a _{i j} =i*j. Положение элемента a _{i j} в таблице задается двумя индексами. Индекс i обозначает номер строки, а индекс j – номер столбца, на пересечении которых находится элемент матрицы. В программировании такие данные удобно описывать как двумерный массив, в котором каждому элементу так же соответствует два индекса: первый индекс - это номер строки, а второй - номер столбца, где расположен элемент матрицы. Таким образом, в матрице два измерения, то есть её размерность – два. Размер матрицы задается количеством элементов по каждому измерению и вычисляется выражением n * m, где n - число строк, а m - число столбцов в матрице. Для программирования рассмотренной выше таблицы Пифагора понадобится двумерный массив размером 10*10=100 элементов.

В математике принято обозначать элемент матрицы, указывая номера строки и столбца мелким шрифтом после имени матрицы. Например, обращение к элементу 2-й строки 3-го столбца матрицы А обозначается a ₂₃. В программировании индексы элементов записываются в скобках, в зависимости от языка программирования, квадратных или круглых, а индексы элемента или перечисляются через запятую, или помещаются каждый в свою пару скобок. В данном пособии при описании алгоритмов всеми способами, кроме непосредственно текста программы на конкретном языке, используется запись индексов строки и столбца через запятую в квадратных скобках после имени матрицы Например, запись А[2,3] означает обращение к элементу 2-й строки 3-го столбца матрицы А.

Количество используемых индексов массива может быть различным. Как уже известно, массивы с одним индексом являются одномерными, с двумя – двумерными и т. д. Чаще всего применяются массивы с одним или двумя индексами, реже – с тремя, ещё большее количество индексов встречается крайне редко. Массивы с несколькими индексами называют многомерными.

Многомерные массивы создаются на основе одномерных. Двумерный массив – это одномерный массив, элементы которого являются одномерными массивами. Трехмерный массив – одномерный массив, элементы которого являются двумерными массивами. N-мерный массив – одномерный массив, элементы которого являются (N-1)-мерными массивами.

Проиллюстрировать, как строятся многомерные массивы, можно на приведенном ниже примере.

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

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

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

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

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