Infografika

Polecenie 1

Zapoznaj się z infografiką przedstawiającą przebieg działania algorytmu Huffmana dla przykładowego ciągu znaków. Zdekoduj podaną wiadomość.

Nad infografiką znajdują się przyciski odnoszące się do kolejnych kroków.

Algorytm Huffmana dla przykładowego ciągu znaków

R1BMJrrVjf2DW1

Mapa interaktywna: Opisy kroków. Infografika przedstawia przebieg działania algorytmu Huffmana dla przykładowego ciągu znaków. Przedstawiono siedem kroków. Krok 1: Zliczamy wystąpienia każdego znaku dla ciągu AAABBCABCDC. Ilustracja ukazuje krok pierwszy. W okręgach znajdują się wartości: A-4, B-3, C-3, D-1. Krok 2: Tworzymy cztery wierzchołki – każdy zawierający znak i częstość. Ilustracja przedstawia Krok drugi. Jest rząd czterech okręgów. W pierwszym okręgu napis: Znak A częstość 4, w drugim Znak B częstość 3, w trzecim Znak C częstość 3, w czwartym Znak D częstość 1. Krok 3: Zgodnie z algorytmem Huffmana wybieramy dwa wierzchołki o najmniejszych częstościach. W omawianym przypadku będzie to wierzchołek ze znakiem D, a także ze znakiem B lub C. Na ilustracji jest Krok trzeci. W jednym rzędzie są trzy okręgi. W pierwszym jest napis: Znak B częstość 3, w drugim Znak C częstość 3, w trzecim Znak D częstość 1. Krok 4: Nie bez przyczyny umieściliśmy wierzchołki w kolejności od największej częstości do najmniejszej. Wystarczy wybrać dwa wierzchołki znajdujące się na końcu, a potem umieścić je w takim miejscu listy, by częstości wciąż były malejące. Idąc tym tokiem rozumowania, wybieramy wierzchołki z C i D. Na ilustracji jest przedstawiony Krok czwarty. W okręgach znajdują się wartości: znak A częstość 4, znak brak częstość 4, znak B częstość 3, znak C częstość 3, znak D częstość 1. Od okręgu z znakiem brak częstość cztery prowadzą linie proste w dół do okręgów z napisami: znak C częstość 3 oraz znak D częstość 1. Krok 5: Wierzchołki ze znakiem C i D połączyliśmy w nowy wierzchołek, którego częstość stanowi sumę częstości jego potomków. W nowym wierzchołku znak oznaczyliśmy jako „brak” (zauważmy, że wierzchołki ze znakami nie mogą mieć żadnego potomka, zatem każdy wierzchołek posiadający choć jednego potomka nie będzie miał swojego znaku). Kontynuując algorytm, wybieramy kolejne dwa wierzchołki z najmniejszymi częstościami znajdującymi się w liście. Warto zwrócić uwagę, że wierzchołek o większej częstości umieszczamy z lewej strony (można to zrobić również z prawej, jednak należy postępować w sposób konsekwentny, tzn. umieszczać wierzchołki z większą częstością po konkretnej stronie). Ilustracja przedstawia Krok piąty. W górnej części ilustracji są dwa okręgi. W pierwszym jest napis: Znak brak częstość 7 oraz Znak A częstość 4. Od okręgu Znak brak częstość 7 dwie kreski w dół do dwóch okręgów. W jednym z nich jest napis: Znak brak częstość 4, w drugim Znak B częstość 3. Od okręgu Znak brak częstość 4 dwie kreski w dół do dwóch okręgów. W pierwszym napis: Znak C częstość 3, w drugim Znak D częstość 1. Krok 6: Wybieramy dwa ostatnie wierzchołki, kończąc tym samym algorytm. Ilustracja przedstawia Krok szósty. W górnej części ilustracji jest jeden okrąg. W nim napis: Znak brak częstość 11. Od okręgu w dół dwie kreski do dwóch okręgów. W jednym z nich napis: Znak brak częstość 7, w drugim Znak A częstość 4. Od okręgu Znak brak częstość 7 dwie kreski w dół do dwóch okręgów. W pierwszym napis: Znak brak częstość 4, w drugim: Znak B częstość 3. Od okręgu z napisem: Znak brak częstość 4 dwie kreski w dół do dwóch okręgów. W jednym z nich napis: Znak C częstość 3, w drugim Znak C częstość 1. Krok 7: Na podstawie tego drzewa tworzymy słownik kodowy. Każdą odnogę w lewo oznaczymy jako 0, a każdą odnogę w prawo jako 1. Tym samym otrzymamy graf. Książka kodowa: A: 1, B: 01, C: 000, D: 001. Spróbuj zdekodować następującą wiadomość: 01000001011, odczytując kolejne znaki prosto z grafu. Zacznij od korzenia grafu z częstością 11. Następnie, jeśli napotkasz 0, przejdź do wierzchołka z lewej, a jeśli 1 – do wierzchołka z prawej. Jeżeli wierzchołek jest korzeniem, odczytaj z niego literę i wróć do korzenia. Jeżeli nim nie jest, odczytaj kolejną liczbę i kontynuuj zgodnie ze sposobem opisanym w poprzednich krokach. Ilustracja przedstawia Krok siódmy. W górnej części ilustracji jest jeden okrąg. W nim napis: Znak brak częstość 11. Od okręgu w dół dwie kreski do dwóch okręgów. W jednym napis: Znak brak częstość 7, nad okręgiem cyfra 0; w drugim okręgu napis: Znak A częstość 4, nad okręgiem cyfra 1. Od okręgu z napisem: Znak brak częstość 7 dwie kreski w dół do dwóch okręgów. W jednym napis: Znak brak częstość 4, nad okręgiem cyfra 0, w drugim okręgu napis: Znak B częstość 3, nad okręgiem cyfra 1. Od okręgu z napisem: Znak brak częstość 4 dwie kreski w dół do dwóch okręgów. W jednym napis: Znak C częstość 3, nad okręgiem cyfra 0, w drugim Znak D częstość 1 - nad okręgiem cyfra 1.

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Ćwiczenie 1

