Методы последовательного размещения для представления разреженных
матриц обычно позволяют быстрее выполнять операции над матрицами
и более эффективно использовать память, чем методы со связанными
структурами. Однако последовательное представление матриц имеет
определенные недостатки. Так включение и исключение новых элемен-
тов матрицы вызывает необходимость перемещения большого числа
других элементов. Если включение новых элементов и их исключение
осуществляется часто, то должен быть выбран описываемый ниже ме-
тод связанных структур.
Метод связанных структур, однако, переводит представляемую
структуру данных в другой раздел классификации. При том, что ло-
гическая структура данных остается статической, физическая струк-
тура становится динамической.
┌───────┬───────┐ Для представления разреженных мат-
│ LEFT │ UP │ риц требуется базовая структура вершины
├────┬──┴──┬────┤ (рис.3.6), называемая MATRIX_ELEMENT
│ V │ R │ C │ ("элемент матрицы"). Поля V, R и С каж-
└────┴─────┴────┘ дой из этих вершин содержат соответс-
Рис.3.6. Формат вер- твенно значение, индексы строки и
шины для представле- столбца элемента матрицы. Поля LEFT и
ния разреженых матриц UP являются указателями на следующий
элемент для строки и столбца в циклическом списке, содержащем
элементы матрицы. Поле LEFT указывает на вершину со следующим на-
именьшим номером строки.
На рис. 3.7 приведена многосвязная структура, в которой ис-
пользуются вершины такого типа для представления матрицы А, опи-
санной ранее в данном пункте. Циклический список представляет все
строки и столбцы. Список столбца может содержать общие вершины с
одним списком строки или более. Для того, чтобы обеспечить ис-
пользование более эффективных алгоритмов включения и исключения
элементов, все списки строк и столбцов имеют головные вершины.
Головная вершина каждого списка строки содержит нуль в поле С;
аналогично каждая головная вершина в списке столбца имеет нуль в
┌───┬──┐ ┌──┬──┐ ┌──┬──┐ ┌──┬──┐ ┌──┬──┐ ┌──┬──┐ ┌──┬──┐
│ │ ─┼┐│ │ ┼┐│ │ ─┼┐│ │ ┼┐│ │ ┼┐│ │ ┼┐│ │ ┼┐
├──┬┴┬─┤│├─┬┴┬─┤│├─┬┴┬─┤│├─┬┴┬─┤│├─┬┴┬─┤│├─┬┴┬─┤│├─┬┴┬─┤│
│ │0│ │││ │0│ │││ │0│ │││ │0│ │││ │0│ │││ │0│ │││ │0│ ││
└──┴─┴┬┘│└─┴─┴┬┘│└─┴─┴┬┘│└─┴─┴┬┘│└─┴─┴┬┘│└─┴─┴┬┘│└─┴─┴┬┘│
┌───────────┼─┼─────┼─┼─────┼─┼─────┼─┼─────┼─┼─┐ │ │ │ │
┌┼─┬──┐ │ │ └─┘┌──┬─┼┐│ │ │┌──┬─┼┐│ │ └─┘ │ │
│ │ ├──────┼─┼────────┼─ │ ├┼─────┼─┼┼─ │ ├┼─┘ │ │
├─┬┴┬─┤ │ │ ├─┬┴┬─┤│ │ │├─┬┴┬─┤│ │ │
│ │ │0│ │ │ │6│1│5││ │ ││9│1│5││ │ │
└─┴─┴─┘ │ │ └─┴─┴┬┘│ │ │└─┴─┴┬┘│ │ │
┌───────────┼─┼─────────────┼─┼─────┼─┼─────┼─┼─────────────┼─┼┐
┌┼─┬──┐┌───┬─┼┐│ │ │┌──┬─┼┐│┌──┬─┼┐│ ┌──┬─┼┐││
│ │ ├┼─ │ ├┼─────────────┼─┼┼─ │ ├┼┼─ │ ├┼────────┼─ │ ├┼┘
├─┬┴┬─┤├──┬┴┬─┤│ │ │├─┬┴┬─┤│├─┬┴┬─┤│ ├─┬┴┬─┤│
│ │ │0││2 │2│1││ │ ││4│2│4│││8│2│5││ │4│2│7││
└─┴─┴─┘└──┴─┴┬┘│ │ │└─┴─┴┬┘│└─┴─┴┬┘│ └─┴─┴┬┘│
┌───────────┼─┼─┐ │ │ │ │ └─┘ │ │
┌┼─┬──┐┌───┬─┼┐│ │ │ │ │ │ │ │
│ │ ├┼─ │ ├┼─┘ │ │ │ │ │ │
├─┬┴┬─┤├──┬┴┬─┤│ │ │ │ │ │ │
│ │ │0││10│3│1││ │ │ │ │ │ │
└─┴─┴─┘└──┴─┴┬┘│ │ │ │ │ │ │
┌───────────┼─┼─────────────┼─┼─┐ │ │ │ │
┌┼─┬──┐ └─┘ ┌───┬─┼┐│ │ │ │ │ │
│ │ ├────────────────┼─ │ ├┼─┘ │ │ │ │
├─┬┴┬─┤ ├──┬┴┬─┤│ │ │ │ │
│ │ │0│ │12│4│3││ │ │ │ │
└─┴─┴─┘ └──┴─┴┬┘│ │ │ │ │
└─┘ │ │ │ │
┌───────────────────────────────────┼─┼─────────────────────┼─┼┐
┌┼─┬──┐ ┌──┬─┼┐│ ┌──┬─┼┐││
│ │ ├─────────────────────────┼─ │ ├┼────────────────┼─ │ ├┼┘
├─┬┴┬─┤ ├─┬┴┬─┤│ ├─┬┴┬─┤│
│ │ │0│ │3│5│4││ │5│5│7││
└─┴─┴─┘ └─┴─┴┬┘│ └─┴─┴┬┘│
└─┘ └─┘
Рис. 3.7. Многосвязная структура для представления матрицы A
поле R. Строка или столбец, содержащие только нулевые элементы,
представлены головными вершинами, у которых поле LEFT или UP ука-
зывает само на себя.
Может показаться странным, что указатели в этой многосвязной
структуре направлены вверх и влево, вследствие чего при сканиро-
вании циклического списка элементы матрицы встречаются в порядке
убывания номеров строк и столбцов. Такой метод представления ис-
пользуется для упрощения включения новых вершин в структуру.
Предполагается, что новые вершины, которые должны быть добавлены
к матрице, обычно располагаются в порядке убывания индексов строк
и индексов столбцов. Если это так, то новая вершина всегда добав-
ляется после головной и не требуется никакого просмотра списка.