Составители:
Глава 4
ПРЕДСТАВЛЕНИЕ МАТРИЦ И МНОГОМЕРНЫХ МАССИВОВ
НА ЯЗЫКАХ ВЫСОКОГО УРОВНЯ
§ 1. Представление матриц и многомерных массивов на языках C, C++.
Специального типа данных матрица или многомерный массив в Си (Си++) нет, однако, можно использовать
массив элементов типа массив. Например, переменная a представляет матрицу размера 3×3 с вещественными
элементами:
double a[3][3];
Элементы матрицы располагаются в памяти последовательно по строкам: сначала идут элементы строки с
индексом 0, затем строки с индексом 1, в конце строки с индексом 2 (в программировании отсчет индексов
всегда начинается с нуля, а не с единицы!). При этом выражение
a[i],
где i -- целая переменная, представляет собой указатель на начальный элемент i-й строки и имеет тип double*.
Для обращения к элементу матрицы надо записать его индексы в квадратных скобках, например, выражение
a[i][j],
представляет собой элемент матрицы a в строке с индексом i и столбце с индексом j. Элемент матрицы можно
использовать в любом выражении как обычную переменную (например, можно читать его значение или
присваивать новое).
Такая реализация матрицы удобна и максимально эффективна с точки зрения времени доступа к элементам. У
нее только один существенный недостаток: так
можно реализовать только матрицу, размер которой известен
заранее. Язык Си не позволяет описывать массивы переменного размера, размер массива должен быть задан
до начала стадии компиляции.
Пусть нужна матрица, размер которой определяется во время работы программы. Тогда пространство под нее
надо захватывать в динамической памяти с помощью функции malloc языка Си или
оператора new языка C++.
При этом в динамической памяти захватывается линейный массив и возвращается указатель на него.
Рассмотрим вещественную матрицу размером n строк m на столбцов. Захват памяти выполняется с помощью
функции malloc языка
Си
double *a;
. . .
a = (double *) malloc(n * m * sizeof(double));
или с помощью оператора new языка C++:
double *a;
int m, n;
. . .
a = new double[n * m];
При этом считается, что элементы матрицы будут располагаться в массиве следующим образом: сначала идут
элементы строки с индексом 0, затем элементы строки с индексом 1 и т.д., последними идут элементы строки
с индексом m − 1. Каждая строка состоит из n элементов, следовательно, индекс элемента строки i и столбца j
в линейном массиве равен
i * n + j
(действительно, поскольку индексы начинаются с нуля, то i равно количеству строк, которые нужно
пропустить, i * n - суммарное количество элементов в пропускаемых строках; число j равно смещению внутри
последней строки). Таким образом, элементу матрицы в строке i и столбце j соответствует выражение
*(a + i * n + j)
Этот способ представления матрицы удобен и эффективен. Его основное преимущество состоит в том, что
элементы матрицы хранятся в непрерывном отрезке памяти. Во-первых, это позволяет оптимизирующему
компилятору преобразовывать текст программы, добиваясь максимального быстродействия; во-вторых, при
выполнении программы максимально используется механизм кеш-памяти, сводящий к минимуму обращения
к памяти и значительно
ускоряющий работу программы.
Страницы
- « первая
- ‹ предыдущая
- …
- 43
- 44
- 45
- 46
- 47
- …
- следующая ›
- последняя »
