Презентация Использование динамической памяти при организации списков и их обработке. Лекция 10 онлайн

Содержание слайда: Программирование на языке С++ Зариковская Наталья Вячеславовна Лекция 10

Содержание слайда: Линейные структуры данных Стек (stack) Очередь (queue) Дэк (deque; double-ended queue) Список (list)

Содержание слайда: Стек Стеком (англ. stack) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Стек должен поддерживать следующие операции: Push Добавить (положить) в конец стека новый элемент Pop Извлечь из стека последний элемент Top Узнать значение последнего элемента (не удаляя его) Size Узнать количество элементов в стеке Clear Очистить стек (удалить из него все элементы)

Содержание слайда: Способы реализации линейных динамических структур Реализация на базе массива фиксированного размера Реализация на базе динамического массива «Ссылочная» реализация

Содержание слайда: Реализация стека на базе массива

Содержание слайда: Реализация на базе динамического массива

Содержание слайда: «Ссылочная» реализация стека

Содержание слайда: Очередь Очередью (aнгл. queue)) называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других. Enqueue Добавить (положить) в конец очереди новый элемент Dequeue Извлечь из очереди первый элемент Front Узнать значение первого элемента (не удаляя его) Size Узнать количество элементов в очереди Clear Очистить очередь (удалить из нее все элементы)

Содержание слайда: Очередь на массиве Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать все элементы очереди, будем в отдельном поле start_index хранить индекс элемента массива, с которого начинается очередь. При удалении элементов, очередь будет "ползти" дальше от начала массива. Чтобы при этом не происходил выход за границы массива, замкнем массив в кольцо: будем считать, что за последним элементом массива следует первый.

Содержание слайда: Очередь на массиве struct Queue { int data[MAX_SIZE]; int size; int start_index; }; void enqueue(Queue *queue, int value) { queue->data[(queue->start_index + queue->size) % MAX_SIZE] = value; queue->size++; } int dequeue(Queue *queue) { int ret = queue->data[queue->start_index % MAX_SIZE]; queue->size--; queue->start_index++; return ret; }

Содержание слайда: Дек Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека: push_front : Добавить (положить) в начало дека новый элемент push_back : Добавить (положить) в конец дека новый элемент pop_front : Извлечь из дека первый элемент pop_back : Извлечь из дека последний элемент front : Узнать значение первого элемента (не удаляя его) back : Узнать значение последнего элемента (не удаляя его) size : Узнать количество элементов в деке clear : Очистить дек (удалить из него все элементы)

Содержание слайда: Связанный список Узел односвязного списка: struct Node { int value; Node *next; };

Содержание слайда: Связанный список Узел двусвязного списка: struct Node { Node *prev; int value; Node *next; };