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?

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.

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.

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.

Linia 1. 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 2. 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 3. tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 4. zamknij nawias klamrowy. Linia 5. 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 6. plus plus tablica podkreślnik zliczen otwórz nawias kwadratowy wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy średnik. Linia 7. zamknij nawias klamrowy. Linia 8. int liczba znak równości 0 średnik. Linia 9. 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 10. 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 11. plus plus liczba średnik. Linia 12. zamknij nawias klamrowy. Linia 13. zamknij nawias klamrowy. Linia 14. return liczba średnik. Linia 15. zamknij nawias klamrowy.

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:

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. 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 8. 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 9. tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 10. zamknij nawias klamrowy. 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. plus plus tablica podkreślnik zliczen otwórz nawias kwadratowy wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy średnik. Linia 13. zamknij nawias klamrowy. Linia 14. int liczba znak równości 0 średnik. Linia 15. 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 16. 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 17. plus plus liczba średnik. Linia 18. zamknij nawias klamrowy. Linia 19. zamknij nawias klamrowy. Linia 20. return liczba średnik. Linia 21. zamknij nawias klamrowy. Linia 23. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. int tablica podkreślnik zliczen otwórz nawias kwadratowy 256 zamknij nawias kwadratowy średnik. Linia 25. string wiadomosc znak równości cudzysłów Dodadodadodatki cudzysłów średnik. Linia 27. prawy ukośnik prawy ukośnik zliczanie znaków w wiadomości. Linia 28. 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 30. prawy ukośnik prawy ukośnik wypisywanie zliczeń dla każdego znaku z wiadomości. Linia 31. 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 32. 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 33. char znak znak równości wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 34. 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 35. zamknij nawias klamrowy. Linia 37. return 0 średnik. Linia 38. zamknij nawias klamrowy.

Wynik działania programu:

Linia 1. Zliczenia kazdego znaku dwukropek. Linia 2. D dwukropek 1. Linia 3. o dwukropek 3. Linia 4. d dwukropek 5. Linia 5. a dwukropek 3. Linia 6. d dwukropek 5. Linia 7. o dwukropek 3. Linia 8. d dwukropek 5. Linia 9. a dwukropek 3. Linia 10. d dwukropek 5. Linia 11. o dwukropek 3. Linia 12. d dwukropek 5. Linia 13. a dwukropek 3. Linia 14. t dwukropek 1. Linia 15. k dwukropek 1. Linia 16. i dwukropek 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.

Linia 1. struct wierzcholek otwórz nawias klamrowy. Linia 2. char znak średnik. Linia 3. int czestosc średnik. Linia 4. wierzcholek asterysk lewy znak równości nullptr średnik. Linia 5. wierzcholek asterysk prawy znak równości nullptr średnik. Linia 6. zamknij nawias klamrowy średnik.

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.

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. 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 15. 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 16. tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 17. zamknij nawias klamrowy. Linia 18. 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 19. plus plus tablica podkreślnik zliczen otwórz nawias kwadratowy wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy średnik. Linia 20. zamknij nawias klamrowy. Linia 21. int liczba znak równości 0 średnik. Linia 22. 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 23. 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 24. plus plus liczba średnik. Linia 25. zamknij nawias klamrowy. Linia 26. zamknij nawias klamrowy. Linia 27. return liczba średnik. Linia 28. zamknij nawias klamrowy. Linia 30. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. int tablica podkreślnik zliczen otwórz nawias kwadratowy 256 zamknij nawias kwadratowy średnik. Linia 32. string wiadomosc znak równości cudzysłów Dodadodadodatki cudzysłów średnik. Linia 34. prawy ukośnik prawy ukośnik zliczanie znaków w wiadomości. Linia 35. 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 37. prawy ukośnik prawy ukośnik wypisywanie zliczeń dla każdego znaku z wiadomości. Linia 38. 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 39. 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 40. char znak znak równości wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 41. 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 42. zamknij nawias klamrowy. Linia 44. prawy ukośnik prawy ukośnik tworzenie listy wierzchołków. Linia 45. list otwórz nawias ostrokątny wierzcholek asterysk zamknij nawias ostrokątny lista podkreślnik wierzcholkow średnik. Linia 46. int j znak równości 0 średnik. Linia 47. 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 48. 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 49. 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 50. 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 51. 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 52. plus plus j średnik. Linia 53. 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 54. break średnik. Linia 55. zamknij nawias klamrowy. Linia 56. zamknij nawias klamrowy. Linia 57. zamknij nawias klamrowy. Linia 59. prawy ukośnik prawy ukośnik wypisywanie listy wierzchołków. Linia 60. 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 61. 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 62. 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 63. zamknij nawias klamrowy. Linia 65. return 0 średnik. Linia 66. zamknij nawias klamrowy.

