РАЗМЕЩЕНИЯ. Один из основных способов хранения подобных разрежен-
ных матриц заключается в запоминании ненулевых элементов в одно-
мерном массиве и идентификации каждого элемента массива индексами
строки и столбца, как это показано на рис. 3.5 а).
Доступ к элементу массива A с индексами i и j выполняется
выборкой индекса i из вектора ROW, индекса j из вектора COLUM и
значения элемента из вектора A. Слева указан индекс k векторов
наибольшеее значение, которого определяется количеством нефоновых
элементов. Отметим, что элементы массива обязательно запоминаются
в порядке возрастания номеров строк.
Более эффективное представление, с точки зрения требований к
памяти и времени доступа к строкам матрицы, показано на рис.
3.5.б). Вектор ROW уменьшнен, количество его элементов соответс-
твует числу строк исходного массива A, содержащих нефоновые эле-
менты. Этот вектор получен из вектора ROW рис. 3.5.а) так, что
его i-й элемент является индексом k для первого нефонового эле-
мента i-ой строки.
Представление матрицы А, данное на рис. 3.5 сокращает требо-
вания к объему памяти более чем в 2 раза. Для больших матриц эко-
номия памяти очень важна. Способ последовательного распределения
имеет также то преимущество, что операции над матрицами могут
быть выполнены быстрее, чем это возможно при представлении в виде
последовательного двумерного массива, особенно если размер матри-
цы велик.
k ROW COLUMN A k COLUMN A
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
1 │ 1 │ │ 3 │ │ 6 │ 1 │ 3 │ │ 6 │
├───┤ ├───┤ ├───┤ ├───┤ ├───┤
2 │ 1 │ │ 5 │ │ 9 │ i ROW 2 │ 5 │ │ 9 │
├───┤ ├───┤ ├───┤ ┌───┐ ├───┤ ├───┤
3 │ 2 │ │ 1 │ │ 2 │ 1 │ 1 │ 3 │ 1 │ │ 2 │
├───┤ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤
4 │ 2 │ │ 4 │ │ 7 │ 2 │ 3 │ 4 │ 4 │ │ 7 │
├───┤ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤
5 │ 2 │ │ 5 │ │ 8 │ 3 │ 7 │ 5 │ 5 │ │ 8 │
├───┤ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤
6 │ 2 │ │ 7 │ │ 4 │ 4 │ 8 │ 6 │ 7 │ │ 4 │
├───┤ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤
7 │ 3 │ │ 1 │ │10 │ Номер 5 │ 9 │ 7 │ 1 │ │10 │
├───┤ ├───┤ ├───┤ строки └───┘ ├───┤ ├───┤
8 │ 4 │ │ 3 │ │12 │ 8 │ 3 │ │12 │
├───┤ ├───┤ ├───┤ ├───┤ ├───┤
9 │ 5 │ │ 4 │ │ 3 │ 9 │ 4 │ │ 3 │
├───┤ ├───┤ ├───┤ ├───┤ ├───┤
10 │ 5 │ │ 7 │ │ 5 │ 10 │ 7 │ │ 5 │
└───┘ └───┘ └───┘ └───┘ └───┘
а) б)
Рис. 3.5. Последовательное представление разреженных матриц.