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.

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.

Wyszukiwarka

Podobne podstrony:
ALG 9 5.1. Listy jednokierunkowe 99 stawałby się on wówczas automatycznie głową listy i musiałby zos
ALG9 5.1. Listy jednokierunkowe 119 wartość zwracaną przez funkcję: w normalnej sytuacji winien to
ALG 5 5.1 Listy jednokierunkowe 95 w tej książce dla uproszczenia operuje się głównie wartościami ty
ALG 7 5.1. Listy jednokierunkowe 97 public: int pusta()    // czy lista jest pusta? {
ALG1 5.1 Listy jednokierunkowe 101 5.1 Listy jednokierunkowe 101 ELEMENT Aprzed=NULL,*po=inf.głowa;
ALG3 5.1 Listy jednokierunkowe 103 noprawny obiekt - może aktywować dowolną metodę swojej klasy, cz
ALG5 5.1 Listy jednokierunkowe 105 Na rysunku 5-7 możemy przykładowo prześledzić jak powinna być wy
ALG7 5.1. Listy jednokierunkowe 107 cout « "L2 = for (i=0; i<n; 12.dorzuc2(tab2[i++])) ; 12
ALG1 5.1. Listy jednokierunkowe 111 i zarobków. (Rozbudowa tych struktur danych nie wniosłaby konce
ALG3 5.1 Listy jednokierunkowe 113 int wzor(int x,int(*fun)(int!) [ return fun(x); ) void main(} i
ALG5 5.1. Listy jednokierunkowe 115 I res->gIowa=przed; res->oqon=pos; return (ras) ; } 1 •
ALG7 5.1. Listy jednokierunkowe 117 Mając już komplet funkcji pusta, zestaw funkcji decyzyjnych i u
ALG1 5.1 Listy jednokierunkowe 121 } cout << "

ALG 4 94 Rozdział 5. Struktury danych5.1. Listy jednokierunkowe Lista jednokierunkowa jest oszczędną
ALG8 108__Rozdział 5. Struktury danych5.1.3.Listy jednokierunkowe - teoria i rzeczywistość Oprócz p
ALG7 5.2. Tablicowa implementacja list 1275.2.3.Listy innych typów Listy jednokierunkowe są bardzo
ALG9 7.3. Transformacja kluczowa 199 Co jest niepokojące w zaproponowanej powyżej metodzie? Zapreze
itp. Porusza także problemy aktualnie najbardziej bolesne, takie jak los osób torturowanych, kampani
13302 PrepOrg cz I9 - 109 - wodnej eterem, zad fazy organicznej kwasem i wodą, dla wymycia resztek

więcej podobnych podstron