Wynik działania programu:

Linia 1. Zliczenia kazdego znaku dwukropek. Linia 2. D dwukropek 1. Linia 3. o dwukropek 3. Linia 4. d dwukropek 5. Linia 5. a dwukropek 3. Linia 6. d dwukropek 5. Linia 7. o dwukropek 3. Linia 8. d dwukropek 5. Linia 9. a dwukropek 3. Linia 10. d dwukropek 5. Linia 11. o dwukropek 3. Linia 12. d dwukropek 5. Linia 13. a dwukropek 3. Linia 14. t dwukropek 1. Linia 15. k dwukropek 1. Linia 16. i dwukropek 1. Linia 17. Lista wierzcholkow dwukropek. Linia 18. D dwukropek 1. Linia 19. a dwukropek 3. Linia 20. d dwukropek 5. Linia 21. i dwukropek 1. Linia 22. k dwukropek 1. Linia 23. o dwukropek 3. Linia 24. t dwukropek 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ę:

Linia 1. 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 2. return w1 minus zamknij nawias ostrokątny czestosc zamknij nawias ostrokątny w2 minus zamknij nawias ostrokątny czestosc średnik. Linia 3. zamknij nawias klamrowy.

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 · log2n)

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:

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. 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 15. 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 16. tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 17. zamknij nawias klamrowy. Linia 18. 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 19. plus plus tablica podkreślnik zliczen otwórz nawias kwadratowy wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy średnik. Linia 20. zamknij nawias klamrowy. Linia 21. int liczba znak równości 0 średnik. Linia 22. 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 23. 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 24. plus plus liczba średnik. Linia 25. zamknij nawias klamrowy. Linia 26. zamknij nawias klamrowy. Linia 27. return liczba średnik. Linia 28. zamknij nawias klamrowy. Linia 30. 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 31. return w1 minus zamknij nawias ostrokątny czestosc zamknij nawias ostrokątny w2 minus zamknij nawias ostrokątny czestosc średnik. Linia 32. zamknij nawias klamrowy. Linia 34. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 35. int tablica podkreślnik zliczen otwórz nawias kwadratowy 256 zamknij nawias kwadratowy średnik. Linia 36. string wiadomosc znak równości cudzysłów Dodadodadodatki cudzysłów średnik. Linia 38. prawy ukośnik prawy ukośnik zliczanie znaków w wiadomości. Linia 39. 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 41. prawy ukośnik prawy ukośnik wypisywanie zliczeń dla każdego znaku z wiadomości. Linia 42. 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 43. 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 44. char znak znak równości wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 45. 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 46. zamknij nawias klamrowy. Linia 48. prawy ukośnik prawy ukośnik tworzenie listy wierzchołków. Linia 49. list otwórz nawias ostrokątny wierzcholek asterysk zamknij nawias ostrokątny lista podkreślnik wierzcholkow średnik. Linia 50. int j znak równości 0 średnik. Linia 51. 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 52. 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 53. 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 54. 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 55. 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 56. plus plus j średnik. Linia 57. 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 58. break średnik. Linia 59. zamknij nawias klamrowy. Linia 60. zamknij nawias klamrowy. Linia 61. zamknij nawias klamrowy. Linia 63. prawy ukośnik prawy ukośnik wypisywanie listy wierzchołków. Linia 64. 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 65. 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 66. 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 67. zamknij nawias klamrowy. Linia 69. prawy ukośnik prawy ukośnik sortowanie listy wierzchołków. Linia 70. lista podkreślnik wierzcholkow kropka sort otwórz nawias okrągły funkcja podkreślnik porownujaca zamknij nawias okrągły średnik. Linia 72. prawy ukośnik prawy ukośnik wypisywanie listy wierzchołków po posortowaniu. Linia 73. 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 74. 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 75. 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 76. zamknij nawias klamrowy. Linia 78. return 0 średnik. Linia 79. zamknij nawias klamrowy.

Wynik działania programu:

