Question

C language huffman

This exercise will familiarize you with linked lists, which you will need for a subsequent programming Getting Started assignment Overview Requirements Getting Started Submit Start by getting the files. Type 264get hw13 and then cd hw13 from bash. Pre-tester You will get the following files: Q&A Updates 1. huffman.h: An empty header file, you have to define your own functions in this homework. 2. huffman.c: An empty c file, you have to define your own functions in this homework. 3. huffman_main.c: You will use self defined functions to implement the huffman coding in this file. See requirements for detail 4. examples: A folder with examples of input and output file. Overview This exercise will familiarize you with linked lists and trees, which would be useful for HW14. Specifically, you will learn 1. To create and manipulate linked lists and trees. 2. To learn to free the memory associated with a linked list and a tree. Please read the explanation of huffman coding. This assignment and HW14 deals with Huffman coding, and in particular, it deals with the construction of a Huffman coding tree. Therefore, please read the section on "Huffman Coding" before you proceed with the remainder of this homework description. READ THE huffman coding BEFORE YOU PROCEED.

Answer 1

Code implemented in C programming

Note: Comments are written for code explanation

Filename: huffman.c

#include "huffman.h"
#include<stdio.h>
#include<stdlib.h>

int cmp_int(int value1, int value2){  
   return value1-value2;  
}

long int* asciicount_fn(long int* asciicount, FILE* fp){
   unsigned char ch = 0;
   do{  
       ch = fgetc(fp);
       if(feof(fp)){
           break;
       }
       asciicount[ch]++;
   }while(ch!=EOF);
   return asciicount;
}

Node* frequency_rank(long int* asciicount){
   Node* head = NULL ;
   for(int i=0;i<256;i++){
       if(asciicount[i]!=0){
           head = _pq_enqueue(&head,i,asciicount[i],cmp_int);
       }  
   }
   return head;  
}

Node *_pq_enqueue(Node **pq, int character, long int freq_ct, int (*cmp_fn)(int, int))  
{  
   Node* new = malloc(sizeof(*new));
   if(new == NULL){
       return NULL;
   }
   TreeNode* new_tn = malloc(sizeof(*new_tn));   //allocate a new node for the new_object to insert
   if(new_tn==NULL){               //failure allocate
       return NULL;
   }
   new_tn->ch =(unsigned char)character;
   new_tn->freq = freq_ct;      
   new_tn->left = NULL;
   new_tn->right = NULL;
   new->t_node = new_tn;

   if((*pq) == NULL){           //if its an empty list, the new node become the first node
       new->next = NULL;
       *pq = new;
       return *pq;
   }  
   if(cmp_fn((*pq)->t_node->freq,freq_ct)>0){
       new->next = *pq;
       *pq = new;  
       return *pq;
   }

   else{  
       Node* head = *pq;//keep head stay at the beginning of the linked_list
       Node* curr = *pq;

       while(((curr->next!=NULL)&&(cmp_fn(curr->next->t_node->freq,freq_ct)<0))){   //whether reach the end of the linked list or inserted in the middle
           curr=curr->next;
       }

       if((curr->next!=NULL)&&(cmp_fn(curr->next->t_node->freq,freq_ct)==0)){
           if(curr->next->next != NULL){
               while(curr->next->t_node->freq==curr->next->next->t_node->freq){
                   curr=curr->next;
                   if(curr->next->next==NULL){
                       break;
                   }
               }
           }
           if(cmp_fn((int)(curr->next->t_node->ch),character)<0){

               new->next = curr->next->next;
               curr->next->next = new;
               return head;
           }
       }
       new->next = curr->next;
       curr->next = new;
       return head;
   }

}

void _destroy_fn(Node *list, void (*destroy_fn)(TreeNode*))
{
   do{
       Node* head = list->next;
       Node* trash = list;       //break the first node from the list
       list->next = NULL;      
       destroy_fn(trash->t_node);      
       free(list);           //free it
       list = head;
   }while(list!=NULL);
   return;
}

Node *_pq_dequeue(Node **pq)
{
   if(*pq == NULL){
       return NULL;
   }
   else if(((*pq)->next==NULL)){   //move the first node and assign NULL to pq.
       Node* curr = *pq;
       *pq = NULL;
       return curr;

   }
   else{
       Node* curr = *pq;
       Node* consq = (*pq)->next;
       *pq = consq;
       curr->next = NULL;
       return curr;
   }
}

Node* build_tree(Node **pq)
{
  
while((*pq)->next!=NULL){
  
       Node* junc_n = malloc(sizeof(*junc_n));
       if(junc_n==NULL){
           return NULL;
       }
       TreeNode* junc_tn = malloc(sizeof(*junc_tn));
       if(junc_tn == NULL){
           return NULL;
       }
       Node* child_a = _pq_dequeue(pq);
       Node* child_b = _pq_dequeue(pq);
       junc_tn->freq = child_a->t_node->freq + child_b->t_node->freq;
       junc_tn->left = child_a->t_node;
       junc_tn->right = child_b->t_node;
       free(child_a);
       free(child_b);
       junc_n->t_node = junc_tn;
       tree_enqueue(pq,junc_n);  
   }
   return *pq;
}

