Дважды связные списки

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

Рис. 10 – Дважды связный список

Важным преимуществом является то, что можно использовать указатель ячейки, содержащей i -й элемент, для определения i -й позиции вместо использования указателя предшествующей ячейки. Однако при этом появляются дополнительные указатели и, следовательно, удлиняются некоторые процедуры. Ниже приведен код объявления дважды связного списка.

На рис. 11 приведены процедура и схема удаления элемента из дважды связного списка. Ниже приведена процедура удаления.

Рис. 11 – Удаление элемента из дважды связного списка

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

Лекция 4

План лекции:

1. Абстрактный тип данных «очередь».

2. Реализация очереди с помощью указателей.

3. Разновидности очередей.

4. Абстрактный тип данных «стек».

5. Реализация стеков с помощью массивов.

4.1 Абстрактный тип данных «очередь»

Очередь – это специальный тип списка. Очередью называют упорядоченный набор элементов, где элементы удаляются с одного его конца, который называется началом, а вставляются с другого, который называется концом очереди. Очереди также называются списками типа FIFO (аббревиатура расшифровывается как first in first out: первым вошел – первым вышел). Для работы с очередями чаще других используются следующие операторы.

1) MAKENULL(Q) очищает очередь Q, делая ее пустой.

2) FRONT(Q) – функция, возвращающая первый элемент очереди Q.

3) ENQUEUE(x, Q) вставляет элемент х в конец очереди Q.

4) DEQUEUE (Q) удаляет первый элемент очереди Q.

5) EMPTY (Q). Эта функция возвращает значение true (истина) тогда и только тогда, когда Q является пустой очередью.

Не нашли, что искали? Воспользуйтесь поиском: