Zad 15. (26 V 2004 i 2 VI 2004 - 9 VI 2004, zadanie za 4 punkty)

(Szkic treści, pełne omówienie było na obu zajęciach)

Napisz program, który na podstawie danego pliku tekstowego utworzy nowy,
zawierający skompresowaną za pomocą kodowania Huffmana postać pliku
wejściowego.. Program będzie wywolywany z dwoma parametrami, którymi
będą odpowiednio nazwa pliku danych i nazwa pliku wynikowego.

Najpierw budujemy strukturę danych z informacją o częstości poszczególnych
bajtów (znaków) w pliku z danymi. W 256-elementowej tablicy zliczamy, ile razy
każdy znak wystąpił. Następnie budujemy węzły drzewa, w każdym zapisujemy
znak (pomijamy te o częstości 0) i jego częstość. Wskaźniki do tych węzłów 
wpisujemy do kolejnej 256-elementowej tablicy. W tym momencie mamy więc
maksymalnie 256 jednoelementowych drzew. Następnie tak długo, jak długo
w tablicy wskaźników jest więcej niż jeden wskaźnik na węzeł, wyjmujemy dwa 
wskaźniki do węzłów, w których częstość jest najmniejsza (spośród węzłów 
o równej częstości wybieramy ten, który w tablicy występuje najwcześniej),
tworzymy nowy węzeł, wpisujemy do niego sumę częstości obu usuniętych 
węzłów i wstawiamy do tablicy wskaźników. Wynikiem działania ma być 
wskaźnik do węzła, który pozostał w tablicy.

Drzewo uzupełniamy o dodatkowe informacje:
- w każdym węźle wpisujemy wskaźnik do ojca (w korzeniu NULL)
- budujemy tablicę, w której dla każdego bajtu jest wskaźnik do
  liścia ten bajt reprezentującego

Następnie generujemy plik skompresowany w formacie:
- bajt z liczbą liści w drzewie  - 1,
- ciąg par bajtów: pierwszy to znak kompresowanego pliku a drugi
  to długość kodu tego znaku. Pary porządkujemy w kolejności
  liści drzewa, od lewej do prawej,
- cztery bajty zawierające długość kompresowanego pliku. Bajty 
  porządkujemy od najmniej znaczącego,
- resztę pliku stanowi wynik kompresji danych: dla każdego bajtu
  ciąg bitów odczytany z drzewa Huffmana. Poszczególne bajty
  zapełniamy w kolejności od najmniej znaczących bitów.

Uwagi:
- plik pusty reprezentujemy jako plik pusty,
- oczywiście to nie jest najefektywniejszy sposób realizacji algorytmu Huffmana,
- program powinien badać poprawność wszystkich wykonywanych operacji i,
  w przypadku błędu, sensownie reagować.