Huffman + kompresja tekstu

Witam!
Mam napisać program, który za pomocą algorytmu Huffmana skompresuje tekst do postaci binarnej. W programie muszę zaimplementować kompresor i dekompresor.

Na razie mam:

Klasę drzewa

class Node
{
    public:
        Node(int k);
        ~Node();
        int getValue();
        void setValue(int val);
        void addToTree(int val);
        void inOrder();
        void postOrder();
        void preOrder();
        
    private:
        Node* left;
        Node* right;
        int value;
};

Funkcja addToTree()

void Node::addToTree(int val)
{
    if(val < value)
    {
        if(left)
            left->addToTree(val);
        else
            left = new Node(val);
    }
    else
    {
        if(right)
            right->addToTree(val);
        else
            right = new Node(val);
    }
}

Funkcję odpowiedzialną za zliczanie wystąpień poszczególnej litery mam.

Ogólnie algorytm Huffmana znam, tylko nie wiem od której strony by się tutaj zabrać...
Ma ktoś jakieś pomysły od czego zacząć? Jak przebudować tą klasę? Ogólnie chodzi mi o jakieś sugestie/pomysły.

Pozdrawiam, Ziem!

podstawa do wyjścia:

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P016

#include <iostream>
#include <string>

using namespace std;

// deklaracja węzła drzewa binarnego
//----------------------------------

struct TBTnode
{
  TBTnode * parent, * left, * right;
  char    c;
};

// deklaracja typu elementu listy
//-------------------------------

struct TlistElement
{
  TlistElement * next, * prev;
  int          key;
  TBTnode      * node;
};

// deklaracja typu klasy listy dwukierunkowej
//-------------------------------------------

class TdoubleList
{
  private:

    TlistElement * front, * back;
    unsigned     cnt;

  public:
           
// konstruktor
//------------

    TdoubleList()
    {
      front = back = NULL;
      cnt   = 0;
    }
    
// Zwraca długość listy
//---------------------

    unsigned size()
    {
      return cnt;
    }

// Dodaje element na początku listy i zwraca jego adres
//-----------------------------------------------------

    TlistElement * push_front(TlistElement * p)
    {
      p->next = front; p->prev = NULL;
      if(front) front->prev = p;
      front = p;
      if(!back) back = front;
      cnt++;
      return front;
    }
    
// Dodaje element na końcu listy i zwraca jego adres
//--------------------------------------------------

    TlistElement * push_back(TlistElement * p)
    {
      if(back) back->next = p;
      p->next = NULL; p->prev = back;
      back = p;
      if(!front) front = back;
      cnt++;
      return back;
    }
    
// Dodaje element p1 za elementem p2 i zwraca adres p1
//----------------------------------------------------

    TlistElement * insert(TlistElement * p1, TlistElement * p2)
    {
      p1->next = p2->next; p1->prev = p2;
      p2->next = p1;
      if(p1->next) p1->next->prev = p1;
      else back = p1;
      cnt++;
      return p1;
    }
    
// Usuwa element z początku listy i zwraca adres usuniętego elementu
//------------------------------------------------------------------

    TlistElement * pop_front()
    {
      TlistElement * p;
      
      if(front)
      {
        p = front;
        front = front->next;
        if(!front) back = NULL;
        else front->prev = NULL;
        cnt--;
        return p;
      }
      else return NULL;     
    }
    
// Usuwa element z końca listy i zwraca adres usuniętego elementu
//---------------------------------------------------------------

    TlistElement * pop_back()
    {
      TlistElement * p;
      
      if(back)
      {
        p = back;
        if(p == front) front = back = NULL;
        else
        {
          back = back->prev;
          back->next = NULL;
        };
        cnt--;
        return p;
      }
      else return NULL;
    }
    
// usuwa z listy element p i zwraca adres usuniętego elementu

    TlistElement * erase(TlistElement * p)
    {
      TlistElement * p1;
      
      if(p->prev) p->prev->next = p->next;
      else front = p->next;
      if(p->next) p->next->prev = p->prev;
      else back = p->prev;
      cnt--;
      return p;
    } 

// zwraca n-ty element listy. Jeśli lista posiada mniej niż n elementów,
// zwraca NULL. Elementy numerujemy od 1.
//----------------------------------------------------------------------

