4.3. Физическое представление сетевых структур

Так же, как и в случае древовидных структур, рассмотренных в пре­дыдущей главе, связи в сетевых структурах можно представить, ис­пользуя физически последовательное размещение, указатели, коль­ца. Рассмотрим простую сетевую структуру, представленную на рис. 4.13.

4.3.1. Физически последовательное размещение

Если древовидные структуры можно представить без избыточности с помощью физически последовательного размещения, то для сете­вых структур это обычно невозможно. Однако в некоторых случаях может оказаться удобным представить один набор связей типа «ис­ходный — порожденный» путем физически последовательного раз­мещения, а для остальных связей использовать другой метод. На­пример, можно использовать физически последовательное размеще­ние для представления связей А и С (рис. 4.14).

Рис. 4.13. Пример простой сетевой структуры

Рис. 4.14. Пример реализации сетевой структуры с последовательным размещением

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

Для множественных указателей на порожденные записи требуются списки указателей переменной длины; для указателей на порожден­ные и подобные записи необходимы длинные цепочки.

Обычно для представления сетевых структур физически после­довательное размещение не применяется.

4.3.2. Использование указателей

Если для реализации сетевых структур используются указатели, то они должны представлять все связи, причем какие-то записи долж­ны называться исходными (например, верхние), а какие-то — поро­жденными (нижние записи).

На практике могут использоваться много различных вариантов конфигураций указателей. На рис. 4.15 показаны кольцевые струк­туры, в которых имеются указатели на исходные, порожденные и подобные записи.

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

Рис. 4.15. Пример реализации сетевой структуры с использованием указателей

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

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