Node* tree_enqueue(Node** pq, Node* branch){
   if((*pq) == NULL){           //if its an empty list, the new node become the first node
       branch->next = NULL;
       *pq = branch;
       return *pq;
   }
   if(((*pq)->t_node->freq)>(branch->t_node->freq)){
       branch->next = *pq;  
       *pq = branch;
       return *pq;      
   }
   else{
       Node* head = *pq;//keep head stay at the beginning of the linked_list
       Node* curr = *pq;
       while((curr->next!=NULL)&&(curr->next->t_node->freq <= branch->t_node->freq)){   //whether reach the end of the linked list or inserted in the middle
           curr=curr->next;
       }
       branch->next = curr->next;
       curr->next = branch;
       return head;
   }      
}

void huffman_code(TreeNode* root, char* array, int index, FILE* fpe){
   index++;
   if((root->left==NULL)&&(root->right==NULL)){
       array[index] = root->ch;  
       fprintf(fpe,"%c%c",array[index],':');
       for(int i = 0;i<=index-1;i++){
           fprintf(fpe,"%c",array[i]);
       }
       fprintf(fpe,"\n");
   }
   else{
       array[index] = '0';
       huffman_code(root->left,array,index,fpe);  
       array[index] = '1';
       huffman_code(root->right,array,index,fpe);
   }
}

2 include "huffman.h" #include<stdio.h> #include<stdlib.h> 00 VODW int cmp_int(int valuel, int value2) { return value1-value2; Long int* asciicount_fn(Long int* asciicount, FILE* fp){ unsigned char ch = 0; do{ ch = fgetc(fp); if(feof(fp)){ break; asciicount[ch]++; }while(ch!=EOF); return asciicount; Node* frequency rank(Long int* asciicount) { Node* head = NULL; for(int i=0;i<256;i++){ if(asciicount[i]!=0){ head = __pq_enqueue(&head, i, asciicount[i],cmp_int); return head; Node * _pq_enqueue (Node **pq, int character, Long int freq_ct, int (*cmp_fn) (int, int)) Node* new = malloc(sizeof(*new)); if(new == NULL) { return NULL; 37 TreeNode* new tn = malloc(sizeof(*new tn)); //allocate a new node for the new object to insert if(new_tn==NULL) { /failure allocate return NULL; 40 new_tn->ch =(unsigned char) character; new_tn->freq = freq_ct; new_tn->left = NULL; new_tn->right = NULL; new->t_node = new_tn; //if its an empty list, the new node become the first node if((*pq) == NULL) { new->next = NULL; *pq = new; return *pq; if(cmp_fn((*pq)->t_node->freq, freq_ct)>0){ new->next = *pq; *pq = new; return *pq; else{

