SHARE
TWEET

Untitled

a guest Jan 21st, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4.  
  5. typedef struct point{
  6.     char letter;
  7.     int freq;
  8.     char huff[50];
  9.     struct point *next;
  10.     struct point *left;
  11.     struct point *right;
  12.     }point_t;
  13.  
  14. point_t *entry;
  15. point_t *start;
  16. point_t *start2;
  17. point_t *root;
  18. point_t *curr;
  19. point_t *prev;
  20. point_t *hold;
  21.  
  22. int to_base10(char chop[]){
  23.     int a,a2,b,prod,prod2,sum=0;
  24.     for(a=0;a<8;a++)
  25.     {
  26.         prod=1;
  27.         switch(chop[a])
  28.         {
  29.             case '1': b=1; break;
  30.             case '0': b=0; break;
  31.         }
  32.         for(a2=a;a2>0;a2--)
  33.         {
  34.             prod=prod*2;
  35.         }
  36.         prod2=b*prod;
  37.         sum=sum+prod2;
  38.     }
  39.     return (sum);
  40. }
  41.  
  42. void to_ascii(char str[], int count,char *argv){
  43.     FILE *ascii;
  44.     int arr[count/8];
  45.     char chop[9];
  46.     int i,j,k,l,ctr;
  47.     for(i=0,l=0;i<count-1;i+=8,l++)
  48.     {
  49.         for(j=i,k=7;j<i+8;j++,k--)
  50.         {
  51.             chop[k]=str[j];
  52.         }
  53.         arr[l]=to_base10(chop);
  54.     }
  55.     ascii=fopen(argv, "w");
  56.     for(ctr=0;ctr<count/8;ctr++)
  57.     {
  58.         fprintf(ascii, "%c", (char)(arr[ctr]));
  59.     }
  60.     fclose(ascii);
  61. }
  62.  
  63. void freq_table(char *argv){
  64.     start=NULL;
  65.     FILE *ascii;
  66.     char ch;
  67.     ascii=fopen(argv, "r");
  68.     while(!feof(ascii))
  69.     {
  70.         ch=getc(ascii);
  71.         if(start==NULL)
  72.         {
  73.             start=(point_t*)malloc(sizeof(point_t));
  74.             start->letter=ch;
  75.             start->freq=1;
  76.             start->next=NULL;
  77.         }
  78.         else
  79.         {
  80.             curr=start;
  81.             while(curr!=NULL)
  82.             {
  83.                 if(ch==curr->letter)
  84.                 {
  85.                     curr->freq=(curr->freq)+1;
  86.                     break;
  87.                 }
  88.                 curr=curr->next;
  89.             }
  90.             if(curr==NULL)
  91.             {
  92.                 entry=(point_t*)malloc(sizeof(point_t));
  93.                 entry->letter=ch;
  94.                 entry->freq=1;
  95.                 entry->next=NULL;
  96.                 curr=start;
  97.                 while(curr!=NULL)
  98.                 {
  99.                     if(entry->letter<curr->letter)
  100.                     {
  101.                         if(curr==start)
  102.                         {
  103.                             entry->next=curr;
  104.                             start=entry;
  105.                         }
  106.                         else
  107.                         {
  108.                             entry->next=curr;
  109.                             prev->next=entry;
  110.                         }
  111.                         break;
  112.                     }
  113.                     prev=curr;
  114.                     curr=curr->next;
  115.                 }
  116.                 if(curr==NULL)
  117.                 {
  118.                     prev->next=entry;
  119.                 }
  120.             }
  121.         }
  122.     }
  123.     curr=start;
  124.     start=start->next;
  125.     curr->next=NULL;
  126.     free(curr);}
  127.  
  128. void sortbyfreq(){
  129.     start2=NULL;
  130.     curr=start;
  131.     while(curr!=NULL)
  132.     {
  133.         hold=curr;
  134.         entry=(point_t*)malloc(sizeof(point_t));
  135.         entry->letter=curr->letter;
  136.         entry->freq=curr->freq;
  137.         entry->next=NULL;
  138.         entry->left=NULL;
  139.         entry->right=NULL;
  140.         if(start2==NULL)
  141.         {
  142.             start2=entry;
  143.         }
  144.         else
  145.         {
  146.             curr=start2;
  147.             while(curr!=NULL)
  148.             {
  149.                 if(entry->freq<=curr->freq)
  150.                 {
  151.                     if(curr==start2)
  152.                     {
  153.                         entry->next=curr;
  154.                         start2=entry;
  155.                     }
  156.                     else
  157.                     {
  158.                         entry->next=curr;
  159.                         prev->next=entry;
  160.                     }
  161.                     break;
  162.                 }
  163.                 prev=curr;
  164.                 curr=curr->next;
  165.             }
  166.             if(curr==NULL)
  167.             {
  168.                 prev->next=entry;
  169.             }
  170.             curr=hold;
  171.         }
  172.         curr=curr->next;
  173.     }
  174. }
  175.  
  176. void huffman_tree(long num){
  177.  
  178.     if(start2->freq==num){}
  179.     else
  180.     {
  181.         root=(point_t*)malloc(sizeof(point_t));
  182.         root->left=start2;
  183.         root->right=start2->next;
  184.         root->freq=(root->left->freq)+(root->right->freq);
  185.         root->next=NULL;
  186.         hold=start2;
  187.         start2=start2->next->next;
  188.         hold->next->next=NULL;
  189.         if(start2==NULL)
  190.         {
  191.             start2=root;
  192.         }
  193.         else
  194.         {
  195.             curr=start2;
  196.             while(curr!=NULL)
  197.             {
  198.                 if(root->freq<=curr->freq)
  199.                 {
  200.                     if(curr==start2)
  201.                     {
  202.                         root->next=curr;
  203.                         start2=root;
  204.                     }
  205.                     else
  206.                     {
  207.                         prev->next=root;
  208.                         root->next=curr;
  209.                     }
  210.                     break;
  211.                 }
  212.                 prev=curr;
  213.                 curr=curr->next;
  214.             }
  215.             if(curr==NULL)
  216.             {
  217.                 prev->next=root;
  218.             }
  219.  
  220.         }
  221.         huffman_tree(num);
  222.     }
  223. }
  224.  
  225. void huffman_encoding(point_t *curr, char encode[], char let, int ctr){
  226.     if(curr==NULL)
  227.     {
  228.         encode[ctr-1]='\0';
  229.         hold=start;
  230.         while(hold!=NULL)
  231.         {
  232.             if(prev->letter==hold->letter)
  233.             {
  234.                 strcpy(hold->huff, encode);
  235.                 break;
  236.             }
  237.             hold=hold->next;
  238.         }
  239.     }
  240.     else
  241.     {
  242.         prev=curr;
  243.         if(ctr==0){}
  244.         else
  245.         {
  246.             encode[ctr-1]=let;
  247.         }
  248.         huffman_encoding(curr->left,encode,'0',ctr+1);
  249.         huffman_encoding(curr->right,encode,'1',ctr+1);
  250.     }
  251. }
  252.  
  253. void to_prefix(char *argv){
  254.     FILE *prefix;
  255.     prefix=fopen(argv, "w");
  256.     curr=start;
  257.     while(curr!=NULL)
  258.     {
  259.         fprintf(prefix, "%c\t%d\t%s\n", curr->letter,curr->freq,curr->huff);
  260.         curr=curr->next;
  261.     }
  262.     fclose(prefix);
  263. }
  264.  
  265. void to_output(char *argv1, char *argv2)
  266. {
  267.     FILE *ascii;
  268.     FILE *output;
  269.     char get;
  270.     ascii=fopen(argv1, "r");
  271.     output=fopen(argv2,"w");
  272.     while(!feof(ascii))
  273.     {
  274.         get=getc(ascii);
  275.         curr=start;
  276.         while(curr!=NULL)
  277.         {
  278.             if(get==curr->letter)
  279.             {
  280.                 fprintf(output,"%s", curr->huff);
  281.                 break;
  282.             }
  283.             curr=curr->next;
  284.         }
  285.     }
  286.     fclose(output);
  287.     fclose(ascii);
  288. }
  289.  
  290. void to_output(char *argv1, char *argv2);
  291.  
  292. int main(int argc, char *argv[])
  293. {
  294.     if(argc!=5)
  295.     {
  296.         printf("HOW TO USE: <input file> <ASCII file> <prefix file> <output file>\n");
  297.         exit(1);
  298.     }
  299.  
  300.     FILE *input;
  301.     char c, encode[50],let;
  302.     int x,y,z,ctr=0;
  303.     long count=0;
  304.     if((input=fopen(argv[1], "r"))==NULL)
  305.     {
  306.         printf("INVALID!\n");
  307.         exit(1);
  308.     }
  309.     while(!feof(input))
  310.     {
  311.         c=getc(input);
  312.         count++;
  313.     }
  314.     char str[count];
  315.     rewind(input);
  316.     while(!feof(input))
  317.     {
  318.         fscanf(input,"%s", str);
  319.     }
  320.     fclose(input);
  321.  
  322.     to_ascii(str,count,argv[2]);
  323.     freq_table(argv[2]);
  324.     sortbyfreq();
  325.     huffman_tree(count/8);
  326.     curr=root;
  327.     huffman_encoding(curr,encode,let,ctr);
  328.     to_prefix(argv[3]);
  329.     to_output(argv[2],argv[4]);
  330. }
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