Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- uint32_t* frequency_table(uint64_t &size, ifstream &input) {
- size = static_cast<uint64_t>(input.seekg(0, ios::end).tellg()); //размер файла
- input.seekg(0); //на начало файла
- char * buff = new char[static_cast<size_t>(size)]; // выделяем память под buff!!!
- input.read(buff, size); //считываем туда наш файл
- uint32_t * code = new uint32_t[256]{}; //табличка частот с нулевыми частотами
- for (uint64_t iter = 0; iter < size; iter++) {
- code[static_cast<unsigned char>(buff[iter])]++; //пробежались по всем элементам и заполнили
- }
- delete[] buff; //освободили занятую память под buf!!!
- return code; //вернули обратно таблицу часто с нулевыми частотами
- }
- //после у нас есть количество симвлов файла в size по ссылке + выделение памяти под табличку частот
- Node * buildTree(uint32_t * freq) {
- priority_queue<Node*, vector<Node*>, compare > heap = {}; //куча из указателей на node, можно брать минимум за O(1)
- for (size_t index = 0; index < 256; ++index) { //создаем листья, пробегаемся по табличке и смотрим где частота больше нуля
- if (freq[index] > 0) {
- Node * list = new Node(); // выделяем память, надо не забыть вызвать дистукртор
- list->count = freq[index]; //задаем параметры и кладем на кучу
- list->letter = static_cast<char>(index);
- heap.push(list);
- }
- }
- if (heap.empty()) return NULL; //обрабатываем граничные случаи
- if (heap.size() == 1) return heap.top();
- while (heap.size() > 1) { //строим дерево, опять же выделяем память
- Node * fst = heap.top();
- heap.pop();
- Node * snd = heap.top();
- heap.pop();
- Node * meta_root = new Node(fst, snd);
- heap.push(meta_root);
- }
- Node * root = heap.top(); //возвращаем корень дерева, надо не забыть освободить память!!!!
- return root;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement