SHARE
TWEET

Untitled

a guest May 22nd, 2019 55 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
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