    TlistElement * index(unsigned n)
    {
      TlistElement * p;
      
      if((!n) || (n > cnt)) return NULL;
      else if(n == cnt) return back;
      else if(n < cnt / 2)
      {
        p = front;
        while(--n) p = p->next;
        return p;
      }
      else
      {
        p = back;
        while(cnt > n++) p = p->prev;
        return p;
      }  
    }

// wyświetla kolejno klucze wszystkich elementów listy
//----------------------------------------------------

    void showKeys()
    {
      TlistElement * p;
      
      if(!front) cout << "Lista jest pusta." << endl;
      else
      {
        p = front;
        while(p)
        {
          if(p->node) 
            cout << p->node->c << " : " << p->key << endl;
          p = p->next;
        }
      }
    }

// Wyszukuje na liście dwa najmniejsze elementy
//---------------------------------------------

    void find2min(TlistElement * &p1, TlistElement * &p2)
    {
      TlistElement * p;

      p1 = front; p2 = front->next;
      if(p1->key > p2->key)
      {
        TlistElement * x;
        x = p1; p1 = p2; p2 = x;
      }
      p = front->next->next;
      while(p)
      {
        if(p->key < p2->key)
        {
          p2 = p;
          if(p1->key > p2->key)
          {
            TlistElement * x;
            x = p1; p1 = p2; p2 = x;
          }      
        }
        p = p->next;
      }     
    }    
};

// Funkcja rekurencyjne przechodzenia drzewa binarnego
//----------------------------------------------------

void inorder(TBTnode * n, char c[], int lenc)
{
  if(!(n->left))
  {
    cout << n->c << " : ";
    for(int i = 0; i < lenc; i++) cout << c[i];
    cout << endl;
  }
  else
  {
    c[lenc] = '0'; inorder(n->left,c,lenc + 1);
    c[lenc] = '1'; inorder(n->right,c,lenc + 1);    
  }
}

//******************************************************
//**   Przykładowa implementacja algorytmu Huffmana   **
//******************************************************

main()
{
  int i;
    
// Ze standardowego wejścia odczytujemy wiersz znaków

  string line;  // przechowuje odczytany tekst
  
  getline(cin,line);
  
// Zliczamy liczbę wystąpień każdego znaku

  int ccount[256]; // liczniki znaków
  
  for(i = 0; i < 256; i++) ccount[i] = 0;
  for(i = line.size() - 1; i >= 0; i--) ccount[line[i]]++;
  
// tworzymy listę pojedynczych węzłów drzewa binarnego,
// na której umieszczamy tylko znaki występujące w
// odczytanym wierszu - pomijamy znaki nieobecne.

TdoubleList  dl;
TlistElement * p1, * p2, * p;
TBTnode      * n;
  
  for(i = 255; i >= 0; i--)
    if(ccount[i])
    {
      n = new TBTnode;
      n->parent = n->left = n->right = NULL;
      n->c = i;
      p = new TlistElement;
      p->node = n;
      p->key = ccount[i];
      dl.push_front(p);
    }

// wyświetlamy znaki wraz z ich częstościami w wierszu

  cout << endl;
  dl.showKeys();
  cout << endl;
  
// tworzymy drzewo binarne Huffmana

  while(dl.size() > 1)
  {

// na liście wyszukujemy dwa najmniejsze elementy

    dl.find2min(p1,p2);

// z węzłów zawartych w p1 i p2 tworzymy nowy węzeł

    n = new TBTnode;
    n->parent = NULL;
    n->left  = p1->node;
    n->right = p2->node;
    n->left->parent = n->right->parent = n;
    
// nowy węzeł drzewka umieszczamy w p1

    p1->node = n;

// obliczamy wartość klucza

    p1->key += p2->key;
    
// p2 usuwamy z listy i z pamięci - nie jest już potrzebne

    delete dl.erase(p2);
  }  

// wywołujemy rekurencyjną funkcję inorder, która
// przejdzie przez całe drzewko wypisując kody Huffmana
// poszczególnych liści - znaków

  char hcodes[256]; // przechowuje kody Huffmana odczytane z drzewka

  inorder(dl.index(1)->node,hcodes,0);
  
// gotowe - kończymy program

  cout << endl << endl; 
  system("PAUSE");
}

