HUffman encoding(data compression)
i have a static code of hauffman encoding but i want to write a code that reads a file and calculate frequencies and encode the file. here is my code can any one help me to change it to adaptive code..
Code:
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
const int max=10;
class node
{
public:
int freq;
char ch[10];
node* right;
node* left;
};
node* make_node(char* a, int x)
{
node* nptr= new node;
nptr->freq = x;
strcpy( nptr->ch , a);
nptr->right = nptr->left = NULL;
return nptr;
}
void sort(node* a[], int n)
{
node* tptr;
for (int i = 0; i < n-1 ; i++)
for (int j = i; j < n; j++)
if (a[i]->freq > a[j]->freq)
{
tptr = a[i];
a[i] = a[j];
a[j] = tptr;
}
}
void shift_right(node* a[], int n)
{
for (int i = 1; i < n - 1; i++)
a[i] = a[i + 1];
}
void encode(node* tptr, int c[], int n)
{
if ((tptr->left == NULL) && (tptr->right == NULL))
{
cout<<" code: "<< tptr->ch<<" ";
for (int i = 0; i < n; i++)
{
cout<< c[i];
}
cout<<endl;
}
else
{
c[n] = 1;
n++;
encode(tptr->left, c, n);
c[n - 1] = 0;
encode(tptr->right, c, n);
}
}
void del(node * root)
{
if(root!=NULL)
{
del(root->left);
del(root->right);
delete root;
}
}
int main()
{
node* nptr;
node* head;
node* a[20];
int n,freq,b,c[15];
char str[10];
cout<<"\n\n\tEnter the no.of letter you want to code: " ;
cin>>n;
for (int i = 0; i < n; i++)
{
cout<<"\n\tEnter the string: " ;
cin>>str;
cout<<"\n\tEnter frequency: ";
cin>>freq;
a[i] = make_node(str, freq);
}
while (n > 1)
{
sort(a, n);
b = a[0]->freq + a[1]->freq;
strcpy(str,a[0]->ch);
strcat(str,a[1]->ch);
nptr = make_node(str, b);
nptr->right = a[1];
nptr->left = a[0];
a[0] = nptr;
shift_right(a, n);
n--;
}
encode(a[0], c, 0);
system("pause");
}
