Przeczytaj

Już wiesz

W roku $1952$ David Huffman opracował prefiksową metodę kompresji bezstratnejbezstratna kompresja danychkompresji bezstratnej.

Mówimy, że kodowanie jest prefiksowe, gdy żadne słowo kodoweSłowo kodowesłowo kodowe nie jest początkiem innego słowa.

Słowem kodowym w kontekście kodowania Huffmana określamy ciągi bitów, które jednoznacznie interpretujemy jako znak. Uwaga – w implementacji dla uproszczenia będziemy kodować każdy znak osobno, bez wcześniejszego grupowania.

Problem 1

Załóżmy, że w alfabecie, którym się posługujemy, są trzy znaki zgrupowane w następującej książce kodowejksiążka kodowaksiążce kodowej:

A – reprezentowane przez 1,
B – reprezentowane przez 01,
C – reprezentowane przez 00.

Za ich pomocą zakodowaliśmy pewną wiadomość i otrzymaliśmy taki oto wynik: 1010000011.

Spróbuj odkodować samodzielnie ten napis.

Problem 2

Załóżmy, że w alfabecie, którym się posługujemy, są trzy znaki zgrupowane w następującej książce kodowej:

A – reprezentowane przez 0,
B – reprezentowane przez 01,
C – reprezentowane przez 1.

Za ich pomocą zakodowaliśmy pewną wiadomość i otrzymaliśmy taki oto wynik:
00111010.

Spróbuj odkodować samodzielnie ten napis:

Kodowanie prefiksowe umożliwia odkodowanie wiadomości metodą zachłanną, tzn. odkodowujemy najwcześniejsze odnalezione słowo kodowe.

Słowa kodowe używane w algorytmie Huffmana mają postać binarną, a w języku C++ domyślnie posługujemy się kodem ASCII.

Problem 3

Używając słów kodowych z problemu pierwszego, udało nam się zakodować 6 znaków (ABCCBA) na $10$ bitach. Należy pamiętać, że każdy z tych znaków zajmuje w pamięci programu po 8 bitów, czyli po $1$ bajcie. Udało nam się więc skompresować 48 bitów do $10$ bitów, czyli 6 bajtów do niecałych $2$ bajtów.

Jaki jest stopień kompresjistopień kompresjistopień kompresji?

Stopień kompresji wynosi $\frac{48}{10} = 4,8$ .

Implementacja w języku C++

Problem 4

Zaimplementujmy w języku C++ program kodujący podany ciąg znaków za pomocą algorytmu Huffmana.

W celu uproszczenia implementacji do przechowywania zakodowanej wiadomości w postaci bitowej posłużymy się łańcuchem znaków, w którym wykorzystamy znaki ASCII odpowiadające cyfrom 0 oraz 1. Należy pamiętać, że taka forma przechowywania danych w pamięci nie powoduje zmniejszenia liczby wykorzystanych bitów, lecz dodatkowo ją zwiększa.

Specyfikacja problemu:

Dane:

wiadomosc – łańcuch znaków do zakodowania

Wynik:

zakodowana_wiadomosc – łańcuch znaków (zer lub jedynek) reprezentujący w postaci bitowej zakodowany według kodowania Huffmana ciąg znaków wiadomosc

Algorytm zaimplementujemy w kilku etapach. Najpierw zaimportujemy potrzebne biblioteki oraz wskażemy użycie standardowej przestrzeni nazw. Wykorzystamy bibliotekę <iostream> do pobierania i wypisywania danych ze standardowego wejścia oraz wyjścia, a także bibliotekę <string> do wykonywania operacji na łańcuchach znaków. Potrzebna będzie nam również implementacja listy w języku C++, dostępna w bibliotece <list>, która w przeciwieństwie do zwykłych tablic pozwala na szybkie usuwanie oraz dodawanie elementów.

#include <iostream>
#include <string>
#include <list>

using namespace std;

Następnie utworzymy funkcję, której zadaniem będzie wpisanie do tablicy informacji, ile razy w ciągu znaków zdanie wystąpiły poszczególne znaki kodowane za pomocą standardu ASCII. Dodatkowo funkcja zliczy oraz zwróci liczbę unikalnych znaków, która wskazuje, jak dużo liści będzie występować w drzewie kodowym używanym do kodowania Huffmana.

int zlicz_znaki(string wiadomosc, int* tablica_zliczen) {
    for (int i = 0; i <= 255; ++i) {
        tablica_zliczen[i] = 0;
    }
    for (int i = 0; i < wiadomosc.length(); ++i) {
        ++tablica_zliczen[wiadomosc[i]];
    }
    int liczba = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            ++liczba;
        }
    }
    return liczba;
}

W tym momencie możemy przetestować działanie utworzonej funkcji. Poniższy kod wypisze wszystkie znaki z łańcucha znaków wiadomosc oraz ich zliczenia:

#include <iostream>
#include <string>
#include <list>

using namespace std;

int zlicz_znaki(string wiadomosc, int* tablica_zliczen) {
    for (int i = 0; i <= 255; ++i) {
        tablica_zliczen[i] = 0;
    }
    for (int i = 0; i < wiadomosc.length(); ++i) {
        ++tablica_zliczen[wiadomosc[i]];
    }
    int liczba = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            ++liczba;
        }
    }
    return liczba;
}

int main() {
    int tablica_zliczen[256];
    string wiadomosc = "Dodadodadodatki";

    // zliczanie znaków w wiadomości
    int liczba_znakow = zlicz_znaki(wiadomosc, tablica_zliczen);

    // wypisywanie zliczeń dla każdego znaku z wiadomości
    cout << "Zliczenia kazdego znaku:" << endl;
    for (int i = 0; i < wiadomosc.length(); ++i) {
        char znak = wiadomosc[i];
        cout << znak << ": " << tablica_zliczen[znak] << endl;
    }

    return 0;
}

Wynik działania programu:

Zliczenia kazdego znaku:
D: 1
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
t: 1
k: 1
i: 1

Program wyświetlił zliczenia kolejnych znaków. Jak widzisz, jeśli dany znak się powtarza, przy każdym jego wystąpieniu w łańcuchu znaków pojawia się informacja, ile razy dany znak się pojawił w całym łańcuchu (w tym przypadku zwróć uwagę na literę d; po pierwsze osobno jest liczone jej wystąpienie jako wielkiej litery, po drugie – cały łańcuch znaków jest wyświetlony w formie kolumny, więc powtarzające się wystąpienia litery d również się pojawiają).

Utworzymy teraz definicję struktury drzewiastej, którą wykorzystamy do przechowywania drzewa kodowego Huffmana. Głównym elementem struktury będzie wierzcholek, który posiada pola takie jak: znak, częstość występowania tego znaku w ciągu znaków wiadomosc oraz wskaźniki na lewy i prawy wierzchołek w strukturze drzewa. Domyślne wartości pól lewy oraz prawy zostały ustawione na nullptr, co w języku C++ oznacza wskaźnik pustywskaźnik pustywskaźnik pusty. Taki zabieg umożliwi rozpoznanie wierzchołków, które nie posiadają wierzchołków podrzędnych.

struct wierzcholek {
    char znak;
    int czestosc;
    wierzcholek* lewy = nullptr;
    wierzcholek* prawy = nullptr;
};

W kolejnym kroku utworzymy listę unikalnych znaków wraz z ich częstościami. Korzystając z zaimplementowanej funkcji, zliczymy unikalne znaki, a następnie dla każdego z nich, jeśli jego częstość wynosi więcej niż 0, utworzymy nowy wierzchołek i dodamy go do listy wierzchołków. Lista ta posłuży nam później do utworzenia drzewa kodowego. Fragment kodu umieścimy w funkcji main.

Ważne!

Poniższy fragment kodu, jak i niektóre z kolejnych fragmentów nie zwalniają pamięci rezerwowanej z wykorzystaniem słowa kluczowego new. Dlatego po zakończeniu algorytmu należy zwolnić każdy rezerwowany wcześniej fragment pamięci, wykorzystując słowo kluczowe delete. Zwalnianie pamięci zostanie przez nas zaimplementowane w ostatecznym kodzie.

#include <iostream>
#include <string>
#include <list>

using namespace std;

struct wierzcholek {
    char znak;
    int czestosc;
    wierzcholek* lewy = nullptr;
    wierzcholek* prawy = nullptr;
};

int zlicz_znaki(string wiadomosc, int* tablica_zliczen) {
    for (int i = 0; i <= 255; ++i) {
        tablica_zliczen[i] = 0;
    }
    for (int i = 0; i < wiadomosc.length(); ++i) {
        ++tablica_zliczen[wiadomosc[i]];
    }
    int liczba = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            ++liczba;
        }
    }
    return liczba;
}

int main() {
    int tablica_zliczen[256];
    string wiadomosc = "Dodadodadodatki";

    // zliczanie znaków w wiadomości
    int liczba_znakow = zlicz_znaki(wiadomosc, tablica_zliczen);

    // wypisywanie zliczeń dla każdego znaku z wiadomości
    cout << "Zliczenia kazdego znaku:" << endl;
    for (int i = 0; i < wiadomosc.length(); ++i) {
        char znak = wiadomosc[i];
        cout << znak << ": " << tablica_zliczen[znak] << endl;
    }

    // tworzenie listy wierzchołków
    list<wierzcholek*> lista_wierzcholkow;
    int j = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            lista_wierzcholkow.push_back(new wierzcholek());
            lista_wierzcholkow.back()->znak = i;
            lista_wierzcholkow.back()->czestosc = tablica_zliczen[i];
            ++j;
            if (j == liczba_znakow) {
                break;
            }
        }
    }

    // wypisywanie listy wierzchołków
    cout << "Lista wierzcholkow:" << endl;
    for (wierzcholek* w : lista_wierzcholkow) {
        cout << w->znak << ": " << w->czestosc << endl;
    }
    
    return 0;
}

Wynik działania programu:

Zliczenia kazdego znaku:
D: 1
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
t: 1
k: 1
i: 1
Lista wierzcholkow:
D: 1
a: 3
d: 5
i: 1
k: 1
o: 3
t: 1

Poza zliczeniami znaków pojawiła się lista wierzchołków. Każdy znak z łańcucha znaków jest już w niej unikalny.

Moglibyśmy teraz przejść do tworzenia drzewa kodowego Huffmana, które polegałoby na pobraniu z listy dwóch wierzchołków o najmniejszej częstości, usunięciu ich z listy oraz połączeniu w nowy wierzchołek, a następnie umieszczeniu na liście. Tak skonstruowany algorytm wymagałby jednak przeszukiwania listy w każdym kroku. Znacznie prostszym rozwiązaniem może okazać się zadbanie o to, aby lista w każdym momencie była posortowana.

Dzięki wykorzystaniu implementacji listy ze standardowej biblioteki języka C++ możemy skorzystać z metody sort(), która sortuje elementy listy według przekazanej do niej funkcji porównującej. Napiszmy zatem potrzebną funkcję:

bool funkcja_porownujaca(wierzcholek* w1, wierzcholek* w2) {
    return w1->czestosc > w2->czestosc;
}

Warto wiedzieć, że metoda sort() korzysta z algorytmu sortowania introspektywnego (IntroSort), który jest pochodną sortowania szybkiego, kopcowego oraz przez wstawianie. Jego złożoność obliczeniowa wynosi: $O = (n \cdot \log_{2} (n))$

Tak skonstruowana funkcja umożliwi wykorzystanie metody sort() do posortowania listy wierzchołków nierosnąco według ich częstości. Przetestujmy jej działanie, wykorzystując poniższy kod:

#include <iostream>
#include <string>
#include <list>

using namespace std;

struct wierzcholek {
    char znak;
    int czestosc;
    wierzcholek* lewy = nullptr;
    wierzcholek* prawy = nullptr;
};

int zlicz_znaki(string wiadomosc, int* tablica_zliczen) {
    for (int i = 0; i <= 255; ++i) {
        tablica_zliczen[i] = 0;
    }
    for (int i = 0; i < wiadomosc.length(); ++i) {
        ++tablica_zliczen[wiadomosc[i]];
    }
    int liczba = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            ++liczba;
        }
    }
    return liczba;
}

bool funkcja_porownujaca(wierzcholek* w1, wierzcholek* w2) {
    return w1->czestosc > w2->czestosc;
}

