Нульсвязные списки

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

В нульсвязных списках нет заглавных звеньев. У них есть только начало и конец. Началом (или начальным звеном) называется звено, которое можно взять из списка, концом – звено, после которого можно добавить в список новый элемент (новое звено).

В языке Паскаль нет средств, позволяющих описывать переменные типа нульсвязных списков. Их приходится моделировать односвязными списками с запретом перемещения по указателям звеньев. Работа с нульсвязными списками выполняется, только используя специальные процедуры и функции. Обычно достаточно использовать функцию проверки не пуст ли список и две процедуры: добавления элемента к списку и выбора элемента из списка (с удалением выбираемого звена).

Рассмотрим варианты нульсвязных списков.

Стек – это нульсвязный список, иногда называемый очередью, с правилом обслуживания LIFO (Last In – First Out – последним пришел – первым ушел). У стека начало и конец – это одно и то же звено, обычно называемое вершиной стека.

Создание пустого стека – это, по сути, создание указателя на вершину стека (N), и присвоение ему значения nil. Этот указатель в дальнейшем играет роль адреса начала и конца стека текущего звена.

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

Процедура выбора из стека последнего введенного звена выполняется наоборот: в переменную для выбираемых данных переносятся значения поля Dt, новое значение указателя на вершину стека берется из поля ссылки на следующее звено, а старая вершина стека удаляется процедурой Dispose. В обоих процедурах используется рабочий указатель на звено стека. Описатели типов для стека полностью совпадают с описателями односвязного списка.

Очередь – нульсвязный список с правилом обслуживания FIFO (First In – First Out – первым пришел – первым ушел).

Для работы с очередью необходимы такие же процедуры, как и для стека. При создании пустой очереди указателям N и K присваивается значение nil. Процедурам добавления в очередь и выбора из очереди приходится передавать указатели на оба конца, так как при создании первого звена, его адрес необходимо занести в оба указателя, а при удалении последнего звена очереди, обоим указателям надо присвоить значение nil.

Дек – это нульсвязный список, в котором добавление и выбор элементов возможен с любого конца. Его можно рассматривать как двусторонний стек или двустороннюю очередь. Название (deque) расшифровывается как double-ended queue – очередь с двумя концами.

Проще всего дек моделировать двусвязным линейным списком, по которому запрещено перемещаться. Формально для него приходится составлять две процедуры добавления и две процедуры удаления элементов, находящихся на первом и втором концах дека. На практике процедуры добавления можно объединить в одну, используя дополнительный признак – к какому концу добавляется элемент. Хотя оба конца дека равноправны, для определенности одну сторону будем называть началом, обозначая указателем NK, а вторую –концом, с обозначением KN.

Обе процедуры удаления элемента также можно объединить в одну. В процедуру добавления (удаления) элемента таким образом придется передавать указатели на оба конца списка, данные (или адрес, куда их поместить при удалении) и признак, в начало ли идет добавление. В зависимости от того, какая сторона будет указана в списке параметров первой, с той и будет производиться работа. Вторая сторона необходима при занесении первого или удалении последнего звена из дека. Примеры этих процедур разобраны в контрольном варианте № 31.

Примеры процедур по добавлению и удалению элементов нульсвязных списков приведены в разобранном ниже контрольном варианте.

Дата добавления: 2014-11-06