else{ Node* head = *pq;//keep head stay at the beginning of the linked_list Node* curr = *pq; while(((curr->next!=NULL) && (cmp_fn(curr->next->t_node->freq, freq_ct)<))){ //whether reach the end of the linked list or inserted in the middle curr=curr->next; if((curr->next!=NULL)&& (cmp_fn(curr->next->t_node->freq, freq_ct)==0){ if(curr->next->next != NULL) { while(curr->next->t_node->freg==curr->next->next->t node->freg) { curr=curr->next; if(curr->next->next==NULL) { break; if(cmp_fn((int)(curr->next->t_node->ch), character)<6){ new->next = curr->next->next; curr->next->next = new; return head; new->next = curr->next; curr->next = new; return head; void _destroy_fn(Node *list, void (*destroy_fn) (TreeNode*)) doſ Node* head = list->next; Node* trash = list; //break the first node from the list list->next = NULL; destroy_fn(trash->t_node); free(list); //free it list = head; }while(list!=NULL); return; Node * _pq_dequeue (Node **p9) the scene if(*pq == NULL) { return NULL; 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 //move the first node and assign NULL to pq. else if(((*pg)->next==NULL)){ Node* curr = *pa; *pq = NULL; return curr; else{ Node* curr = *pq;

114 115 116 117 118 else{ Node* curr = *pq; Node* consq = (*pq)->next; *pq = consq; curr->next = NULL; return curr; 120 121 122 123 124 125 126 Node* build_tree (Node **p9) while((*pq)->next!-NULL) { 127 128 129 130 131 132 Node* junc_n = malloc(sizeof("junc_n)); if(junc_n==NULL) { return NULL; 133 TreeNode* junc_tn = malloc(sizeof(*junc_tn)); if(junc_tn == NULL) { return NULL; 134 135 136 137 138 139 140 141 Node* child_a = _pq_dequeue (pa); Node* child_b = _pq_dequeue (pa); junctn->freq = child_a->t_node->freq + child_b->t_node->freg junc_tn->left = child_a->t_node; junc_tn->right = child_b->t_node; free(child_a); free (child_b); junc_n->t_node = junc_tn; tree_enqueue (pq, junc_n); 142 return *pq; 143 144 145 146 147 148 149 150 151 152 Node* tree_enqueue (Node** pq, Node* branch) { if((*pq) == NULL) { //if its an empty list, the new node become the first node branch->next = NULL; *pq = branch; return *pq; if(((*pg)->t_node->freq)>(branch->t_node->freg)){ branch->next = *pq; *pq = branch; return *pq; 158 159 160 161 else{ Node* head = *pq;//keep head stay at the beginning of the linked_list Node* curr = *pq; while((curr->next!=NULL)&&(curr->next->t_node->freq <= branch->t_node->freq)){ curr=curr->next; //whether reach the end of the linked list or inserted in the middle 162 163 164 165 166 167 168 169 170 171 branch->next = curr->next; curr->next = branch; return head;

free(child_a); free (child_b); junc_n->t_node = junc_tn; tree_enqueue (pq, junc_n); return *pq; 145 146 147 148 149 150 151 Node* tree enqueue (Node** pq, Node* branch) if((*pq) == NULL) { //if its an empty list, the new node become the first node branch->next = NULL; *pq = branch; return *pq; if(((*pg)->t_node->freq)>(branch->t_node->freq)){ branch->next = *pa; *pq = branch; return *pq; 160 161 162 163 else{ Node* head = *pq;//keep head stay at the beginning of the linked_list Node* curr = *pq; while((curr->next!=NULL)&&(curr->next->t_node->freq <= branch->t_node->freq)){ curr=curr->next; //whether reach the end of the linked list or inserted in the middle 166 167 168 branch->next = curr->next; curr->next = branch; return head; 169 170 171 172 174 175 176 void huffman_code(TreeNode* root, char* array, int index, FILE* fpe) { index++; if((root->left==NULL)&&(root->right==NULL)){ array[index] = root->ch; fprintf(fpe, "%c%c", array[index],':'); for(int i = 0;i<=index-1; i++){ fprintf(fpe, "%c", array[i]); fprintf(fpe,"\n"); else{ array[index] = '@'; huffman code(root->left, array, index, fpe); array[index] = '1'; huffman_code(root->right, array, index, fpe); 185 186 187 188 189 190

Filename: huffman.h

#include<stdio.h>
#include<stdlib.h>

typedef struct _TreeNode {
   long int freq; // freq (weight) of char
   unsigned char ch; // character
   struct _TreeNode * left; // left
   struct _TreeNode * right; // right
} TreeNode;

typedef struct _Node {
   TreeNode* t_node;
   struct _Node *next;
} Node;

Node* tree_enqueue(Node**, Node*);
Node* build_tree(Node**);
Node *_pq_enqueue(Node **pq, int, long int freq_ct,int (*cmp_fn)(int,int));
void _destroy_fn(Node *list, void (*destroy_fn)(TreeNode *));
Node *_pq_dequeue(Node **pq);
long int* asciicount_fn(long int*, FILE*);
Node* frequency_rank(long int*);
void huffman_code(TreeNode*,char*, int,FILE*);

1 #include<stdio.h> #include<stdlib.h> ovo AWN typedef struct _TreeNode { Long int freq; // freq (weight) of char unsigned char ch; // character struct TreeNode * left; // left struct _TreeNode * right; // right } TreeNode; 11 V typedef struct _Node { TreeNode* t_node; struct _Node *next; Node; 14 15 17 18 Node* tree_enqueue (Node**, Node*); Node* build_tree (Node**); Node * pq enqueue (Node **pq, int, Long int freq_ct, int (*cmp_fn) (int, int)); void destroy_fn (Node *list, void (*destroy_fn) (TreeNode *)); Node *_pq_dequeue (Node **p9); Long int* asciicount fn(Long int*, FILE); Node* frequency_rank(Long int*); void huffman_code(TreeNode*,char*, int, FILE*); 23 24

Filename: huffman_main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "huffman.h"

void print_node(Node *list, void (*print_fn)(Node*))
{  
   while (list != NULL) {
       // print the memory associated with list->ptr
       print_fn(list);
       // print an arrow
       fprintf(stdout,"->");
       list = list->next;
   }
   // print NULL and a newline after that
   fprintf(stdout, "NULL\n");
}
/*
static void print_fn(Node* list){
   printf("%c:%ld",list->t_node->ch,list->t_node->freq);
}
*/
void write_file(FILE* fp2, Node* head){
   while(head!=NULL){
       fprintf(fp2,"%c",head->t_node->ch);
       fprintf(fp2,"%c",':');
       fprintf(fp2,"%ld",head->t_node->freq);
       fprintf(fp2,"%s","->");  
       head = head->next;
   }  
   fprintf(fp2,"%s","NULL");
   fprintf(fp2,"\n");
}

void destroy_fn(TreeNode* node){
   free(node);
}

void free_tree(TreeNode* node){
   if((node->right!=NULL)){
       free_tree(node->right);
   }
   if(node->left!=NULL){
       free_tree(node->left);
   }
   free(node);
}

int main(int argc, char* argv[])
{
   if(argc!=5){
       return EXIT_FAILURE;
   }
   //Output file1 start
   FILE *fp = fopen(argv[1],"r");
   fseek(fp,0,SEEK_SET);
   if(fp==NULL){
       return EXIT_FAILURE;
   }
   FILE *fpw = fopen(argv[2],"w");
   if(fpw==NULL){
       return EXIT_FAILURE;
   }
   fseek(fpw,0,SEEK_SET);
   long int asciicount[256] = {0};
   asciicount_fn(asciicount,fp);
   for(int i = 0; i<256; i++){
       fprintf(fpw,"%ld\n",asciicount[i]);
   }
   // Output file1 end

   Node* head =NULL;
   head = frequency_rank(asciicount);
   FILE* fp2 = fopen(argv[3],"w");
   write_file(fp2,head);      

//   print_node(head,print_fn);// debugging purpose

   Node* tree_head = NULL;
   tree_head = build_tree(&head);
   TreeNode* root = tree_head->t_node;
   int count = 0;
   while(root->right!= NULL){
       count++;
       root = root->right;
   }

   root = tree_head->t_node;
   char adda;
   char* array = &adda;
   for(int i = 0;i<count;i++){
       array[i] = '\0';
   }
   FILE* fpe = fopen(argv[4],"w");
   int index = -1;
   huffman_code(root,array,index,fpe);     
   free(tree_head);
   free_tree(root);  
   fclose(fp2);  
   fclose(fp);
   fclose(fpw);
   fclose(fpe);
}

#include <stdio.h> #include <stdlib.h> #include <string.h> #include "huffman.h" void print_node (Node *list, void (*print_fn) (Node*)), while (list != NULL) { // print the memory associated with list->ptr print_fn(list); // print an arrow fprintf(stdout,"->"); list = list->next; 15 // print NULL and a newline after that fprintf(stdout, "NULL\n"); 18 static void print_fn (Node* list) { printf("%c:%ld", list->t_node->ch, list->t_node->freq); ode* head), void write_file(FILE* fp2, Node* head) { while(head!=NULL) fprintf(fp2, "%c", head->t_node->ch); fprintf(fp2, "%c",':'); fprintf(fp2,"%ld", head->t_node->freq); fprintf(fp2,"%s","->"); head = head->next; CD2 C fprintf(fp2,"%s", "NULL"); fprintf(fp2,"\n"); void destroy_fn(TreeNode* node) { free(node); 37 void free_tree(TreeNode* node) { if((node->right !=NULL)){ free_tree (node->right); 44 45 if(node->left!=NULL) { free_tree (node->left); 46 free (node); int main(int argc, char* argv[]) if(argc!=5){ return EXIT_FAILURE; //Output filel start FILE *fp = fopen(argv[1],"r"); fseek(fp, 0, SEEK_SET);

if(argc!=5){ return EXIT_FAILURE; //Output file1 start FILE *fp = fopen(argv[1],"r"); fseek(fp, 0,SEEK_SET); if(fp==NULL) { return EXIT_FAILURE; FILE *fpw = fopen(argv[2], "w"); if(fpw==NULL) { return EXIT_FAILURE; fseek(fpw,,SEEK_SET); Long int asciicount[256] = {@}; asciicount_fn(asciicount, fp); for(int i = 0; i<256; i++){ fprintf(fpw, "%d\n", asciicount[i]); // Output file1 end Node* head =NULL; head = frequency_rank(asciicount); FILE* fp2 = fopen(argv[3],"w"); write_file(fp2, head); print_node(head, print_fn);// debugging purpose Node* tree_head = NULL; tree_head = build_tree(&head); TreeNode* root = tree_head->t_node; int count = 0; while(root->right!= NULL) { count++; root = root->right; root = tree_head->t_node; char adda; char* array = &adda; for(int i = 0;i<count;i++){ array[i] = '\0'; 100 101 102 103 FILE* fpe = fopen(argv[4], "w"); int index = -1; huffman_code(root, array, index, fpe); free (tree_head); free_tree (root); fclose(fp2); fclose(fp); fclose(fpw); fclose(fpe); 104 105 106 107

If you like my answer, hit thumbs up. Thank you