kodowanie Huffmana- programowanie c

ktosja
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 28 kwie 2011, o 10:21
Płeć: Kobieta
Lokalizacja: gdzies

kodowanie Huffmana- programowanie c

Post autor: ktosja »

Mam do napisania program kodujący metoda Huffmana. Rozumiem jak tworzy się te słowa kodowe tym algorytmem, poradziłam sobie z zapisaniem tablicy występujących znaków i posortowaniem jej według malejącej liczby wystąpień znaku, mam problem z stworzeniem drzewa binarnego.... nie potrafię zrozumieć w jaki sposób tworzyć drzewa binarne. w węzłach muszą przechowywać symbol i liczbę wystąpień danego symboli.Poprzez łączenie najmniej prawdopodobnych liter , tworze nowe drzewo które w korzeniu ma sumę liczby wystąpień dwóch połączonych itd.
proszę o jakieś jasne wytłumaczenie, czy prosty przykładowy kod w jaki sposób tworzy się drzewa binarne.
Awatar użytkownika
kuma
Użytkownik
Użytkownik
Posty: 259
Rejestracja: 16 sie 2007, o 22:03
Płeć: Mężczyzna
Podziękował: 12 razy
Pomógł: 70 razy

kodowanie Huffmana- programowanie c

Post autor: kuma »

Czego nie rozumiesz w dzrewie binarnym?
Ogólnie rzecz biorąc masz korzeń (inaczej niż intuicja mówi na samej górze) i od niego masz kolejne podrzewa. W zależności od tego na jakiej zasadzie tworzysz drzewo (kryterium rozróżniania węzłów) dodajesz kolejne węzły drzewa itd. Tak powstanie drzewo.
ktosja
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 28 kwie 2011, o 10:21
Płeć: Kobieta
Lokalizacja: gdzies

kodowanie Huffmana- programowanie c

Post autor: ktosja »

nie rozumiem w jaki sposób mam stworzyć to drzewo.....
Doszłam do tege że za pomocą
struct El {
int info;
struct El *lewy;
struct El *prawy;
};
napierw tworze drzewo z najmniejszymu prawdopodobienstwami i w korzeniu przypisuje wartosc sumy prawdopodobienstw z prawego i lewego... nie wiem jak to poprawnie zapisac w c
Awatar użytkownika
kuma
Użytkownik
Użytkownik
Posty: 259
Rejestracja: 16 sie 2007, o 22:03
Płeć: Mężczyzna
Podziękował: 12 razy
Pomógł: 70 razy

kodowanie Huffmana- programowanie c

Post autor: kuma »

Prawdę mówiąc nie znam metody Huffmana. Jednak użyta przez Ciebie struktura jest poprawna. Właśnie na takiej buduje się drzewa. Tworzysz teraz jakisz korzen (Root) i dodajesz kolejne węzły.

np.

El *nowy;
nowy = (struct El *) malloc(sizeof(struct El));
Root->left=nowy;

Jest kupe takich rzeczy na necie.
ktosja
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 28 kwie 2011, o 10:21
Płeć: Kobieta
Lokalizacja: gdzies

kodowanie Huffmana- programowanie c

Post autor: ktosja »

no tak jest tego pełno na necie już od kilku godzin przeglądam strony w poszukiwaniu jakiegoś jasnego wytłumaczenia i nic
Mogę prosić o jakiś przykładowy kod , że np mam tablice:
t[0]=1
t[1]=2
t[3]=2
t[4]=7
i teraz chce stworzyć drzewo w ten sposób ze buduje korzeń którego potomkami są te elementy które mają najmniejsza wartość w tym przykładzie to będzie t[0] i t[1] a wartość w korzeniu będzie równa 2+1=3 i otrzymuje następną liste:
d[0]=3
t[3]=2
t[4]=7
znowu łączę te 2 które maja najmniejsze wartości więc d[0] i t[3] w drzewo d[1] w korzeniu wartość 5
itd otrzymując jakieś drzewo binarne.
Nie wiem w jaki sposób stworzyć korzeń i przypisać wartość lewa i prawa a korzeniu przypisać wartość równą sumie wartości potomków, oraz jak później mogę operować tym korzeniem by móc porównywać wartość z korzenia z innymi elementami początkowej tablicy, by tworzyć dalej drzewo. Znalazłam różne kody algorytmu Huffmana tylko nie chcę bezmyślnie ich kopiować po prostu chce to zrozumieć w jaki sposób tworzyć te drzewa a niestety brakuje mi podstawowych wiadomości i każde informacje na necie są dla mnie nie zrozumiałe...
ODPOWIEDZ