Huffman Coding

0

Witam.
Potrzebuję pomocy z napisaniem programu dotyczącego kodowania Huffmana. Nie do końca rozumiem struktury, a tak ma to być własnie napisane i sam sobie z tym nie poradzę. Wiem, że tego jest pełno w internecie, jednak wszędzie gdzie szukałem programy napisane są głównie w klasach. Program ma działać następująco:
Użytkownik wpisuje ilość znaków do kodowania, następnie po kolei litery i po każdej literze ilość jej wystąpień. - To już zrobiłem
Następnie program segreguje je według alfabetu (segregowanie też zrobione)


Każdej literze przypisuje wartości A(000) B(001) C(010) D(011) itd.
Program bierze dwie litery o najmniejszej liczbie wystąpień sumuje ilości wystąpień tych dwóch(tworzy nowy węzeł) i tak dalej do stworzenia jednego wielkiego drzewa i na końcu program ma wywalić że teraz litera 'A' ma kod tam np 101 (droga po drzewie).
Potem trzeba wyliczyć prawdopodobieństwo wystąpienia każdej z liter ale to już sobie zrobię.
Mam jakiś szkielet kodu, który trzeba rozbudować, wygląda to następująco:

#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
// Sortowanie danych
void vSortowanie()
{
ifstream wejscie;
wejscie.open( "Wejscie.txt" );
int iIleWierszy;
wejscie >> iIleWierszy;
string sTab[ 2 ][ iIleWierszy ];
// Wczytuje dane do posortowania
for( int i = 0; i < iIleWierszy; i++ )
for( int j = 0; j < 2; j++ )
wejscie >> sTab[ j ][ i ];//endfor / endfor
wejscie.close();
// Sortowanie
for( int j = 1; j < iIleWierszy; j++ )
for( int i = 1; i < iIleWierszy; i++ )
if( sTab[ 0 ][ i ] < sTab[ 0 ][ i - 1 ] )
{
swap( sTab[ 0 ][ i ], sTab[ 0 ][ i - 1 ] );
swap( sTab[ 1 ][ i ], sTab[ 1 ][ i - 1 ] );
}//ednif / endfor
// Wypisuje posortowane dane do pliku
ofstream posortowane( "Wejscie_Alfabetycznie.txt" );
for( int i = 0; i < iIleWierszy; i++ )
{
for( int j = 0; j < 2; j++ )
posortowane << sTab[ j ][ i ] << "\t";
posortowane << "\n";
}
posortowane.close();
}
struct drzewo
{
int iWartosc;
drzewo *lewo;
drzewo *prawo;
drzewo *rodzic;
drzewo();
};
struct lista
{
drzewo *head;
lista();
};
int main()
{
vSortowanie();
system( "pause" );
return 0;
}

Pomoże ktoś?

0
matizpk napisał(a):

Użytkownik wpisuje ilość znaków do kodowania, następnie po kolei litery i po każdej literze ilość jej wystąpień.
Czy na pewno ten kod ty pisałeś? Bo z tego co widzę to użytkownik nic nie powinien podawać.

matizpk napisał(a):

To już zrobiłem
To czyli co?

matizpk napisał(a):

Następnie program segreguje je według alfabetu (segregowanie też zrobione)
A powinno być wg ilości wystąpień.

struct Dane { char Alpha; unsigned Count; };

size_t Count;
wejscie>>Count;
Dane *tb=new Dane[Count];
for(size_t i=0;i<Count;++i) wejscie>>ws>>tb[i].Alpha>>ws>>tb[i].Count; // #include <iomanip> dla ws
0

Witaj.
Tak - kod sam pisałem.
"To już zrobiłem" czyli chodzi o to, że użytkownik wprowadza dane do pliku następnie program te dane segreguje.
Poprawiłem to sortowanie i teraz sortuje rosnąco według ilości wystąpień (zamieniłem tablice dwuwymiarową na dwie tablice dynamiczne).
Właściwie nie wiem jak zrobić samo kodowanie.
Teraz kod wygląda tak:

#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
// Sortowanie danych
void vSortowanie()
{
ifstream wejscie;
wejscie.open( "Wejscie.txt" );
int iIleWierszy;
wejscie >> iIleWierszy;
char *cTab = new char[ iIleWierszy ]; // tablica liter
int *iTab = new int[ iIleWierszy ]; //tablica ilosci wystapien liter
// Wczytuje dane do posortowania
for( int i = 0; i < iIleWierszy; i++ )
wejscie >> cTab[ i ] >> iTab[ i ];//endfor
wejscie.close();
// Sortowanie
for( int j = 1; j < iIleWierszy; j++ )
for( int i = 1; i < iIleWierszy; i++ )
if( iTab[ i ] < iTab[ i - 1 ] )
{
swap( cTab[ i ], cTab[ i - 1 ] );
swap( iTab[ i ], iTab[ i - 1 ] );
}//ednif / endfor / endfor
// Wypisuje posortowane dane do pliku
ofstream posortowane( "Wejscie_Alfabetycznie.txt" );
for( int i = 0; i < iIleWierszy; i++ )
posortowane << cTab[ i ] << "\t" << iTab[ i ] << "\n";//endfor
posortowane.close();
}
struct drzewo
{
int iWartosc;
drzewo *lewo;
drzewo *prawo;
drzewo *rodzic;
drzewo();
};
struct lista
{
drzewo *head;
lista();
};
int main()
{
vSortowanie();
system( "pause" );
return 0;
}

Masz jakieś pomysł czy cokolwiek?

1 użytkowników online, w tym zalogowanych: 0, gości: 1