Wednesday, March 23, 2011

Program for huffman coding

// huff.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include

typedef struct node {
char name[20]; // name of the node
float data;
struct node* right;
struct node* left;
struct node* parent;
struct node* next;
}NODE;

using namespace std;

void display_list(NODE* head) {
if(head) {
cout<<"\nList contents:\n";
NODE* temp = head;
while(temp) {
cout<<"Node : "<name<<" probability:"<data< temp = temp->next;
}
} else {
cout<<"\nEmpty List";
}
}

void find_smallest(NODE* head,NODE** smallest1, NODE** smallest2) {
*smallest1 = NULL;
*smallest2 = NULL;
NODE* t = head;
while(t) {
// Skip the nodes who has parent
if(t->parent) {
t = t->next;
continue;
}

if(!*smallest1) {
*smallest1 = t;
} else if(!*smallest2) {
*smallest2 = t;
} else if(t->data < (*smallest1)->data) {
if ((*smallest1)->data < (*smallest2)->data) {
*smallest2 = *smallest1;
}
*smallest1 = t;
} else if(t->data < (*smallest2)->data) {
*smallest2 = t;
} else {
// Do nothing
}

if(*smallest1 && *smallest2) {
if((*smallest1)->data > (*smallest2)->data) {
NODE* temp = *smallest1;
*smallest1 = *smallest2;
*smallest2 = temp;
}
}
t = t->next;
}
}

void add_element(NODE** head,NODE** e) {
if(!*head) {
*head = *e;
} else {
NODE* t = *head;
while(t->next!=NULL) {
t = t->next;
}
t->next = *e;
}
}

void tree_traversal(NODE* root,char code[20]) {
if(!root) {
return;
}
//cout<<"\n NODE : "<name<<" prob: "<data;
if(root->left==NULL && root->right==NULL) {
cout<<" \nNODE : "<name<<" prob : "<data<<" code: "< return;
}
int len = strlen(code);
if(root->left) {
code[len]='1';
code[len+1]='\0';
tree_traversal(root->left,code);
}
if(root->right) {
code[len]='0';
code[len+1]='\0';
tree_traversal(root->right,code);
}
}


int _tmain(int argc, _TCHAR* argv[])
{
NODE* list = NULL;
float arr[10];
int n;
cout<<"Enter n:";
cin>>n;
for(int i=0; i cin>>arr[i];
// Create a new node and append it to the list
NODE* current = new NODE;
current->data = arr[i];
current->next = NULL;
current->left = NULL;
current->right = NULL;
current->parent = NULL;
current->name[0] = 65+i; current->name[1] = '\0';

// Appending the node to the list
add_element(&list,¤t);
}

// Display the nodes entered by the user along with their probabilities
display_list(list);

NODE* root = NULL;

while(1) {

// Find the 2 smallest elements from the list
NODE* smallest1 = NULL;
NODE* smallest2 = NULL;
find_smallest(list,&smallest1,&smallest2);

if(!smallest2) {
root = smallest1;
break;
}

float small1 = smallest1->data;
float small2 = smallest2->data;
NODE* current = new NODE;
current->data = small1 + small2;
current->left = smallest1;
current->right = smallest2;
current->parent = NULL;
current->next = NULL;
strcpy(current->name,smallest1->name);
strcat(current->name,smallest2->name);

smallest1->parent = current;
smallest2->parent = current;

add_element(&list,¤t);
//cout<<"\n\n LIST: \n\n";
//display_list(list);
}

cout<<"\n\nHuffman code :\n\n";
char code[20];
code[0]='\0';
tree_traversal(root,code);

cout< return 0;
}

No comments:

Post a Comment