Гнездовое хранение структуры

1.8.2.Гнездовое хранение структуры.

При этом способе хранения структуры каждая вершина задается гнездом следующего вида:

где:

О_i - номер объекта;

А1 - первый адрес перехода к следующей вершине;

А2 - второй адрес перехода к следующей вершине.

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

Тогда хранение структуры с помощью гнезд можно выразить следующим способом.

Каждое гнездо состоит из 3^х слов. Общий объем занимаемой памяти составит

Матрица смежности с битовым заданием строк и хранение гнездами занимают одинаковый объем памяти, однако гнездовой способ не имеет ограничения n <16 или n <32 и, в тоже время, является более гибким. Например, для удаления перехода Р₅ нужно уничтожить связь Р₄ Р₅. Для этого необходимо лишь в гнезде с адресом А₃ убрать адрес А₄ и поставить * (отсутствие адреса). В то время как в 1-ом способе для удаления лишнего перехода понадобиться проделать ряд операций над битовыми строками.

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