ALG9

5,1. Listy jednokierunkowe 109

Poruszony powyżej problem był na tyle charakterystyczny dla wielu rzeczywistych programów', że zostało do jego rozwiązania wymyślone pewne „sprytne” rozwiązanie, które postaram się dość szczegółowo omówić.

Pomysł polega na uproszczeniu i na skomplikowaniu zarazem tego, co poznaliśmy wcześniej. Uproszczenie polega na tym, że rekordy zapamiętywane w liście nie sąw żaden sposób wstępnie sortowane, inaczej mówiąc, do zapamiętywania możemy użyć odpowiednika jakże prostej funkcji dorzuci ze strony 98. Słowo „odpowiednik” pasuje tutaj najlepiej, bowiem niezbędne okaże się wprowadzenie kilku kosmetycznych zabiegów związanych z ogólną zmianą koncepcji.

Obok listy danych będziemy ponadto dysponować kilkoma listami wskaźników do nich. List tych będzie tyle, ile sobie zażyczymy kryteriów sortowania.

Jak nietrudno się domyślić, jeśli nie zamierzamy sortować listy danych (a jednocześnie chcemy mieć dostęp do danych posortowanych!), to podczas wstawiania nowego adresu do którejś z list wskaźników musimy dokonać jej sortowania. Zadanie jest zbliżone do tego, które wykonywała funkcja dorzuci, z tą tylko różnicą, że dostęp do danych nie odbyw'a się w sposób bezpośredni.

Podczas sortowania list wskaźników dane nie są w ogóle „ruszane” - przemieszczaniu w listach będą ulegały wyłącznie same wskaźniki! Na tym etapie ma prawo to wszystko brzmieć dość enigmatycznie, pora zatem na jakiś konkretny przykład. Popatrzmy w tym celu na rysunek 5-8.

adrl    adr2    adr3

Rys. 5-«.

Sortowanie listy be: przemieszczaniu jej elementów <!)■

Zawiera on listę o nazwie DANL, zbudowaną z kilku rekordów, które stanowią zaczątek miniaturowej bazy danych o pracownikach pewnego przedsiębiorstwa. Przyjmijmy dla uproszczenia, że jedyne istotne informacje, które chcemy zapamiętać, to: imię, nazwisko, pewien kod i oczywiście zarobek. Na rysunku są zaznaczone symbolicznie adresy rekordów: adrl, adrl i adr3, przydzielone przez funkcję dorzuci.