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

Сентябрь 6, 2022

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

Содержание

2. Линейные структуры данных Стек (stack) Очередь (queue) Дэк (deque; double-ended queue) Список (list)
3. Стек Стеком (англ. stack) называется хранилище данных, в котором можно работать только с одним элементом: тем,
4. Способы реализации линейных динамических структур Реализация на базе массива фиксированного размера Реализация на базе динамического массива
5. Реализация стека на базе массива
6. Реализация на базе динамического массива
7. «Ссылочная» реализация стека
8. Очередь Очередью (aнгл. queue)) называется структура данных, в которой элементы кладутся в конец, а извлекаются из
9. Очередь на массиве Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый
10. Очередь на массиве struct Queue { int data[MAX_SIZE]; int size; int start_index; }; void enqueue(Queue *queue,
11. Дек Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую
12. Связанный список Узел односвязного списка: struct Node { int value; Node *next; };
14. Скачать презентацию

Слайд 2

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

Слайд 3

Стек
Стеком (англ. stack) называется хранилище данных, в котором можно работать только

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

Слайд 4

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

базе динамического массива
«Ссылочная» реализация

Слайд 5

Реализация стека на базе массива

Слайд 6

Реализация на базе динамического массива

Слайд 7

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

Слайд 8

Очередь
Очередью (aнгл. queue)) называется структура данных, в которой элементы кладутся в

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

Слайд 9

Очередь на массиве
Элементы очереди будем также хранить в массиве. При

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

Слайд 10

$Очередь на массиве struct Queue { int data[MAX_SIZE]; int size; int$

Очередь на массиве
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;
}

Слайд 11

Дек
Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется

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

Слайд 12

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

Содержание

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

Стек Стеком (англ. stack) называется хранилище данных, в котором можно работать только

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

Реализация стека на базе массива

Реализация на базе динамического массива

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

Очередь Очередью (aнгл. queue)) называется структура данных, в которой элементы кладутся в

Очередь на массиве Элементы очереди будем также хранить в массиве. При

Очередь на массивеstruct Queue { int data[MAX_SIZE]; int size; int start_index;};void

Дек Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется

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

Похожие презентации