Cтраница 2
В иерархическом списке, схематически изображенном на рис. 3.11, двунаправленный список самого верхнего уровня состоит из четырех элементов, причем первый и третий элементы являются обычными записями. Второй элемент этого списка представляет собой однонаправленный список, в котором третий элемент - это двунаправленный кольцевой список, состоящий из обычной записи, однонаправленного кольцевого списка и еще одной обычной записи. Четвертый элемент списка самого верхнего уровня является двунаправленным кольцевым списком из двух записей. Таким образом, иерархически связанные между собой списки могут быть разных типов. [16]
В иерархическом списке, схематически изображенном на рис. 3.11, двунаправленный список самого верхнего уровня состоит из четырех элементов, причем первый и третий элементы являются обычными записями. Второй элемент этого списка представляет собой однонаправленный список, в котором третий элемент - это двунаправленный кольцевой список, состоящий из обычной записи, однонаправленного кольцевого списка и еще одной обычной записи. Четвертый элемент списка самого верхнего уровня является двунаправленным кольцевым списком из двух записей. Таким образом, иерархически связанные между собой списки могут быть разных типов. [17]
Кольцевые списки наиболее полно удовлетворяют требованиям, предъявляемым к структурам данных. Имеется возможность входа в любую точку списка, и по адресным ссылкам вперед и назад можно найти любой другой интересующий нас элемент. Редактирование кольцевого списка сводится к дозаписи на свободное место памяти нового элемента списка и изменению адресных ссылок у первого, последнего и добавляемого элементов. Удаление ненужного элемента списка может быть сведено к записи соответствующего признака в удаляемый элемент либо к замене адресных ссылок у предыдущего и последующего элементов списка. [18]
Однако в структуре данных самостоятельность двух соединенных элементов должна быть сохранена, поскольку во время обработки может возникнуть необходимость их разделения. На рис. 2.6 г приведено возможное представление изображения в виде кольцевого списка. Для построения списка используются два указателя: правый, указывающий на соседний элемент, и левый, устанавливающий отношение иерархии. Неиспользованный правый указатель узла Р может пригодиться, например, для того, чтобы указать, какой отрезок включен в оба элемента. [19]