ЗАДАНИЕ 9. Деревья и польская запись
Вариант 1. Создание и обработка структур типа «дерево»
Разработать проект для обработки дерева поиска, каждый элемент которого содержит целочисленный ключ и строку текста, содержащую, например, ФИО и номер паспорта (ввод исходной информации рекомендуется записать в файл). В программе должны быть реализованы следующие возможности:
– создание дерева;
– добавление новой записи;
– поиск информации по заданному ключу;
– удаление информации с заданным ключом;
– вывод информации;
– решение индивидуального задания;
– освобождение памяти при выходе из программы.
1. Поменять местами информацию, содержащую максимальный и минимальный ключи.
2. Подсчитать число листьев в дереве.
3. Удалить из дерева ветвь с вершиной, имеющей заданный ключ.
4. Определить глубину дерева.
5. Определить число узлов на каждом уровне дерева.
6. Удалить из левой ветви дерева узел с максимальным значением ключа и все связанные с ним узлы.
7. Определить количество узлов с четными ключами.
8. Определить число листьев на каждом уровне дерева.
9. Определить число узлов в дереве, имеющих только одного потомка.
10. Определить количество узлов правой ветви дерева.
11. Определить количество записей в дереве, начинающихся с введенной с клавиатуры буквы.
12. Найти среднее значение всех ключей дерева и найти строку, имеющую ближайший к этому значению ключ.
13. Определить количество узлов левой ветви дерева.
14. Определить число узлов в дереве, имеющих двух потомков.
15. Найти запись с ключом, ближайшим к среднему значению между максимальным и минимальным значениями ключей.
Вариант 2. Создание и использование польской записи
Написать программу формирования обратной польской записи и расчета полученного выражения. Предусмотреть возможности того, что идентификаторы могут состоять более чем из одного символа и могут быть использованы операции % и возведение в степень. Результат работы программы проверить на конкретном примере (табл. 15.1).
Например, если ввести выражение (a + b)*(c – d)/e и значения переменных а = 3, b = 5, c = 6, d = 9, е = 7, должны получиться следующие результаты:
Постфиксная форма ab+cd– *e/
Результат расчета – 3.42857
Таблица 15.1
| № | Выражение | a | b | c | d | e | Результат |
| a/(b– c)*(d+e) | 8.6 | 2.4 | 5.1 | 0.3 | 7.9 | – 26.12 | |
| (a+b)*(c– d)/e | 7.4 | 3.6 | 2.8 | 9.5 | 0.9 | – 81.89 | |
| a– (b+c*d)/e | 3.1 | 5.4 | 0.2 | 9.6 | 7.8 | 2.16 | |
| a/b– ((c+d)*e) | 1.2 | 0.7 | 9.3 | 6.5 | 8.4 | – 131.006 | |
| a*(b– c+d)/e | 9.7 | 8.2 | 3.6 | 4.1 | 0.5 | 168.78 | |
| (a+b)*(c– d)/e | 0.8 | 4.1 | 7.9 | 6.2 | 3.5 | 2.38 | |
| a*(b– c)/(d+e) | 1.6 | 4.9 | 5.7 | 0.8 | 2.3 | – 0.413 | |
| a/(b*(c+d))– e | 8.5 | 0.3 | 2.4 | 7.9 | 1.6 | 1.151 | |
| (a+(b/c– d))*e | 5.6 | 7.4 | 8.9 | 3.1 | 0.2 | 0.666 | |
| a*(b+c)/(d– e) | 0.4 | 2.3 | 6.7 | 5.8 | 9.1 | – 1.091 | |
| a– (b/c*(d+e)) | 5.6 | 3.2 | 0.9 | 1.7 | 4.8 | – 17.51 | |
| (a– b)/(c+d)*e | 0.3 | 6.7 | 8.4 | 9.5 | 1.2 | – 0.429 | |
| a/(b+c– d*e) | 7.6 | 4.8 | 3.5 | 9.1 | 0.2 | 1.173 | |
| a*(b– c)/(d+e) | 0.5 | 6.1 | 8.9 | 2.4 | 7.3 | – 0.144 | |
| (a+b*c)/(d– e) | 9.1 | 0.6 | 2.4 | 3.7 | 8.5 | – 2.196 |
ГЛАВА 16. Переход к ООП
При переходе от языка Си к языку С++ в стандарт ANSI были введены дополнительные механизмы, которые позволили в конечном итоге создать среду для разработки программ в объектно-ориентированном стиле.
Рассмотрим некоторые из них.
Дата добавления: 2016-09-20; просмотров: 774;