Linia 1. Zliczenia kazdego znaku dwukropek. Linia 2. D dwukropek 1. Linia 3. o dwukropek 3. Linia 4. d dwukropek 5. Linia 5. a dwukropek 3. Linia 6. d dwukropek 5. Linia 7. o dwukropek 3. Linia 8. d dwukropek 5. Linia 9. a dwukropek 3. Linia 10. d dwukropek 5. Linia 11. o dwukropek 3. Linia 12. d dwukropek 5. Linia 13. a dwukropek 3. Linia 14. t dwukropek 1. Linia 15. k dwukropek 1. Linia 16. i dwukropek 1. Linia 17. Lista wierzcholkow dwukropek. Linia 18. D dwukropek 1. Linia 19. a dwukropek 3. Linia 20. d dwukropek 5. Linia 21. i dwukropek 1. Linia 22. k dwukropek 1. Linia 23. o dwukropek 3. Linia 24. t dwukropek 1. Linia 25. Lista wierzcholkow po posortowaniu dwukropek. Linia 26. d dwukropek 5. Linia 27. a dwukropek 3. Linia 28. o dwukropek 3. Linia 29. D dwukropek 1. Linia 30. i dwukropek 1. Linia 31. k dwukropek 1. Linia 32. t dwukropek 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.

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. 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 15. 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 16. tablica podkreślnik zliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 17. zamknij nawias klamrowy. Linia 18. 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 19. plus plus tablica podkreślnik zliczen otwórz nawias kwadratowy wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy średnik. Linia 20. zamknij nawias klamrowy. Linia 21. int liczba znak równości 0 średnik. Linia 22. 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 23. 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 24. plus plus liczba średnik. Linia 25. zamknij nawias klamrowy. Linia 26. zamknij nawias klamrowy. Linia 27. return liczba średnik. Linia 28. zamknij nawias klamrowy. Linia 30. 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 31. return w1 minus zamknij nawias ostrokątny czestosc zamknij nawias ostrokątny w2 minus zamknij nawias ostrokątny czestosc średnik. Linia 32. zamknij nawias klamrowy. Linia 34. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 35. int tablica podkreślnik zliczen otwórz nawias kwadratowy 256 zamknij nawias kwadratowy średnik. Linia 36. string wiadomosc znak równości cudzysłów Dodadodadodatki cudzysłów średnik. Linia 38. prawy ukośnik prawy ukośnik zliczanie znaków w wiadomości. Linia 39. 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 41. prawy ukośnik prawy ukośnik wypisywanie zliczeń dla każdego znaku z wiadomości. Linia 42. 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 43. 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 44. char znak znak równości wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 45. 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 46. zamknij nawias klamrowy. Linia 48. prawy ukośnik prawy ukośnik tworzenie listy wierzchołków. Linia 49. list otwórz nawias ostrokątny wierzcholek asterysk zamknij nawias ostrokątny lista podkreślnik wierzcholkow średnik. Linia 50. int j znak równości 0 średnik. Linia 51. 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 52. 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 53. 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 54. 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 55. 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 56. plus plus j średnik. Linia 57. 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 58. break średnik. Linia 59. zamknij nawias klamrowy. Linia 60. zamknij nawias klamrowy. Linia 61. zamknij nawias klamrowy. Linia 63. prawy ukośnik prawy ukośnik wypisywanie listy wierzchołków. Linia 64. 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 65. 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 66. 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 67. zamknij nawias klamrowy. Linia 69. prawy ukośnik prawy ukośnik sortowanie listy wierzchołków. Linia 70. lista podkreślnik wierzcholkow kropka sort otwórz nawias okrągły funkcja podkreślnik porownujaca zamknij nawias okrągły średnik. Linia 72. prawy ukośnik prawy ukośnik wypisywanie listy wierzchołków po posortowaniu. Linia 73. 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 74. 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 75. 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 76. zamknij nawias klamrowy. Linia 78. prawy ukośnik prawy ukośnik tworzenie drzewa kodowego. Linia 79. 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 80. prawy ukośnik prawy ukośnik zdejmujemy z listy 2 wierzchołki w1 i w2. Linia 81. 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 82. lista podkreślnik wierzcholkow kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 83. 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 84. lista podkreślnik wierzcholkow kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 86. prawy ukośnik prawy ukośnik łączymy wierzchołki w1 oraz w2 przecinek tworząc wierzchołek w3. Linia 87. wierzcholek asterysk w3 znak równości new wierzcholek otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 88. 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 89. w3 minus zamknij nawias ostrokątny lewy znak równości w1 średnik. Linia 90. w3 minus zamknij nawias ostrokątny prawy znak równości w2 średnik. Linia 92. prawy ukośnik prawy ukośnik umieszczamy wierzchołek w3 na końcu listy przecinek a następnie ją sortujemy. Linia 93. lista podkreślnik wierzcholkow kropka push podkreślnik back otwórz nawias okrągły w3 zamknij nawias okrągły średnik. Linia 94. lista podkreślnik wierzcholkow kropka sort otwórz nawias okrągły funkcja podkreślnik porownujaca zamknij nawias okrągły średnik. Linia 95. zamknij nawias klamrowy. Linia 97. prawy ukośnik prawy ukośnik gotowe drzewo kodowe. Linia 98. 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 100. return 0 średnik. Linia 101. zamknij nawias klamrowy.

