ALG5

5.7. Uniwersalna struktura słownikowa 155

Dla oszczędności miejsca słowa będą zapamiętywane już w postaci przetrans-formowanej na duże litery. Słowo odpowiada jest tu bardzo charakterystyczne, bowiem słowa nie są w USS zapamiętywane bezpośrednio.

Zapętlenie wskaźnika t[n-1] do swojej własnej tablicy oznacza znacznik końca słowa.

Dokładną zasadę działania USS wyjaśnimy na przykładzie zamieszczonym na rysunku 5 - 26.

Rys. 5 - 26.

Reprezentacjo słów w USS.

Założeniem przyjętym podczas analizy niech będzie ograniczenie liczby liter alfabetu do 4\ A, B, K, N. USS zawiera tablicę t o rozmiarze 5: ostatnia komórka służy jako znacznik końca słowa. Jeśli wskaźnik w t[4] wskazuje na /, to oznacza że w tym miejscu pewne słowo zawiera swój znacznik końca. Które dokładnie? Spójrzmy jeszcze raz na rysunek 5 - 26. Komórka nazwana pierwotną umożliwia dostęp do wszystkich słów naszego -/-literowego alfabetu. Wskaźnik znajdujący się w t[l] (czyli t[‘B']) zawiera adres komórki oznaczonej jako (*). Znajdujący się w niej wskaźnik t(0] (czyli // 'A j) wskazuje na (**). Tu uwaga! W komórce (**) t[4] jest „zapętlony”, czyli znajduje się tu znacznik końca słowa, na którego litery składały się odwiedzane ostatnio indeksy: wpierw ‘B’, potem ‘A’, na koniec znacznik końca słowa - co daje razem słowo BA'.

² Przyjmijmy dla potrzeb tej książki, że ono coś istotnie oznacza....