Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ЛАБОРАТОРНАЯ РАБОТА №8
1. Цель работы
Приобретение и закрепление навыков в работе с деревьями.
2. Прорабатываемые темы
Нелинейные структуры данных.
3. Постановка задачи
Из входного потока (терминала или файла) поступает текст, состоящий из слов, которые разделены пробелами. Между словами может быть более одного пробела.
Разобрать текст по словам или по символам (в зависимости от условия), упорядочив его путем сортировки двоичным деревом. Под символами в данном случае подразумеваются лишь те, которые входят в слова. Дерево представить в виде объекта, в который включить следующие методы:
построить дерево по тексту, заданному в файле;
удалить поддерево с корнем, значение в котором равно заданному;
вывести дерево на экран в наглядном виде.
Сохранить-восстановить дерево.
Кроме этих, в объект включить метод, соответствующий варианту задания. Составить тестовую программу для проверки всех методов объекта.
Варианты
Разобрать дерево по словам реализовать один из следующих методов.
Выдать все слова, упорядоченные по алфавиту в прямом порядке.
Выдать все слова, упорядоченные по алфавиту в обратном порядке.
Построить частотный словарь - список слов без повторения по алфавиту с указанием частоты появления каждого слова в тексте.
Выдать список слов без повторения, упорядоченный по возрастанию их длин.
Выдать список слов без повторения, упорядоченный по убыванию их длин.
Выдать все слова, упорядоченные по алфавиту, с указанием номера каждого слова в тексте.
Выдать все слова, встречающиеся в тексте по одному разу.
Выдать все слова, встречающиеся в тексте более, чем по одному разу.
Выдать все слова заданной длины.
Выдать все слова, начинающиеся на заданную букву.
Разобрать дерево по символам и реализовать один из следующих методов.
Выдать все символы, встречающиеся в тексте заданное число раз.
Подсчитать частоту появления в тексте заданного символа.
Построить таблицу из всех различных символов текста с указанием частоты их появления (частотный словарь символов).
Найти все символы с максимальным числом вхождений в текст.
Найти все символы с минимальным числом вхождений в текст.
Построить таблицу из всех различных символов текста с указанием количества слов, в которых каждый символ появляется.
Вывести путь от вершины до заданного узла (узел задается значением символа).
Подсчитать число вершин в заданном поддереве.
Подсчитать число терминальных (конечных) вершин в заданном поддереве.
Подсчитать число нетерминальных (промежуточных) вершин в заданном поддереве.
Подсчитать количество уровней в заданном поддереве, считая корень.
Построить дерево:
Построить бинарное дерево из заданного м-арного дерева;
построить бинарное дерево из леса деревьев;
Построить идеально сбалансированное дерево;
Построить бинарное дерево поиска;
Построить сбалансированное АВЛ –дерево поиска;
Построить рандомизированное дерево поиска;
Построить оптимальное дерево поиска.
Срок сдачи работы 30.05.12г.