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.
kodowanie Huffmana- programowanie c
- kuma
- 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
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.
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.
kodowanie Huffmana- programowanie c
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
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
- kuma
- 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
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.
np.
El *nowy;
nowy = (struct El *) malloc(sizeof(struct El));
Root->left=nowy;
Jest kupe takich rzeczy na necie.
kodowanie Huffmana- programowanie c
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...
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...