ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
25
Для доступа к произвольному элементу по его индексу
k
в струк-
туре IgushArray необходимо:
1)
рассчитать индекс в массиве с помощью простой арифметиче-
ской операции
/
_ ,
i
k deq size
= ⎢
⎥
⎣
⎦
сложность
О
(1);
2)
получить указатель на очередь
i
D
в массиве
V
,
сложность
O
(1);
3)
вычислить индекс в очереди при помощи простой арифметиче-
ской операции
% _
j k deq size
=
,
О(1);
4)
получить элемент
,
i j
E
в очереди
i
D
,
сложность
O
(1).
Псевдокод операции доступа:
/
_ ;
i
k deq size
= ⎢
⎥
⎣
⎦
[ ]
i
D V i
=
;
j
=
% _ ;
k deq size
=
,
[ ]
i j
i
E D j
=
;
,
.
k
i j
E E
=
Произвольный доступ к элементу по индексу (рис. 4) состоит из
двух простых арифметических операций и двух операций доступа к па-
мяти, а значит операция в целом имеет сложность
О
(1)
+
О
(1)
+
О
(1)
+
+
О
(1)
=
О
(1).
Рис. 4. Операция доступа в IgushArray
Для вставки элемента в позицию
k
в структуре IgushArray, необ-
ходимо:
1)
получить доступ к элементу
,
i j
E
,
на место которого требуется
вставка, сложность
О
(1) ;
2)
вставить новый элемент в очередь
i
D
в полученную позицию
j
,
сложность
( )
D
O S
;
3) «
сдвинуть» элементы в этой и следующих очередях вниз, для
чего следует: