рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Логическая структура дека

Реферат Курсовая Конспект

Выберите учебное заведение

Логическая структура дека

Логическая структура дека - раздел Образование, Полустатические структуры данных Дек - Особый Вид Очереди. Дек (От Англ. Deq - Double Ended Queue,т.е...

Дек - особый вид очереди. Дек (от англ. deq - double ended

queue,т.е очередь с двумя концами) - это такой последовательный

список, в котором как включение, так и исключение элементов может

осуществляться с любого из двух концов списка. Частный случай де-

ка - дек с ограниченным входом и дек с ограниченным выходом. Ло-

гическая и физическая структуры дека аналогичны логической и фи-

зической структуре кольцевой FIFO-очереди. Однако, применительно

к деку целесообразно говорить не о начале и конце, а о левом и

правом конце.

Операции над деком:

- включение элемента справа;

- включение элемента слева;

- исключение элемента справа;

- исключение элемента слева;

- определение размера;

- очистка.

──────────────────────────┬──────────────────────────────

1. ─┬──┬──┬──┬─ │7. ─┬──┬──┬──┬─

│ │ │ │ ABCDE │ BC <┐ │D │A │ │ ─┐ E

─┴──┴──┴──┴─ │ │ ─┴──┴──┴──┴─ │

│ └──────────────┘

2. ─┬──┬──┬──┬─ │ 8. ─┬──┬──┬──┬─

│ │ │A │ BCDE │ BCA <┐ │D │ │ │ ─┐ E

─┴──┴──┴──┴─ │ │ ─┴──┴──┴──┴─ │

│ └──────────────┘

3. ─┬──┬──┬──┬─ │ 9. ─┬──┬──┬──┬─

┌> │ │B │A │ ┌─CDE │ BCAD <┐ │ │ │ │ ─┐ E

│ ─┴──┴──┴──┴─ │ │ │ ─┴──┴──┴──┴─ │

└──────────────┘ │ └──────────────┘

4. ─┬──┬──┬──┬─ │ 10. ─┬──┬──┬──┬─

B <─ │ │ │A │ CDE │ BCAD │ │ │E │ <──

─┴──┴──┴──┴─ │ ─┴──┴──┴──┴─

5. ─┬──┬──┬──┬─ │ 11. ─┬──┬──┬──┬─

B │ │A │C │ <── DE │ BCADE <── │ │ │ │

─┴──┴──┴──┴─ │ ─┴──┴──┴──┴─

6. ─┬──┬──┬──┬─ │

B ┌> │D │A │C │ ┌─ E │

│ ─┴──┴──┴──┴─ │ │

└──────────────┘ │

───────────────────────────┴──────────────────────────────

Рис. 4.2. Состояния дека в процессе изменения.

На рис. 4.2 в качестве примера показана последовательность

состояний дека при включении и удалении пяти элементов. На каждом

этапе стрелка указывает с какого конца дека (левого или правого)

осуществляется включение или исключение элемента. Элементы соот-

ветственно обозначены буквами A, B, C, D, E.

Физическая структура дека в статической памяти идентична

структуре кольцевой очереди. Разработать программный пример, ил-

люстрирующий организацию дека и операции над ним не сложно по об-

разцу примеров 4.1, 4.3. В этом модуле должны быть реализованы

процедуры и функции:

Function DeqWrRight(a: data): boolean; - включение элемента

справа;

Function DeqWrLeft(a: data): boolean; - включение элемента сле-

ва;

Function DeqRdRight(var a: data): boolean; - исключение элемен-

та справа;

Function DeqRdLeft(var a: data) : boolean; - исключение элемен-

та слева;

Procedure DeqClr; - очистка;

Function DeqSize : integer; - определение размера.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Полустатические структуры данных

Полустатические структуры данных Характерные особенности полустатических... Стеки Логическая... Очереди FIFO Логическая структура...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Логическая структура дека

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Характерные особенности полустатических структур
Полустатические структуры данных характеризуются следующими признаками: - они имеют переменную длину и простые процедуры ее изменения; - изменение длины структуры происхо

Логическая структура стека
Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Приме

Машинное представление стека и реализация операций
При представлении стека в статической памяти для стека выде- ляется память, как для вектора. В дескрипторе этого вектора кроме обычных для вектора параметров должен находиться так

Стеки в вычислительных системах
Стек является чрезвычайно удобной структурой данных для многих задач вычислительной техники. Наиболее типичной из таких задач является обеспечение вложенных вызовов процедур.

Логическая структура очереди
Очередью FIFO (First - In - First- Out - "первым пришел - первым исключается"). называется такой последовательный список с переменной длиной, в котором включение элемент

Операций
При представлении очереди вектором в статической памяти в дополнение к обычным для дескриптора вектора параметрам в нем должны находиться два указателя: на начало очереди (на перв

Очереди с приоритетами
В реальных задачах иногда возникает необходимость в форми- ровании очередей, отличных от FIFO или LIFO. Порядок выборки элементов из таких очередей определяется приоритетами элеме

Очереди в вычислительных системах
Идеальным примером кольцевой очереди в вычислительной систе- мы является буфер клавиатуры в Базовой Системе Ввода-Вывода ПЭВМ IBM PC. Буфер клавиатуры занимает последовательность

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

Логическая структура строки
Строка - это линейно упорядоченная последовательность симво- лов, принадлежащих конечному множеству символов, называемому ал- фавитом. Строки обладают следующими важными

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

ПРЕДСТАВЛЕНИЕ СТРОК ВЕКТОРОМ ПЕРЕМЕННОЙ ДЛИНЫ С ПРИЗНАКОМ
КОНЦА. Этот и все последующие за ним методы учитывают переменную длину строк. Признак конца - это особый символ, принадлежащий ал- фавиту (таким образом, полезный

ПРЕДСТАВЛЕНИЕ СТРОК ВЕКТОРОМ ПЕРЕМЕННОЙ ДЛИНЫ СО СЧЕТЧИКОМ.
Счетчик символов - это целое число, и для него отводится доста- точное количество битов, чтобы их с избытком хватало для предс- тавления длины самой длинной строки,какую только мо