int main() {
    int tablica_zliczen[256];
    string wiadomosc = "Dodadodadodatki";

    // zliczanie znaków w wiadomości
    int liczba_znakow = zlicz_znaki(wiadomosc, tablica_zliczen);

    // wypisywanie zliczeń dla każdego znaku z wiadomości
    cout << "Zliczenia kazdego znaku:" << endl;
    for (int i = 0; i < wiadomosc.length(); ++i) {
        char znak = wiadomosc[i];
        cout << znak << ": " << tablica_zliczen[znak] << endl;
    }

    // tworzenie listy wierzchołków
    list<wierzcholek*> lista_wierzcholkow;
    int j = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            lista_wierzcholkow.push_back(new wierzcholek());
            lista_wierzcholkow.back()->znak = i;
            lista_wierzcholkow.back()->czestosc = tablica_zliczen[i];
            ++j;
            if (j == liczba_znakow) {
                break;
            }
        }
    }

    // wypisywanie listy wierzchołków
    cout << "Lista wierzcholkow:" << endl;
    for (wierzcholek* w : lista_wierzcholkow) {
        cout << w->znak << ": " << w->czestosc << endl;
    }

    // sortowanie listy wierzchołków
    lista_wierzcholkow.sort(funkcja_porownujaca);

    // wypisywanie listy wierzchołków po posortowaniu
    cout << "Lista wierzcholkow po posortowaniu:" << endl;
    for (wierzcholek* w : lista_wierzcholkow) {
        cout << w->znak << ": " << w->czestosc << endl;
    }

    return 0;
}

Wynik działania programu:

Zliczenia kazdego znaku:
D: 1
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
t: 1
k: 1
i: 1
Lista wierzcholkow:
D: 1
a: 3
d: 5
i: 1
k: 1
o: 3
t: 1
Lista wierzcholkow po posortowaniu:
d: 5
a: 3
o: 3
D: 1
i: 1
k: 1
t: 1

Lista wierzchołków została posortowana. Ułatwi to tworzenie drzewa Huffmana.

W tym momencie możemy przejść do budowy drzewa kodowego. Dopóki na liście jest więcej niż jeden wierzchołek, zdejmujemy z listy dwa ostatnie wierzchołki (o najmniejszej częstości), łączymy je w nowy wierzchołek o częstości będącej sumą częstości obu wierzchołków, a następnie dodajemy go do listy w odpowiednie miejsce. Gdy na liście zostanie jeden wierzchołek, mamy gotowe drzewo kodowe.

Ważne!

W celu uproszczenia implementacji, zamiast wyszukiwać odpowiednie miejsce dla nowopowstałego wierzchołka, odłożymy go na koniec listy, a następnie ją posortujemy. Należy pamiętać, że takie rozwiązanie zwiększa złożoność obliczeniową algorytmu.

#include <iostream>
#include <string>
#include <list>

using namespace std;

struct wierzcholek {
    char znak;
    int czestosc;
    wierzcholek* lewy = nullptr;
    wierzcholek* prawy = nullptr;
};

int zlicz_znaki(string wiadomosc, int* tablica_zliczen) {
    for (int i = 0; i <= 255; ++i) {
        tablica_zliczen[i] = 0;
    }
    for (int i = 0; i < wiadomosc.length(); ++i) {
        ++tablica_zliczen[wiadomosc[i]];
    }
    int liczba = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            ++liczba;
        }
    }
    return liczba;
}

bool funkcja_porownujaca(wierzcholek* w1, wierzcholek* w2) {
    return w1->czestosc > w2->czestosc;
}

int main() {
    int tablica_zliczen[256];
    string wiadomosc = "Dodadodadodatki";

    // zliczanie znaków w wiadomości
    int liczba_znakow = zlicz_znaki(wiadomosc, tablica_zliczen);

    // wypisywanie zliczeń dla każdego znaku z wiadomości
    cout << "Zliczenia kazdego znaku:" << endl;
    for (int i = 0; i < wiadomosc.length(); ++i) {
        char znak = wiadomosc[i];
        cout << znak << ": " << tablica_zliczen[znak] << endl;
    }

    // tworzenie listy wierzchołków
    list<wierzcholek*> lista_wierzcholkow;
    int j = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            lista_wierzcholkow.push_back(new wierzcholek());
            lista_wierzcholkow.back()->znak = i;
            lista_wierzcholkow.back()->czestosc = tablica_zliczen[i];
            ++j;
            if (j == liczba_znakow) {
                break;
            }
        }
    }

    // wypisywanie listy wierzchołków
    cout << "Lista wierzcholkow:" << endl;
    for (wierzcholek* w : lista_wierzcholkow) {
        cout << w->znak << ": " << w->czestosc << endl;
    }

    // sortowanie listy wierzchołków
    lista_wierzcholkow.sort(funkcja_porownujaca);

    // wypisywanie listy wierzchołków po posortowaniu
    cout << "Lista wierzcholkow po posortowaniu:" << endl;
    for (wierzcholek* w : lista_wierzcholkow) {
        cout << w->znak << ": " << w->czestosc << endl;
    }

    // tworzenie drzewa kodowego
    while (lista_wierzcholkow.size() > 1) {
        // zdejmujemy z listy 2 wierzchołki w1 i w2
        wierzcholek* w1 = lista_wierzcholkow.back();
        lista_wierzcholkow.pop_back();
        wierzcholek* w2 = lista_wierzcholkow.back();
        lista_wierzcholkow.pop_back();

        // łączymy wierzchołki w1 oraz w2, tworząc wierzchołek w3
        wierzcholek* w3 = new wierzcholek();
        w3->czestosc = w1->czestosc + w2->czestosc;
        w3->lewy = w1;
        w3->prawy = w2;

        // umieszczamy wierzchołek w3 na końcu listy, a następnie ją sortujemy
        lista_wierzcholkow.push_back(w3);
        lista_wierzcholkow.sort(funkcja_porownujaca);
    }

    // gotowe drzewo kodowe
    wierzcholek* drzewo_kodowe = lista_wierzcholkow.back();

    return 0;
}

Wynik działania programu:

Zliczenia kazdego znaku:
D: 1
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
t: 1
k: 1
i: 1
Lista wierzcholkow:
D: 1
a: 3
d: 5
i: 1
k: 1
o: 3
t: 1
Lista wierzcholkow po posortowaniu:
d: 5
a: 3
o: 3
D: 1
i: 1
k: 1
t: 1

W tym momencie możemy napisać funkcję, która rekurencyjnie przeszuka drzewo kodowe w celu utworzenia książki kodowej. Utwórzmy prostą strukturę, która będzie zawierała znak oraz odpowiadający mu kod:

struct kod {
    char znak;
    string slowo_kodowe;
};

Rekurencyjne przeszukiwanie drzewa kodowego zaczniemy od sprawdzenia, czy obecny wierzchołek jest liściem — nie posiada potomka. Jeśli trafiliśmy na taki wierzchołek, spełniony jest warunek rekurencji. W książce kodowej dodany zostanie nowy wpis, po czym nastąpi powrót. Jeśli jednak wierzchołek nie jest liściem, przechodzimy rekurencyjnie do obu jego potomków, powiększając dotychczasowy kod o cyfrę 0 lub 1.

Ważne!

Kodowanie Huffmana nie jest jednoznaczne. W przypadku poniższego kodu przejściu do lewego potomka odpowiada cyfra 0, a do prawego cyfra 1. Jeśli sytuację odwrócimy, otrzymamy inny kod, ale o takiej samej długości.

void utworz_ksiazke_kodowa(wierzcholek* drzewo_kodowe, kod* ksiazka_kodowa, string dotychczasowy_kod = "") {
    static int i = 0;
    if (drzewo_kodowe->lewy == nullptr && drzewo_kodowe->prawy == nullptr) {
        ksiazka_kodowa[i].znak = drzewo_kodowe->znak;
        ksiazka_kodowa[i].slowo_kodowe = dotychczasowy_kod;
        ++i;
    }
    else {
        utworz_ksiazke_kodowa(drzewo_kodowe->lewy, ksiazka_kodowa, dotychczasowy_kod + "0");
        utworz_ksiazke_kodowa(drzewo_kodowe->prawy, ksiazka_kodowa, dotychczasowy_kod + "1");
    }
}

Wewnątrz funkcji main umieszczamy fragment odpowiadający za rezerwację pamięci dla tablicy o długości równej liczbie znaków tak, aby każdy otrzymał swoje słowo kodowe, a następnie wywołujemy rekurencyjnie funkcję wypełniającą książkę kodową. Na koniec, aby sprawdzić poprawność, możemy wypisać książkę kodową.

#include <iostream>
#include <string>
#include <list>

using namespace std;

struct wierzcholek {
    char znak;
    int czestosc;
    wierzcholek* lewy = nullptr;
    wierzcholek* prawy = nullptr;
};

struct kod {
    char znak;
    string slowo_kodowe;
};

int zlicz_znaki(string wiadomosc, int* tablica_zliczen) {
    for (int i = 0; i <= 255; ++i) {
        tablica_zliczen[i] = 0;
    }
    for (int i = 0; i < wiadomosc.length(); ++i) {
        ++tablica_zliczen[wiadomosc[i]];
    }
    int liczba = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            ++liczba;
        }
    }
    return liczba;
}

bool funkcja_porownujaca(wierzcholek* w1, wierzcholek* w2) {
    return w1->czestosc > w2->czestosc;
}

void utworz_ksiazke_kodowa(wierzcholek* drzewo_kodowe, kod* ksiazka_kodowa, string dotychczasowy_kod = "") {
    static int i = 0;
    if (drzewo_kodowe->lewy == nullptr && drzewo_kodowe->prawy == nullptr) {
        ksiazka_kodowa[i].znak = drzewo_kodowe->znak;
        ksiazka_kodowa[i].slowo_kodowe = dotychczasowy_kod;
        ++i;
    }
    else {
        utworz_ksiazke_kodowa(drzewo_kodowe->lewy, ksiazka_kodowa, dotychczasowy_kod + "0");
        utworz_ksiazke_kodowa(drzewo_kodowe->prawy, ksiazka_kodowa, dotychczasowy_kod + "1");
    }
}

int main() {
    int tablica_zliczen[256];
    string wiadomosc = "Dodadodadodatki";

    // zliczanie znaków w wiadomości
    int liczba_znakow = zlicz_znaki(wiadomosc, tablica_zliczen);

    // wypisywanie zliczeń dla każdego znaku z wiadomości
    cout << "Zliczenia kazdego znaku:" << endl;
    for (int i = 0; i < wiadomosc.length(); ++i) {
        char znak = wiadomosc[i];
        cout << znak << ": " << tablica_zliczen[znak] << endl;
    }

    // tworzenie listy wierzchołków
    list<wierzcholek*> lista_wierzcholkow;
    int j = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            lista_wierzcholkow.push_back(new wierzcholek());
            lista_wierzcholkow.back()->znak = i;
            lista_wierzcholkow.back()->czestosc = tablica_zliczen[i];
            ++j;
            if (j == liczba_znakow) {
                break;
            }
        }
    }

    // wypisywanie listy wierzchołków
    cout << "Lista wierzcholkow:" << endl;
    for (wierzcholek* w : lista_wierzcholkow) {
        cout << w->znak << ": " << w->czestosc << endl;
    }

    // sortowanie listy wierzchołków
    lista_wierzcholkow.sort(funkcja_porownujaca);

    // wypisywanie listy wierzchołków po posortowaniu
    cout << "Lista wierzcholkow po posortowaniu:" << endl;
    for (wierzcholek* w : lista_wierzcholkow) {
        cout << w->znak << ": " << w->czestosc << endl;
    }

    // tworzenie drzewa kodowego
    while (lista_wierzcholkow.size() > 1) {
        // zdejmujemy z listy 2 wierzchołki w1 i w2
        wierzcholek* w1 = lista_wierzcholkow.back();
        lista_wierzcholkow.pop_back();
        wierzcholek* w2 = lista_wierzcholkow.back();
        lista_wierzcholkow.pop_back();

        // łączymy wierzchołki w1 oraz w2, tworząc wierzchołek w3
        wierzcholek* w3 = new wierzcholek();
        w3->czestosc = w1->czestosc + w2->czestosc;
        w3->lewy = w1;
        w3->prawy = w2;

        // umieszczamy wierzchołek w3 na końcu listy, a następnie ją sortujemy
        lista_wierzcholkow.push_back(w3);
        lista_wierzcholkow.sort(funkcja_porownujaca);
    }

    // gotowe drzewo kodowe
    wierzcholek* drzewo_kodowe = lista_wierzcholkow.back();

    // tworzenie książki kodowej
    kod* ksiazka_kodowa = new kod[liczba_znakow];
    utworz_ksiazke_kodowa(drzewo_kodowe, ksiazka_kodowa);

    // wypisywanie książki kodowej
    cout << "Ksiazka kodowa:" << endl;
    for (int i = 0; i < liczba_znakow; ++i) {
        cout << ksiazka_kodowa[i].znak << ": " << ksiazka_kodowa[i].slowo_kodowe << endl;
    }

    return 0;
}

