Однонаправленный список

Cтраница 1

Однонаправленный список представляется в виде цепочки, в которой справка каждого звена состоит из двух значений. Вторым значением является ссылка на начало следующего звена. [1]

Исключение записи из кольцевого списка. [2]

Как и в случае однонаправленного списка, для наглядности используем переменные нов и след. [3]

Таблица может быть организована как однонаправленный список, в котором объекты следуют один за другим в произвольном порядке. Операции над таблицами при такой организации трудоемкие. [4]

Операция исключения последнего элемента из однонаправленного списка всегда связана с просмотром всего списка. Иногда для избежания затрат времени на просмотр списка имеет смысл воспользоваться двунаправленным связанным списком. [5]

Описанные нами операции включения элемента в однонаправленный список и исключения его оттуда оказывают воздействие на преемника некоторого элемента списка. [6]

Чтобы эффективно присоединять элементы к концу однонаправленного списка, используйте при его организации указатель tail. [7]

Наиболее естественным и простым типом списка является однонаправленный список, предназначаемый для того, чтобы просматривать его в одном направлении, от начала к концу. [8]

Пример вырожденного дерева. [9]

В частности, может встретиться дерево, выродившееся в однонаправленный список. Такое дерево может возникнуть, например, если записи заносились в него строго в порядке возрастания ключей. Но при случайном чередовании ключей заносимых в таблицу записей вероятность подобных вырожденных деревьев очень мала. [10]

Линейный двунаправленный список ниже будет обозначаться как Л2 - список, а линейный однонаправленный список - как Л1 - список. [11]

В операции ( 5) изменяются значения пяти свя-аей, поэтому она несколько медленнее, чем операция включения в однонаправленный список, где необходимо изменить только три связи. [12]

Удобно иметь в конце каждого списка признак меньший при сравнении в некотором поле, по которому упорядочен список. Можно использовать и простой однонаправленный список, сохраняя, например, только связи LEFT в BASE ROW [ ] и UP в BASECOL [ / ] и модифицируя алгоритм таким образом. [13]

Чтобы внести новый элемент в однонаправленный список со ссылкой на следующий, необходимо знать адрес того элемента, после которого необходимо добавить новый. [14]

В иерархическом списке, схематически изображенном на рис. 3.11, двунаправленный список самого верхнего уровня состоит из четырех элементов, причем первый и третий элементы являются обычными записями. Второй элемент этого списка представляет собой однонаправленный список, в котором третий элемент - это двунаправленный кольцевой список, состоящий из обычной записи, однонаправленного кольцевого списка и еще одной обычной записи. Четвертый элемент списка самого верхнего уровня является двунаправленным кольцевым списком из двух записей. Таким образом, иерархически связанные между собой списки могут быть разных типов. [15]

Страницы: 1 2