Обобщение треугольных матриц для больших измерений называется тетраэдральным массивом {tetrahedral array). Рассмотрение этой интересной темы продолжается в упр. 6-8.

Типичные приемы программирования при работе с последовательно адресуемыми массивами описаны в упр. 1.3.2-10 и в двух ответах к данному упражнению. Особенно интересными в этих программах являются фундаментальные методы эффективного обхода строк и столбцов, а также использование последовательных стеков.

Связанное распределение. Связанное распределение памяти прекрасно подходит и для представления многомерных массивов данных." Вообще, узлы могут содержать fc полей связи, по одному для каждого списка, которому принадлежит этот узел. Связанное распределение памяти обычно используется в случаях, когда массивы данных не строго прямоугольны.

В качестве примера рассмотрим список, в котором каждый узел представляет описание некоторого человека, с четырьмя полями связи для обозначения: пола SEX, возраста AGE, цвета глаз EYES и цвета волос HAIR. Например с помощью полей EYES связьшаются узлы с одним цветом глаз и т. д. (рис. 13). Тогда нетрудно представить эффективный алгоритм вставки в этот список узлов с описаниями новых людей. Операция удаления в такой структуре будет выполняться гораздо медленнее, но ее эффективность можно повысить, используя дважды связанные списки. В таком случае можно представить алгоритмы с разной степенью эффективности для вьшолнения, например, таких запросов: "Найти всех голубоглазых блондинок в возрасте от 21 до 23 лет" (см. упр. 9 и 10). Подобного рода задачи, в которых узлы одного списка могут принадлежать нескольким другим спискам, встречаются довольно часто. Действительно, описанная в предыдущем разделе модель работы лифта содержит узлы, которые находятся сразу в двух списках: QUEUE и WAIT.

Е ь. «««« mmox (Я S Q

PERSON[6] PERSON[5] PERSON[4] PERSON[3] PERSON[2] PERSON[1]

Женщина, 21 год, карие глаза, темные волосы Мужчина, 24 года, карие глаза, темные волосы Женщина, 22 года, зеленые глаза, светлые волосы Мужчина, 28 лет, светло-карие глаза, светлые волосы Женщина, 22 года, голубые глаза, рыжие волосы Женщина, 21 год, голубые глаза, светлые волосы

Рис. 13. Каждый узел находится в четырех различных списках.

В качестве примера использования связанного распределения памяти для прямоугольных списков рассмотрим разреженные матрицы {sparse matrices) (т. е. матрицы большого размера, в которых большинство элементов равно нулю). Назначение задачи - организовать работу с такими структурами, как с обычной матрицей.

но достичь при этом большой экономии времени и пространства в памяти за счет исключения из нее равных нулю элементов. Один способ организации произвольного доступа к элементам этой матрицы заключается в использовании методов хранения и извлечения данных, которые описаны в главе 6, т. е. поиск элемента A[j,fc] вьшолняется на основе ключа "[j, fc]". Существует, однако, еще один способ работы с разреженными матрицами, который часто более предпочтителен, поскольку он точнее соответствует структуре матрицы. Именно этот метод будет рассмотрен ниже.

Рассматриваемое здесь представление состоит из циклически связанных списков, т. е. циклически связанных строк и столбцов. Каждый узел матрицы имеет длину в три слова и содержит пять полей:

(11)

Здесь ROW и COL - индексы, обозначающие строку и столбец узла; VAL - значение, хранимое в элементе матрицы; LEFT и UP - связи со следующим ненулевым элементом слева в строке или сверху в столбце соответственно. Для каждой строки и каждого столбца заданы заголовки списков BASEROW[«] и BASECOL[j] соответственно. Эти узлы идентифицируются благодаря следующим условиям:

COL(LOC(BASEROW[г] )) < О и ROW(LOC(BASECOL[j])) < 0.

Как обычно, в циклическом списке ссылка LEFT в строке BASEROW [г] является адресом крайнего справа значения в этой строке, а ссылка UP в строке BASECOL [j] указывает на последнее значение в столбце. Например, матрица

/ 50 10 О

V-30

О О О О

О 20 О

(12)

при таких условиях будет иметь вид, приведенный на рис. 14.

При использовании метода последовательного распределения памяти для матрицы размера 200 х 200 потребуется 40 ООО слов, что гораздо больше размера оперативной памяти большинства компьютеров. Но для представления умеренно разреженной матрицы размера 200 х 200 с помощью описанного выше способа в оперативной памяти компьютера MIX потребуется только 4 ООО слов (см. упр. 11). При этом время доступа к произвольному элементу А Lj, fc] также будет вполне приемлемым, если в каждой строке и каждом столбце содержится немного ненулевых (или неодинаковых) элементов. Поскольку в большинстве алгоритмов обработки матриц используется последовательный доступ к элементам, а не произвольный, то при таком связанном представлении данных работа может выполняться гораздо быстрее, чем при последовательном представлении.

Типичным примером нетривиального алгоритма работы с разреженными матрицами такого типа является осевое преобразование {pivot step), которое является

-И I

2 3 20

4 I 1 I -30 .

ТТ 1 -60 I

4 I 4 I 5 .

Рис. 14. Представление матрицы (12) с узлами в виде ков находятся слева и сверху

LEFT

ROW COL VAL

Заголовки спис-

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

До преобразования

Любой Осевой другой столбец столбец

Осевая строка

Любая другая строка

ь d

После преобразования Любой

Осевой столбец

-с/а

другой столбец

Ь/а d - Ьс/а

(13)

Предполагается, что осевой элемент, а, не равен нулю. Например, применение осевого преобразования к матрице (12), где осевым элементом считается число 10 в строке 2 и столбце 1, приводит к такому результату:

/-Ь О -100 0\

0.1 О 2 0

0 0 0 0

V 3 О 0 5/