Wynik działania programu:

Zliczenia kazdego znaku:
D: 1
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
t: 1
k: 1
i: 1
Lista wierzcholkow:
D: 1
a: 3
d: 5
i: 1
k: 1
o: 3
t: 1
Lista wierzcholkow po posortowaniu:
d: 5
a: 3
o: 3
D: 1
i: 1
k: 1
t: 1
Ksiazka kodowa:
o: 00
a: 01
i: 1000
D: 1001
t: 1010
k: 1011
d: 11

Każdy zakodowany znak ma teraz przypisany właściwy łańcuch znaków.

Teraz możemy przejść do kodowania wiadomości. W tym celu utworzymy dwie funkcje. Pierwsza z nich będzie odpowiadać za odnalezienie w książce kodowej danego znaku oraz zwrócenie jego słowa kodowego. Druga zaś dla każdego znaku w wiadomości wywoła pierwszą funkcję, a następnie połączy słowa kodowe oraz zwróci zakodowaną wiadomość.

Linia 1. string znajdz podkreślnik slowo podkreślnik kodowe otwórz nawias okrągły char znak przecinek kod asterysk ksiazka podkreślnik kodowa przecinek int dlugosc podkreślnik ksiazki podkreślnik kodowej zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dlugosc podkreślnik ksiazki podkreślnik kodowej średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. if otwórz nawias okrągły ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka znak znak równości znak równości znak zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. return ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowo podkreślnik kodowe średnik. Linia 5. zamknij nawias klamrowy. Linia 6. zamknij nawias klamrowy. Linia 7. zamknij nawias klamrowy. Linia 9. string zakoduj podkreślnik wiadomosc otwórz nawias okrągły string wiadomosc przecinek kod asterysk ksiazka podkreślnik kodowa przecinek int dlugosc podkreślnik ksiazki podkreślnik kodowej zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. string zakodowana podkreślnik wiadomosc znak równości cudzysłów cudzysłów średnik. Linia 11. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. zakodowana podkreślnik wiadomosc plus znak równości znajdz podkreślnik slowo podkreślnik kodowe otwórz nawias okrągły wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek ksiazka podkreślnik kodowa przecinek dlugosc podkreślnik ksiazki podkreślnik kodowej zamknij nawias okrągły średnik. Linia 13. zamknij nawias klamrowy. Linia 14. return zakodowana podkreślnik wiadomosc średnik. Linia 15. zamknij nawias klamrowy.

string znajdz_slowo_kodowe(char znak, kod* ksiazka_kodowa, int dlugosc_ksiazki_kodowej) {
    for (int i = 0; i < dlugosc_ksiazki_kodowej; ++i) {
        if (ksiazka_kodowa[i].znak == znak) {
            return ksiazka_kodowa[i].slowo_kodowe;
        }
    }
}

string zakoduj_wiadomosc(string wiadomosc, kod* ksiazka_kodowa, int dlugosc_ksiazki_kodowej) {
    string zakodowana_wiadomosc = "";
    for (int i = 0; i < wiadomosc.length(); ++i) {
        zakodowana_wiadomosc += znajdz_slowo_kodowe(wiadomosc[i], ksiazka_kodowa, dlugosc_ksiazki_kodowej);
    }
    return zakodowana_wiadomosc;
}

W funkcji main możemy teraz dodać kod odpowiadający za wywołanie funkcji kodującej oraz wypisywanie zakodowanej wiadomości:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny string zamknij nawias ostrokątny. Linia 3. kratka include otwórz nawias ostrokątny list zamknij nawias ostrokątny. Linia 5. using namespace std średnik. Linia 7. struct wierzcholek otwórz nawias klamrowy. Linia 8. char znak średnik. Linia 9. int czestosc średnik. Linia 10. wierzcholek asterysk lewy znak równości nullptr średnik. Linia 11. wierzcholek asterysk prawy znak równości nullptr średnik. Linia 12. zamknij nawias klamrowy średnik. Linia 14. struct kod otwórz nawias klamrowy. Linia 15. char znak średnik. Linia 16. string slowo podkreślnik kodowe średnik. Linia 17. zamknij nawias klamrowy średnik. Linia 19. int zlicz podkreślnik znaki otwórz nawias okrągły string wiadomosc przecinek int asterysk tablica podkreślnik zliczen zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny znak równości 255 średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 22. zamknij nawias klamrowy. Linia 23. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. plus plus tablica podkreślnik zliczen otwórz nawias kwadratowy wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy średnik. Linia 25. zamknij nawias klamrowy. Linia 26. int liczba znak równości 0 średnik. Linia 27. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny znak równości 255 średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. if otwórz nawias okrągły tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. plus plus liczba średnik. Linia 30. zamknij nawias klamrowy. Linia 31. zamknij nawias klamrowy. Linia 32. return liczba średnik. Linia 33. zamknij nawias klamrowy. Linia 35. bool funkcja podkreślnik porownujaca otwórz nawias okrągły wierzcholek asterysk w1 przecinek wierzcholek asterysk w2 zamknij nawias okrągły otwórz nawias klamrowy. Linia 36. return w1 minus zamknij nawias ostrokątny czestosc zamknij nawias ostrokątny w2 minus zamknij nawias ostrokątny czestosc średnik. Linia 37. zamknij nawias klamrowy. Linia 39. void utworz podkreślnik ksiazke podkreślnik kodowa otwórz nawias okrągły wierzcholek asterysk drzewo podkreślnik kodowe przecinek kod asterysk ksiazka podkreślnik kodowa przecinek string dotychczasowy podkreślnik kod znak równości cudzysłów cudzysłów zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. static int i znak równości 0 średnik. Linia 41. if otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny lewy znak równości znak równości nullptr ampersant ampersant drzewo podkreślnik kodowe minus zamknij nawias ostrokątny prawy znak równości znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 42. ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka znak znak równości drzewo podkreślnik kodowe minus zamknij nawias ostrokątny znak średnik. Linia 43. ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowo podkreślnik kodowe znak równości dotychczasowy podkreślnik kod średnik. Linia 44. plus plus i średnik. Linia 45. zamknij nawias klamrowy. Linia 46. else otwórz nawias klamrowy. Linia 47. utworz podkreślnik ksiazke podkreślnik kodowa otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny lewy przecinek ksiazka podkreślnik kodowa przecinek dotychczasowy podkreślnik kod plus cudzysłów 0 cudzysłów zamknij nawias okrągły średnik. Linia 48. utworz podkreślnik ksiazke podkreślnik kodowa otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny prawy przecinek ksiazka podkreślnik kodowa przecinek dotychczasowy podkreślnik kod plus cudzysłów 1 cudzysłów zamknij nawias okrągły średnik. Linia 49. zamknij nawias klamrowy. Linia 50. zamknij nawias klamrowy. Linia 52. string znajdz podkreślnik slowo podkreślnik kodowe otwórz nawias okrągły char znak przecinek kod asterysk ksiazka podkreślnik kodowa przecinek int dlugosc podkreślnik ksiazki podkreślnik kodowej zamknij nawias okrągły otwórz nawias klamrowy. Linia 53. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dlugosc podkreślnik ksiazki podkreślnik kodowej średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 54. if otwórz nawias okrągły ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka znak znak równości znak równości znak zamknij nawias okrągły otwórz nawias klamrowy. Linia 55. return ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowo podkreślnik kodowe średnik. Linia 56. zamknij nawias klamrowy. Linia 57. zamknij nawias klamrowy. Linia 58. zamknij nawias klamrowy. Linia 60. string zakoduj podkreślnik wiadomosc otwórz nawias okrągły string wiadomosc przecinek kod asterysk ksiazka podkreślnik kodowa przecinek int dlugosc podkreślnik ksiazki podkreślnik kodowej zamknij nawias okrągły otwórz nawias klamrowy. Linia 61. string zakodowana podkreślnik wiadomosc znak równości cudzysłów cudzysłów średnik. Linia 62. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 63. zakodowana podkreślnik wiadomosc plus znak równości znajdz podkreślnik slowo podkreślnik kodowe otwórz nawias okrągły wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek ksiazka podkreślnik kodowa przecinek dlugosc podkreślnik ksiazki podkreślnik kodowej zamknij nawias okrągły średnik. Linia 64. zamknij nawias klamrowy. Linia 65. return zakodowana podkreślnik wiadomosc średnik. Linia 66. zamknij nawias klamrowy. Linia 68. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 69. int tablica podkreślnik zliczen otwórz nawias kwadratowy 256 zamknij nawias kwadratowy średnik. Linia 70. string wiadomosc znak równości cudzysłów Dodadodadodatki cudzysłów średnik. Linia 72. prawy ukośnik prawy ukośnik zliczanie znaków w wiadomości. Linia 73. int liczba podkreślnik znakow znak równości zlicz podkreślnik znaki otwórz nawias okrągły wiadomosc przecinek tablica podkreślnik zliczen zamknij nawias okrągły średnik. Linia 75. prawy ukośnik prawy ukośnik wypisywanie zliczeń dla każdego znaku z wiadomości. Linia 76. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Zliczenia kazdego znaku dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 77. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 78. char znak znak równości wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 79. cout otwórz nawias ostrokątny otwórz nawias ostrokątny znak otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny tablica podkreślnik zliczen otwórz nawias kwadratowy znak zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 80. zamknij nawias klamrowy. Linia 82. prawy ukośnik prawy ukośnik tworzenie listy wierzchołków. Linia 83. list otwórz nawias ostrokątny wierzcholek asterysk zamknij nawias ostrokątny lista podkreślnik wierzcholkow średnik. Linia 84. int j znak równości 0 średnik. Linia 85. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny znak równości 255 średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 86. if otwórz nawias okrągły tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 87. lista podkreślnik wierzcholkow kropka push podkreślnik back otwórz nawias okrągły new wierzcholek otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 88. lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły minus zamknij nawias ostrokątny znak znak równości i średnik. Linia 89. lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły minus zamknij nawias ostrokątny czestosc znak równości tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 90. plus plus j średnik. Linia 91. if otwórz nawias okrągły j znak równości znak równości liczba podkreślnik znakow zamknij nawias okrągły otwórz nawias klamrowy. Linia 92. break średnik. Linia 93. zamknij nawias klamrowy. Linia 94. zamknij nawias klamrowy. Linia 95. zamknij nawias klamrowy. Linia 97. prawy ukośnik prawy ukośnik wypisywanie listy wierzchołków. Linia 98. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Lista wierzcholkow dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 99. for otwórz nawias okrągły wierzcholek asterysk w dwukropek lista podkreślnik wierzcholkow zamknij nawias okrągły otwórz nawias klamrowy. Linia 100. cout otwórz nawias ostrokątny otwórz nawias ostrokątny w minus zamknij nawias ostrokątny znak otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny w minus zamknij nawias ostrokątny czestosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 101. zamknij nawias klamrowy. Linia 103. prawy ukośnik prawy ukośnik sortowanie listy wierzchołków. Linia 104. lista podkreślnik wierzcholkow kropka sort otwórz nawias okrągły funkcja podkreślnik porownujaca zamknij nawias okrągły średnik. Linia 106. prawy ukośnik prawy ukośnik wypisywanie listy wierzchołków po posortowaniu. Linia 107. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Lista wierzcholkow po posortowaniu dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 108. for otwórz nawias okrągły wierzcholek asterysk w dwukropek lista podkreślnik wierzcholkow zamknij nawias okrągły otwórz nawias klamrowy. Linia 109. cout otwórz nawias ostrokątny otwórz nawias ostrokątny w minus zamknij nawias ostrokątny znak otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny w minus zamknij nawias ostrokątny czestosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 110. zamknij nawias klamrowy. Linia 112. prawy ukośnik prawy ukośnik tworzenie drzewa kodowego. Linia 113. while otwórz nawias okrągły lista podkreślnik wierzcholkow kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias ostrokątny 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 114. prawy ukośnik prawy ukośnik zdejmujemy z listy 2 wierzchołki w1 i w2. Linia 115. wierzcholek asterysk w1 znak równości lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 116. lista podkreślnik wierzcholkow kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 117. wierzcholek asterysk w2 znak równości lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 118. lista podkreślnik wierzcholkow kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 120. prawy ukośnik prawy ukośnik łączymy wierzchołki w1 oraz w2 przecinek tworząc wierzchołek w3. Linia 121. wierzcholek asterysk w3 znak równości new wierzcholek otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 122. w3 minus zamknij nawias ostrokątny czestosc znak równości w1 minus zamknij nawias ostrokątny czestosc plus w2 minus zamknij nawias ostrokątny czestosc średnik. Linia 123. w3 minus zamknij nawias ostrokątny lewy znak równości w1 średnik. Linia 124. w3 minus zamknij nawias ostrokątny prawy znak równości w2 średnik. Linia 126. prawy ukośnik prawy ukośnik umieszczamy wierzchołek w3 na końcu listy przecinek a następnie ją sortujemy. Linia 127. lista podkreślnik wierzcholkow kropka push podkreślnik back otwórz nawias okrągły w3 zamknij nawias okrągły średnik. Linia 128. lista podkreślnik wierzcholkow kropka sort otwórz nawias okrągły funkcja podkreślnik porownujaca zamknij nawias okrągły średnik. Linia 129. zamknij nawias klamrowy. Linia 131. prawy ukośnik prawy ukośnik gotowe drzewo kodowe. Linia 132. wierzcholek asterysk drzewo podkreślnik kodowe znak równości lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 134. prawy ukośnik prawy ukośnik tworzenie książki kodowej. Linia 135. kod asterysk ksiazka podkreślnik kodowa znak równości new kod otwórz nawias kwadratowy liczba podkreślnik znakow zamknij nawias kwadratowy średnik. Linia 136. utworz podkreślnik ksiazke podkreślnik kodowa otwórz nawias okrągły drzewo podkreślnik kodowe przecinek ksiazka podkreślnik kodowa zamknij nawias okrągły średnik. Linia 138. prawy ukośnik prawy ukośnik wypisywanie książki kodowej. Linia 139. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Ksiazka kodowa dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 140. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczba podkreślnik znakow średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 141. cout otwórz nawias ostrokątny otwórz nawias ostrokątny ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka znak otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowo podkreślnik kodowe otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 142. zamknij nawias klamrowy. Linia 144. prawy ukośnik prawy ukośnik kodowanie wiadomości. Linia 145. string zakodowana podkreślnik wiadomosc znak równości zakoduj podkreślnik wiadomosc otwórz nawias okrągły wiadomosc przecinek ksiazka podkreślnik kodowa przecinek liczba podkreślnik znakow zamknij nawias okrągły średnik. Linia 147. prawy ukośnik prawy ukośnik wypisywanie niezakodowanej i zakodowanej wiadomości. Linia 148. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Niezakodowana wiadomosc dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 149. cout otwórz nawias ostrokątny otwórz nawias ostrokątny wiadomosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 150. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Zakodowana wiadomosc dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 151. cout otwórz nawias ostrokątny otwórz nawias ostrokątny zakodowana podkreślnik wiadomosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 153. return 0 średnik. Linia 154. zamknij nawias klamrowy.

