Программирование на языке С++
Линейные структуры данных
Стек
Способы реализации линейных динамических структур
Реализация стека на базе массива
Реализация на базе динамического массива
«Ссылочная» реализация стека
Очередь
Очередь на массиве
Очередь на массиве
Дек
Связанный список
Связанный список
1.01M
Category: programmingprogramming

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

1. Программирование на языке С++

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

2. Линейные структуры данных

• Стек (stack)
• Очередь (queue)
• Дэк (deque; double-ended queue)
• Список (list)
2

3. Стек

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

4. Способы реализации линейных динамических структур

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

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

struct Stack {
int data[MAX_SIZE];
int size;
};
void push(Stack *stack, int value) {
stack->data[stack->size] = value;
stack->size++;
}
int size(Stack *stack) {
return stack->size;
}
void clear(Stack *stack) {
stack->size = 0;
}
int pop(Stack *stack) {
stack->size--;
return stack->data[stack->size];
}
int top(Stack *stack) {
return stack->data[stack->size – 1];
}
5

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

struct Stack {
int *data;
int size;
int max_size;
};
void push(Stack *stack, int value) {
if(stack->size == stack->max_size) {
resize(stack, stack->max_size * 2);
}
stack->data[stack->size] = value;
stack->size++;
}
int pop(Stack *stack) {
stack->size--;
return stack->data[stack->size];
}
int top(Stack *stack) {
return stack->data[stack->size – 1];
}
int size(Stack *stack) {
return stack->size;
}
void clear(Stack *stack) {
stack->size = 0;
}
void resize(Stack *stack, int new_size) {
int *new_data = new int[new_size];
for(int i = 0; i < stack->size; i++) {
new_data[i] = stack->data[i];
}
delete [] stack->data;
stack->data = new_data;
stack->max_size = new_size;
6
}

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

struct StackElement {
int value;
StackElement *prev;
};
struct Stack {
StackElement *top;
int size;
};
int pop(Stack *stack) {
StackElement *top = stack->top;
int ret = top->value;
stack->top = top->prev;
delete top;
stack->size--;
return ret;
}
void push(Stack *stack, int value) {
StackElement *new_top =
new StackElement();
new_top->value = value;
new_top->prev = stack->top;
stack->top = new_top;
stack->size++;
}
int size(Stack *stack) {
return stack->size;
}
int top(Stack *stack) {
return stack->top->value;
}
void clear(Stack *stack) {
StackElement *cur = stack->top;
while(cur != 0) {
cur = cur->prev;
delete cur;
}
stack->top = 0;
}
7

8. Очередь

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

9. Очередь на массиве

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

10. Очередь на массиве

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;
}
10

11. Дек

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








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

12. Связанный список

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

13. Связанный список

• Узел двусвязного списка:
struct Node {
Node *prev;
int value;
Node *next;
};
13
English     Русский Rules