Zaimplementuj w języku C++ algorytm Huffmana służący do kodowania ciągu znaków. Podczas łączenia wierzchołków upewnij się, że prawy potomek będzie wierzchołkiem z mniejszą częstością niż lewy. Jeśli wierzchołki mają tę samą częstość, za mniejszy uznajemy ten o znaku z niższą wartością w kodowaniu ASCII. Nie musisz uwzględniać sytuacji, w której porównywane wierzchołki mają takie same częstości, a nie mają znaku (nie są liśćmi) – dane testowe ją wykluczają. Podczas poruszania się po drzewie kodowym zakładamy, że przejściu na lewo odpowiada cyfra 1, a przejściu na prawo cyfra 0. Do napisania programu możesz wykorzystać zmodyfikowany algorytm przedstawiony w sekcji „Przeczytaj”. Działanie programu przetestuj dla podanej wiadomości:

wiadomosc = "AAAADBABCABCDAC"

Specyfikacja problemu:

Dane:

wiadomosc – łańcuch znaków do zakodowania

Wynik:

zakodowanaWiadomosc – łańcuch znaków (zer i jedynek) reprezentujący zakodowany do postaci binarnej zgodnie z kodowaniem Huffmana łańcuch znaków wiadomosc

R1MuRzteyrJBA1

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. if otwórz nawias okrągły w1 minus zamknij nawias ostrokątny czestosc znak równości znak równości w2 minus zamknij nawias ostrokątny czestosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 37. return w1 minus zamknij nawias ostrokątny znak zamknij nawias ostrokątny w2 minus zamknij nawias ostrokątny znak średnik. Linia 38. zamknij nawias klamrowy. Linia 39. return w1 minus zamknij nawias ostrokątny czestosc zamknij nawias ostrokątny w2 minus zamknij nawias ostrokątny czestosc średnik. Linia 40. zamknij nawias klamrowy. Linia 42. 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 43. static int i znak równości 0 średnik. Linia 44. 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 45. 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 46. 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 47. plus plus i średnik. Linia 48. zamknij nawias klamrowy. Linia 49. else otwórz nawias klamrowy. Linia 50. 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 1 cudzysłów zamknij nawias okrągły średnik. Linia 51. 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 0 cudzysłów zamknij nawias okrągły średnik. Linia 52. zamknij nawias klamrowy. Linia 53. zamknij nawias klamrowy. Linia 55. 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 56. 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 57. 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 58. return ksiazka podkreślnik kodowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowo podkreślnik kodowe średnik. Linia 59. zamknij nawias klamrowy. Linia 60. zamknij nawias klamrowy. Linia 61. zamknij nawias klamrowy. Linia 63. 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 64. string zakodowana podkreślnik wiadomosc znak równości cudzysłów cudzysłów średnik. Linia 65. 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 66. 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 67. zamknij nawias klamrowy. Linia 68. return zakodowana podkreślnik wiadomosc średnik. Linia 69. zamknij nawias klamrowy. Linia 71. 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 72. 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 73. 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 74. 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 75. zamknij nawias klamrowy. Linia 76. delete drzewo podkreślnik kodowe średnik. Linia 77. zamknij nawias klamrowy. Linia 79. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 80. int tablica podkreślnik zliczen otwórz nawias kwadratowy 256 zamknij nawias kwadratowy średnik. Linia 81. string wiadomosc znak równości cudzysłów AAAADBABCABCDAC cudzysłów średnik. Linia 83. prawy ukośnik prawy ukośnik zliczanie znaków w wiadomości. Linia 84. 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 86. prawy ukośnik prawy ukośnik tworzenie listy wierzchołków. Linia 87. list otwórz nawias ostrokątny wierzcholek asterysk zamknij nawias ostrokątny lista podkreślnik wierzcholkow średnik. Linia 88. int j znak równości 0 średnik. Linia 89. 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 90. 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 91. 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 92. 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 93. 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 94. plus plus j średnik. Linia 95. 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 96. break średnik. Linia 97. zamknij nawias klamrowy. Linia 98. zamknij nawias klamrowy. Linia 99. zamknij nawias klamrowy. Linia 101. prawy ukośnik prawy ukośnik sortowanie listy wierzchołków. Linia 102. lista podkreślnik wierzcholkow kropka sort otwórz nawias okrągły funkcja podkreślnik porownujaca zamknij nawias okrągły średnik. Linia 104. prawy ukośnik prawy ukośnik tworzenie drzewa kodowego. Linia 105. 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 106. prawy ukośnik prawy ukośnik zdejmujemy z listy 2 wierzchołki w1 i w2. Linia 107. 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 108. lista podkreślnik wierzcholkow kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 109. 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 110. lista podkreślnik wierzcholkow kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 112. prawy ukośnik prawy ukośnik łączymy wierzchołki w1 oraz w2 przecinek tworząc wierzchołek w3. Linia 113. wierzcholek asterysk w3 znak równości new wierzcholek otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 114. 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 115. w3 minus zamknij nawias ostrokątny lewy znak równości w2 średnik. Linia 116. w3 minus zamknij nawias ostrokątny prawy znak równości w1 średnik. Linia 118. prawy ukośnik prawy ukośnik umieszczamy wierzchołek w3 na końcu listy przecinek a następnie ją sortujemy. Linia 119. lista podkreślnik wierzcholkow kropka push podkreślnik back otwórz nawias okrągły w3 zamknij nawias okrągły średnik. Linia 120. lista podkreślnik wierzcholkow kropka sort otwórz nawias okrągły funkcja podkreślnik porownujaca zamknij nawias okrągły średnik. Linia 121. zamknij nawias klamrowy. Linia 123. prawy ukośnik prawy ukośnik gotowe drzewo kodowe. Linia 124. 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 126. prawy ukośnik prawy ukośnik tworzenie książki kodowej. Linia 127. 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 128. 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 130. prawy ukośnik prawy ukośnik kodowanie wiadomości. Linia 131. 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 133. prawy ukośnik prawy ukośnik wypisywanie zakodowanej wiadomości. Linia 134. 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 136. prawy ukośnik prawy ukośnik zwolnienie pamięci. Linia 137. zwolnij podkreślnik pamiec otwórz nawias okrągły drzewo podkreślnik kodowe zamknij nawias okrągły średnik. Linia 138. delete otwórz nawias kwadratowy zamknij nawias kwadratowy ksiazka podkreślnik kodowa średnik. Linia 140. return 0 średnik. Linia 141. 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) {
    if (w1->czestosc == w2->czestosc) {
        return w1->znak > w2->znak;
    }
    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 + "1");
        utworz_ksiazke_kodowa(drzewo_kodowe->prawy, ksiazka_kodowa, dotychczasowy_kod + "0");
    }
}

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 = "AAAADBABCABCDAC";

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

    // 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;
            }
        }
    }

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

    // 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 = w2;
        w3->prawy = w1;

        // 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);

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

    // wypisywanie zakodowanej wiadomości
    cout << zakodowana_wiadomosc << endl;
    
    // zwolnienie pamięci
    zwolnij_pamiec(drzewo_kodowe);
    delete[] ksiazka_kodowa;

    return 0;
}

Przeczytaj

Sprawdź się

Algorytm Huffmana dla przykładowego ciągu znaków