Раздел 9 — Двумерные массивы

Двумерный массив — таблица: int table[3][4] — 3 строки по 4 столбца. Элемент — table[строка][столбец], оба индекса с нуля. Формально это массив из 3 элементов, каждый из которых — массив из 4 int.

int table[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};
table[1][2] = 70;                  /* строка 1, столбец 2: было 7 */

В памяти таблица лежит по строкам, подряд: сначала вся строка 0, за ней вся строка 1:

  table[0][0] [0][1] [0][2] [0][3] [1][0] [1][1] [1][2] [1][3] [2][0] …
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬───
  │  1  │  2  │  3  │  4  │  5  │  6  │ 70  │  8  │  9  │ …
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴───
  номер    0     1     2     3     4     5     6     7     8

Элемент [i][j] массива с C столбцами — на месте i · C + j от начала. Отсюда два следствия. Первое: обход «по строкам» (внешний цикл по i) идёт по памяти подряд и работает быстрее, чем «по столбцам» — для больших матриц в разы, потому что процессор читает память блоками. Второе: выход за границу строки (table[0][4]) молча попадает в следующую строку (table[1][0]) — ошибка, которую трудно заметить.

Как и для одномерного, наибольшие размеры задаются константами, фактические — переменными. В параметре-матрице число столбцов должно быть указано: без него компилятор не сможет вычислить место i · C + j. Число строк можно опустить:

/* Ввод и вывод матрицы, суммы строк и столбцов */
#include <stdio.h>

enum { MAX_ROWS = 10, MAX_COLS = 10 };

/* Прочитать rows x cols элементов; 1 — успешно, 0 — ошибка ввода */
int read_matrix(int m[][MAX_COLS], int rows, int cols)
{
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (scanf("%d", &m[i][j]) != 1) {
                return 0;
            }
        }
    }
    return 1;
}

void print_matrix(int m[][MAX_COLS], int rows, int cols)
{
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%5d", m[i][j]);
        }
        printf("\n");
    }
}

int main(void)
{
    int m[MAX_ROWS][MAX_COLS];
    int rows = 0, cols = 0;
    if (scanf("%d %d", &rows, &cols) != 2 || rows < 1 || rows > MAX_ROWS
        || cols < 1 || cols > MAX_COLS || !read_matrix(m, rows, cols)) {
        printf("Error: rows, cols (1..10) and the matrix expected\n");
        return 1;
    }
    print_matrix(m, rows, cols);

    printf("row sums:");
    for (int i = 0; i < rows; i++) {
        int sum = 0;
        for (int j = 0; j < cols; j++) {
            sum += m[i][j];
        }
        printf(" %d", sum);
    }
    printf("\ncol sums:");
    for (int j = 0; j < cols; j++) {          /* внешний — по столбцам */
        int sum = 0;
        for (int i = 0; i < rows; i++) {
            sum += m[i][j];
        }
        printf(" %d", sum);
    }
    printf("\n");
    return 0;
}

2 3
1 2 3
4 5 6
    1    2    3
    4    5    6
row sums: 6 15
col sums: 5 7 9

Сумма строки — внутренний цикл по столбцам, сумма столбца — наоборот. Накопитель обнуляется перед внутренним циклом: если объявить его один раз до внешнего, суммы будут нарастающими.

У квадратной матрицы n × n части задаются условиями на индексы:

Для диагонали вложенный цикл не нужен: элементов n, это m[i][i] и m[i][n - 1 - i] — O(n). Перебирать все n² элементов с проверкой if (i == j) — верно, но в n раз дольше. Для треугольника внутренний цикл начинается не с нуля: выше главной — for (int j = i + 1; j < n; j++).

Транспонировать — сделать строки столбцами: элемент [i][j] переходит в [j][i]. Матрица rows × cols становится cols × rows. Для неквадратной результат записывают в другой массив. Квадратную можно транспонировать на месте, меняя элементы симметрично главной диагонали. Ошибка, которую делают почти все в первый раз:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {          /* ошибка: j от 0 */
        int t = m[i][j];
        m[i][j] = m[j][i];
        m[j][i] = t;
    }
}

Матрица остаётся прежней: каждая пара меняется дважды — при (i, j) и при (j, i). Правильно — только для элементов выше диагонали, j от i + 1: каждая пара обменивается один раз, n(n − 1) / 2 обменов.

  1 2 3          1 4 7
  4 5 6    →     2 5 8
  7 8 9          3 6 9

Произведение матрицы A (n × m) на B (m × p) — матрица C (n × p): элемент C[i][j] — сумма произведений строки i матрицы A на столбец j матрицы B. Число столбцов A должно равняться числу строк B.

void multiply(int a[][MAX_COLS], int b[][MAX_COLS], int c[][MAX_COLS],
              int n, int m, int p)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < p; j++) {
            int sum = 0;
            for (int k = 0; k < m; k++) {
                sum += a[i][k] * b[k][j];
            }
            c[i][j] = sum;
        }
    }
}

  ⎡1 2 3⎤   ⎡ 7  8⎤   ⎡ 1·7+2·9+3·11   1·8+2·10+3·12⎤   ⎡ 58  64⎤
  ⎣4 5 6⎦ · ⎢ 9 10⎥ = ⎣ 4·7+5·9+6·11   4·8+5·10+6·12⎦ = ⎣139 154⎦
            ⎣11 12⎦

Три вложенных цикла — n · m · p умножений; для квадратных n × n это O(n³): матрицы 1000 × 1000 — миллиард умножений. Матрицы-результата c не может совпадать с a или b: элементы, которые ещё нужны для вычисления, были бы затёрты.

Обмен строк — поэлементный обмен в цикле по столбцам. Так сортируют строки матрицы, например по сумме: те же сортировки раздела 8, только вместо обмена двух чисел — обмен двух строк.

void swap_rows(int m[][MAX_COLS], int cols, int r1, int r2)
{
    for (int j = 0; j < cols; j++) {
        int t = m[r1][j];
        m[r1][j] = m[r2][j];
        m[r2][j] = t;
    }
}

Соседи клетки — в играх на поле (крестики-нолики, «Жизнь», сапёр, лабиринт в разделе 28) нужно перебрать клетки вокруг [i][j], не выходя за края поля. Смещения удобно хранить в массивах:

const int DR[4] = {-1, 1, 0, 0};       /* вверх, вниз, влево, вправо */
const int DC[4] = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
    int r = i + DR[d], c = j + DC[d];
    if (r >= 0 && r < rows && c >= 0 && c < cols) {   /* сосед на поле */
        … m[r][c] …
    }
}

Проверка границ — до обращения к элементу, сокращённое вычисление гарантирует, что m[-1][c] не будет прочитан. Для восьми соседей (с диагоналями) — два вложенных цикла по смещениям −1…1, кроме (0, 0).