Срок выполнения задания:
по 31.05.2025
Разработать версию бинарного дерева поиска для частотного анализа слов из текстового файла. Загрузить и проанализировать англоязычную версию романа Л.Толстого "Война и мир".
В данной работе нужно взять за основу реализацию обычного бинарного дерева поиска (без самобалансировки) и адаптировать его для анализа слов из текстового файла.
Под анализом в данной работе понимается частотный анализ встречаемости слов, то есть какое слово сколько раз встретилось.
Известный шаблон бинарного дерева необходимо поместить в include/bst.h. Все необходимые методы для работы с деревом должны содержаться в этом же файле.
Помимо основных, в классе BST должны быть определены следующие методы:
- depth() - измерение глубины (высоты) дерева
- search(T value) - поиск ключа в дереве
Определить функцию void makeTree(BST<std::string>& tree, const char* filename), расположенную в файле alg.cpp. Функция должна принимать ссылку на пустое дерево и строку с именем файла для анализа и строить дерево, переданное в первом параметре. Дерево должно содержать слова из предложенного файла src/war_peace.txt.
Важно!
Под словом понимается непрерывная последовательность латинских букв, преобразованная к НИЖНЕМУ регистру. Кроме того, в каждом узле дерева кроме слова должен храниться счетчик повторений.
Мы анализируем из файла только последовательности символов в ASCII-кодировке, латинские буквы. Все другие сочетания символов игнорируются! Цифровые последовательности тоже игнорируются! Заглавные буквы должны преобразовываться в нижний регистр!
При создании дерева, шаблон должен быть инстанцирован с типом <std::string>:
BST<std::string> const char* filename = "name.txt"
// открываем файл на чтение
std::ifstream file(filename);
// если файл не открылся, прекращаем работу
if (!file) {
std::cout << "File error!" << std::endl;
return;
}
int count=0;
// читаем содержимое файла посимвольно
while(!file.eof())
{
int ch=file.get();
count++;
}
// закрываем файл
file.close();
// выводим число символов
std::cout << count <<std::endl;Определить функцию void printFreq(BST<std::string>& tree), которая выдает слова из дерева в порядке убывания частоты на экран (std::cout). Сохранить эти слова/частоты в файле result/freq.txt
В проект должен входить заголовочный файл include/bst.h. Файл src/alg.cpp должен содержать реализацию makeTree и printFreq. Файл src/main.cpp содержит пример с построением дерева и вызовом таблицы слов с частотами. Файл result/freq.txt содержит результат вывода слов в порядке убывания частоты.