Wynik działania programu:

Linia 1. Zliczenia kazdego znaku dwukropek. Linia 2. D dwukropek 1. Linia 3. o dwukropek 3. Linia 4. d dwukropek 5. Linia 5. a dwukropek 3. Linia 6. d dwukropek 5. Linia 7. o dwukropek 3. Linia 8. d dwukropek 5. Linia 9. a dwukropek 3. Linia 10. d dwukropek 5. Linia 11. o dwukropek 3. Linia 12. d dwukropek 5. Linia 13. a dwukropek 3. Linia 14. t dwukropek 1. Linia 15. k dwukropek 1. Linia 16. i dwukropek 1. Linia 17. Lista wierzcholkow dwukropek. Linia 18. D dwukropek 1. Linia 19. a dwukropek 3. Linia 20. d dwukropek 5. Linia 21. i dwukropek 1. Linia 22. k dwukropek 1. Linia 23. o dwukropek 3. Linia 24. t dwukropek 1. Linia 25. Lista wierzcholkow po posortowaniu dwukropek. Linia 26. d dwukropek 5. Linia 27. a dwukropek 3. Linia 28. o dwukropek 3. Linia 29. D dwukropek 1. Linia 30. i dwukropek 1. Linia 31. k dwukropek 1. Linia 32. t dwukropek 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:

Linia 1. struct kod otwórz nawias klamrowy. Linia 2. char znak średnik. Linia 3. string slowo podkreślnik kodowe średnik. Linia 4. zamknij nawias klamrowy średnik.

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.

Linia 1. 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 2. static int i znak równości 0 średnik. Linia 3. 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 4. 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 5. 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 6. plus plus i średnik. Linia 7. zamknij nawias klamrowy. Linia 8. else otwórz nawias klamrowy. Linia 9. 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 10. 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 11. zamknij nawias klamrowy. Linia 12. zamknij nawias klamrowy.

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ą.

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. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 53. int tablica podkreślnik zliczen otwórz nawias kwadratowy 256 zamknij nawias kwadratowy średnik. Linia 54. string wiadomosc znak równości cudzysłów Dodadodadodatki cudzysłów średnik. Linia 56. prawy ukośnik prawy ukośnik zliczanie znaków w wiadomości. Linia 57. 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 59. prawy ukośnik prawy ukośnik wypisywanie zliczeń dla każdego znaku z wiadomości. Linia 60. 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 61. 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 62. char znak znak równości wiadomosc otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 63. 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 64. zamknij nawias klamrowy. Linia 66. prawy ukośnik prawy ukośnik tworzenie listy wierzchołków. Linia 67. list otwórz nawias ostrokątny wierzcholek asterysk zamknij nawias ostrokątny lista podkreślnik wierzcholkow średnik. Linia 68. int j znak równości 0 średnik. Linia 69. 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 70. 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 71. 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 72. 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 73. 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 74. plus plus j średnik. Linia 75. 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 76. break średnik. Linia 77. zamknij nawias klamrowy. Linia 78. zamknij nawias klamrowy. Linia 79. zamknij nawias klamrowy. Linia 81. prawy ukośnik prawy ukośnik wypisywanie listy wierzchołków. Linia 82. 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 83. 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 84. 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 85. zamknij nawias klamrowy. Linia 87. prawy ukośnik prawy ukośnik sortowanie listy wierzchołków. Linia 88. lista podkreślnik wierzcholkow kropka sort otwórz nawias okrągły funkcja podkreślnik porownujaca zamknij nawias okrągły średnik. Linia 90. prawy ukośnik prawy ukośnik wypisywanie listy wierzchołków po posortowaniu. Linia 91. 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 92. 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 93. 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 94. zamknij nawias klamrowy. Linia 96. prawy ukośnik prawy ukośnik tworzenie drzewa kodowego. Linia 97. 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 98. prawy ukośnik prawy ukośnik zdejmujemy z listy 2 wierzchołki w1 i w2. Linia 99. 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 100. lista podkreślnik wierzcholkow kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 101. 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 102. lista podkreślnik wierzcholkow kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 104. prawy ukośnik prawy ukośnik łączymy wierzchołki w1 oraz w2 przecinek tworząc wierzchołek w3. Linia 105. wierzcholek asterysk w3 znak równości new wierzcholek otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 106. 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 107. w3 minus zamknij nawias ostrokątny lewy znak równości w1 średnik. Linia 108. w3 minus zamknij nawias ostrokątny prawy znak równości w2 średnik. Linia 110. prawy ukośnik prawy ukośnik umieszczamy wierzchołek w3 na końcu listy przecinek a następnie ją sortujemy. Linia 111. lista podkreślnik wierzcholkow kropka push podkreślnik back otwórz nawias okrągły w3 zamknij nawias okrągły średnik. 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 113. zamknij nawias klamrowy. Linia 115. prawy ukośnik prawy ukośnik gotowe drzewo kodowe. Linia 116. 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 118. prawy ukośnik prawy ukośnik tworzenie książki kodowej. Linia 119. 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 120. 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 122. prawy ukośnik prawy ukośnik wypisywanie książki kodowej. Linia 123. 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 124. 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 125. 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 126. zamknij nawias klamrowy. Linia 128. return 0 średnik. Linia 129. zamknij nawias klamrowy.

