Структуры данных и модели вычислений



             

Списки с последовательным доступом - часть 2


Для доступа к полям узла

используем форму ,

и т.д. Оператор для создания нового узла будем записывать в виде

Для обеспечения сканирования как от начала к концу, так и от конца к началу используют узлы следующего вида:

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

На рис. 2.1—2.6 представлено несколько разновидностей списков. Узлы списков изображены прямоугольниками, разделенными на части по числу полей. Стрелки проведены в соответствии со значениями полей и .


Рис. 2.1.  Односторонний список: вход через первый элемент, сканирование от начала к концу, признак конца — Next(pos) = nil


Рис. 2.2.  Односторонний список: вход через первый элемент; сканирование от начала к концу, признак конца — Next(pos) = pos


Рис. 2.3.  Односторонний циклический список: вход через первый элемент; сканирование от начала к концу, признак конца — Next(pos) = first


Рис. 2.4.  Односторонний циклический список: вход через последний элемент с помощью ссылки Last^.next; сканирование от начала к концу, признак конца — pos = last


Рис. 2.5.  Двусторонний список: вход через первый элемент, сканирование от начала к концу и от конца к началу; признак начала — Procede(pos) = nil; признак конца — Next(pos) = nil


Рис. 2.6.  Двусторонний циклический список: вход через первый элемент; сканирование от начала к концу и от конца к началу, признак конца — Next(pos) = first




Содержание  Назад  Вперед