Стеком (англ. stack) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Стек должен поддерживать следующие операции:
Стек можно хранить двумя способами: либо массивом некоторого фиксированного размера, либо при помощи ссылочной реализации.
Stack
Для работы со стеком создадим структуру данных Stack
. Поскольку
элементами стека могут быть любые данные (числа, строки и т.д.), то эта структура
будет шаблоном (template) над произвольным типом данных T
. Вот каким
должен быть интерфейс стека:
template <typename T> struct Stack { Stack(); // Конструктор ~Stack(); // Деструктор void push(T d); // Добавить в стек новый элемент T pop(); // Удалить из стека последний элемент // и вернуть его значение T top(); // Вернуть значение последнего элемента int size(); // Вернуть количество элементов в стеке void clear(); // Очистить стек };
В простейшем случае для хранения элементов стека можно использовать массив.
Элементы стека будем класть в начало стека. Заведем два поля в структуре:
поле m_data
— массив элементов стека и
m_size
— число элементов в стеке. Объявим их, как приватные
члены класса.
private: T m_data[MAXSIZE]; int m_size;
Значение m_size
инициализируем в конструкторе:
Stack () { m_size = 0; }
Добавление элементов в стек заключается в увеличении поля m_size
и записи элемента в массив m_data
:
void push(T val) { ++m_size; m_data[m_size - 1] = val; }
Оставшиеся методы реализовать также просто:
T top() { return m_data[m_size - 1]; } T pop() { --m_size; return m_data[m_size]; } void size() { return m_size; } void clear() { m_size = 0; }
Данная реализация имеет недостаток: размер стека фиксирован константой MAXSIZE
.
Попробуем сделать реализацию, в которой размер массива будет увеличиваться динамически.
Для этого заменим статический массив m_data
на указатель и будем динамически
выделять память. Размер выделенной памяти (т.е. максимальное число элементов в стеке без увеличения его размера)
будем хранить в поле m_maxsize
. В конструкторе необходимо выделить память для хранения
данных:
Stack() { m_size = 0; m_maxsize = 1; m_data = new T[m_maxsize]; }
В деструкторе нужно освободить выделенную память:
~Stack() { delete[] m_data; }
Создадим вспомогательный метод resize
, выделяющий дополнительную память:
void resize(int newsize) { T * newdata = new T[newsize]; for (int i = 0; i < m_size; ++i) newdata[i] = m_data[i]; delete[] m_data; m_data = newdata; m_maxsize = newsize; }
Теперь при добавлении нового элемента в стек проверим, не заполнен ли стек полностью.
Если это произошло, то вызовем метод resize
для увеличения размера стека:
void push(T val) { if (m_size == m_maxsize) resize(2 * m_maxsize); ++m_size; m_data[m_size - 1] = val; }
Другой способ реализации стека: ссылочная реализация. В ссылочной реализации стек хранится в виде последовательности отдельных элементов. Каждый элемент состоит из двух полей: данных и указателя на предыдущий элемент стека:
template <typename T> struct StackElem { T m_data; StackElem<T> * m_prev; }
В самой структуре Stack
хранится число элементов в стеке m_size
и
указатель на последний элемент стека m_top
:
private: int m_size; StackElem<T> * m_top;
При создании стека нужно проинициализировать поле m_top
нулевым указателем
(указатель в “никуда” свидетельствует о том, что в стеке нет ни одного элемента:
Stack() { m_data = 0; m_top = 0; }
Чтобы вернуть значение последнего элемента в стеке, разыменуем указатель m_top
и вернем поле m_data
результирующей структуры:
T top() { return m_top -> m_data; }
Чтобы удалить верхний элемент в стеке нужно освободить занимаемую им память и передвинуть указатель:
void pop() { StackElem<T> prev = m_top -> m_prev; delete m_top; m_top = prev; --m_size; }
Для добавления нового элемента необходимо выделить для него память и связать его с последним элементом стека:
void push(T val) { StackElem<T> new_top = new StackElem<T> new_top -> m_data = val; new_top -> m_prev = m_top; m_top = new_top; ++m_size; }
Для очистки стека будем удалять из него элементы по одному, пока стек не пуст:
void clear() { while (m_size > 0) pop(); }
Также в деструкторе нужно вызвать метод очистки стека, чтобы осводить всю выделенную память:
~Stack () { clear(); }
Реализуйте структуру данных “стек“, релизовав все методы стека. Стек должен быть реализован в виде шаблона над произвольным типом данных. Стек должен иметь произвольный размер. Можно выбрать одну из двух реализаций: на базе динамического массива или ссылочную реализацию.
Программа получает на вход последовательность команд:
ok
.
error
.
error
.
ok
.
bye
и завершить работу.
При этом должна быть реализована двойная защита: вызов методов top
и pop
для пустого стека
не должен приводить к обращению к несуществующим элементам массива m_data
, а функция main
должна
выводить сообщение error
, при считывании некорректной операции.
Ввод | Вывод |
---|---|
push 2 top pop size pop push 1 size exit |
ok 2 2 0 error ok 1 bye |
Очередью (aнгл. queue)) называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других.
Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать
все элементы очереди, будем в отдельном поле m_start
хранить индекс элемента массива, с которого начинается
очередь. При удалении элементов, очередь будет "ползти" дальше от начала массива. Чтобы при этом не происходил выход
за границы массива, замкнем массив в кольцо: будем считать, что за последним элементом массива следует первый.
Описание структуры очередь:
const int MAX_SIZE=1000; struct queue { int m_size; // Количество элементов в очереди int m_start; // Номер элемента, с которого начинается очередь int m_elems[MAX_SIZE]; // Массив для хранения элементов queue(); // Конструктор ~queue(); // Деструктор void push(int d); // Добавить в очередь новый элемент int pop(); // Удалить из очереди первый элемент // и вернуть его значение int front(); // Вернуть значение первого элемента int size(); // Вернуть количество элементов в очереди void clear(); // Очистить стек };
Реализуйте очередь. Очередь поддерживает те же операции, что и стек, за исключением операции top
,
которая заменена операцией front
.
Очередь должна быть реализована на базе закольцованного динамического массива.
Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека:
Аналогично заданиям A и B, но для дека.
Дек должен быть реализован при помощи ссылочной реализации.
Списки представляют собой последовательности элементов, в которые можно произвольно вставлять элементы и удалять элементы. Списки реализовываются в виде двусвязных ссылочных структур, поэтому в списках легко перемещаться от одного элемента к следующему и к предыдущему, но нельзя быстро перейти к элементу с заданным номером в списке (как в массиве).
Реализуйте список, элементами которого являются целые числа.
Список состоит из произвольного числа элементов. Один из элементов списка будем называть текущим.
Также в качестве текущего элемента может выступать фиктивный элемент, находящийся за последним элементом
списка - будем называть его концом списка, это аналог итератора end()
. Этот фиктивный
элемент нужен для того, чтобы можно было добавлять элементы в конец списка.
В самом начале список пустой, а текущим элементом является конец списка.
Список поддерживает следующие операции:
error
.
ok
или error
,
если текущим является конец списка.
end
, если текущим элементом стал конец списка, или error
,
если текущим элементом уже был конец списка.
error
, если текущим элементом был первый элемент списка.
ok
.
error
,
если текущим был конец списка. Текущим элементом становится элемент, следущий за текущим.
ok
.
bye
и завершить работу.
Ввод | Вывод |
---|---|
insert 1 insert 2 insert 3 next erase get set 4 prev prev erase next next insert 5 prev insert 6 next erase erase get size clear size exit |
ok ok ok 2 2 1 ok 3 error 3 end error ok 4 ok 4 4 5 error 1 ok 0 bye |
Реализуйте бинарное дерево поиска. Программа получает на вход последовательность чисел и строит из них бинарное дерево поиска. Элементы в деревья добавляются в соответствии с результатом поиска их места. Если элемент уже существует в дереве, добавлять его не надо. Балансировка дерева не производится.
Программа получает на вход последовательность натуральных чисел (типа int
).
Последовательность завершается число 0, которое означает конец ввода, и добавлять его в дерево не надо.
Вот пример построенного дерева для последовательности 7 3 2 1 9 5 4 6 8 0
:
После построения дерева решите поставленную задачу.
Выведите высоту полученного дерева (реализуйте рекурсивную процедуру, возвращающую высоту дерева).
Ввод | Вывод |
---|---|
7 3 2 1 9 5 4 6 8 0 |
4 |
Подсчитайте количество элементов в получившемся дереве (реализуйте рекурсивную процедуру, возвращающую количество элементов в дереве).
Ввод | Вывод |
---|---|
1 2 3 1 0 |
3 |
Выведите второй по величине элемент в построенном дереве. Гарантируется, что такой найдется.
Ввод | Вывод |
---|---|
7 3 2 1 9 5 4 6 8 0 |
8 |
1 1 1 2 2 2 0 |
1 |
Выведите все элементы полученного дерева в порядке возрастания. Удобней это делать при помощи рекурсивной процедуры.
Ввод | Вывод |
---|---|
7 3 2 1 9 5 4 6 8 0 |
1 2 3 4 5 6 7 8 9 |
Для полученного дерева выведите список всех листьев (вершин, не имеющих потомков) в порядке возрастания.
Ввод | Вывод |
---|---|
7 3 2 1 9 5 4 6 8 0 |
1 4 6 8 |
Для полученного дерева выведите список всех вершин, имеющих по два ребёнка, в порядке возрастания.
Ввод | Вывод |
---|---|
7 3 2 1 9 5 4 6 8 0 |
3 5 7 |
Для полученного дерева выведите список всех вершин, имеющих только одного ребёнка, в порядке возрастания.
Ввод | Вывод |
---|---|
7 3 2 1 9 5 4 6 8 0 |
2 9 |
Дерево называется сбалансированным, если для любой его вершины высота левого и правого поддерева для этой вершины различаются не более чем на 1. Определите, является ли дерево сбалансированным, выведите слово YES или NO.
Ввод | Вывод |
---|---|
7 3 2 1 9 5 4 6 8 0 |
YES |
1 2 3 0 |
NO |
По данной последовательности постройте дерево, запоминая для каждого элемента его значение и количество его повторений в последовательности.
Выведите на экран содержимое дерева в порядке возрастания, по одному элементу на строку. В каждой строке выводите значение элемента, затем, через пробел, укажите, сколько раз он встречается в исходной последовательности.
Ввод | Вывод |
---|---|
9 7 9 1 7 9 0 |
1 1 |
Реализуйте процедуру удаления элементов из бинарного дерева поиска. Правила удаления следующие:
Программа получает на вход последовательность целых чисел, заверщающаяся числом 0. При этом положительное число \(+d\) обозначает, что в дерево нужно добавить элемент со значением \(d\) (возможно, что он уже есть в дереве).
Отрицательное число \(-d\) означает, что из дерева нужно удалить элемент со значением \(d\), вполне возможно, что в дереве такого элемента нет (тогда дерево не модифицируется).
После окончания ввода программа должна вывести все элементы в дереве в порядке возрастания. В одной строке выводится три числа: значение элемента, значение его левого потомка, значение его правого потомка. Если у элемента нет соответствующего потомка, то выводится число 0.
Ввод | Вывод |
---|---|
7 3 2 1 9 5 4 6 8 -2 -4 -7 0 |
1 0 0 |
Красно-черные деревья это бинарные деревья поиска, все операции с которыми (поиск, добавление, удаление) выполняются за логарифм от числа элементов в дереве. При этом высота дерева также поддерживается пропорциональной логарифму от числа элементов: это достигается за счет балансировки дерева — поворотов отдельных поддеревьев при добавлении и удалении элементов.
В красно-черном дереве каждому элементу приписывается “цвет” — один бит информации, принимающий два значения: красная или черная вершина. При этом выполняются следующие свойства:
Для простоты реализации удобно считать, что все листья дерева — это фиктивные элементы, не хранящие данных, и они покрашены в черный цвет.
О том, как выполняются операции добавления и удаления в красно-черном дереве можно прочитать в книге Кормен, Лейзерсон, Ривест, Штайн, “Алгоритмы: построение и анализ”, глава 13.
Реализуйте красно-черное дерево только с операцией добавления элементов.
Программа получает на вход последовательность целых чисел, заверщающаяся числом 0. Программа последовательно добавляет данные элементы в красно-черное дерево, осуществляя балансировку дерева при необходимости. Число 0 обозначает конец ввода, его добавлять не надо. Если число уже содержится в дереве, его добавлять не надо.
После окончания ввода программа должна вывести все элементы в дереве в порядке возрастания.
В каждой строке выводится подряд через пробел: значение элемента,
цвет этого элемента (один символ, либо R
, либо B
,
что означает красный и черный цвет соответственно),
значение его левого потомка, значение его правого потомка. Если у элемента нет соответствующего потомка, то выводится число 0.
Ввод | Вывод |
---|---|
1 2 3 4 5 6 7 8 9 10 0 |
1 B 0 0 2 B 1 3 3 B 0 0 4 B 2 6 5 B 0 0 6 B 5 8 7 B 0 0 8 R 7 9 9 B 0 10 10 R 0 0 |
Реализуйте красно-черное дерево с операциями добавления и удаления элементов.
Формат входных данных аналогичен задаче E-10, формат выходных данных аналогичен задаче F-1.