#include <iostream>
#include <string>
#include <list>

using namespace std;

struct wierzcholek {
    char znak;
    int czestosc;
    wierzcholek* lewy = nullptr;
    wierzcholek* prawy = nullptr;
};

struct kod {
    char znak;
    string slowo_kodowe;
};

int zlicz_znaki(string wiadomosc, int* tablica_zliczen) {
    for (int i = 0; i <= 255; ++i) {
        tablica_zliczen[i] = 0;
    }
    for (int i = 0; i < wiadomosc.length(); ++i) {
        ++tablica_zliczen[wiadomosc[i]];
    }
    int liczba = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            ++liczba;
        }
    }
    return liczba;
}

bool funkcja_porownujaca(wierzcholek* w1, wierzcholek* w2) {
    return w1->czestosc > w2->czestosc;
}

void utworz_ksiazke_kodowa(wierzcholek* drzewo_kodowe, kod* ksiazka_kodowa, string dotychczasowy_kod = "") {
    static int i = 0;
    if (drzewo_kodowe->lewy == nullptr && drzewo_kodowe->prawy == nullptr) {
        ksiazka_kodowa[i].znak = drzewo_kodowe->znak;
        ksiazka_kodowa[i].slowo_kodowe = dotychczasowy_kod;
        ++i;
    }
    else {
        utworz_ksiazke_kodowa(drzewo_kodowe->lewy, ksiazka_kodowa, dotychczasowy_kod + "0");
        utworz_ksiazke_kodowa(drzewo_kodowe->prawy, ksiazka_kodowa, dotychczasowy_kod + "1");
    }
}

string znajdz_slowo_kodowe(char znak, kod* ksiazka_kodowa, int dlugosc_ksiazki_kodowej) {
    for (int i = 0; i < dlugosc_ksiazki_kodowej; ++i) {
        if (ksiazka_kodowa[i].znak == znak) {
            return ksiazka_kodowa[i].slowo_kodowe;
        }
    }
}

string zakoduj_wiadomosc(string wiadomosc, kod* ksiazka_kodowa, int dlugosc_ksiazki_kodowej) {
    string zakodowana_wiadomosc = "";
    for (int i = 0; i < wiadomosc.length(); ++i) {
        zakodowana_wiadomosc += znajdz_slowo_kodowe(wiadomosc[i], ksiazka_kodowa, dlugosc_ksiazki_kodowej);
    }
    return zakodowana_wiadomosc;
}

int main() {
    int tablica_zliczen[256];
    string wiadomosc = "Dodadodadodatki";

    // zliczanie znaków w wiadomości
    int liczba_znakow = zlicz_znaki(wiadomosc, tablica_zliczen);

    // wypisywanie zliczeń dla każdego znaku z wiadomości
    cout << "Zliczenia kazdego znaku:" << endl;
    for (int i = 0; i < wiadomosc.length(); ++i) {
        char znak = wiadomosc[i];
        cout << znak << ": " << tablica_zliczen[znak] << endl;
    }

    // tworzenie listy wierzchołków
    list<wierzcholek*> lista_wierzcholkow;
    int j = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            lista_wierzcholkow.push_back(new wierzcholek());
            lista_wierzcholkow.back()->znak = i;
            lista_wierzcholkow.back()->czestosc = tablica_zliczen[i];
            ++j;
            if (j == liczba_znakow) {
                break;
            }
        }
    }

    // wypisywanie listy wierzchołków
    cout << "Lista wierzcholkow:" << endl;
    for (wierzcholek* w : lista_wierzcholkow) {
        cout << w->znak << ": " << w->czestosc << endl;
    }

    // sortowanie listy wierzchołków
    lista_wierzcholkow.sort(funkcja_porownujaca);

    // wypisywanie listy wierzchołków po posortowaniu
    cout << "Lista wierzcholkow po posortowaniu:" << endl;
    for (wierzcholek* w : lista_wierzcholkow) {
        cout << w->znak << ": " << w->czestosc << endl;
    }

    // tworzenie drzewa kodowego
    while (lista_wierzcholkow.size() > 1) {
        // zdejmujemy z listy 2 wierzchołki w1 i w2
        wierzcholek* w1 = lista_wierzcholkow.back();
        lista_wierzcholkow.pop_back();
        wierzcholek* w2 = lista_wierzcholkow.back();
        lista_wierzcholkow.pop_back();

        // łączymy wierzchołki w1 oraz w2, tworząc wierzchołek w3
        wierzcholek* w3 = new wierzcholek();
        w3->czestosc = w1->czestosc + w2->czestosc;
        w3->lewy = w1;
        w3->prawy = w2;

        // umieszczamy wierzchołek w3 na końcu listy, a następnie ją sortujemy
        lista_wierzcholkow.push_back(w3);
        lista_wierzcholkow.sort(funkcja_porownujaca);
    }

    // gotowe drzewo kodowe
    wierzcholek* drzewo_kodowe = lista_wierzcholkow.back();

    // tworzenie książki kodowej
    kod* ksiazka_kodowa = new kod[liczba_znakow];
    utworz_ksiazke_kodowa(drzewo_kodowe, ksiazka_kodowa);

    // wypisywanie książki kodowej
    cout << "Ksiazka kodowa:" << endl;
    for (int i = 0; i < liczba_znakow; ++i) {
        cout << ksiazka_kodowa[i].znak << ": " << ksiazka_kodowa[i].slowo_kodowe << endl;
    }

    // kodowanie wiadomości
    string zakodowana_wiadomosc = zakoduj_wiadomosc(wiadomosc, ksiazka_kodowa, liczba_znakow);

    // wypisywanie niezakodowanej i zakodowanej wiadomości
    cout << "Niezakodowana wiadomosc:" << endl;
    cout << wiadomosc << endl;
    cout << "Zakodowana wiadomosc:" << endl;
    cout << zakodowana_wiadomosc << endl;
    
    return 0;
}

Wynik działania programu:

Zliczenia kazdego znaku:
D: 1
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
t: 1
k: 1
i: 1
Lista wierzcholkow:
D: 1
a: 3
d: 5
i: 1
k: 1
o: 3
t: 1
Lista wierzcholkow po posortowaniu:
d: 5
a: 3
o: 3
D: 1
i: 1
k: 1
t: 1
Ksiazka kodowa:
o: 00
a: 01
i: 1000
D: 1001
t: 1010
k: 1011
d: 11
Niezakodowana wiadomosc:
Dodadodadodatki
Zakodowana wiadomosc:
10010011011100110111001101101010111000

Pozostało już tylko uzupełnić kod o zwalnianie pamięci dynamicznej. Ponieważ wszystkie wskaźniki na istniejące w pamięci struktury typu wierzcholek zawierają się w drzewie kodowym, napiszemy funkcję, która rekurencyjnie zwalnia dla nich wszystkich pamięć.

void zwolnij_pamiec(wierzcholek* drzewo_kodowe) {
    if (drzewo_kodowe->lewy != nullptr && drzewo_kodowe->prawy != nullptr) {
        zwolnij_pamiec(drzewo_kodowe->lewy);
        zwolnij_pamiec(drzewo_kodowe->prawy);
    }
    delete drzewo_kodowe;
}

