Huffman's data compression technique coding in C / C++ Language needed? plz post the coding..?

Question

I am Unable to design the coding part for data compression technique, So Please post the coding of Data compression Huffman's Technique in c or C++ language. Please post it..

Answer 1

Here is the reasymade code for you. At the end, it will print the weight and corresponding huffman code. Coma back to me if you got any doubt.

#include
#include
#include
#include

struct tree_node
{
float weight;
char code[100];
struct tree_node *left_child;
struct tree_node *right_child;
};

struct link_node
{
tree_node *current_tree_node;
struct link_node *next_node;
struct link_node *previous_node;
};

void insearch(tree_node *current_tree);
void assign_codes(tree_node *current_tree,int i,char *c);

void main()
{
int number_of_elements = 4;
float a[7] = {0.5,0.25,0.125,0.125,0.1,0.2,0.1};

clrscr();
if(number_of_elements < 3)
{
printf("useless input");
return;
}


link_node *root = new(link_node);

root->current_tree_node = NULL;
root->next_node = NULL;
root->previous_node=NULL;
link_node *current;
current = root;

//creating the forest with each tree as a single node
for(int i = 0;i<=number_of_elements-1;i++)
{
tree_node *first_node = new(tree_node);
first_node->weight = a[i];
strcpy(first_node->code,"");
first_node->left_child = NULL;
first_node->right_child = NULL;

current->current_tree_node=first_node;
link_node *next = new(link_node);
current->next_node = next;
next->previous_node=current;
current = current->next_node;
current->next_node = NULL;
//printf("number %d i weight %f \n",i,a[i]);
}

current = current->previous_node;
free(current->next_node);
current->next_node = NULL;
//our forest is ready

while(root->next_node!=NULL)//continue till one node remains in forest
{
//first find out two smallest nodes to create a new bigger node
link_node *smallest1,*smallest2;
if(root->current_tree_node->weight < root->next_node->current_tree_node->weight)
{
smallest1 = root;
smallest2 = root->next_node;
}
else
{
smallest1 = root->next_node;
smallest2 = root;
}

/*printf("smallest1 and smallest2 %f %f \n",
smallest1->current_tree_node->weight,
smallest2->current_tree_node->weight
);*/

//This is to find out the two smallest nodes
current=root->next_node->next_node;
if(root->next_node->next_node!=NULL)
do
{
if (smallest1->current_tree_node->weight > current->current_tree_node->weight)
{
smallest2 = smallest1;
smallest1 = current;
}
else if (smallest2->current_tree_node->weight > current->current_tree_node->weight)
smallest2 = current;
current=current->next_node;
}
while(current!=NULL);


/*printf("smallest1 %u and smallest2 %u %f %f \n",smallest1,smallest2,
smallest1->current_tree_node->weight,
smallest2->current_tree_node->weight
);*/


//smallest1 and smallest2 are two smallest nodes
//now we will create a node temp_node and we will put smallest1
//and smallest2 as its child nodes
tree_node *temp_node = new(tree_node);
temp_node->weight = smallest1->current_tree_node->weight + smallest2->current_tree_node->weight;
strcpy(temp_node->code,"");
temp_node->left_child = smallest1->current_tree_node;
temp_node->right_child = smallest2->current_tree_node;

link_node *temp_link_node = new(link_node);
temp_link_node->current_tree_node = temp_node;

//if only two nodes are there then we are done
if(root->next_node->next_node==NULL)
{
root = temp_link_node;
root->next_node=NULL;
root->previous_node=NULL;
free(smallest1);
free(smallest2);
//printf("inside root \n");
//getch();
}
else
{
//delete smallest1 and smallest2 from original forest
if(smallest1->previous_node != NULL)
smallest1->previous_node->next_node = smallest1->next_node;
else root = root->next_node;
if(smallest1->next_node != NULL)
smallest1->next_node->previous_node = smallest1->previous_node;
else smallest1->previous_node->next_node = NULL;

if(smallest2->previous_node != NULL)
smallest2->previous_node->next_node = smallest2->next_node;
else root = root->next_node;
if(smallest2->next_node != NULL)
smallest2->next_node->previous_node = smallest2->previous_node;
else smallest2->previous_node->next_node = NULL;

free(smallest1);
free(smallest2);

//add the temp_node at the end of forest
current = root;
while(current->next_node!=NULL) current=current->next_node;
temp_link_node->previous_node = current;
temp_link_node->next_node=NULL;
current->next_node = temp_link_node;
}

/*current=root;
while(current!=NULL)
{
printf(" %u %f ",current,current->current_tree_node->weight);
current=current->next_node;
}
printf("pass complete \n");
getch();*/
}

//now scan the tree and assign the code to each node

char code[100];
assign_codes(root->current_tree_node,0,code);
//again scan the tree and print the code for the leaf nodes
insearch(root->current_tree_node);

getch();

//print the list
/*current=root;
while(current!=NULL)
{
printf(" weight of this node %f \n",current->current_tree_node->weight);
current=current->next_node;
getchar();
} */

}



void insearch(tree_node *current_tree)
{
if(current_tree == NULL) return;
insearch(current_tree->left_child);
if((current_tree->left_child == NULL) && (current_tree->right_child == NULL))
printf(" %f %s\n",current_tree->weight,current_tree->code);
insearch(current_tree->right_child);
return;
}

void assign_codes(tree_node *current_tree,int i,char *c)
{
if(current_tree == NULL)
{
i--;
*(c+i) = '\0';
return;
}

*(c+i)='0';*(c+i+1)='\0';
i++;
assign_codes(current_tree->left_child,i,c);


i--;
*(c+i)='\0';
strcpy(current_tree->code,c);


*(c+i)='1';
*(c+i+1)='\0';
i++;
assign_codes(current_tree->right_child,i,c);


i--;
*(c+i)='\0';
return;
}

Answer 2

will a pseudo code work for you? I can write you a pseudo code.