adydan napisał(a)

podstawa do wyjścia:

Dzięki za odpowiedź!
Jednak wole w miarę samemu pisać tego typu rzeczy, przynajmniej coś się nauczę :).

Btw. Mam już najważniejsze rzeczy do Huffmana, tylko wystąpił mały problem....
Wszystko byłoby cacy, gdyby działała mi funkcja (właściwie, nie wiem czy to ona jest winna) odpowiedzialna za sortowanie. Gdy ją usunę wszystko działa ok, gdy zostawię, program się wywala. Wiem, że kod pozostawia wiele do życzenia. Wydaje mi się, że przyczyną tego problemu może być złe budowanie listy.

Czy mógłby mi ktoś podpowiedzieć jak to popoprawiać?

#include <iostream>

using namespace std;
int counter = 0;
struct Tree
{
       Tree* left;
       Tree* right;
       //char c;
       int value;
       };
       
struct List
{
       int value;
       List* prev;
       List* next;
       
       Tree* t;
       List()
       {
             t = new Tree;
             t->left = 0;
             t->right = 0;
             t->value = 0;
       }
       };

List* head = 0;
List* tail = 0;

void addTree(Tree* t, int val)
{
     List* newitem;
     newitem = new List;
     newitem->value = val;
     newitem->t = t;
     newitem->t->value = val;
    
     if(head==0)
     {
               newitem->next = 0;
               newitem->prev = 0;
               
               head = newitem;
               tail = newitem;
     }
     else
     {
               newitem->next = 0;
               newitem->prev = tail;
               tail->next = newitem;
               tail = newitem;
     }
     counter++;     
}
       
void add(int val)
{
     List* newitem;
     
     newitem = new List;
     newitem->value = val;
    
    if(head==0)
    {
               newitem->next = 0;
               newitem->prev = 0;
               
               head = newitem;
               tail = newitem;
    }
    else
    {
               newitem->next = 0;
               newitem->prev = tail;
               tail->next = newitem;
               tail = newitem;
    }
    counter++;
}
void remove()
{
     cout << "Usuwam: " << head->value << endl;
     List* temp;
     if(head)
     {
             temp = head;
             head = temp->next;
             if(!head) tail = 0;
             else head->prev = 0;

             delete temp;      
     }
     counter--;
}

void print()
{
     List* temp;
     temp = head;

     while(temp)
     {
      cout << temp->value << endl;
      temp = temp->next;
     }
}

void sort_wstaw()
{ List *tmp, *pom;
  List *nowypierwszy = NULL;

  while (head)
     {  tmp = head;
        head = tmp->next;

        if (nowypierwszy==NULL)
           { tmp->next=nowypierwszy;
             nowypierwszy = tmp;
           }
        else if (nowypierwszy->value>= tmp->value)
           { tmp->next = nowypierwszy;
             nowypierwszy = tmp;
           }
         else
           { pom = nowypierwszy;
             while (pom->next)
               { if (pom->next->value>tmp->value) break;
                 pom = pom->next;
               }
             tmp->next = pom->next;
             pom->next = tmp;
           }
     }
  head = nowypierwszy;
 }
 void inOrder(Tree* tw)
{
    if(tw->left)
        inOrder(tw->left);
        
    cout << tw->value << " ";
    
    if(tw->right)
        inOrder(tw->right);
}
int main()
{
    Tree* tw = new Tree;
    
    tw->right =0;
    tw->left = 0;
    tw->value =0;
    addTree(tw,1); 
    addTree(tw,2);
    addTree(tw,3);
    addTree(tw,4);
    

    while(head->next)
    {
               Tree* tt = new Tree;
               tt->left = head->t;
               tt->right = head->next->t;
               addTree(tt, head->value + head->next->value);
               remove();
               remove();
               //sort_wstaw();
               
               
               
    }

    print();
    cout << "#INORDER#" << endl;
    inOrder(head->t);

    delete tw;

    system("PAUSE");
    return 0;
}

Pozdrawiam, Ziem!