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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

25
e) Включение циклического списка L
2
в циклический список L
1
: Ес-
ли PTR
2
≠ Λ и PTR
1
≠ Λ, то P ← LINK(PTR
1
), LINK(PTR
1
) ← LINK(PTR
2
),
LINK(PTR
2
) ← P, PTR
1
← PTR
2
, PTR
2
← Λ.
Расщепление одного циклического списка на два представляет ещё
одну простую операцию.
Таким образом, циклические списки можно использовать не только
для циклических, но и для линейных структур. Тогда возникает вопрос о
конце циклического списка. Ответом на него может быть включение в
каждый циклический список специального, отличимого от всех, узла,
называемого головой списка.
Одним из преимуществ циклического списка с головным узлом яв-
ляется то, что он никогда не будет пустым. При ссылке на списки такого
типа вместо указателя на правый конец списка используется обычно го-
лова списка, которая часто находится в фиксированной ячейке памяти.
В качестве примера использования циклических списков рассмот-
рим арифметическую операцию сложения многочленов. Предположим,
что многочлен представлен в виде списка, в котором каждый узел, кроме
специального, обозначает ненулевой член и имеет следующий вид:
COEF A B C LINK
Здесь COEF является коэффициентом при члене x
A
y
B
z
C
. У специаль-
ного узла COEF = 0 и A = – 1. Для полей A, B и C узла списка далее будет
использоваться обобщённое обозначение ABC. Узлы списка всегда
располагаются в порядке убывания поля ABC, за исключением специаль-
ного узла, после которого находится узел с наибольшим значением ABC.
Например, многочлен x
6
– 6xy
5
+ 5y
6
будет представлен следующим
образом:
Алгоритм A. (Сложение многочленов.) Этот алгоритм прибавляет
многочлен, на который указывает P, к многочлену, на который указы-
вает Q. При этом список по указателю P не изменяется, а в списке по ука-
зателю Q будет получена сумма двух многочленов. В конце алгоритма
переменные P и Q принимают свои исходные значения. В алгоритме ис-
пользуются также вспомогательные указатели Q
1
и Q
2
.
1
6
0
0
-6
1
5
0
5
0
6
0
0
-1
0
0
PTR

Страницы