Wynik działania programu:

Linia 1. Zliczenia kazdego znaku dwukropek. Linia 2. D dwukropek 1. Linia 3. o dwukropek 3. Linia 4. d dwukropek 5. Linia 5. a dwukropek 3. Linia 6. d dwukropek 5. Linia 7. o dwukropek 3. Linia 8. d dwukropek 5. Linia 9. a dwukropek 3. Linia 10. d dwukropek 5. Linia 11. o dwukropek 3. Linia 12. d dwukropek 5. Linia 13. a dwukropek 3. Linia 14. t dwukropek 1. Linia 15. k dwukropek 1. Linia 16. i dwukropek 1. Linia 17. Lista wierzcholkow dwukropek. Linia 18. D dwukropek 1. Linia 19. a dwukropek 3. Linia 20. d dwukropek 5. Linia 21. i dwukropek 1. Linia 22. k dwukropek 1. Linia 23. o dwukropek 3. Linia 24. t dwukropek 1. Linia 25. Lista wierzcholkow po posortowaniu dwukropek. Linia 26. d dwukropek 5. Linia 27. a dwukropek 3. Linia 28. o dwukropek 3. Linia 29. D dwukropek 1. Linia 30. i dwukropek 1. Linia 31. k dwukropek 1. Linia 32. t dwukropek 1. Linia 33. Ksiazka kodowa dwukropek. Linia 34. o dwukropek 00. Linia 35. a dwukropek 01. Linia 36. i dwukropek 1000. Linia 37. D dwukropek 1001. Linia 38. t dwukropek 1010. Linia 39. k dwukropek 1011. Linia 40. d dwukropek 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.

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.

Wynik działania programu:

Linia 1. Zliczenia kazdego znaku dwukropek. Linia 2. D dwukropek 1. Linia 3. o dwukropek 3. Linia 4. d dwukropek 5. Linia 5. a dwukropek 3. Linia 6. d dwukropek 5. Linia 7. o dwukropek 3. Linia 8. d dwukropek 5. Linia 9. a dwukropek 3. Linia 10. d dwukropek 5. Linia 11. o dwukropek 3. Linia 12. d dwukropek 5. Linia 13. a dwukropek 3. Linia 14. t dwukropek 1. Linia 15. k dwukropek 1. Linia 16. i dwukropek 1. Linia 17. Lista wierzcholkow dwukropek. Linia 18. D dwukropek 1. Linia 19. a dwukropek 3. Linia 20. d dwukropek 5. Linia 21. i dwukropek 1. Linia 22. k dwukropek 1. Linia 23. o dwukropek 3. Linia 24. t dwukropek 1. Linia 25. Lista wierzcholkow po posortowaniu dwukropek. Linia 26. d dwukropek 5. Linia 27. a dwukropek 3. Linia 28. o dwukropek 3. Linia 29. D dwukropek 1. Linia 30. i dwukropek 1. Linia 31. k dwukropek 1. Linia 32. t dwukropek 1. Linia 33. Ksiazka kodowa dwukropek. Linia 34. o dwukropek 00. Linia 35. a dwukropek 01. Linia 36. i dwukropek 1000. Linia 37. D dwukropek 1001. Linia 38. t dwukropek 1010. Linia 39. k dwukropek 1011. Linia 40. d dwukropek 11. Linia 41. Niezakodowana wiadomosc dwukropek. Linia 42. Dodadodadodatki. Linia 43. Zakodowana wiadomosc dwukropek. Linia 44. 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ęć.

