Istniejące ograniczenie zmusza użytkownika do racjonalnego i oszczędnego gospodarowania pamięcią. W mikrokomputerze ZX Spectrum jedną z dróg prowadzących do przedstawionego wyżej celu jest wykorzystanie nieograniczonej długości zmiennej znakowej do operacji na rekordach o zmiennej długości.
Wyobraźmy sobie, że chcemy napisać program katalogujący nasz księgozbiór (lub zbiór posiadanych płyt, kaset itp.). Dla każdej pozycji należy zapamiętać nazwisko i imię autora oraz tytuł książki. Nazwiska autorów i tytuły mogą mieć różnorodną długość. Gdybyśmy chcieli przechowywać nazwiska w tablicy znakowej, trzeba by zadeklarować tablicę o rozmiarze (n, m), gdzie:
n — sumaryczna liczba pozycji do skatalogowania,
m — liczba znaków w najdłuższym nazwisku (około 25 znaków).
Podobne rozumowanie można przeprowadzić dla tytułów. Przechowywanie nazwisk i tytułów w tablicach znakowych okazuje się więc bardzo nieefektywne, gdyż duża część tych tablic pozostaje niewykorzystana.
Nazwiska i tytuły tworzą rekordy o zmiennej długości. Ekonomicznym — z punktu widzenia pamięcio- chłonności — rozwiązaniem jest przechowywanie nazwisk w jednej zmiennej znakowej, np. n$, a tytułów w drugiej, np. t$. Wykorzystujemy tu pewną osobliwość ZX Spectrum, polegającą na tym, że długość zmiennej znakowej jest nieograniczona (ściślej mówiąc jest ograniczona tylko pojemnością pamięci). Nazwiska i tytuły dopisywane są do zmiennych n$ i t$ w kolejności ich wprowadzania przy użyciu instrukcji
LET n$ = n$ + u$ -f
LET t$ = t$ + v$ + ";"
gdzie: u$ — kolejne nazwisko,
v$ — kolejny tytuł.
Znak średnika jest separatorem, oddzielającym kolejne nazwiska lub tytuły od siebie.
Dostęp do tak zapisanych rekordów możliwy jest dzięki zapamiętaniu początków wszystkich rekordów. Najlepiej użyć do tego dwóch tablic znakowych (odrębne tablice dla nazwisk i tytułów), np. a$ (n, 3) i b$ (n, 3). Zakładam tu, że z każdym tytułem skojarzone jest tylko jedno nazwisko, pozwalające dotrzeć do danego tytułu (fizycznie zapisanych może być więcej nazwisk, ale pamiętany jest tylko początek pierwszego). Aby uniknąć tego ograniczenia, należy zwiększyć wymiar tablicy a$, np. a$ (n + 1. 5 n, 3).
Takie rozwiązanie pozwala na dostęp do rekordów zarówno wg nazwisk, jak i tytułów. Aby dostęp do rekordów był szybki (np. metodą podziałów połówkowych) tablice a$ i b$ muszą być posortowane w kolejności alfabetycznej. Jeżeli zależy nam na szybkim dostępie tylko wg nazwisk, wystarczy aby posortowana była tylko tablica a$. Dwa pierwsze bajty w każdym wierszu tablic a$ i b$ użyte będą do przechowywania adresu początku rekordu w zmiennej znakowej odpowiednio n$ i t$, bajt trzeci jest odsyłaczem do tablicy organizacyjnej r$ (n, 4). Tablica ta wiąże nazwisko z odpowiednim tytułem i odwrotnie. Zawiera ona w każdym wierszu adres początku nazwiska w zmiennej n$ i adres początku tytułu w zmiennej t$ skojarzonego z danym nazw skiem. Adresy początków rekordów przechows wane są w postaci znakowej na dwóch bajtach (jest to oszczędniejsze, gdyż liczby zajmują 5 bajtów):
adres = 200 bajt 1. + bajt 2.
Znając adres początku rekordu (x) możemy go zapisać w postaci znakowej przykładowo dla. — tego wiersza tablic a$:
LET a$ (i, 1) = CHR$ (INT(x) 200) -32
LET a$ (i, 2) = CHR$ (x — 200 (CODE a$ (i, 1) - 32) + 32)
Adresy można łatwo rozkodować wg wzoru:
LET adres = 200 (CODE a$ (i, 1) — 32) * (CODE a$ (i, 2)-32)
Dodanie stałej 32 przy kodowaniu adresów pozwala na przesunięcie kodu znaku do przedziału 32, 232. Znaki o kodach mniejszych od 32 nie dają się bowiem wyświetlić, co utrudnia testowanie programu. Również mnożnik 200 został przyjęty arbitralnie z myślą o ułatwieniu testowania programu (można przyjąć dowolny inny mnożnik — 223). Zapewnia on przestrzeń adresową w przedziale (0,44823) co w praktyce i tak znacznie przekracza potrzeby. Odsyłacze do tablicy organizacyjnej mogą być pamiętane na jednym bajcie, gdy założymy, że liczba rekordów nic przekroczy 223.
Wtedy przykładowo:
a$ (i, 3) = CHR$ (n + 32)
n= CODE (a$ (i, 3)) — 32
gdzie: i — nr wiersza w tablicy a$,
n — nr wiersza w tablicy r$, pod którym zapisane są informacje dotyczące nazwiska i tytułu.
Ograniczenie liczby rekordów do 223 wynika ż prób przeprowadzonych na mikre komputerze ZX Spectrum 48K.
Przykładowy schemat powiązań w omówionych strukturach danych przedstawiony został poniżej (uwaga: w celu zwiększenia przejrzystości wszystkie adresy podane są dziesiętnie, a nie znakowo):
n$ = "Naur. P.; Turski. W.M.; Strizenec. M.;"
t$ = "Zarys, metod, informatyki; Propedeutyka, informatyki; System: człowiek — komputer."
Tablica a$
adres początki, nazwiska
w zmiennej n$
(2 bajty) odsyłacz
do tablicy r$
(1 bajt)
1
21
9 1
2
9
dokończenie ze str. 5
Tablica b$
adres początku tytułu
zmiennej t$
(2 bajty) odsyłacz
do tablicy r$
(1 bajt)
25
50
1 3
2
1
Tablica r$
adres początki, nazwiska
w n$
(2 bajty) odsyłacz
do tablicy t$
(2 bajty)
1
21
9 1
50
25
Wyszukiwanie informacji wg nazwiska odbywa się zgodnie ze schematem:
- a) znaleźć n-nr wiersza w tablicy a$, w którym zapisany jest adres początku podanego nazwiska,
- b) odczytać p -— odsyłacz do tablicy organizacyjnej (odsyłacz ten zapisany jest w a$ (n, 3)),
- c) odczytać z tablicy organizacyjnej adres początku tytułu — ap (adres ten zapisany jest w elementach r$ (p, 3) i r$ (p, 4)),
- d) odczytać tytuł ze zmiennej t$, począwszy od elementu ap aż do pierwszego znaku średnika.
Wyszukiwanie informacji wg tytułu odbywa się podobnie, przy czym odsyłacza do tablicy organizacyjnej szukamy i odczytujemy go z tablicy b$.
Zaletą przedstawionego rozwiązania jest całkowite wykorzystanie pamięci oraz szybki dostęp do rekordów zarówno wg nazwisk, jak i tytułów (przy założeniu, że obydwie tablice, tj. a$ i b$ są posortowane). Wadą jest konieczność deklarowania dodatkowych tablic do pamiętania odsyłaczy i adresów początków rekordów oraz wydłużenie obliczeń, wynikające z kodowania i dekodowania adresów.
Rozwiązanie to jest jednak eleganckie i wykorzystuje typowe metody informatyczne (odsyłacze). Jest godne polecenia we wszystkich programach, gdzie mogą wystąpić rekordy o zmiennej długości, np. przy budowie wielojęzycznych słowników, wszelkiego rodzaju katalogów itp.
Janusz Morbitzer