}

Delphi.int.ru — Портал программистов

Вход Регистрация | Забыли пароль?

Просмотр кода

Идентификатор: 07abb011 Описание: Код загружен: 28 мая 2012, 01:43 (IlluminatI)

  1. #include <iostream>
  2. #include <fstream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <map>
  6.  
  7. using namespace std;
  8. int finded = 0;
  9. struct haffnode {
  10. char sym;
  11. int freq;
  12. haffnode *left, *right;
  13. };
  14.  
  15. void qusort(haffnode **arr, int l, int r) {
  16. int key = arr[(l+r)/2]->freq;
  17. int i = l;
  18. int j = r;
  19. do {
  20. while (arr[i]->freq < key) i++;
  21. while (arr[j]->freq > key) j--;
  22. if (arr[i]->freq >= arr[j]->freq) {
  23. haffnode *tmp = arr[i];
  24. arr[i] = arr[j];
  25. arr[j] = tmp;
  26. i++; j--;
  27. }
  28.  
  29. } while (i < j);
  30.  
  31. if (i < l) qusort(arr, i, l);
  32. if (j > r) qusort(arr, j, r);
  33. }
  34. haffnode** get_frequences(int &size) {
  35. //ifstream fin("hin");
  36. map <char, int> fq;
  37. char t;
  38.  
  39. // while (fin >> t)
  40. // fq[t]++;
  41. FILE *fin = fopen("hin", "r");
  42. while (fscanf(fin, "%c", &t) != -1) {
  43. if ((t != '\n')&&(t != '\0'))
  44. fq[t]++;
  45. }
  46. fclose(fin);
  47.  
  48. int i = 0;
  49. haffnode **arr = new haffnode*[fq.size()];
  50. for (map <char, int>::iterator it = fq.begin(); it != fq.end(); it++) {
  51. arr[i] = new haffnode;
  52. arr[i]->sym = (it)->first;
  53. arr[i]->freq = (it)->second;
  54. arr[i]->left = NULL;
  55. arr[i]->right = NULL;
  56. i++;
  57. }
  58. size = fq.size();
  59. return (arr);
  60. }
  61. void dgout(haffnode **arr, int size, int offset) {
  62. for (int i = 0 + offset; i < size; i++)
  63. cout << (arr[i]->sym == '\0' ? '0' : arr[i]->sym) << ":" << arr[i]->freq << " ";
  64. cout << endl;
  65. }
  66. haffnode *embrace_node(haffnode *first, haffnode *second) {
  67. haffnode *one = new haffnode;
  68. one->freq = first->freq;
  69. one->left = first->left;
  70. one->right = first->right;
  71. one->sym = first->sym;
  72.  
  73. haffnode *two = new haffnode;
  74. two->freq = second->freq;
  75. two->left = second->left;
  76. two->right = second->right;
  77. two->sym = second->sym;
  78.  
  79. haffnode *general = new haffnode;
  80. general->left = one;
  81. general->right = two;
  82. general->freq = first->freq + second->freq;
  83. general->sym = '\0';
  84.  
  85. return (general);
  86. }
  87. void set_interval(int cnt) {
  88. for (int i = 0; i < cnt; i++)
  89. cout << " ";
  90.  
  91. }
  92. void print_tree(haffnode *first, int lvl) {
  93. if (!first)
  94. return;
  95. print_tree(first->right, lvl+1);
  96. set_interval(lvl*8);
  97. cout << (first->sym == '\0' ? '*' : first->sym) << ":" << first->freq << endl;
  98. print_tree(first->left, lvl+1);
  99. }
  100. void get_code(haffnode *first, char symb, vector <int> &answ) {
  101. if (finded) return;
  102. if (first == NULL) return;
  103. if (first->sym == symb) {
  104. finded = 1;
  105. return;
  106. }
  107.  
  108. answ.push_back(0);
  109. get_code(first->left, symb, answ);
  110. if (finded) return;
  111. answ.pop_back();
  112.  
  113. answ.push_back(1);
  114. get_code(first->right, symb, answ);
  115. if (finded) return;
  116. answ.pop_back();
  117. }
  118.  
  119. int main(void) {
  120. int size;
  121. haffnode **list = get_frequences(size);
  122.  
  123. int k = 0;
  124. int offset = 0;
  125. haffnode *first;
  126. while (k < size - 1) {
  127. dgout(list, size - 1, offset);
  128. qusort(list, offset, size - 1);
  129. first = embrace_node(list[0 + offset], list[1 + offset]);
  130. offset++;
  131. list[offset] = first;
  132. k++;
  133. }
  134. print_tree(first, 0);
  135.  
  136. char tmp;
  137. FILE *inp = fopen("hin", "r");
  138. ofstream otp("hout");
  139. ofstream tbl("htable");
  140.  
  141. vector <int> vec;
  142. while (fscanf(inp, "%c", &tmp) != -1) {
  143. if ((tmp == '\0')||(tmp == '\n'))
  144. continue;
  145.  
  146. vec.clear();
  147. get_code(first, tmp, vec);
  148. for (int i = 0; i < vec.size(); i++)
  149. otp << vec[i];
  150. finded = 0;
  151. }
  152. otp << endl;
  153.  
  154. char c;
  155. for (int i = 0; i < 127; i++) {
  156. finded = 0;
  157. c = (char)i;
  158. vec.clear();
  159. get_code(first, c, vec);
  160. if (!vec.size())
  161. continue;
  162. tbl << "| " << c << " | ";
  163. for (int i = 0; i < vec.size(); i++)
  164. tbl << vec[i];
  165. tbl << " |" << endl;
  166. finded = 0;
  167. }
  168.  
  169. return 0;
  170. }

Ссылка на данный код:

На главную страницу сервиса обмена кодом »