Wewnątrz funkcji main zawrzemy wywołanie napisanej funkcji, a także usunięcie pamięci przeznaczonej na książkę kodową, która jest tablicą dynamiczną. Ostateczny kod prezentuje się następująco:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny string zamknij nawias ostrokątny. Linia 3. kratka include otwórz nawias ostrokątny list zamknij nawias ostrokątny. Linia 5. using namespace std średnik. Linia 7. struct wierzcholek otwórz nawias klamrowy. Linia 8. char znak średnik. Linia 9. int czestosc średnik. Linia 10. wierzcholek asterysk lewy znak równości nullptr średnik. Linia 11. wierzcholek asterysk prawy znak równości nullptr średnik. Linia 12. zamknij nawias klamrowy średnik. Linia 14. struct kod otwórz nawias klamrowy. Linia 15. char znak średnik. Linia 16. string slowo podkreślnik kodowe średnik. Linia 17. zamknij nawias klamrowy średnik. Linia 19. int zlicz podkreślnik znaki otwórz nawias okrągły string wiadomosc przecinek int asterysk tablica podkreślnik zliczen zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny znak równości 255 średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 22. zamknij nawias klamrowy. Linia 23. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. plus plus tablica podkreślnik zliczen otwórz nawias kwadratowy wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy średnik. Linia 25. zamknij nawias klamrowy. Linia 26. int liczba znak równości 0 średnik. Linia 27. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny znak równości 255 średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. if otwórz nawias okrągły tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. plus plus liczba średnik. Linia 30. zamknij nawias klamrowy. Linia 31. zamknij nawias klamrowy. Linia 32. return liczba średnik. Linia 33. zamknij nawias klamrowy. Linia 35. bool funkcja podkreślnik porownujaca otwórz nawias okrągły wierzcholek asterysk w1 przecinek wierzcholek asterysk w2 zamknij nawias okrągły otwórz nawias klamrowy. Linia 36. return w1 minus zamknij nawias ostrokątny czestosc zamknij nawias ostrokątny w2 minus zamknij nawias ostrokątny czestosc średnik. Linia 37. zamknij nawias klamrowy. Linia 39. void utworz podkreślnik ksiazke podkreślnik kodowa otwórz nawias okrągły wierzcholek asterysk drzewo podkreślnik kodowe przecinek kod asterysk ksiazka podkreślnik kodowa przecinek string dotychczasowy podkreślnik kod znak równości cudzysłów cudzysłów zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. static int i znak równości 0 średnik. Linia 41. if otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny lewy znak równości znak równości nullptr ampersant ampersant drzewo podkreślnik kodowe minus zamknij nawias ostrokątny prawy znak równości znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 42. ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka znak znak równości drzewo podkreślnik kodowe minus zamknij nawias ostrokątny znak średnik. Linia 43. ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowo podkreślnik kodowe znak równości dotychczasowy podkreślnik kod średnik. Linia 44. plus plus i średnik. Linia 45. zamknij nawias klamrowy. Linia 46. else otwórz nawias klamrowy. Linia 47. utworz podkreślnik ksiazke podkreślnik kodowa otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny lewy przecinek ksiazka podkreślnik kodowa przecinek dotychczasowy podkreślnik kod plus cudzysłów 0 cudzysłów zamknij nawias okrągły średnik. Linia 48. utworz podkreślnik ksiazke podkreślnik kodowa otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny prawy przecinek ksiazka podkreślnik kodowa przecinek dotychczasowy podkreślnik kod plus cudzysłów 1 cudzysłów zamknij nawias okrągły średnik. Linia 49. zamknij nawias klamrowy. Linia 50. zamknij nawias klamrowy. Linia 52. string znajdz podkreślnik slowo podkreślnik kodowe otwórz nawias okrągły char znak przecinek kod asterysk ksiazka podkreślnik kodowa przecinek int dlugosc podkreślnik ksiazki podkreślnik kodowej zamknij nawias okrągły otwórz nawias klamrowy. Linia 53. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dlugosc podkreślnik ksiazki podkreślnik kodowej średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 54. if otwórz nawias okrągły ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka znak znak równości znak równości znak zamknij nawias okrągły otwórz nawias klamrowy. Linia 55. return ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowo podkreślnik kodowe średnik. Linia 56. zamknij nawias klamrowy. Linia 57. zamknij nawias klamrowy. Linia 58. zamknij nawias klamrowy. Linia 60. string zakoduj podkreślnik wiadomosc otwórz nawias okrągły string wiadomosc przecinek kod asterysk ksiazka podkreślnik kodowa przecinek int dlugosc podkreślnik ksiazki podkreślnik kodowej zamknij nawias okrągły otwórz nawias klamrowy. Linia 61. string zakodowana podkreślnik wiadomosc znak równości cudzysłów cudzysłów średnik. Linia 62. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 63. zakodowana podkreślnik wiadomosc plus znak równości znajdz podkreślnik slowo podkreślnik kodowe otwórz nawias okrągły wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek ksiazka podkreślnik kodowa przecinek dlugosc podkreślnik ksiazki podkreślnik kodowej zamknij nawias okrągły średnik. Linia 64. zamknij nawias klamrowy. Linia 65. return zakodowana podkreślnik wiadomosc średnik. Linia 66. zamknij nawias klamrowy. Linia 68. void zwolnij podkreślnik pamiec otwórz nawias okrągły wierzcholek asterysk drzewo podkreślnik kodowe zamknij nawias okrągły otwórz nawias klamrowy. Linia 69. if otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny lewy wykrzyknik znak równości nullptr ampersant ampersant drzewo podkreślnik kodowe minus zamknij nawias ostrokątny prawy wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 70. zwolnij podkreślnik pamiec otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny lewy zamknij nawias okrągły średnik. Linia 71. zwolnij podkreślnik pamiec otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny prawy zamknij nawias okrągły średnik. Linia 72. zamknij nawias klamrowy. Linia 73. delete drzewo podkreślnik kodowe średnik. Linia 74. zamknij nawias klamrowy. Linia 76. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 77. int tablica podkreślnik zliczen otwórz nawias kwadratowy 256 zamknij nawias kwadratowy średnik. Linia 78. string wiadomosc znak równości cudzysłów Dodadodadodatki cudzysłów średnik. Linia 80. prawy ukośnik prawy ukośnik zliczanie znaków w wiadomości. Linia 81. int liczba podkreślnik znakow znak równości zlicz podkreślnik znaki otwórz nawias okrągły wiadomosc przecinek tablica podkreślnik zliczen zamknij nawias okrągły średnik. Linia 83. prawy ukośnik prawy ukośnik wypisywanie zliczeń dla każdego znaku z wiadomości. Linia 84. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Zliczenia kazdego znaku dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 85. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 86. char znak znak równości wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 87. cout otwórz nawias ostrokątny otwórz nawias ostrokątny znak otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny tablica podkreślnik zliczen otwórz nawias kwadratowy znak zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 88. zamknij nawias klamrowy. Linia 90. prawy ukośnik prawy ukośnik tworzenie listy wierzchołków. Linia 91. list otwórz nawias ostrokątny wierzcholek asterysk zamknij nawias ostrokątny lista podkreślnik wierzcholkow średnik. Linia 92. int j znak równości 0 średnik. Linia 93. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny znak równości 255 średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 94. if otwórz nawias okrągły tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 95. lista podkreślnik wierzcholkow kropka push podkreślnik back otwórz nawias okrągły new wierzcholek otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 96. lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły minus zamknij nawias ostrokątny znak znak równości i średnik. Linia 97. lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły minus zamknij nawias ostrokątny czestosc znak równości tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 98. plus plus j średnik. Linia 99. if otwórz nawias okrągły j znak równości znak równości liczba podkreślnik znakow zamknij nawias okrągły otwórz nawias klamrowy. Linia 100. break średnik. Linia 101. zamknij nawias klamrowy. Linia 102. zamknij nawias klamrowy. Linia 103. zamknij nawias klamrowy. Linia 105. prawy ukośnik prawy ukośnik wypisywanie listy wierzchołków. Linia 106. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Lista wierzcholkow dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 107. for otwórz nawias okrągły wierzcholek asterysk w dwukropek lista podkreślnik wierzcholkow zamknij nawias okrągły otwórz nawias klamrowy. Linia 108. cout otwórz nawias ostrokątny otwórz nawias ostrokątny w minus zamknij nawias ostrokątny znak otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny w minus zamknij nawias ostrokątny czestosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 109. zamknij nawias klamrowy. Linia 111. prawy ukośnik prawy ukośnik sortowanie listy wierzchołków. Linia 112. lista podkreślnik wierzcholkow kropka sort otwórz nawias okrągły funkcja podkreślnik porownujaca zamknij nawias okrągły średnik. Linia 114. prawy ukośnik prawy ukośnik wypisywanie listy wierzchołków po posortowaniu. Linia 115. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Lista wierzcholkow po posortowaniu dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 116. for otwórz nawias okrągły wierzcholek asterysk w dwukropek lista podkreślnik wierzcholkow zamknij nawias okrągły otwórz nawias klamrowy. Linia 117. cout otwórz nawias ostrokątny otwórz nawias ostrokątny w minus zamknij nawias ostrokątny znak otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny w minus zamknij nawias ostrokątny czestosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 118. zamknij nawias klamrowy. Linia 120. prawy ukośnik prawy ukośnik tworzenie drzewa kodowego. Linia 121. while otwórz nawias okrągły lista podkreślnik wierzcholkow kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias ostrokątny 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 122. prawy ukośnik prawy ukośnik zdejmujemy z listy 2 wierzchołki w1 i w2. Linia 123. wierzcholek asterysk w1 znak równości lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 124. lista podkreślnik wierzcholkow kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 125. wierzcholek asterysk w2 znak równości lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 126. lista podkreślnik wierzcholkow kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 128. prawy ukośnik prawy ukośnik łączymy wierzchołki w1 oraz w2 przecinek tworząc wierzchołek w3. Linia 129. wierzcholek asterysk w3 znak równości new wierzcholek otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 130. w3 minus zamknij nawias ostrokątny czestosc znak równości w1 minus zamknij nawias ostrokątny czestosc plus w2 minus zamknij nawias ostrokątny czestosc średnik. Linia 131. w3 minus zamknij nawias ostrokątny lewy znak równości w1 średnik. Linia 132. w3 minus zamknij nawias ostrokątny prawy znak równości w2 średnik. Linia 134. prawy ukośnik prawy ukośnik umieszczamy wierzchołek w3 na końcu listy przecinek a następnie ją sortujemy. Linia 135. lista podkreślnik wierzcholkow kropka push podkreślnik back otwórz nawias okrągły w3 zamknij nawias okrągły średnik. Linia 136. lista podkreślnik wierzcholkow kropka sort otwórz nawias okrągły funkcja podkreślnik porownujaca zamknij nawias okrągły średnik. Linia 137. zamknij nawias klamrowy. Linia 139. prawy ukośnik prawy ukośnik gotowe drzewo kodowe. Linia 140. wierzcholek asterysk drzewo podkreślnik kodowe znak równości lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 142. prawy ukośnik prawy ukośnik tworzenie książki kodowej. Linia 143. kod asterysk ksiazka podkreślnik kodowa znak równości new kod otwórz nawias kwadratowy liczba podkreślnik znakow zamknij nawias kwadratowy średnik. Linia 144. utworz podkreślnik ksiazke podkreślnik kodowa otwórz nawias okrągły drzewo podkreślnik kodowe przecinek ksiazka podkreślnik kodowa zamknij nawias okrągły średnik. Linia 146. prawy ukośnik prawy ukośnik wypisywanie książki kodowej. Linia 147. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Ksiazka kodowa dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 148. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczba podkreślnik znakow średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 149. cout otwórz nawias ostrokątny otwórz nawias ostrokątny ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka znak otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowo podkreślnik kodowe otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 150. zamknij nawias klamrowy. Linia 152. prawy ukośnik prawy ukośnik kodowanie wiadomości. Linia 153. string zakodowana podkreślnik wiadomosc znak równości zakoduj podkreślnik wiadomosc otwórz nawias okrągły wiadomosc przecinek ksiazka podkreślnik kodowa przecinek liczba podkreślnik znakow zamknij nawias okrągły średnik. Linia 155. prawy ukośnik prawy ukośnik wypisywanie niezakodowanej i zakodowanej wiadomości. Linia 156. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Niezakodowana wiadomosc dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 157. cout otwórz nawias ostrokątny otwórz nawias ostrokątny wiadomosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 158. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Zakodowana wiadomosc dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 159. cout otwórz nawias ostrokątny otwórz nawias ostrokątny zakodowana podkreślnik wiadomosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 161. prawy ukośnik prawy ukośnik zwolnienie pamięci. Linia 162. zwolnij podkreślnik pamiec otwórz nawias okrągły drzewo podkreślnik kodowe zamknij nawias okrągły średnik. Linia 163. delete otwórz nawias kwadratowy zamknij nawias kwadratowy ksiazka podkreślnik kodowa średnik. Linia 165. return 0 średnik. Linia 166. zamknij nawias klamrowy.

#include <iostream>
#include <string>
#include <list>

using namespace std;

struct wierzcholek {
    char znak;
    int czestosc;
    wierzcholek* lewy = nullptr;
    wierzcholek* prawy = nullptr;
};

struct kod {
    char znak;
    string slowo_kodowe;
};

int zlicz_znaki(string wiadomosc, int* tablica_zliczen) {
    for (int i = 0; i <= 255; ++i) {
        tablica_zliczen[i] = 0;
    }
    for (int i = 0; i < wiadomosc.length(); ++i) {
        ++tablica_zliczen[wiadomosc[i]];
    }
    int liczba = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            ++liczba;
        }
    }
    return liczba;
}

