SHARE
TWEET

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 node_t {
  5.     struct node_t *left, *right;
  6.     int freq;
  7.     char c;
  8. } *node;
  9.  
  10. struct node_t pool[256] = {{0}};
  11. node qqq[255], *q = qqq - 1;
  12. int n_nodes = 0, qend = 1;
  13. char *code[128] = {0}, buf[1024];
  14.  
  15. node new_node(int freq, char c, node a, node b)
  16. {
  17.     node n = pool + n_nodes++;
  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. /* priority queue */
  27. void qinsert(node n)
  28. {
  29.     int j, i = qend++;
  30.     while ((j = i / 2)) {
  31.         if (q[j]->freq <= n->freq) break;
  32.         q[i] = q[j], i = j;
  33.     }
  34.     q[i] = n;
  35. }
  36.  
  37. node qremove()
  38. {
  39.     int i, l;
  40.     node n = q[i = 1];
  41.  
  42.     if (qend < 2) return 0;
  43.     qend--;
  44.     while ((l = i * 2) < qend) {
  45.         if (l + 1 < qend && q[l + 1]->freq < q[l]->freq) l++;
  46.         q[i] = q[l], i = l;
  47.     }
  48.     q[i] = q[qend];
  49.     return n;
  50. }
  51.  
  52. /* walk the tree and put 0s and 1s */
  53. void build_code(node n, char *s, int len)
  54. {
  55.     static char *out = buf;
  56.     if (n->c) {
  57.         s[len] = 0;
  58.         strcpy(out, s);
  59.         code[n->c] = out;
  60.         out += len + 1;
  61.         return;
  62.     }
  63.  
  64.     s[len] = '0'; build_code(n->left,  s, len + 1);
  65.     s[len] = '1'; build_code(n->right, s, len + 1);
  66. }
  67.  
  68. void init(const char *s)
  69. {
  70.     int i, freq[128] = {0};
  71.     char c[16];
  72.  
  73.     while (*s) freq[(int)*s++]++;
  74.  
  75.     for (i = 0; i < 128; i++)
  76.         if (freq[i]) qinsert(new_node(freq[i], i, 0, 0));
  77.  
  78.     while (qend > 2)
  79.         qinsert(new_node(0, 0, qremove(), qremove()));
  80.  
  81.     build_code(q[1], c, 0);
  82. }
  83.  
  84. void encode(const char *s, char *out)
  85. {
  86.     while (*s) {
  87.         strcpy(out, code[*s]);
  88.         out += strlen(code[*s++]);
  89.     }
  90. }
  91.  
  92. void decode(const char *s, node t)
  93. {
  94.     node n = t;
  95.     while (*s) {
  96.         if (*s++ == '0') n = n->left;
  97.         else n = n->right;
  98.  
  99.         if (n->c) putchar(n->c), n = t;
  100.     }
  101.  
  102.     putchar('\n');
  103.     if (t != n) printf("garbage input\n");
  104. }
  105.  
  106. int main(void)
  107. {
  108.     int i, a;
  109.     const char *str = "this is an example for huffman encoding", buf[1024];
  110. puts("podaj a: 1-kodowanie, 2-dekodowanie");
  111. scanf("%d", &a);
  112.  
  113.     init(str);
  114.     for (i = 0; i < 128; i++)
  115.         if (code[i]) printf("'%c': %s\n", i, code[i]);
  116. if(a==1)
  117. {
  118.     encode(str, buf);
  119.     printf("encoded: %s\n", buf);
  120.     decode(buf, q[1]);
  121. }
  122.     if(a==2)
  123.     {
  124.         encode(str, buf);
  125.         printf("decoded: ");
  126.     decode(buf, q[1]);
  127.     }
  128.  
  129.  
  130.  
  131.     return 0;
  132. }
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