SHARE
TWEET

Untitled

a guest Oct 21st, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top