bool funkcja_porownujaca(wierzcholek* w1, wierzcholek* w2) {
    return w1->czestosc > w2->czestosc;
}

void utworz_ksiazke_kodowa(wierzcholek* drzewo_kodowe, kod* ksiazka_kodowa, string dotychczasowy_kod = "") {
    static int i = 0;
    if (drzewo_kodowe->lewy == nullptr && drzewo_kodowe->prawy == nullptr) {
        ksiazka_kodowa[i].znak = drzewo_kodowe->znak;
        ksiazka_kodowa[i].slowo_kodowe = dotychczasowy_kod;
        ++i;
    }
    else {
        utworz_ksiazke_kodowa(drzewo_kodowe->lewy, ksiazka_kodowa, dotychczasowy_kod + "0");
        utworz_ksiazke_kodowa(drzewo_kodowe->prawy, ksiazka_kodowa, dotychczasowy_kod + "1");
    }
}

string znajdz_slowo_kodowe(char znak, kod* ksiazka_kodowa, int dlugosc_ksiazki_kodowej) {
    for (int i = 0; i < dlugosc_ksiazki_kodowej; ++i) {
        if (ksiazka_kodowa[i].znak == znak) {
            return ksiazka_kodowa[i].slowo_kodowe;
        }
    }
}

string zakoduj_wiadomosc(string wiadomosc, kod* ksiazka_kodowa, int dlugosc_ksiazki_kodowej) {
    string zakodowana_wiadomosc = "";
    for (int i = 0; i < wiadomosc.length(); ++i) {
        zakodowana_wiadomosc += znajdz_slowo_kodowe(wiadomosc[i], ksiazka_kodowa, dlugosc_ksiazki_kodowej);
    }
    return zakodowana_wiadomosc;
}

void zwolnij_pamiec(wierzcholek* drzewo_kodowe) {
    if (drzewo_kodowe->lewy != nullptr && drzewo_kodowe->prawy != nullptr) {
        zwolnij_pamiec(drzewo_kodowe->lewy);
        zwolnij_pamiec(drzewo_kodowe->prawy);
    }
    delete drzewo_kodowe;
}

int main() {
    int tablica_zliczen[256];
    string wiadomosc = "Dodadodadodatki";

    // zliczanie znaków w wiadomości
    int liczba_znakow = zlicz_znaki(wiadomosc, tablica_zliczen);

    // wypisywanie zliczeń dla każdego znaku z wiadomości
    cout << "Zliczenia kazdego znaku:" << endl;
    for (int i = 0; i < wiadomosc.length(); ++i) {
        char znak = wiadomosc[i];
        cout << znak << ": " << tablica_zliczen[znak] << endl;
    }

    // tworzenie listy wierzchołków
    list<wierzcholek*> lista_wierzcholkow;
    int j = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            lista_wierzcholkow.push_back(new wierzcholek());
            lista_wierzcholkow.back()->znak = i;
            lista_wierzcholkow.back()->czestosc = tablica_zliczen[i];
            ++j;
            if (j == liczba_znakow) {
                break;
            }
        }
    }

    // wypisywanie listy wierzchołków
    cout << "Lista wierzcholkow:" << endl;
    for (wierzcholek* w : lista_wierzcholkow) {
        cout << w->znak << ": " << w->czestosc << endl;
    }

    // sortowanie listy wierzchołków
    lista_wierzcholkow.sort(funkcja_porownujaca);

    // wypisywanie listy wierzchołków po posortowaniu
    cout << "Lista wierzcholkow po posortowaniu:" << endl;
    for (wierzcholek* w : lista_wierzcholkow) {
        cout << w->znak << ": " << w->czestosc << endl;
    }

    // tworzenie drzewa kodowego
    while (lista_wierzcholkow.size() > 1) {
        // zdejmujemy z listy 2 wierzchołki w1 i w2
        wierzcholek* w1 = lista_wierzcholkow.back();
        lista_wierzcholkow.pop_back();
        wierzcholek* w2 = lista_wierzcholkow.back();
        lista_wierzcholkow.pop_back();

        // łączymy wierzchołki w1 oraz w2, tworząc wierzchołek w3
        wierzcholek* w3 = new wierzcholek();
        w3->czestosc = w1->czestosc + w2->czestosc;
        w3->lewy = w1;
        w3->prawy = w2;

        // umieszczamy wierzchołek w3 na końcu listy, a następnie ją sortujemy
        lista_wierzcholkow.push_back(w3);
        lista_wierzcholkow.sort(funkcja_porownujaca);
    }

    // gotowe drzewo kodowe
    wierzcholek* drzewo_kodowe = lista_wierzcholkow.back();

    // tworzenie książki kodowej
    kod* ksiazka_kodowa = new kod[liczba_znakow];
    utworz_ksiazke_kodowa(drzewo_kodowe, ksiazka_kodowa);

    // wypisywanie książki kodowej
    cout << "Ksiazka kodowa:" << endl;
    for (int i = 0; i < liczba_znakow; ++i) {
        cout << ksiazka_kodowa[i].znak << ": " << ksiazka_kodowa[i].slowo_kodowe << endl;
    }

    // kodowanie wiadomości
    string zakodowana_wiadomosc = zakoduj_wiadomosc(wiadomosc, ksiazka_kodowa, liczba_znakow);

    // wypisywanie niezakodowanej i zakodowanej wiadomości
    cout << "Niezakodowana wiadomosc:" << endl;
    cout << wiadomosc << endl;
    cout << "Zakodowana wiadomosc:" << endl;
    cout << zakodowana_wiadomosc << endl;

    // zwolnienie pamięci
    zwolnij_pamiec(drzewo_kodowe);
    delete[] ksiazka_kodowa;

    return 0;
}

Wynik działania programu:

Zliczenia kazdego znaku:
D: 1
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
t: 1
k: 1
i: 1
Lista wierzcholkow:
D: 1
a: 3
d: 5
i: 1
k: 1
o: 3
t: 1
Lista wierzcholkow po posortowaniu:
d: 5
a: 3
o: 3
D: 1
i: 1
k: 1
t: 1
Ksiazka kodowa:
o: 00
a: 01
i: 1000
D: 1001
t: 1010
k: 1011
d: 11
Niezakodowana wiadomosc:
Dodadodadodatki
Zakodowana wiadomosc:
10010011011100110111001101101010111000

Problem 5

Zaimplementujmy w języku C++ program, który odkoduje wcześniej zakodowany za pomocą algorytmu Huffmana ciąg znaków.

Zakodowana wiadomość może zostać jednoznacznie zdekodowana pod warunkiem, że znana jest książka kodowa lub drzewo kodowe. Napiszmy funkcję dekodującą wiadomość za pomocą wcześniej utworzonego drzewa kodowego. Z uwagi na trudność w zawarciu drzewa kodowego jako dane programu, przedstawiona implementacja będzie polegała na odkodowaniu wcześniej zakodowanej wiadomości według już zawartego w programie drzewa kodowego.

Specyfikacja problemu:

Dane:

zakodowana_wiadomosc – łańcuch znaków (zer lub jedynek) do odkodowania
drzewo_kodowe – drzewo Huffmana utworzone w poprzednim programie

Wynik:

odkodowana_wiadomosc – łańcuch znaków reprezentujący odkodowany łańcuch znaków zakodowana_wiadomosc

Odkodowywanie wiadomości polega na poruszaniu się po drzewie kodowym według podanych w zakodowanej wiadomości zer lub jedynek. Jeśli aktualny znak to 0, schodzimy po drzewie w lewą stronę, natomiast w przypadku znaku 1 – w prawą. Gdy dojdziemy do wierzchołka, który jest liściem, możemy dodać do odkodowanej wiadomości znak zawarty w danym wierzchołku, a następnie rozpocząć poruszanie się po drzewie od początku. Kończymy w momencie, kiedy wyczerpiemy znaki z zakodowanej wiadomości. Proces ten przedstawmy w formie funkcji.

Linia 1. string odkodujWiadomosc otwórz nawias okrągły string zakodowanaWiadomosc przecinek wierzcholek asterysk drzewo podkreślnik kodowe zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. string odkodowanaWiadomosc znak równości cudzysłów cudzysłów średnik. Linia 3. wierzcholek asterysk aktualny podkreślnik wierzcholek znak równości drzewo podkreślnik kodowe średnik. Linia 4. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny zakodowanaWiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. if otwórz nawias okrągły aktualny podkreślnik wierzcholek minus zamknij nawias ostrokątny lewy znak równości znak równości nullptr ampersant ampersant aktualny podkreślnik wierzcholek minus zamknij nawias ostrokątny prawy znak równości znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. odkodowanaWiadomosc plus znak równości aktualny podkreślnik wierzcholek minus zamknij nawias ostrokątny znak średnik. Linia 7. aktualny podkreślnik wierzcholek znak równości drzewo podkreślnik kodowe średnik. Linia 8. zamknij nawias klamrowy. Linia 9. if otwórz nawias okrągły zakodowanaWiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości apostrof 0 apostrof zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. aktualny podkreślnik wierzcholek znak równości aktualny podkreślnik wierzcholek minus zamknij nawias ostrokątny lewy średnik. Linia 11. zamknij nawias klamrowy. Linia 12. else otwórz nawias klamrowy. Linia 13. aktualny podkreślnik wierzcholek znak równości aktualny podkreślnik wierzcholek minus zamknij nawias ostrokątny prawy średnik. Linia 14. zamknij nawias klamrowy. Linia 15. zamknij nawias klamrowy. Linia 16. odkodowanaWiadomosc plus znak równości aktualny podkreślnik wierzcholek minus zamknij nawias ostrokątny znak średnik. Linia 17. return odkodowanaWiadomosc średnik. Linia 18. zamknij nawias klamrowy.

string odkodujWiadomosc(string zakodowanaWiadomosc, wierzcholek* drzewo_kodowe) {
    string odkodowanaWiadomosc = "";
    wierzcholek* aktualny_wierzcholek = drzewo_kodowe;
    for (int i = 0; i < zakodowanaWiadomosc.length(); ++i) {
        if (aktualny_wierzcholek->lewy == nullptr && aktualny_wierzcholek->prawy == nullptr) {
            odkodowanaWiadomosc += aktualny_wierzcholek->znak;
            aktualny_wierzcholek = drzewo_kodowe;
        }
        if (zakodowanaWiadomosc[i] == '0') {
            aktualny_wierzcholek = aktualny_wierzcholek->lewy;
        }
        else {
            aktualny_wierzcholek = aktualny_wierzcholek->prawy;
        }
    }
    odkodowanaWiadomosc += aktualny_wierzcholek->znak;
    return odkodowanaWiadomosc;
}

