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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

33
S4. [Поиск нового столбца.] P0 ← LEFT(P0), J ← COL(P0). Если J < 0,
то VAL(Q0) ← – ALPHA · VAL(Q0) и вернуться к S3. Если J = J0, то вы-
полнить этот шаг сначала.
S5. [Поиск элемента I, J.] Если COL(P1) > J, то P ← P1, P1 ← LEFT(P)
и повторить этот шаг сначала. Если COL(P1) = J, то перейти к S7; в про-
тивном случае перейти к следующему шагу.
S6. [Включение элемента I, J.] Если ROW(UP(PTR[J])) > I, то
PTR[J] ← UP(PTR[J]) и повторить этот шаг сначала; в противном случае
X ⇐ AVAIL, VAL(X) ← 0, ROW(X) ← I, COL(X) ← J, LEFT(X) ← P1,
UP(X) ← UP(PTR[J]), LEFT(P) ← X, UP(PTR[J]) ←X, P1 ← X, PTR[J] ← X.
S7. [Осевая операция.] VAL(P1) ← VAL(P1) – VAL(Q0) · VAL(P0). Ес-
ли VAL(P1) = 0, то перейти к следующему шагу; в противном случае
PTR[J] ← P1, P ← P1, P1 ← LEFT(P) и вернуться к S4.
S8. [Исключение элемента I, J.] Если UP(PTR[J]) ≠ P1, то PTR[J] ←
UP(PTR[J]) и повторить этот шаг сначала; в противном случае
UP(PTR[J]) ← UP(P1), LEFT(P) ← LEFT(P1), AVAIL ⇐ P1, P1 ← LEFT(P).
Вернуться к шагу S4. ■
Заметим, что в узлах BASEROW[I] и BASECOL[J] используются
только два поля. Поэтому для остальных полей можно не отводить место
в памяти.
Время работы алгоритма S приблизительно пропорционально коли-
честву элементов матрицы, которые изменяются при выполнении осевой
операции.
Упражнения
1. Выполнить по алгоритму S осевой шаг в разреженной матрице с
ненулевыми элементами m[1][1] = 50, m[2][3] = 20, m[2][1] = 10, m[4][4] = 5,
m[4][3] = −60, m[4][1] = −30, если осевым элементом является m[2][1] = 10.
Привести последовательность выполненных шагов алгоритма и конеч-
ную матрицу в виде, аналогичном виду исходной матрицы (по строкам с
убыванием второго индекса в строке).
5. ДЕРЕВЬЯ И ПРЕДСТАВЛЕНИЕ ДЕРЕВЬЕВ
Деревья являются наиболее важными нелинейными структурами.
Под деревом понимают конечное множество T, состоящее из одного или
более узлов таких, что:
a) имеется один специально обозначенный узел, называемый кор-
нем данного дерева;
b) остальные узлы (исключая корень) содержатся в m ≥ 0 попарно
не пересекающихся подмножествах T
1
, T
2
, …, T
m
, каждое из которых в

Страницы