ALG4

154 Rozdział 5. Struktury danych

weźmy pod uwagę następującą grupę słów: KROKUS, KROSNO, KRAWIEC, KROKODYL, KRAJ. Gdyby można było zapamiętać je w pamięci w fomiie drzewa przedstawionego na rysunku 5 - 25, to problem kompresji mielibyśmy z głowy. Z 31 znaków do zapamiętania zrobiło nam się raptem 21. co może nie oszałamia, ale pozwala przypuszczać, że w przypadku rozbudowanych słowników zysk byłby jeszcze większy. Zakładamy oczywiście, że w słowniku będą zapamiętywane w dużej części serie słów zaczynających się od tych samych liter-czyli przykładowo pełne odmiany rzeczowników etc.

Rys. 5 - 25.

Kompresju danych zaletą Uniwersalnej Struktury Słownikowej.

Pora już na przedstawienie owej tajemniczej USS w szczegółach. Jej realizacja jest nieco przewrotna, bowiem zbędne staje się zapamiętywanie słów' i ich fragmentów, a pomimo tego cel i tak zostaje osiągnięty!

Program zaprezentuję w szczegółowo skomentowanych fragmentach. Oto pierwszy z nich zawierający programową realizacją USS:

uss.cpp

const int n=29; // liczba rozpoznawanych liter

typedof struct słownik

<

struct słownik *tlnj;

)USS,*USS_PTR;

Mamy oto typową dla C++ deklarację typu rekurencyjnego, którego jedynym elementem jest tablica wskaźników do tegoż właśnie typu. (Tak, zdaję sobie spraw⁽ę, iż brzmi to okropnie). Literze 'a’ (lub ‘A’) odpowiada komórka t[0]. analogicznie literom ‘z’ (lub ‘Z’) komórka t[25]. Dodatkowe komórki pamięci będą służyły do znaków specjalnych, które nie należą do podstawowych liter alfabetu, ale dość często wchodzą w skład słów (np. myślnik, polskie znaki diakrytyczne...).

Wyszukiwarka

Podobne podstrony:
ALG 4 94 Rozdział 5. Struktury danych5.1. Listy jednokierunkowe Lista jednokierunkowa jest oszczędną
ALG4 104 Rozdział 5, Struktury danych dla danego obiektu wykonanie na sobie operacji „dekrementacji
ALG4 114 Rozdział 5. Struktury danych stan—ZAKOŃCZ; else { przcd=po; po=po->nastepny; I Różnica
ALG4 124 Rozdział 5. Struktury danych Co jednak z dołączaniem elementów do listy? Poniżej są omówio
ALG4 144 Rozdział 5. Struktury danych studia dotyczące drzew można znaleźć w zasadzie w większości
ALG0 130 Rozdział 5. Struktury danych Symboliczny stos znajdujący się pod każdą z sześciu grup inst
ALG8 138 Rozdział 5. Struktury danych • „prawy” potomek /-tego węzła jest „schowany” pod indeksem 2
ALG 6 96 Rozdział 5. Struktury danych Rys. 5 - 3. FCOOh FCI4h FFEEh Przykład listy jedno-kierunk
ALG 8 98 Rozdział 5. Struktury danych W następnych paragrafach zostaną przedstawione wszystkie metod
ALG2 102___Rozdział 5. Struktury danych I ELEMENT *q=inf.głowa; if (pusta()) cout << "(l
ALG8 108__Rozdział 5. Struktury danych5.1.3.Listy jednokierunkowe - teoria i rzeczywistość Oprócz p
ALG0 110 Rozdział 5. Struktury danych Rysunek 5-9 zawiera już kilka nowości w porównaniu z tym, co
ALG2 112 Rozdział 5. Struktury danych 112 Rozdział 5. Struktury danych //rekord informacyjny listy
ALG6 116 Rozdział 5. Struktury danych Iisla2.li int alfabetycznie(ELEMENT *q],ELEMENT *q2) { II czy
ALG8 118 Rozdział 5. Struktury danych if(pŁzed==NULL) // wstawiamy na początek listy ( inf_ptr[nr].
ALG0 120 Rozdział 5. Struktury danych i if (pos!=q) rsturn(O);    II element nie
Alg0 120 Rozdział 5. Struktury danych i if (pos!=q) rsturn(O);    II element nie
ALG2 122 Rozdział 5. Struktury danych Czerniak zarabia 3000zl Wynik usunięcia rekordu pracownika za
ALG6 126 Rozdział 5. Struktury danych Rys. 5 - 12. Metoda„ tablic równoległych " (2) DANE L2

więcej podobnych podstron