Курсовая работа: Динамические структуры данных: дек

Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти.

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

Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. К таким структурам относятся списки (однаправленные, двунаправленные, кольцевые однаправленные и кольцевые двунаправленные), стеки, деки, очереди, деревья и другие. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач.

Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.

Динамическая структура называется деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) или двунаправленным списком, если каждый узел её содержит два указателя: один указывает на предшествующий узел, другой - на последующий. Такие списки могут быть линейными и циклическими, а члены в них добавляются и удаляются с 2 сторон.

???. 1. ???

Мы будем различать деки с ограниченным выходом или ограниченным входом; в таких деках соответственно исключение или включение допускается только на одном конце.

Рис. 2. Дек с ограниченным входом

Рис. 3. Дек с ограниченным выходом

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

В деке все исключения и добавления происходят на обоих его концах.

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

Описание алгоритма

Создаваемый класс в данной программе называется Deq.

Данный класс должен реализовывать функции вставки и удаления элементов в начало и конец дека.

Для создания класса «Дек» необходимо сначала создать структуру элемента с указателем на следующий элемент. В данной программе такой структурой является Node.

При создании класса надо создать указатели на первый и последний элементы дека. Данные указатели прописываются в private, т. е. обращаться к этим указателям возможно только из методов класса Deq.

В общедоступной области доступа прописываются методы класса, прописанные в постановке задачи.

Указателям изначально присваиваются пустые значения (NULL).

Добавление элемента в начало дека

Для добавления элемента в начало дека используется метод класса add . Его параметрами является добавляемый элемент b .

Необходимо создать новый элемент структуры Node (el). Элементу el присваивается значение введенного с клавиатуры числа. Для добавления элемента в начало дека, необходимо, чтобы ячейка была пуста. Поэтому, проверяется условие наличия в ячейке элемента. Если ячейка не пуста, то указатель на первый элемент переходит на следующую ячейку, в которую и будет записан элемент. Количество ячеек возрастает на 1.

Удаление элемента из начала дека

Для удаления элемента из начала дека используется метод класса delete .

Удаление элемента происходит по тому же алгоритму, но ячейка не проверяется на наличие элемента в нем. Элементу el присваивается указатель first и указатель переходит в следующую ячейку. Затем элемент el удаляется и количество ячеек понижается на единицу.