Динамические структуры данных. Алексеев А.Ю - 17 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

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

Рубрика: 

В качестве пустой ссылки используется значение NilLst = 0. При этом при-
мер размещения списка в массиве, приведенный на рис.1.10, принимает вид
рис. 1.16. Список свободной памяти здесь также организован как Л2–список,
что позволяет эффективно реализовать операции Empty и Destroy (см. послед-
ний абзац 1.4).
Рис. 1.16. Представление ограниченного Л2-списка при ссылочной реализации
на базе вектора: а – размещение списка s в массиве Memory; б,в – формуляры
списка s в состояниях BOList и EOList соответственно; г – формуляр пустого списка l
Вычисление ссылки на элемент списка s, следующий за текущим, произво-
дится как Memory [ s. Cur ]. Diff + s. PredCur (не следует вычислять в состоянии
EOList ). Ссылка на элемент списка s, предшествующий тому, на который указы-
вает s.PredCur, вычисляется как s. Cur – Memory[ s. PredCur ].Diff (не следует
вычислять в состоянии BOList ). Дополнительное поле Last в фор- муляре списка
предназначено для хранения ссылки на последний элемент списка.
Модуль Global здесь имеет тот же вид, что и на рис. 1.13.
1.6. Рекурсивная обработка линейных списков
Рассмотренный ранее подход к организации линейных списков ориентиро-
ван на итеративную их обработку, при которой на каждом шаге выделяется
8 -9 5 3 3 9 -4 -11 9 2 3 2 9
0 2 3 1 4 5 6 7 8 9 10 11
12 ] Memory [
.
I
n
f
o :
.Next :
s
.Head = 2
a
b
d
c
a
H
ead :
Cur :
L
ast :
P
redCu
r
:
l
.
H
ead :
Cur :
L
ast :
P
redCu
r
:
S
.
H
ead :
Cur :
L
ast :
P
redCu
r
:
S
.
0
0
0
00
0
7
77
2
2 2
г ва
17
   В качестве пустой ссылки используется значение NilLst = 0. При этом при-
мер размещения списка в массиве, приведенный на рис.1.10, принимает вид
рис. 1.16. Список свободной памяти здесь также организован как Л2–список,
что позволяет эффективно реализовать операции Empty и Destroy (см. послед-
ний абзац 1.4).




Memory [            0        1           2       3        4         5                6         7       8        9       10           11           12 ]

 .Info :                             a                         b                          d                                      c
 .Next :        8       -9           5       3        3        9            -4           -11       9        2       3            2            9

s.Head = 2


                                                                        a



                Head             :       2                    Head               :       2                      Head         :            0

                Last         :           7                    Last           :           7                      Last         :            0
           S.                                        S.                                                l.
                Cur          :           2                    Cur            :           0                      Cur          :            0

                PredCur :                0                    PredCur :                  7                      PredCur :                 0

                         а                                           в                                                  г

      Рис. 1.16. Представление ограниченного Л2-списка при ссылочной реализации
      на базе вектора: а – размещение списка s в массиве Memory; б,в – формуляры
  списка s в состояниях BOList и EOList соответственно; г – формуляр пустого списка l

   Вычисление ссылки на элемент списка s, следующий за текущим, произво-
дится как Memory [ s. Cur ]. Diff + s. PredCur (не следует вычислять в состоянии
EOList ). Ссылка на элемент списка s, предшествующий тому, на который указы-
вает s.PredCur, вычисляется как s. Cur – Memory[ s. PredCur ].Diff (не следует
вычислять в состоянии BOList ). Дополнительное поле Last в фор- муляре списка
предназначено для хранения ссылки на последний элемент списка.
   Модуль Global здесь имеет тот же вид, что и на рис. 1.13.


                        1.6. Рекурсивная обработка линейных списков

   Рассмотренный ранее подход к организации линейных списков ориентиро-
ван на итеративную их обработку, при которой на каждом шаге выделяется

                                                                   17

Страницы