Стеком (англ. 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.