Cały działający kod – stworzony w oparciu o używanie ciągów znaków zamiast ciągów bitów do kodowania – prezentuje się następująco:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny string zamknij nawias ostrokątny. Linia 3. kratka include otwórz nawias ostrokątny list zamknij nawias ostrokątny. Linia 5. using namespace std średnik. Linia 7. struct wierzcholek otwórz nawias klamrowy. Linia 8. char znak średnik. Linia 9. int czestosc średnik. Linia 10. wierzcholek asterysk lewy znak równości nullptr średnik. Linia 11. wierzcholek asterysk prawy znak równości nullptr średnik. Linia 12. zamknij nawias klamrowy średnik. Linia 14. struct kod otwórz nawias klamrowy. Linia 15. char znak średnik. Linia 16. string slowo podkreślnik kodowe średnik. Linia 17. zamknij nawias klamrowy średnik. Linia 19. int zlicz podkreślnik znaki otwórz nawias okrągły string wiadomosc przecinek int asterysk tablica podkreślnik zliczen zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny znak równości 255 średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 22. zamknij nawias klamrowy. Linia 23. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. plus plus tablica podkreślnik zliczen otwórz nawias kwadratowy wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy średnik. Linia 25. zamknij nawias klamrowy. Linia 26. int liczba znak równości 0 średnik. Linia 27. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny znak równości 255 średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. if otwórz nawias okrągły tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. plus plus liczba średnik. Linia 30. zamknij nawias klamrowy. Linia 31. zamknij nawias klamrowy. Linia 32. return liczba średnik. Linia 33. zamknij nawias klamrowy. Linia 35. bool funkcja podkreślnik porownujaca otwórz nawias okrągły wierzcholek asterysk w1 przecinek wierzcholek asterysk w2 zamknij nawias okrągły otwórz nawias klamrowy. Linia 36. return w1 minus zamknij nawias ostrokątny czestosc zamknij nawias ostrokątny w2 minus zamknij nawias ostrokątny czestosc średnik. Linia 37. zamknij nawias klamrowy. Linia 39. void utworz podkreślnik ksiazke podkreślnik kodowa otwórz nawias okrągły wierzcholek asterysk drzewo podkreślnik kodowe przecinek kod asterysk ksiazka podkreślnik kodowa przecinek string dotychczasowy podkreślnik kod znak równości cudzysłów cudzysłów zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. static int i znak równości 0 średnik. Linia 41. if otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny lewy znak równości znak równości nullptr ampersant ampersant drzewo podkreślnik kodowe minus zamknij nawias ostrokątny prawy znak równości znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 42. ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka znak znak równości drzewo podkreślnik kodowe minus zamknij nawias ostrokątny znak średnik. Linia 43. ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowo podkreślnik kodowe znak równości dotychczasowy podkreślnik kod średnik. Linia 44. plus plus i średnik. Linia 45. zamknij nawias klamrowy. Linia 46. else otwórz nawias klamrowy. Linia 47. utworz podkreślnik ksiazke podkreślnik kodowa otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny lewy przecinek ksiazka podkreślnik kodowa przecinek dotychczasowy podkreślnik kod plus cudzysłów 0 cudzysłów zamknij nawias okrągły średnik. Linia 48. utworz podkreślnik ksiazke podkreślnik kodowa otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny prawy przecinek ksiazka podkreślnik kodowa przecinek dotychczasowy podkreślnik kod plus cudzysłów 1 cudzysłów zamknij nawias okrągły średnik. Linia 49. zamknij nawias klamrowy. Linia 50. zamknij nawias klamrowy. Linia 52. string znajdz podkreślnik slowo podkreślnik kodowe otwórz nawias okrągły char znak przecinek kod asterysk ksiazka podkreślnik kodowa przecinek int dlugosc podkreślnik ksiazki podkreślnik kodowej zamknij nawias okrągły otwórz nawias klamrowy. Linia 53. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dlugosc podkreślnik ksiazki podkreślnik kodowej średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 54. if otwórz nawias okrągły ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka znak znak równości znak równości znak zamknij nawias okrągły otwórz nawias klamrowy. Linia 55. return ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowo podkreślnik kodowe średnik. Linia 56. zamknij nawias klamrowy. Linia 57. zamknij nawias klamrowy. Linia 58. zamknij nawias klamrowy. Linia 60. string zakoduj podkreślnik wiadomosc otwórz nawias okrągły string wiadomosc przecinek kod asterysk ksiazka podkreślnik kodowa przecinek int dlugosc podkreślnik ksiazki podkreślnik kodowej zamknij nawias okrągły otwórz nawias klamrowy. Linia 61. string zakodowana podkreślnik wiadomosc znak równości cudzysłów cudzysłów średnik. Linia 62. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 63. zakodowana podkreślnik wiadomosc plus znak równości znajdz podkreślnik slowo podkreślnik kodowe otwórz nawias okrągły wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek ksiazka podkreślnik kodowa przecinek dlugosc podkreślnik ksiazki podkreślnik kodowej zamknij nawias okrągły średnik. Linia 64. zamknij nawias klamrowy. Linia 65. return zakodowana podkreślnik wiadomosc średnik. Linia 66. zamknij nawias klamrowy. Linia 68. void zwolnij podkreślnik pamiec otwórz nawias okrągły wierzcholek asterysk drzewo podkreślnik kodowe zamknij nawias okrągły otwórz nawias klamrowy. Linia 69. if otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny lewy wykrzyknik znak równości nullptr ampersant ampersant drzewo podkreślnik kodowe minus zamknij nawias ostrokątny prawy wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 70. zwolnij podkreślnik pamiec otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny lewy zamknij nawias okrągły średnik. Linia 71. zwolnij podkreślnik pamiec otwórz nawias okrągły drzewo podkreślnik kodowe minus zamknij nawias ostrokątny prawy zamknij nawias okrągły średnik. Linia 72. zamknij nawias klamrowy. Linia 73. delete drzewo podkreślnik kodowe średnik. Linia 74. zamknij nawias klamrowy. Linia 76. string odkodujWiadomosc otwórz nawias okrągły string zakodowanaWiadomosc przecinek wierzcholek asterysk drzewo podkreślnik kodowe zamknij nawias okrągły otwórz nawias klamrowy. Linia 77. string odkodowanaWiadomosc znak równości cudzysłów cudzysłów średnik. Linia 78. wierzcholek asterysk aktualny podkreślnik wierzcholek znak równości drzewo podkreślnik kodowe średnik. Linia 79. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny zakodowanaWiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 80. if otwórz nawias okrągły aktualny podkreślnik wierzcholek minus zamknij nawias ostrokątny lewy znak równości znak równości nullptr ampersant ampersant aktualny podkreślnik wierzcholek minus zamknij nawias ostrokątny prawy znak równości znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 81. odkodowanaWiadomosc plus znak równości aktualny podkreślnik wierzcholek minus zamknij nawias ostrokątny znak średnik. Linia 82. aktualny podkreślnik wierzcholek znak równości drzewo podkreślnik kodowe średnik. Linia 83. zamknij nawias klamrowy. Linia 84. if otwórz nawias okrągły zakodowanaWiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości apostrof 0 apostrof zamknij nawias okrągły otwórz nawias klamrowy. Linia 85. aktualny podkreślnik wierzcholek znak równości aktualny podkreślnik wierzcholek minus zamknij nawias ostrokątny lewy średnik. Linia 86. zamknij nawias klamrowy. Linia 87. else otwórz nawias klamrowy. Linia 88. aktualny podkreślnik wierzcholek znak równości aktualny podkreślnik wierzcholek minus zamknij nawias ostrokątny prawy średnik. Linia 89. zamknij nawias klamrowy. Linia 90. zamknij nawias klamrowy. Linia 91. odkodowanaWiadomosc plus znak równości aktualny podkreślnik wierzcholek minus zamknij nawias ostrokątny znak średnik. Linia 92. return odkodowanaWiadomosc średnik. Linia 93. zamknij nawias klamrowy. Linia 95. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 96. int tablica podkreślnik zliczen otwórz nawias kwadratowy 256 zamknij nawias kwadratowy średnik. Linia 97. string wiadomosc znak równości cudzysłów Dodadodadodatki cudzysłów średnik. Linia 99. prawy ukośnik prawy ukośnik zliczanie znaków w wiadomości. Linia 100. int liczba podkreślnik znakow znak równości zlicz podkreślnik znaki otwórz nawias okrągły wiadomosc przecinek tablica podkreślnik zliczen zamknij nawias okrągły średnik. Linia 102. prawy ukośnik prawy ukośnik wypisywanie zliczeń dla każdego znaku z wiadomości. Linia 103. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Zliczenia kazdego znaku dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 104. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 105. char znak znak równości wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 106. cout otwórz nawias ostrokątny otwórz nawias ostrokątny znak otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny tablica podkreślnik zliczen otwórz nawias kwadratowy znak zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 107. zamknij nawias klamrowy. Linia 109. prawy ukośnik prawy ukośnik tworzenie listy wierzchołków. Linia 110. list otwórz nawias ostrokątny wierzcholek asterysk zamknij nawias ostrokątny lista podkreślnik wierzcholkow średnik. Linia 111. int j znak równości 0 średnik. Linia 112. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny znak równości 255 średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 113. if otwórz nawias okrągły tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 114. lista podkreślnik wierzcholkow kropka push podkreślnik back otwórz nawias okrągły new wierzcholek otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 115. lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły minus zamknij nawias ostrokątny znak znak równości i średnik. Linia 116. lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły minus zamknij nawias ostrokątny czestosc znak równości tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 117. plus plus j średnik. Linia 118. if otwórz nawias okrągły j znak równości znak równości liczba podkreślnik znakow zamknij nawias okrągły otwórz nawias klamrowy. Linia 119. break średnik. Linia 120. zamknij nawias klamrowy. Linia 121. zamknij nawias klamrowy. Linia 122. zamknij nawias klamrowy. Linia 124. prawy ukośnik prawy ukośnik wypisywanie listy wierzchołków. Linia 125. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Lista wierzcholkow dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 126. for otwórz nawias okrągły wierzcholek asterysk w dwukropek lista podkreślnik wierzcholkow zamknij nawias okrągły otwórz nawias klamrowy. Linia 127. cout otwórz nawias ostrokątny otwórz nawias ostrokątny w minus zamknij nawias ostrokątny znak otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny w minus zamknij nawias ostrokątny czestosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 128. zamknij nawias klamrowy. Linia 130. prawy ukośnik prawy ukośnik sortowanie listy wierzchołków. Linia 131. lista podkreślnik wierzcholkow kropka sort otwórz nawias okrągły funkcja podkreślnik porownujaca zamknij nawias okrągły średnik. Linia 133. prawy ukośnik prawy ukośnik wypisywanie listy wierzchołków po posortowaniu. Linia 134. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Lista wierzcholkow po posortowaniu dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 135. for otwórz nawias okrągły wierzcholek asterysk w dwukropek lista podkreślnik wierzcholkow zamknij nawias okrągły otwórz nawias klamrowy. Linia 136. cout otwórz nawias ostrokątny otwórz nawias ostrokątny w minus zamknij nawias ostrokątny znak otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny w minus zamknij nawias ostrokątny czestosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 137. zamknij nawias klamrowy. Linia 139. prawy ukośnik prawy ukośnik tworzenie drzewa kodowego. Linia 140. while otwórz nawias okrągły lista podkreślnik wierzcholkow kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias ostrokątny 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 141. prawy ukośnik prawy ukośnik zdejmujemy z listy 2 wierzchołki w1 i w2. Linia 142. wierzcholek asterysk w1 znak równości lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 143. lista podkreślnik wierzcholkow kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 144. wierzcholek asterysk w2 znak równości lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 145. lista podkreślnik wierzcholkow kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 147. prawy ukośnik prawy ukośnik łączymy wierzchołki w1 oraz w2 przecinek tworząc wierzchołek w3. Linia 148. wierzcholek asterysk w3 znak równości new wierzcholek otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 149. w3 minus zamknij nawias ostrokątny czestosc znak równości w1 minus zamknij nawias ostrokątny czestosc plus w2 minus zamknij nawias ostrokątny czestosc średnik. Linia 150. w3 minus zamknij nawias ostrokątny lewy znak równości w1 średnik. Linia 151. w3 minus zamknij nawias ostrokątny prawy znak równości w2 średnik. Linia 153. prawy ukośnik prawy ukośnik umieszczamy wierzchołek w3 na końcu listy przecinek a następnie ją sortujemy. Linia 154. lista podkreślnik wierzcholkow kropka push podkreślnik back otwórz nawias okrągły w3 zamknij nawias okrągły średnik. Linia 155. lista podkreślnik wierzcholkow kropka sort otwórz nawias okrągły funkcja podkreślnik porownujaca zamknij nawias okrągły średnik. Linia 156. zamknij nawias klamrowy. Linia 158. prawy ukośnik prawy ukośnik gotowe drzewo kodowe. Linia 159. wierzcholek asterysk drzewo podkreślnik kodowe znak równości lista podkreślnik wierzcholkow kropka back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 161. prawy ukośnik prawy ukośnik tworzenie książki kodowej. Linia 162. kod asterysk ksiazka podkreślnik kodowa znak równości new kod otwórz nawias kwadratowy liczba podkreślnik znakow zamknij nawias kwadratowy średnik. Linia 163. utworz podkreślnik ksiazke podkreślnik kodowa otwórz nawias okrągły drzewo podkreślnik kodowe przecinek ksiazka podkreślnik kodowa zamknij nawias okrągły średnik. Linia 165. prawy ukośnik prawy ukośnik wypisywanie książki kodowej. Linia 166. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Ksiazka kodowa dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 167. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczba podkreślnik znakow średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 168. cout otwórz nawias ostrokątny otwórz nawias ostrokątny ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka znak otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowo podkreślnik kodowe otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 169. zamknij nawias klamrowy. Linia 171. prawy ukośnik prawy ukośnik kodowanie wiadomości. Linia 172. string zakodowana podkreślnik wiadomosc znak równości zakoduj podkreślnik wiadomosc otwórz nawias okrągły wiadomosc przecinek ksiazka podkreślnik kodowa przecinek liczba podkreślnik znakow zamknij nawias okrągły średnik. Linia 174. prawy ukośnik prawy ukośnik wypisywanie niezakodowanej i zakodowanej wiadomości. Linia 175. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Niezakodowana wiadomosc dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 176. cout otwórz nawias ostrokątny otwórz nawias ostrokątny wiadomosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 177. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Zakodowana wiadomosc dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 178. cout otwórz nawias ostrokątny otwórz nawias ostrokątny zakodowana podkreślnik wiadomosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 180. prawy ukośnik prawy ukośnik odkodowanie zakodowanej wiadomości. Linia 181. string odkodowana podkreślnik wiadomosc znak równości odkodujWiadomosc otwórz nawias okrągły zakodowana podkreślnik wiadomosc przecinek drzewo podkreślnik kodowe zamknij nawias okrągły średnik. Linia 183. prawy ukośnik prawy ukośnik wypisanie odkodowanej wiadomości. Linia 184. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Odkodowana wiadomosc dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 185. cout otwórz nawias ostrokątny otwórz nawias ostrokątny odkodowana podkreślnik wiadomosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 187. prawy ukośnik prawy ukośnik zwolnienie pamięci. Linia 188. zwolnij podkreślnik pamiec otwórz nawias okrągły drzewo podkreślnik kodowe zamknij nawias okrągły średnik. Linia 189. delete otwórz nawias kwadratowy zamknij nawias kwadratowy ksiazka podkreślnik kodowa średnik. Linia 191. return 0 średnik. Linia 192. zamknij nawias klamrowy.

