Левосписковые структуры с переполнениями
Включение и удаление элементов могут быть выполнены с помощью метода переполнения или метода распределенной свободной памяти, рассмотренных ранее на примере метода ведения файлов с индексно-последовательной организацией данных.
На рис. 4.9 и 4.10 представлен пример реализации иерархической структуры до и после обновления путем использования области переполнения.
В этом случае для определения местонахождения записей А, В или С можно использовать индексы.
Использование указателей на «подобные» и «порожденные»
Для обеспечения эффективных процедур выборки записей могут использоваться межзаписные ссылки следующих типов:
•указатели на порожденные записи;
•указатели на подобные записи;
•указатели на исходные записи.
При построении древовидных структур, в которых используется какой-либо один тип указателя, всегда исходят из альтернативы между сложностью реализации списка указателей переменной длины на порожденные записи и увеличением времени поиска, связанным с использованием цепочки указателей на подобные записи.
Практически эффективные компромиссы могут быть достигнуты путем использования в каждой записи двух указателей каких-либо двух типов (рис. 4.11), а также использованием кольцевых структур (например, рис. 4.12).
На рис. 4.12 ссылки образуют кольца двух типов: подобных записей и кольца «исходный — порожденный». В записях самого нижнего уровня показаны указатели на исходные записи. Для единообразия здесь каждая запись имеет два указателя. Однако кольца большей частью создаются двусторонними. В этом случае число указателей в каждой записи увеличится до четырех.
Дата добавления: 2015-04-15; просмотров: 796;