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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

29
LOC (A[3, 1]) = LOC (A[0, 0]) + 8 · 3 + 2 · 1 =
= LOC (A[0, 0]) + 26 = 0 + 26 = 26.
Приведённый выше метод хорош для хранения массивов, имеющих
полную прямоугольную структуру. Однако во многих случаях приходится
иметь дело с треугольной матрицей элементов A [ j, k] для 0 ≤ k ≤ j ≤ n:
],[...]1,[]0,[
......
]1,1[]0,1[
]0,0[
nnAnAnA
AA
A
.
Такую матрицу можно использовать, когда известно, что все другие
элементы матрицы равны нулю или A [ j, k] = A [k, j]. Поэтому необходи-
мо и достаточно хранить в памяти немного больше половины значений:
)2)(1(
2
1
++ nn
. Если хранить эти элементы в последовательных ячейках
памяти, то вместо линейного распределения (26) можно использовать
распределение в форме:
LOC (A[ j, k]) = A
0
+ c f
1
( j) + c f
2
(k),
где f
1
( j
) =
2
)1( +jj
, f
2
(k) = k. Следовательно, получаем довольно простую
формулу:
LOC (A[j, k]) = LOC (A [0, 0]) + c
2
)1( +jj
+ c k.
Например, для треугольной матрицы вида
]3,3[]2,3[]1,3[]0,3[
]2,2[]1,2[]0,2[
]1,1[]0,1[
]0,0[
AAAA
AAA
AA
A
при c = 2 получаем такое распределение памяти:
0 1 2 3 4 5 6 7 8 9 10
11
12
13
14
15
16
17
18
19
A[0, 0]
A[1, 0]
A[1, 1]
A[2, 0]
A[2, 1]
A[2, 2]
A[3, 0]
A[3, 1]
A[3, 2]
A[3, 3]
и адрес элемента A[3, 2]:
LOC (A[3, 2]) = LOC (A[0, 0]) + 2
2
)13(3 +
+ 2 · 2 = 0 + 12 + 4 = 16.

Страницы