Linia 1. 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 2. 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 3. 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 4. 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 5. zamknij nawias klamrowy. Linia 6. delete drzewo podkreślnik kodowe średnik. Linia 7. zamknij nawias klamrowy.

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.

Wynik działania programu:

Linia 1. Zliczenia kazdego znaku dwukropek. Linia 2. D dwukropek 1. Linia 3. o dwukropek 3. Linia 4. d dwukropek 5. Linia 5. a dwukropek 3. Linia 6. d dwukropek 5. Linia 7. o dwukropek 3. Linia 8. d dwukropek 5. Linia 9. a dwukropek 3. Linia 10. d dwukropek 5. Linia 11. o dwukropek 3. Linia 12. d dwukropek 5. Linia 13. a dwukropek 3. Linia 14. t dwukropek 1. Linia 15. k dwukropek 1. Linia 16. i dwukropek 1. Linia 17. Lista wierzcholkow dwukropek. Linia 18. D dwukropek 1. Linia 19. a dwukropek 3. Linia 20. d dwukropek 5. Linia 21. i dwukropek 1. Linia 22. k dwukropek 1. Linia 23. o dwukropek 3. Linia 24. t dwukropek 1. Linia 25. Lista wierzcholkow po posortowaniu dwukropek. Linia 26. d dwukropek 5. Linia 27. a dwukropek 3. Linia 28. o dwukropek 3. Linia 29. D dwukropek 1. Linia 30. i dwukropek 1. Linia 31. k dwukropek 1. Linia 32. t dwukropek 1. Linia 33. Ksiazka kodowa dwukropek. Linia 34. o dwukropek 00. Linia 35. a dwukropek 01. Linia 36. i dwukropek 1000. Linia 37. D dwukropek 1001. Linia 38. t dwukropek 1010. Linia 39. k dwukropek 1011. Linia 40. d dwukropek 11. Linia 41. Niezakodowana wiadomosc dwukropek. Linia 42. Dodadodadodatki. Linia 43. Zakodowana wiadomosc dwukropek. Linia 44. 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.

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.

Wynik działania programu:

Linia 1. Zliczenia kazdego znaku dwukropek. Linia 2. D dwukropek 1. Linia 3. o dwukropek 3. Linia 4. d dwukropek 5. Linia 5. a dwukropek 3. Linia 6. d dwukropek 5. Linia 7. o dwukropek 3. Linia 8. d dwukropek 5. Linia 9. a dwukropek 3. Linia 10. d dwukropek 5. Linia 11. o dwukropek 3. Linia 12. d dwukropek 5. Linia 13. a dwukropek 3. Linia 14. t dwukropek 1. Linia 15. k dwukropek 1. Linia 16. i dwukropek 1. Linia 17. Lista wierzcholkow dwukropek. Linia 18. D dwukropek 1. Linia 19. a dwukropek 3. Linia 20. d dwukropek 5. Linia 21. i dwukropek 1. Linia 22. k dwukropek 1. Linia 23. o dwukropek 3. Linia 24. t dwukropek 1. Linia 25. Lista wierzcholkow po posortowaniu dwukropek. Linia 26. d dwukropek 5. Linia 27. a dwukropek 3. Linia 28. o dwukropek 3. Linia 29. D dwukropek 1. Linia 30. i dwukropek 1. Linia 31. k dwukropek 1. Linia 32. t dwukropek 1. Linia 33. Ksiazka kodowa dwukropek. Linia 34. o dwukropek 00. Linia 35. a dwukropek 01. Linia 36. i dwukropek 1000. Linia 37. D dwukropek 1001. Linia 38. t dwukropek 1010. Linia 39. k dwukropek 1011. Linia 40. d dwukropek 11. Linia 41. Niezakodowana wiadomosc dwukropek. Linia 42. Dodadodadodatki. Linia 43. Zakodowana wiadomosc dwukropek. Linia 44. 10010011011100110111001101101010111000. Linia 45. Odkodowana wiadomosc dwukropek. Linia 46. 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
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
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
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 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
stopień kompresji

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

wierzchołek drzewa binarnego
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
wskaźnik pusty

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