SHARE
TWEET

Untitled

a guest Oct 13th, 2019 88 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. // C program for Huffman Coding
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. // This constant can be avoided by explicitly
  7. // calculating height of Huffman Tree
  8. #define MAX_TREE_HT 100
  9.  
  10. // A Huffman tree node
  11. struct MinHeapNode {
  12.  
  13.     // One of the input characters
  14.     char data;
  15.  
  16.     // Frequency of the character
  17.     unsigned freq;
  18.  
  19.     // Left and right child of this node
  20.     struct MinHeapNode *left, *right;
  21. };
  22.  
  23. // A Min Heap:  Collection of
  24. // min-heap (or Huffman tree) nodes
  25. struct MinHeap {
  26.  
  27.     // Current size of min heap
  28.     unsigned size;
  29.  
  30.     // capacity of min heap
  31.     unsigned capacity;
  32.  
  33.     // Array of minheap node pointers
  34.     struct MinHeapNode **array;
  35. };
  36.  
  37. // A utility function allocate a new
  38. // min heap node with given character
  39. // and frequency of the character
  40. struct MinHeapNode *newNode(char data, unsigned freq) {
  41.     struct MinHeapNode *temp
  42.             = (struct MinHeapNode *) malloc
  43.                     (sizeof(struct MinHeapNode));
  44.  
  45.     temp->left = temp->right = NULL;
  46.     temp->data = data;
  47.     temp->freq = freq;
  48.  
  49.     return temp;
  50. }
  51.  
  52. // A utility function to create
  53. // a min heap of given capacity
  54. struct MinHeap *createMinHeap(unsigned capacity) {
  55.  
  56.     struct MinHeap *minHeap
  57.             = (struct MinHeap *) malloc(sizeof(struct MinHeap));
  58.  
  59.     // current size is 0
  60.     minHeap->size = 0;
  61.  
  62.     minHeap->capacity = capacity;
  63.  
  64.     minHeap->array
  65.             = (struct MinHeapNode **) malloc(minHeap->
  66.             capacity * sizeof(struct MinHeapNode *));
  67.     return minHeap;
  68. }
  69.  
  70. // A utility function to
  71. // swap two min heap nodes
  72. void swapMinHeapNode(struct MinHeapNode **a,
  73.                      struct MinHeapNode **b) {
  74.  
  75.     struct MinHeapNode *t = *a;
  76.     *a = *b;
  77.     *b = t;
  78. }
  79.  
  80. // The standard minHeapify function.
  81. void minHeapify(struct MinHeap *minHeap, int idx) {
  82.  
  83.     int smallest = idx;
  84.     int left = 2 * idx + 1;
  85.     int right = 2 * idx + 2;
  86.  
  87.     if (left < minHeap->size && minHeap->array[left]->
  88.             freq < minHeap->array[smallest]->freq)
  89.         smallest = left;
  90.  
  91.     if (right < minHeap->size && minHeap->array[right]->
  92.             freq < minHeap->array[smallest]->freq)
  93.         smallest = right;
  94.  
  95.     if (smallest != idx) {
  96.         swapMinHeapNode(&minHeap->array[smallest],
  97.                         &minHeap->array[idx]);
  98.         minHeapify(minHeap, smallest);
  99.     }
  100. }
  101.  
  102. // A utility function to check
  103. // if size of heap is 1 or not
  104. int isSizeOne(struct MinHeap *minHeap) {
  105.  
  106.     return (minHeap->size == 1);
  107. }
  108.  
  109. // A standard function to extract
  110. // minimum value node from heap
  111. struct MinHeapNode *extractMin(struct MinHeap *minHeap) {
  112.  
  113.     struct MinHeapNode *temp = minHeap->array[0];
  114.     minHeap->array[0]
  115.             = minHeap->array[minHeap->size - 1];
  116.  
  117.     --minHeap->size;
  118.     minHeapify(minHeap, 0);
  119.  
  120.     return temp;
  121. }
  122.  
  123. // A utility function to insert
  124. // a new node to Min Heap
  125. void insertMinHeap(struct MinHeap *minHeap,
  126.                    struct MinHeapNode *minHeapNode) {
  127.  
  128.     ++minHeap->size;
  129.     int i = minHeap->size - 1;
  130.  
  131.     while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
  132.  
  133.         minHeap->array[i] = minHeap->array[(i - 1) / 2];
  134.         i = (i - 1) / 2;
  135.     }
  136.  
  137.     minHeap->array[i] = minHeapNode;
  138. }
  139.  
  140. // A standard function to build min heap
  141. void buildMinHeap(struct MinHeap *minHeap) {
  142.  
  143.     int n = minHeap->size - 1;
  144.     int i;
  145.  
  146.     for (i = (n - 1) / 2; i >= 0; --i)
  147.         minHeapify(minHeap, i);
  148. }
  149.  
  150. // A utility function to print an array of size n
  151. void printArr(int arr[], int n) {
  152.     int i;
  153.     for (i = 0; i < n; ++i)
  154.         printf("%d", arr[i]);
  155.  
  156.     printf("\n");
  157. }
  158.  
  159. // Utility function to check if this node is leaf
  160. int isLeaf(struct MinHeapNode *root) {
  161.  
  162.     return !(root->left) && !(root->right);
  163. }
  164.  
  165. // Creates a min heap of capacity
  166. // equal to size and inserts all character of
  167. // data[] in min heap. Initially size of
  168. // min heap is equal to capacity
  169. struct MinHeap *createAndBuildMinHeap(char data[], int freq[], int size) {
  170.  
  171.     struct MinHeap *minHeap = createMinHeap(size);
  172.  
  173.     for (int i = 0; i < size; ++i)
  174.         minHeap->array[i] = newNode(data[i], freq[i]);
  175.  
  176.     minHeap->size = size;
  177.     buildMinHeap(minHeap);
  178.  
  179.     return minHeap;
  180. }
  181.  
  182. // The main function that builds Huffman tree
  183. struct MinHeapNode *buildHuffmanTree(char data[], int freq[], int size) {
  184.     struct MinHeapNode *left, *right, *top;
  185.  
  186.     // Step 1: Create a min heap of capacity
  187.     // equal to size.  Initially, there are
  188.     // modes equal to size.
  189.     struct MinHeap *minHeap = createAndBuildMinHeap(data, freq, size);
  190.  
  191.     // Iterate while size of heap doesn't become 1
  192.     while (!isSizeOne(minHeap)) {
  193.  
  194.         // Step 2: Extract the two minimum
  195.         // freq items from min heap
  196.         left = extractMin(minHeap);
  197.         right = extractMin(minHeap);
  198.  
  199.         // Step 3:  Create a new internal
  200.         // node with frequency equal to the
  201.         // sum of the two nodes frequencies.
  202.         // Make the two extracted node as
  203.         // left and right children of this new node.
  204.         // Add this node to the min heap
  205.         // '$' is a special value for internal nodes, not used
  206.         top = newNode('$', left->freq + right->freq);
  207.  
  208.         top->left = left;
  209.         top->right = right;
  210.  
  211.         insertMinHeap(minHeap, top);
  212.     }
  213.  
  214.     // Step 4: The remaining node is the
  215.     // root node and the tree is complete.
  216.     return extractMin(minHeap);
  217. }
  218.  
  219. // Prints huffman codes from the root of Huffman Tree.
  220. // It uses arr[] to store codes
  221. void printCodes(struct MinHeapNode *root, int arr[], int top) {
  222.  
  223.     // Assign 0 to left edge and recur
  224.     if (root->left) {
  225.  
  226.         arr[top] = 0;
  227.         printCodes(root->left, arr, top + 1);
  228.     }
  229.  
  230.     // Assign 1 to right edge and recur
  231.     if (root->right) {
  232.  
  233.         arr[top] = 1;
  234.         printCodes(root->right, arr, top + 1);
  235.     }
  236.  
  237.     // If this is a leaf node, then
  238.     // it contains one of the input
  239.     // characters, print the character
  240.     // and its code from arr[]
  241.     if (isLeaf(root)) {
  242.  
  243.         printf("%c: ", root->data);
  244.         printArr(arr, top);
  245.     }
  246. }
  247.  
  248. // The main function that builds a
  249. // Huffman Tree and print codes by traversing
  250. // the built Huffman Tree
  251. void HuffmanCodes(char data[], int freq[], int size) {
  252.     // Construct Huffman Tree
  253.     struct MinHeapNode *root
  254.             = buildHuffmanTree(data, freq, size);
  255.  
  256.     // Print Huffman codes using
  257.     // the Huffman tree built above
  258.     int arr[MAX_TREE_HT], top = 0;
  259.  
  260.     printCodes(root, arr, top);
  261. }
  262.  
  263. // Driver program to test above functions
  264. int main() {
  265.     FILE *fp;
  266.  
  267.     fp = fopen("/home/tj/CLionProjects/untitled/test.txt", "r");
  268.     if (fp == NULL) {
  269.         printf("file does not exist");
  270.         exit(1);
  271.     }
  272.  
  273.     /* a buffer to hold the count of characters 0,...,256; it is
  274.      * initialized to zero on every element */
  275.     int count[256] = {0};
  276.  
  277.     char words[256];
  278.  
  279.     int freq[256];
  280.     /* loop counter */
  281.     int k;
  282.  
  283.     /* a holder for each character (stored as int) */
  284.     int c;
  285.     int counter =0;
  286.  
  287.     /* for as long as we can get characters... */
  288.     while ((c = fgetc(fp))) {
  289.  
  290.         /* break if end of file */
  291.         if (c == EOF) break;
  292.  
  293.         /* otherwise add one to the count of that particular character */
  294.         count[c] += 1;
  295.         counter++;
  296.     }
  297.  
  298.     /* now print the results; only if the count is different from
  299.      * zero */
  300.     for (k = 0; k < 256; k++) {
  301.         if (count[k] > 0) {
  302.             words[k] = k;
  303.             freq[k] = count[k];
  304.             printf("char %c occurs %d times\n", k, count[k]);
  305.         }
  306.     }
  307. /* close the file */
  308.     fclose(fp);
  309.  
  310.     int size = sizeof(words) / sizeof(words[0]);
  311.  
  312.     HuffmanCodes(words, count, size);
  313.  
  314.     return 0;
  315. }
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