Guest User

Untitled

a guest
May 22nd, 2019
63
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. typedef struct wezel_t {
  5. struct wezel_t *left, *right;
  6. int freq;
  7. char c;
  8. } *wezel;
  9.  
  10. struct wezel_t pool[256] = {{0}};
  11. wezel kolejka[255], *q = kolejka - 1;
  12. int n_wezly=0, k_koniec=1;
  13. char *code[128] = {0}, buf[1024];
  14.  
  15. wezel nowy_wezel(int freq, char c, wezel a, wezel b)
  16. {
  17. wezel n = pool + n_wezly++;
  18. if (freq) n->c = c, n->freq = freq;
  19. else {
  20. n->left = a, n->right = b;
  21. n->freq = a->freq + b->freq;
  22. }
  23. return n;
  24. }
  25.  
  26. void k_dodaj(wezel n)
  27. {
  28. int j, i = k_koniec++;
  29. while ((j = i / 2)) {
  30. if (q[j]->freq <= n->freq) break;
  31. q[i] = q[j], i = j;
  32. }
  33. q[i] = n;
  34. }
  35.  
  36. wezel k_usun()
  37. {
  38. int i, l;
  39. wezel n = q[i = 1];
  40.  
  41. if (k_koniec < 2) return 0;
  42. k_koniec--;
  43. while ((l = i * 2) < k_koniec) {
  44. if (l + 1 < k_koniec && q[l + 1]->freq < q[l]->freq) l++;
  45. q[i] = q[l], i = l;
  46. }
  47. q[i] = q[k_koniec];
  48. return n;
  49. }
  50.  
  51. void kodowanie(wezel n, char *s, int len)
  52. {
  53. static char *out = buf;
  54. if (n->c) {
  55. s[len] = 0;
  56. strcpy(out, s);
  57. code[n->c] = out;
  58. out += len + 1;
  59. return;
  60. }
  61.  
  62. s[len] = '0'; kodowanie(n->left, s, len + 1);
  63. s[len] = '1'; kodowanie(n->right, s, len + 1);
  64. }
  65.  
  66. void start(const char *s)
  67. {
  68. int i, freq[128] = {0};
  69. char c[16];
  70.  
  71. while (*s) freq[(int)*s++]++;
  72.  
  73. for (i = 0; i < 128; i++)
  74. if (freq[i]) k_dodaj(nowy_wezel(freq[i], i, 0, 0));
  75.  
  76. while (k_koniec > 2)
  77. k_dodaj(nowy_wezel(0, 0, k_usun(), k_usun()));
  78.  
  79. kodowanie(q[1], c, 0);
  80. }
  81.  
  82. void kodowanie1(const char *s, char *out)
  83. {
  84. while (*s)
  85. {
  86. strcpy(out, code[*s]);
  87. out += strlen(code[*s++]);
  88. }
  89. }
  90.  
  91. void dekodowanie(const char *s, wezel t)
  92. {
  93. wezel n = t;
  94. while (*s) {
  95. if (*s++ == '0') n = n->left;
  96. else n = n->right;
  97.  
  98. if (n->c) putchar(n->c), n = t;
  99. }
  100.  
  101. putchar('\n');
  102. if (t != n) printf("zle dane\n");
  103. }
  104.  
  105. int main(void)
  106. {
  107. int a;
  108.  
  109. puts("podaj a: 1-kodowanie, 2-dekodowanie");
  110. scanf("%d", &a);
  111.  
  112. const char *str = "nasz tekst", buf[1024];
  113.  
  114. start(str);
  115. for (int i = 0; i < 128; i++)
  116. if (code[i]) printf("%c: %s\n", i, code[i]);
  117.  
  118. if(a==1)
  119. {
  120. kodowanie1(str, buf);
  121. printf("zakodowane: %s\n", buf);
  122. dekodowanie(buf, q[1]);
  123. }
  124.  
  125. if(a==2)
  126. {
  127. kodowanie1(str, buf);
  128. printf("odkodowane: ");
  129. dekodowanie(buf, q[1]);
  130. }
  131.  
  132.  
  133. return 0;
  134. }
RAW Paste Data