I need a full working program of Huffman Algorithm (Data Compression)
implemented in C++.
In other words complete codes for Huffman Algorithm using C++ is
required. I dont need a compiled *.exe program but *.cpp files and
others as possible, I will compiled it my self.
Thanks!

Hi, 

I found several examples, tutorials, and source code using the Huffman
compression. Below you will find links which will bring you to pages
which have these ready for downloading. This first one was very
informative and had the C++ code, the others have various adaptions
but are basically the same thing.

Huffman Trees for Data Compression 
http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=6733&lngWId=3


#include<stdio.h>

#include<string.h>

#include<conio.h>

#include<stdlib.h>

#define MAX 10

struct link

{

            int freq;

            char ch[MAX];

            struct link* right;

            struct link* left;

};

typedef struct link node;

void sort(node *[], int);

node* create(char[], int);

void sright(node *[], int);

void Assign_Code(node*, int [], int);

void Delete_Tree(node *);

main()

{

            node* ptr, * head;

            int i, n, total = 0, u, c[15];

            char str[MAX];

            node* a[12];

            int freq;

            clrscr();

            printf(  "Huffman Algorithm\n");

            printf("\nEnter the no. of letter to be coded:");/*input
the no. of letters*/

            scanf("%d", &n);

            for (i = 0; i < n; i++)

            {

                        printf("Enter the letter &
frequency:");/*input the letter & frequency*/

                        scanf("%s %d", str, &freq);

                        a[i] = create(str, freq);

            }

            while (n > 1)

            {

                        sort(a, n);

                        u = a[0]->freq + a[1]->freq;

                        strcpy(str,a[0]->ch);

                        strcat(str,a[1]->ch);

                        ptr = create(str, u);

                        ptr->right = a[1];

                        ptr->left = a[0];

                        a[0] = ptr;

                        sright(a, n);

                        n--;

            }

            Assign_Code(a[0], c, 0);

            getch();

            Delete_Tree(a[0]);

}

node* create(char a[], int x)

{

            node* ptr;

            ptr = (node *) malloc(sizeof(node));

            ptr->freq = x;

            strcpy( ptr->ch , a);

            ptr->right = ptr->left = NULL;

            return(ptr);

}

void sort(node* a[], int n)

{

            int i, j;

            node* temp;

            for (i = 0; i < n - 1; i++)

                        for (j = i; j < n; j++)

                                    if (a[i]->freq > a[j]->freq)

                                    {

                                                temp = a[i];

                                                a[i] = a[j];

                                                a[j] = temp;

                                    }

}

void sright(node* a[], int n)

{

            int i;

            for (i = 1; i < n - 1; i++)

                        a[i] = a[i + 1];

}

void Assign_Code(node* tree, int c[], int n)

{

            int i;

            if ((tree->left == NULL) && (tree->right == NULL))

            {

                        printf("%s code:", tree->ch);

                        for (i = 0; i < n; i++)

                         {

                          printf("%d", c[i]);

                         }

                        printf("\n");

            }

            else

            {

                        c[n] = 1;

                        n++;

                        Assign_Code(tree->left, c, n);

                        c[n - 1] = 0;

                        Assign_Code(tree->right, c, n);

            }

}

void Delete_Tree(node * root)

{

    if(root!=NULL)

    {

            Delete_Tree(root->left);

            Delete_Tree(root->right);

            free(root);

    }

}




Other links with Algorithm. 

Programmer's Heaven
http://www.programmersheaven.com/zone3/cat855/

Data Compression.info
http://datacompression.info/SourceCode.shtml


Search Used

Huffman Algorithm Compression +"Source Code"
Huffman Algorithm Compression +"Source Code" +"C++"



thanks, 

webadept-ga

---

Clarification of Answer by webadept-ga on 09 Sep 2003 02:22 PDT

Hi again, 

Something I didn't know and just ran across, is apparently bzip uses
the Huffman algorithm, and bzip is open source.

This link shows the Huffman adaption in bzip
http://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/lxr/source/src/util/compress/bzip2/huffman.c

And this site has yet another adaption, with cpp and huff.h files in
the zip.
http://www.devhood.com/tools/tool_details.aspx?tool_id=615

And this project looked interesting on Source forge,  -n-ary Huffman
Template Algorithm. Source and all CPP with Class and H files in the
download
http://sourceforge.net/projects/huffman-ta

And I'll stop here with this one from CodeMonkeyX, which only does
text files, not binary, but is laid out rather well and readable.
http://www.codemonkeyx.net/forums/viewtopic.php?t=207

thanks again, I learned quite a bit about compression going over these
sites and files.

If for some reason one of these doesn't cover your need, which I'm
sure they will, let me know using the Clarification button, and drop a
line as to what you require.

webadpet-ga