#include <iostream>
#include <string>
#include <list>

using namespace std;

struct wierzcholek {
    char znak;
    int czestosc;
    wierzcholek* lewy = nullptr;
    wierzcholek* prawy = nullptr;
};

struct kod {
    char znak;
    string slowo_kodowe;
};

int zlicz_znaki(string wiadomosc, int* tablica_zliczen) {
    for (int i = 0; i <= 255; ++i) {
        tablica_zliczen[i] = 0;
    }
    for (int i = 0; i < wiadomosc.length(); ++i) {
        ++tablica_zliczen[wiadomosc[i]];
    }
    int liczba = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            ++liczba;
        }
    }
    return liczba;
}

bool funkcja_porownujaca(wierzcholek* w1, wierzcholek* w2) {
    return w1->czestosc > w2->czestosc;
}

void utworz_ksiazke_kodowa(wierzcholek* drzewo_kodowe, kod* ksiazka_kodowa, string dotychczasowy_kod = "") {
    static int i = 0;
    if (drzewo_kodowe->lewy == nullptr && drzewo_kodowe->prawy == nullptr) {
        ksiazka_kodowa[i].znak = drzewo_kodowe->znak;
        ksiazka_kodowa[i].slowo_kodowe = dotychczasowy_kod;
        ++i;
    }
    else {
        utworz_ksiazke_kodowa(drzewo_kodowe->lewy, ksiazka_kodowa, dotychczasowy_kod + "0");
        utworz_ksiazke_kodowa(drzewo_kodowe->prawy, ksiazka_kodowa, dotychczasowy_kod + "1");
    }
}

string znajdz_slowo_kodowe(char znak, kod* ksiazka_kodowa, int dlugosc_ksiazki_kodowej) {
    for (int i = 0; i < dlugosc_ksiazki_kodowej; ++i) {
        if (ksiazka_kodowa[i].znak == znak) {
            return ksiazka_kodowa[i].slowo_kodowe;
        }
    }
}

string zakoduj_wiadomosc(string wiadomosc, kod* ksiazka_kodowa, int dlugosc_ksiazki_kodowej) {
    string zakodowana_wiadomosc = "";
    for (int i = 0; i < wiadomosc.length(); ++i) {
        zakodowana_wiadomosc += znajdz_slowo_kodowe(wiadomosc[i], ksiazka_kodowa, dlugosc_ksiazki_kodowej);
    }
    return zakodowana_wiadomosc;
}

void zwolnij_pamiec(wierzcholek* drzewo_kodowe) {
    if (drzewo_kodowe->lewy != nullptr && drzewo_kodowe->prawy != nullptr) {
        zwolnij_pamiec(drzewo_kodowe->lewy);
        zwolnij_pamiec(drzewo_kodowe->prawy);
    }
    delete drzewo_kodowe;
}

string odkodujWiadomosc(string zakodowanaWiadomosc, wierzcholek* drzewo_kodowe) {
    string odkodowanaWiadomosc = "";
    wierzcholek* aktualny_wierzcholek = drzewo_kodowe;
    for (int i = 0; i < zakodowanaWiadomosc.length(); ++i) {
        if (aktualny_wierzcholek->lewy == nullptr && aktualny_wierzcholek->prawy == nullptr) {
            odkodowanaWiadomosc += aktualny_wierzcholek->znak;
            aktualny_wierzcholek = drzewo_kodowe;
        }
        if (zakodowanaWiadomosc[i] == '0') {
            aktualny_wierzcholek = aktualny_wierzcholek->lewy;
        }
        else {
            aktualny_wierzcholek = aktualny_wierzcholek->prawy;
        }
    }
    odkodowanaWiadomosc += aktualny_wierzcholek->znak;
    return odkodowanaWiadomosc;
}

int main() {
    int tablica_zliczen[256];
    string wiadomosc = "Dodadodadodatki";

    // zliczanie znaków w wiadomości
    int liczba_znakow = zlicz_znaki(wiadomosc, tablica_zliczen);

    // wypisywanie zliczeń dla każdego znaku z wiadomości
    cout << "Zliczenia kazdego znaku:" << endl;
    for (int i = 0; i < wiadomosc.length(); ++i) {
        char znak = wiadomosc[i];
        cout << znak << ": " << tablica_zliczen[znak] << endl;
    }

    // tworzenie listy wierzchołków
    list<wierzcholek*> lista_wierzcholkow;
    int j = 0;
    for (int i = 0; i <= 255; ++i) {
        if (tablica_zliczen[i] > 0) {
            lista_wierzcholkow.push_back(new wierzcholek());
            lista_wierzcholkow.back()->znak = i;
            lista_wierzcholkow.back()->czestosc = tablica_zliczen[i];
            ++j;
            if (j == liczba_znakow) {
                break;
            }
        }
    }

    // wypisywanie listy wierzchołków
    cout << "Lista wierzcholkow:" << endl;
    for (wierzcholek* w : lista_wierzcholkow) {
        cout << w->znak << ": " << w->czestosc << endl;
    }

    // sortowanie listy wierzchołków
    lista_wierzcholkow.sort(funkcja_porownujaca);

    // wypisywanie listy wierzchołków po posortowaniu
    cout << "Lista wierzcholkow po posortowaniu:" << endl;
    for (wierzcholek* w : lista_wierzcholkow) {
        cout << w->znak << ": " << w->czestosc << endl;
    }

    // tworzenie drzewa kodowego
    while (lista_wierzcholkow.size() > 1) {
        // zdejmujemy z listy 2 wierzchołki w1 i w2
        wierzcholek* w1 = lista_wierzcholkow.back();
        lista_wierzcholkow.pop_back();
        wierzcholek* w2 = lista_wierzcholkow.back();
        lista_wierzcholkow.pop_back();

        // łączymy wierzchołki w1 oraz w2, tworząc wierzchołek w3
        wierzcholek* w3 = new wierzcholek();
        w3->czestosc = w1->czestosc + w2->czestosc;
        w3->lewy = w1;
        w3->prawy = w2;

        // umieszczamy wierzchołek w3 na końcu listy, a następnie ją sortujemy
        lista_wierzcholkow.push_back(w3);
        lista_wierzcholkow.sort(funkcja_porownujaca);
    }

    // gotowe drzewo kodowe
    wierzcholek* drzewo_kodowe = lista_wierzcholkow.back();

    // tworzenie książki kodowej
    kod* ksiazka_kodowa = new kod[liczba_znakow];
    utworz_ksiazke_kodowa(drzewo_kodowe, ksiazka_kodowa);

    // wypisywanie książki kodowej
    cout << "Ksiazka kodowa:" << endl;
    for (int i = 0; i < liczba_znakow; ++i) {
        cout << ksiazka_kodowa[i].znak << ": " << ksiazka_kodowa[i].slowo_kodowe << endl;
    }

    // kodowanie wiadomości
    string zakodowana_wiadomosc = zakoduj_wiadomosc(wiadomosc, ksiazka_kodowa, liczba_znakow);

    // wypisywanie niezakodowanej i zakodowanej wiadomości
    cout << "Niezakodowana wiadomosc:" << endl;
    cout << wiadomosc << endl;
    cout << "Zakodowana wiadomosc:" << endl;
    cout << zakodowana_wiadomosc << endl;

    // odkodowanie zakodowanej wiadomości
    string odkodowana_wiadomosc = odkodujWiadomosc(zakodowana_wiadomosc, drzewo_kodowe);

    // wypisanie odkodowanej wiadomości
    cout << "Odkodowana wiadomosc:" << endl;
    cout << odkodowana_wiadomosc << endl;

    // zwolnienie pamięci
    zwolnij_pamiec(drzewo_kodowe);
    delete[] ksiazka_kodowa;

    return 0;
}

Wynik działania programu:

Zliczenia kazdego znaku:
D: 1
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
d: 5
o: 3
d: 5
a: 3
t: 1
k: 1
i: 1
Lista wierzcholkow:
D: 1
a: 3
d: 5
i: 1
k: 1
o: 3
t: 1
Lista wierzcholkow po posortowaniu:
d: 5
a: 3
o: 3
D: 1
i: 1
k: 1
t: 1
Ksiazka kodowa:
o: 00
a: 01
i: 1000
D: 1001
t: 1010
k: 1011
d: 11
Niezakodowana wiadomosc:
Dodadodadodatki
Zakodowana wiadomosc:
10010011011100110111001101101010111000
Odkodowana wiadomosc:
Dodadodadodatki

Już wiesz

Podsumujmy najważniejsze informacje:

algorytm Huffmana generuje kod zero‑jedynkowy;
kod każdego znaku nie jest początkowym fragmentem kodu innego znaku;
generowany kod jest tzw. kodem prefiksowym (żaden kod nie jest prefiksem innej litery), który pozwala na jednoznaczne dekodowanie zapisanego znaku;
kod jest tworzony w taki sposób, aby średnia długość kodu znaku była najkrótsza.

Słownik

bezstratna kompresja danych

kompresja, która polega na tym, że informacja po skompresowaniu jest dekompresowalna do takiej samej postaci, z której początkowo wyszliśmy

drzewo binarne

struktura drzewiasta, w której każdy wierzchołek ma co najwyżej dwóch potomków; drzewa w informatyce są jednym z rodzajów struktur danych

książka kodowa

narzędzie ułatwiające kodowanie i wprowadzanie danych do komputera, zawiera instrukcje dotyczące postępowania przy kodowaniu wszystkich odpowiedzi na pytania zamknięte i otwarte, zawiera zbiór kodów z wyjaśnieniem, które odpowiedzi mają być przyporządkowane danemu kodowi

słowo kodowe

słowo, wyrażenie, znak lub ciąg bitów odpowiadające słowu, które chcemy zakodować; we wczesnych etapach rozwoju kryptografii słowa kodowe były układane w ramach książek kodowych i wykorzystywane do szyfrowania wiadomości

stopień kompresji

stosunek wielkości danych przed przeprowadzaniem kompresji do wielkości danych po kompresji

wierzchołek drzewa binarnego

element drzewa binarnego; każdy wierzchołek w drzewie binarnym ma co najwyżej dwóch potomków; wierzchołek może być:

liściem – jeśli nie ma żadnych potomków,
korzeniem – jeśli nie ma żadnego rodzica (jest pierwszym elementem drzewa)

wskaźnik pusty

specjalna wartość liczbowa przeznaczona na celowe reprezentowanie wskaźnika, który nie wskazuje na żaden element w pamięci

Wprowadzenie

Infografika

Implementacja w języku C++

Słownik