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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

27
С таким представлением линейного списка легко выполняются опе-
рации для дека общего вида. Ещё легче оперировать с двусвязным спи-
ском, если его частью является головной узел:
Если такой список пуст, то оба поля связи в его голове указывают на
саму голову. Представление (25) полностью удовлетворяет условию
RLINK(LLINK(X)) = LLINK(RLINK(X)) = X,
где X – адрес любого узла в списке, включая голову. В этом и заключает-
ся главная причина предпочтения (25) по сравнению с (24).
Упражнения
1. Выполнить по алгоритму Т топологическую сортировку элемен-
тов 1, 2, 3, ..., 9 для заданных отношений между ними: 9 < 2, 3 < 7, 7 < 5,
5 < 8, 8 < 6, 4 < 6, 1 < 3, 7 < 4, 9 < 5, 2 < 8.
2. Используя графическую иллюстрацию модели памяти вычисли-
тельной машины, проследить за ходом выполнения алгоритма А, реали-
зующего прибавление многочлена xy + xz – x к многочлену – xz + 2x – 2y.
Определить последовательность выполнения шагов алгоритма и итого-
вый многочлен.
4. МАССИВЫ И ОРТОГОНАЛЬНЫЕ СПИСКИ
Массивы (двумерные и более высокой размерности) являются одним
из простейших обобщений линейных списков. Рассмотрим в качестве
примера матрицу:
],[...]1,[]0,[
............
],1[...]1,1[]0,1[
],0[...]1,0[]0,0[
nmAmAmA
nAAA
nAAA
.
В таком двумерном массиве некоторый узел A [j, k] принадлежит
двум линейным спискам: списку j-й строки A [j, 0], A [j, 1], …, A [j, n] и
списку k-го столбца A [0, k], A [1, k], …, A [m, k]. Эти списки ортогональ-
ных строк и столбцов, по существу, и определяют двумерную структуру
матрицы.
RIGHT
LEFT
(25)
(24)

Страницы