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

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

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

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

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

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

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

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

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

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

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

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

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

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

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