Advertisement
Guest User

Untitled

a guest
Oct 21st, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.80 KB | None | 0 0
  1.  
  2. uint32_t* frequency_table(uint64_t &size, ifstream &input) {
  3. size = static_cast<uint64_t>(input.seekg(0, ios::end).tellg()); //размер файла
  4. input.seekg(0); //на начало файла
  5. char * buff = new char[static_cast<size_t>(size)]; // выделяем память под buff!!!
  6. input.read(buff, size); //считываем туда наш файл
  7.  
  8. uint32_t * code = new uint32_t[256]{}; //табличка частот с нулевыми частотами
  9.  
  10. for (uint64_t iter = 0; iter < size; iter++) {
  11. code[static_cast<unsigned char>(buff[iter])]++; //пробежались по всем элементам и заполнили
  12. }
  13. delete[] buff; //освободили занятую память под buf!!!
  14. return code; //вернули обратно таблицу часто с нулевыми частотами
  15. }
  16. //после у нас есть количество симвлов файла в size по ссылке + выделение памяти под табличку частот
  17.  
  18.  
  19. Node * buildTree(uint32_t * freq) {
  20. priority_queue<Node*, vector<Node*>, compare > heap = {}; //куча из указателей на node, можно брать минимум за O(1)
  21.  
  22. for (size_t index = 0; index < 256; ++index) { //создаем листья, пробегаемся по табличке и смотрим где частота больше нуля
  23. if (freq[index] > 0) {
  24. Node * list = new Node(); // выделяем память, надо не забыть вызвать дистукртор
  25. list->count = freq[index]; //задаем параметры и кладем на кучу
  26. list->letter = static_cast<char>(index);
  27. heap.push(list);
  28. }
  29. }
  30.  
  31. if (heap.empty()) return NULL; //обрабатываем граничные случаи
  32. if (heap.size() == 1) return heap.top();
  33.  
  34. while (heap.size() > 1) { //строим дерево, опять же выделяем память
  35. Node * fst = heap.top();
  36. heap.pop();
  37. Node * snd = heap.top();
  38. heap.pop();
  39. Node * meta_root = new Node(fst, snd);
  40. heap.push(meta_root);
  41. }
  42.  
  43. Node * root = heap.top(); //возвращаем корень дерева, надо не забыть освободить память!!!!
  44. return root;
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement