Методы программирования. Громов Ю.Ю - 30 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

30
В некоторых случаях, когда имеются две треугольные матрицы оди-
накового размера, их можно объединить в одну. Пусть треугольные мат-
рицы A [ j, k] и B [ j, k] определены для 0 ≤ k ≤ j ≤ n. Тогда их можно объе-
динить в матрицу C так, что элемент C[ j, k] будет определён для 0 ≤ j ≤ n,
0 ≤ k ≤ n + 1 и
A[ j, k] = C[ j, k], B[ j, k] = C[k, j + 1].
Таким образом, две треугольные матрицы плотно упаковываются
вместе, занимая (n + 1) (n + 2) ячеек:
≡
+
+
+
],[...]2,[]1,[]0,[
...............
]1,[...]1,1[]1,1[]0,1[
]0,[...]0,1[]0,0[]0,0[
]1,[...]2,[]1,[]0,[
...............
]1,1[...]2,1[]1,1[]0,1[
]1,0[...]2,0[]1,0[]0,0[
nnBnAnAnA
nBBAA
nBBBA
nnCnCnCnC
nCCCC
nCCCC
и может быть использована линейная адресация вида (26).
Рассмотрим связанное распределение памяти при хранении масси-
вов.
Связанное распределение памяти вполне естественно для многомер-
ных массивов информации. При этом в общем случае любой элемент
массива должен содержать k полей связи, по одному на каждый из спи-
сков, в которые входит данный элемент. Связанная память обычно ис-
пользуется в тех случаях, когда массивы по своей форме не являются
строго прямоугольными.
Использование связанного распределения рассмотрим подробно на
примере разреженных матриц – матриц, в которых большинство элемен-
тов равно нулю. Идея заключается в том, что для экономии памяти не
отводить в ней место под нулевые элементы.
Обсудим представление, которое состоит из циклически связанных
ортогональных списков для каждой строки и каждого столбца матрицы.
Пусть узлы списка имеют формат:
LEFT UP
ROW COL VAL
где ROW и COL – индексы соответственно строки и столбца; VAL – зна-
чение элемента матрицы; LEFT и UP – связи со следующими ненулевыми
элементами соответственно слева в строке и сверху в столбце. Для каж-
дой i-й строки и j-го столбца имеются специальные головные узлы спи-
сков BASEROW[i] и BASECOL[ j
] такие, что:
COL(LOC(BASEROW[i])) < 0 и ROW(LOC(BASECOL[ j
] )) < 0.

Страницы