Оценка вычислительной сложности программы. Реализация алгоритма кодирования информации Хаффмана. Кодировка теста двоичным кодом и в дереве Хаффмана. Бинарный код символов. Символ и частота его появления в тексте. Вычисление трудоемкости алгоритма.
Программная реализация 3. Анализ трудоемкости алгоритма Заключение Список использованных источников ВВЕДЕНИЕ Данная работа представляет собой описание программы, реализующей алгоритм Хаффмана, а именно, позволяет закодировать текст двоичным кодом так, чтобы объем информации был минимален, а также оценку вычислительной сложности данной программы. 1. Решение задачи Существует несколько алгоритмов кодирования информации двоичным кодом, но для решения поставленной задачи наиболее подходит алгоритм Хаффмана кодирования информации. Текст программы: #include #include #include #include #include Windows.h using namespace std; class Tree { public: char symbol; int weight; Tree* left_son; Tree* right_son; }; class Symbol_class { public: char symbol; //символ int amount; //его частота в тексте vector code; //код символа }; vector symbol_vector; //список всех символов vector Tree_vector; //дерево Хаффмана vector code; //бинарный код символов Tree* main_tree; //указатель на корень дерева void Find_this_symbol(char c) //поиск символов в списке { coutsymbol = symbol_vector[i].symbol; tr->weight = symbol_vector[i].amount; tr->left_son = NULL; tr->right_son = NULL; Tree_vector.push_back(tr); } } void Sort() //Сортировка эл-тов дерева по их весу { Tree* temp; bool repeat; do { repeat = false; for (int i=1;iweight>Tree_vector[i-1]->weight) { temp = Tree_vector[i]; Tree_vector[i] = Tree_vector[i-1]; Tree_vector[i-1] = temp; repeat = true; } } } while (repeat); } void Create_Tree() //создаем дерево Хаффмана { while (Tree_vector.size()!=1) //до тех пока не останется один узел (корень) { int tr_size = Tree_vector.size(); Sort(); //сортируем символы по их весу (частоте) Tree* temp = new Tree; //создаем новый узел //вес нового узла равен сумме весов двух эл-тов с наименьшим весом temp->weight = Tree_vector[tr_size-2]->weight Tree_vector[tr_size-1]->weight; //левый сын нового узла указывает на последний эл-т temp->left_son = Tree_vector[tr_size-1]; Tree_vector.pop_back(); //выбрасываем из списка эл-т с минимальным весом //повторяем операцию для предпоследнего эл-та temp->right_son = Tree_vector[tr_size-2]; Tree_vector.pop_back(); temp->symbol = 0; //вместо двух выброшенных эл-т записываем новый Tree_vector.push_back(temp); } main_tree = Tree_vector[0]; //запоминаем указатель на корень дерева } void Coding_Tree(Tree* a) //кодируем дерево Хаффмана { if(a->left_son!=NULL) //если у узла есть левый сын { code.push_back(0); //добавляем в строчку кода 0 Coding_Tree(a->left_son); //рекурсивно повторяем операции } if(a->right_son!=NULL) //если у узла есть правый сын { code.push_back(1); //добавляем в строчку кода 1 Coding_Tree(a->right_son); } // если у узла нет сыновей, то: char c = a->symbol; for (int i=0;i Tree_vector в отдельный файл и потом считать, т.к. в ней хранятся коды всех элементов. 4. Отсюда можно предположить что сложность функции будет O(N), т.е. изменяется линейно.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
