ALG6

126 Rozdział 5. Struktury danych

Rys. 5 - 12.

Metoda„ tablic równoległych " (2)

DANE

L2 L3

Kowalski	37	2000
Zaremba	30	3000
Fuks	34	1200

LI

Obok tablicy danych możemy zauważyć trzy osobne tablice „wskaźników”, które umożliwiają dostęp do danych widzianych jako listy' posortowane wedle przeróżnych kryteriów. Tablica dane zawiera rekordy z danymi, przy czym efektywne informacje zaczynają się począwszy od komórki dane 12J w górę. Dlaczego tak dziwnie? Otóż zabieg ten zapewnia nam odpowiedniość „1 do 1" tablicy danych i tablic „wskaźników” (LI, L2 i L3, które są w rzeczywistości zwykłymi tablicami liczb całkowitych).

W tych tablicach bowiem komórki nr 0 i nr / są zarezerwowane odpowiednio na: wskaźnik początku listy i znacznik końca. Należy to rozumieć w ten sposób, że L1[0] zawierający liczbę 4 informuje nas, iż dane[4] są pierwszym rekordem na liście. A jaki jest rekord następny? Oczywiście Ll[4]=2 co oznacza, że drugim rekordem na liście danych jest dane[2]. Postępując tak dalej odtwarzamy całą listę: dane[4], darte[2], dane[3] - łatwo zauważyć, że jest to lista posortowana alfabetycznie wg nazwisk. Skąd jednak wiemy, że dane[3] jest ostatnim rekordem na liście? Otóż LI[3] zawiera 1. co stanowi wg naszej umowy znacznik końca listy.

Analogicznie postępując możemy „odkryć”, że L2 jest listą posortowaną wg kodów 2-cyfruwych, a L3 - wg zarobków. Tablicowa reprezentacja list, w której nastąpiło oddzielenie danych od wskaźników', pozwala na zapamiętanie w tym samym obszarze pamięci kilku list jednocześnie - o ile oczywiście ich elementy składowe w jakiś sposób się pokrywają. W aplikacjach, w których występuje taka sytuacja, jest to cenna właściwość przyczyniająca się do zmniejszenia zużycia pamięci. Ponadto wspomniana na samym początku tego paragrafu wada tablic, tzn. zajmowanie przez nie stałego obszaru, może być w łatwy sposób ominięta poprzez sprytne ukrycie dynamicznego zarządzania tablicą w definicji klasy (patrz np. klasy z grupy TArruy w systemie Borland C++). Samodzielne zdefiniowanie takiej klasy jest jednak czasochłonne -zwłaszcza jeśli zamierzamy zadbać o jej uniwersalność.