ВУЗ:
Составители:
28
Рассмотрим последовательное распределение памяти при хранении
массивов.
Если массив хранится в последовательных ячейках памяти, то па-
мять обычно распределяется так, что:
LOC (A [ j, k]) = A
0
+ A
1
j + A
2
k, (26)
где A
0
, A
1
и A
2
– константы. Это означает, что при любом изменении j или
k легко вычислить адрес узла A [ j, k].
Самым естественным и наиболее часто используемым способом
распределения памяти является способ, при котором массив располагает-
ся в памяти в лексикографическом порядке индексов: A [0, 0], A [0, 1], …,
A [0, n], A [1, 0], A [1, 1], …, A [1, n], …, A [m, 0], A [m, 1], …, A [m, n].
В общем случае, если задан k-мерный массив с элементами A [I
1
,
I
2
, …, I
k
] длины с и 0 ≤ I
1
≤ d
1
, 0 ≤ I
2
≤ d
2
, …, 0 ≤ I
k
≤ d
k
, то можно хранить
его в памяти так, что:
LOC (A [I
1
, I
2
, …, I
k
]) = LOC (A [0, 0, …, 0]) +
+ c (d
2
+ 1) … (d
k
+ 1) I
1
+ … + c (d
k
+ 1) I
k – 1
+ c I
k
=
= LOC (A [0, 0, …, 0]) +
∑
≤≤ kr
rr
Ia
1
, (27)
где a
r
= c
∏
≤<
+
ksr
s
d )1(
.
Например, двумерный массив для d
1
= 3, d
2
= 3 и c = 2 байта будет
размещён в памяти следующим образом:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
А[0,0] А[0,1] А[0,2] А[0,3] А[1,0] А[1,1] А[1,2] А[1,3]
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
А[2,0] А[2,1] А[2,2] А[2,3] А[3,0] А[3,1] А[3,2] А[3,3]
В соответствии с формулой (27) адрес его некоторого элемента
A [I
1
, I
2
] можно определить по выражению:
LOC (A[I
1
, I
2
]) = LOC (A[0, 0]) + c (d
2
+ 1) I
1
+ c I
2
=
= LOC (A[0, 0]) + 2 (3 + 1) I
1
+ 2 I
2
=
= LOC (A[0, 0]) + 8 I
1
+ 2 I
2
.
Пусть I
1
= 3 и I
2
= 1, тогда:
Страницы
- « первая
- ‹ предыдущая
- …
- 26
- 27
- 28
- 29
- 30
- …
- следующая ›
- последняя »
