Ссылочные реализации структур данных

Стек

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

push

Добавить (положить) в конец стека новый элемент

pop

Извлечь из стека последний элемент

top

Узнать значение последнего элемента (не удаляя его)

size

Узнать количество элементов в стеке

clear

Очистить стек (удалить из него все элементы)

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

Очередь

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

Дек

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

push_front

Добавить (положить) в начало дека новый элемент

push_back

Добавить (положить) в конец дека новый элемент

pop_front

Извлечь из дека первый элемент

pop_back

Извлечь из дека последний элемент

front

Узнать значение первого элемента (не удаляя его)

back

Узнать значение последнего элемента (не удаляя его)

size

Узнать количество элементов в деке

clear

Очистить дек (удалить из него все элементы)

Списки

Списки представляют собой последовательности элементов, в которые можно произвольно вставлять элементы и удалять элементы. Списки реализовываются в виде двусвязных ссылочных структур, поэтому в списках легко перемещаться от одного элемента к следующему и к предыдущему, но нельзя быстро перейти к элементу с заданным номером в списке (как в массиве).

A: двусвязный список

Реализуйте список, элементами которого являются целые числа.

Список состоит из произвольного числа элементов. Один из элементов списка будем называть текущим. Также в качестве текущего элемента может выступать фиктивный элемент, находящийся за последним элементом списка - будем называть его концом списка. Этот фиктивный элемент нужен для того, чтобы можно было добавлять элементы в конец списка.

В самом начале список пустой, а текущим элементом является конец списка.

Список поддерживает следующие операции:

get

Вывести значение текущего элемента. Если текущим является конец списка, то вывести error.

set n

Установить значение текущего элемента в n. Вывести ok или error, если текущим является конец списка.

next

Переместиться на один элемент в сторону конца списка. Вывести значение нового текущего элемента, или end, если текущим элементом стал конец списка, или error, если текущим элементом уже был конец списка.

prev

Переместиться на один элемент в сторону начала списка. Вывести значение нового текущего элемента или error, если текущим элементом был первый элемент списка.

insert n

Вставить новый элемент перед текущим и задать ему значение n. Новый элемент становится текущим. Программа выводит ok.

erase

Удалить текущий элемент. Программа выводит значение удаленного элемента или error, если текущим был конец списка. Текущим элементом становится элемент, следущий за текущим.

size

Программа должна вывести количество элементов в списке.

clear

Программа должна очистить список и вывести ok.

exit

Программа должна вывести 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:

После построения дерева решите поставленную задачу.

B: Высота дерева

Выведите высоту полученного дерева (реализуйте рекурсивную процедуру, возвращающую высоту дерева).

7
3
2
1
9
5
4
6
8
0

4

C: Количество элементов

Подсчитайте количество элементов в получившемся дереве (реализуйте рекурсивную процедуру, возвращающую количество элементов в дереве).

1
2
3
1
0

3

D: Второй максимум

Выведите второй по величине элемент в построенном дереве. Гарантируется, что такой найдется.

7
3
2
1
9
5
4
6
8
0

8

1
1
1
2
2
2
0

1

E: Обход

Выведите все элементы полученного дерева в порядке возрастания. Удобней это делать при помощи рекурсивной процедуры.

7
3
2
1
9
5
4
6
8
0

1 2 3 4 5 6 7 8 9

F: Вывод листьев

Для полученного дерева выведите список всех листьев (вершин, не имеющих потомков) в порядке возрастания.

7
3
2
1
9
5
4
6
8
0

1 4 6 8

G: Вывод развилок

Для полученного дерева выведите список всех вершин, имеющих по два ребёнка, в порядке возрастания.

7
3
2
1
9
5
4
6
8
0

3 5 7

H: Вывод веток

Для полученного дерева выведите список всех вершин, имеющих только одного ребёнка, в порядке возрастания.

7
3
2
1
9
5
4
6
8
0

2 9

I: Сбалансированность

Дерево называется сбалансированным, если для любой его вершины высота левого и правого поддерева для этой вершины различаются не более чем на 1. Определите, является ли дерево сбалансированным, выведите слово YES или NO.

7
3
2
1
9
5
4
6
8
0

YES

1
2
3
0

NO

J: Подсчет элементов

По данной последовательности постройте дерево, запоминая для каждого элемента его значение и количество его повторений в последовательности.

Выведите на экран содержимое дерева в порядке возрастания, по одному элементу на строку. В каждой строке выводите значение элемента, затем, через пробел, укажите, сколько раз он встречается в исходной последовательности.

9
7
9
1
7
9
0

1 1
7 2
9 3

K: Удаление элементов

Реализуйте процедуру удаления элементов из бинарного дерева поиска. Правила удаления следующие:

1. Если у удаляемого элемента нет потомков, то он просто удаляется.
2. Если у удаляемого элемента один потомок, то этот потомок становится на место удаляемого.
3. Если у удаляемого элемента два потомка, то на место удаляемого элемента ставится минимальный элемент из его правого поддерева.

Программа получает на вход последовательность целых чисел, заверщающаяся числом 0. При этом положительное число \(+d\) обозначает, что в дерево нужно добавить элемент со значением \(d\) (возможно, что он уже есть в дереве).

Отрицательное число \(-d\) означает, что из дерева нужно удалить элемент со значением \(d\), вполне возможно, что в дереве такого элемента нет (тогда дерево не модифицируется).

После окончания ввода программа должна вывести все элементы в дереве в порядке возрастания. В одной строке выводится три числа: значение элемента, значение его левого потомка, значение его правого потомка. Если у элемента нет соответствующего потомка, то выводится число 0.

7
3
2
1
9
5
4
6
8
-2
-4
-7
0

1 0 0
3 1 5
5 0 6
6 0 0
8 3 9
9 0 0