Matematyka.pl

Mama zaimplementowane drzewo binarne w którym w liściach są zapisane określone znaki, oraz zaszyfrowany tekst który muszę odszyfrować zgodnie z tym drzewem.
kody np.
A:0
B:10
C:110
...
z pliku txt. wczytuje kolejne bajty w jaki sposób mogę przechodzić przez drzewo,wypisać znak jeśli znajdę się w liściu, a następnie wracać do korzenia? Pomysł mam taki żeby sprawdzać kolejne bity jeśli znajduję sie 1 ide w prawo jesli -0 ide w lewo az dojde do wezla ktory nie zawiera potomka.
Wiem w jaki sposób sprawdzać kolejne bity w bajcie np poprzez:

Kod: Zaznacz cały

 
bufor=getc(f); 
i=7;    
while(i>=0){
                                         if((bufor &( 1<<i))==(1<<i)){
                                          
                                                   printf("1");
                                                   i--;
                                                          }
                                         else{
                                               printf("0");
                                               i--;
                                               }
                                         
                                       }

Mój problem polega na tym że nie wiem w jaki sposób poruszać się po drzewie...
a może w ogole pomysl jest nie za dobry?
Prosze o jakieś wskazówki

Miałem zamiar odpisać w poprzednim temacie, ale skoro jesteśmy już tutaj:
powiedzmy że mamy strukture:

Kod: Zaznacz cały

struct foo {
    struct foo *next;
    struct foo *prev;
    char *data;
};

Jeśli masz zaalokowaną pamięć i powiedzmy wskaźnik do Twojej struktury:

Kod: Zaznacz cały

struct foo *moj_wskaznik;

to możesz się poruszać po niej w sposób następujący:

Kod: Zaznacz cały

(moj_wskaznik->next)->prev = moj_wskaznik // teraz wskaznik 'prev' nastepnej struktury wskazuje na tą strukture - bedziesz mogla wrocic do tej kiedy zechcesz
moj_wskaznik = moj_wskaznik->next; // przechodzimy do kolejnej przestrzeni

Znajdziesz się wtedy w kolejnej przestrzeni (kolejny węzeł struktury);
Potem, jeśli będziesz chciała przejść jeden poziom wstecz:

Kod: Zaznacz cały

moj_wskaznik = moj_wskaznik->prev;

Oczywiście wiadomo, że musisz odpowiednio alokować pamięć dla swoich struktur (i odpowiednio ustawiać wskaźniki!), dlatego właśnie sugerowałem napisać funkcje, które będą robić to za Ciebie, przykładowo, dla mojej struktury foo:

Kod: Zaznacz cały

struct foo *alokuj_wezel(struct foo *ostatni_wezel)
{
    struct foo *nowy_wezel = malloc(sizeof(struct foo));
    if (nowy_wezel == NULL) {
        return NULL;
    }
    nowy_wezel->next = NULL;
    nowy_wezel->data = NULL;
    nowy_wezel->prev = ostatni_wezel;
    
    if (ostatni_wezel == NULL) {
        ostatni_wezel = nowy_wezel;
    } else {
        ostatni_wezel->next = nowy_wezel;
    }

    return nowy_wezel;
}

W wyniku wywolania tej funkcji z kontekstu:

Kod: Zaznacz cały

bar()
{
    struct foo *moja_struktura;
    
    // pierwsza alokacja
   alokuj_wezel(moja_struktura);

   // nastepne wezly
   alokuj_wezel(moja_struktura);   
}

Będziesz za każdym razem budować kolejne węzły struktury lub sam szkielet tej struktury (wreszcie nazwijmy to listą obustronnie łączoną).

Dorzuce też dla przykładu funkcję służącą zwolnieniu pamięci całej listy:

Kod: Zaznacz cały

void zwolnij_liste(struct foo *lista)
{
    struct foo *wezel;

    for (wezel = lista; wezel != NULL; wezel = wezel->prev) {
        free(wezel);
    }
    free(lista);
}

Uwierz, że warto sobie w ten sposób upraszczać życie, nawet dla takiego zadania jakie chcesz wykonać.

Ogolem Twoja petla chodząca po drzewie:
1. Przyjmijmy, że pobieramy dane z pliku.
2. Przyjmijmy, że spodziewamy się tylko 2 różnych znaków: 0 i 1

Kod: Zaznacz cały

char ch;
while ((ch = getc(wskaznik_do_pliku)) != EOF) {
    switch (ch) {
    case '1':
        // Twoja czynność którą chcesz wykonać na drzewie
       break;
    case '0':
        // Twoja czynność ktora chcesz wykonac na drzewie
       break;
    default:
       break;
    }
}

Dekoder Morse'a zrobiłem tak:

: obrazek-matematyka.png (5.41 KiB) Przejrzano 166 razy

c=next() // kolejny znak kodu
i=0
while c != ' ' // znak końca kodu
if c == '-' // kreska,
i=2*i+1
else // kropka
i=2*i+2
c=next()[/code]
Podobnie można by dla przykładowego drzewka Huffmanna (liczby teraz nieistotne)

: obrazek-matematyka.png (7.74 KiB) Przejrzano 166 razy

char t[]='......e. star..on............'
i=0
while t=='.' //jakiś spec kod sygnalizujący, że to nie koniec
c=next()
if c==1
i=2*i+1
else
i=2*i+2
znak=t[/code]
t[] jest kopcem (heap), a kopiec jest jednym ze sposobów przedstawienia drzewa binarnego

Bardzo dziękuję za wyczerpujące odpowiedzi i poświęcony czas

Matematyka.pl

dekompresja danych

dekompresja danych

dekompresja danych

dekompresja danych

dekompresja danych