Amiga MA Magazine 1997 #3/amigamamagazinepolishissue03-1/ma_1995/07/ami70

Text File | 1997-04-15 | 6KB | 150 lines

11E

<lead>Muszë stwierdziê, ûe jestem pod wraûeniem. Nigdy nie byîem
przekonany do twórczoôci Quentina Tarrantino. Wedîug mnie "Bad
Lieutenant" ("Zîy porucznik") byî przesadnie brutalny. Nie
podobaî mi sië. Natomiast ostatnie dzieîo -- "Pulp Fiction" --
jest po prostu rewelacyjne. Mimo nieprzeciëtnej dozy przemocy
(czego bardzo nie lubië) film moûe zachwyciê. Rzeczywiôcie,
zgodnie z nazwâ, jest to brukowa powieôê, jednak mistrzowsko pokazana.
Poleciîbym ten film wszystkim kursantom E, jednak
jest pewna przeszkoda -- "Pulp Fiction" jest, sîusznie zresztâ,
dozwolony od 18 lat!

<a>Rafaî Wiosna

<txt>Dziô na warsztacie mamy...

<sr>Listy linkowane

<txt>Wiem, wiem, ûe Lotny Patrol Lingwistyczny wydaî na mnie
wyrok, a ciëûarówki wypeînione ich bojówkami juû tu jadâ. Brzydko to
wyglâda i brzmi, jednak, jak sâdzë, utarîo sië sîowo "linkowaê",
szczególnie w ôrodowisku programistów, a wîaônie do nich kierujë
ten kurs.

Amiga E ma pewnâ cechë, która jest bardzo rzadko spotykana
(zwykle obsîuga list îâczonych, ang. linked lists, jest
realizowana zewnëtrznymi procedurami, nie jest wbudowana "w
jëzyk"). Znowu jak na dîoni widaê, ûe autor E wziâî najlepsze
cechy kilku jëzyków, w tym miëdzy innymi jëzyka Lisp, który ûywi
sië listami.

Do miana listy linkowanej mogâ pretendowaê E-listy oraz E-ciâgi,
gdyû to wîaônie te typy danych moûna obsîugiwaê za pomocâ pewnych
funkcji, oferowanych przez E. Listë linkowanâ moûna porównaê do
normalnej listy list, z tym ûe poszczególne jej elementy sâ
porozrzucane po pamiëci, nie zajmujâ jednego ciâgîego kawaîka.
Kaûdy z elementów takiej linkowanej listy otrzymuje dodatkowy
parametr (niedostëpny dla programisty) -- wskaúnik do elementu
nastëpnego. W szczególnym wypadku, kiedy dany element jest
ostatnim w liôcie, wskaúnik ma wartoôê NIL (czyli zero).

Co prawda autor E nie okreôliî zasady, ûe typy danych w
linkowanej liôcie majâ byê te same (tzn. lista ma sië skîadaê
tylko z E-list lub tylko E-ciâgów), jednak nie powinno sië
zbytnio mieszaê -- wszak nie ma w E funkcji IsString() czy
IsList(), które mogîyby odpowiedzieê na pytanie, czy dana
dana jest ciâgiem czy listâ.

Do obsîugi list linkowanych sîuûâ cztery funkcje.

>Link(COMPLEX1,COMPLEX2)<. Funckja ta îâczy COMPLEX1 z COMPLEX2
(mogâ to byê dwie E-listy, dwa E-ciâgi lub E-lista i E-ciâg). W
ekstremalnych wypadkach COMPLEX2 moûe mieê wartoôê NIL, co
przydaje sië przy obcinaniu "ogona" linkowanej liôcie (jak juû
wspomniaîem, element takiej listy, który wskazuje na NIL, jest
traktowany jako ostatni). Nielinkowane E-ciâgi i E-listy majâ
wskaúnik nastëpnego elementu ustawiony na NIL. Parametrem
zwracanym przez funkcjë jest wskaúnik do COMPLEX1. Jest on
potrzebny do poruszania sië po liôcie.

Sîuûy do tego funcja >Next(COMPLEX)<. Zwraca ona wskaúnik do
nastëpnego elementu wskazywanego przez COMPLEX. Jeûeli jest on
ostatnim elementem listy, zwracany jest NIL. (Koniecznie naleûy
sprawdziê, czy parametr COMPLEX nie jest przypadkiem NIL, gdyû
inaczej dziaîanie funkcji nie jest okreôlone i moûe doprowadziê
do zawieszenia sië komputera!). Oto przykîad uûycia Link() i
Next(). (Zapis "->" oznacza "wskazuje/wskazujâcy na").

<l>DEF s[23]:STRING, t[7]:STRING, lt[41]:LIST, lnk

-> Najpierw tworzymy linkowalnâ listë

lnk:=Link(lt,t) -> lista skîada sië z dwóch elementów: lt->t

lnk:=Link(s,lt) -> teraz jest trzyelementowa: s->lt->t

-> Utworzyliômy trzyelementowâ listë: s->lt->t->NIL


-> Przykîad "wëdrówki" po liôcie (lnk wskazuje na s)

lnk:=Next(lnk) -> Teraz lnk wskazuje na lt->t

lnk:=Next(lnk) -> Teraz lnk wskazuje na t

lnk:=Next(lnk) -> Teraz lnk ma wartoôê NIL, co oznacza koniec listy

<txt>Warto zauwaûyê, ûe powinieneô trzymaê gdzieô wskaúnik na
"gîowë" listy. Amiga E ma bardzo prostâ implementacjë list
linkowalnych, umoûliwiajâcâ "wëdrówkë" tylko w przód. Moûna to
nazwaê "listâ jednostronnie linkowanâ". Brak jest moûliwoôci
wykonania funkcji Previous(), która zwracaîaby adres POPRZEDNIEGO
elementu "listy linkowanej obustronnie". Tak wiëc, gdy
powëdrujesz sobie funkcjâ Next() na koniec listy, utracisz tym
samym jej gîowë (pierwszy element), chyba ûe zapamiëtasz jâ
wczeôniej w jakiejô zmiennej.

Wracajâc do funkcji Next(), moûna jâ wywoîaê z parametrem NIL i
nic sië nie stanie (a dokîadniej -- zwróci NIL).

Bardzo podobnâ funkcjâ, operujâcâ na listach linkowanych, jest
>Forward(COMPLEX,LICZBA)<. Zwraca ona wskaúnik do elementu listy
odlegîego od COMPLEX o LICZBA elementów. Jak moûna zauwaûyê,

<l>nast:=Next(lnk)

<txt>to to samo co

<l>nast:=Forward(lnk,1)

<txt>Instrukcja

<l>nast:=Forward(lnk,5)

<txt>zwróci w zmiennej nast wskaônik do piâtego elemetu po lnk.

Aby pozbyê sië ogona linkowanej listy, naleûy uûyê funkcji
>DisposeLink(COMPLEX)<. Usunie ona z pamiëci wszystkie zlinkowane
do COMPLEX elementy. Oto przykîad:

<l>-> Zakîadam, ûe mamy listë a->b->c->d->NIL

ogon:=Link(b,NIL)

DisposeLink(c) -> usuwa ogon c->d->NIL

-> Teraz lista wyglâda tak: a->b->NIL

<txt>W tym miejscu chciaîbym podkreôliê, ûe nie wolno îâczyê
E-list lub E-ciâgów statycznych, gdyû mija sië to z celem.
Pamiëtacie mój wywód na temat danych statycznych w poprzednim
odcinku? Elementy list linkowanych powinny byê alokowane
dynamicznie, za pomocâ funkcji List() i String()!

Listy linkowalne sâ bardzo pomocne przy budowaniu kompleksowych
struktur danych, a dokîadniej list dynamicznie alokowanych, tzn.
takich, które mogâ sië rozszerzaê lub zmniejszaê, w zaleûnoôci od
wyników dziaîania programu. Bardzo dobrym przykîadem na linkowane
listy jest program D.e znajdujâcy sië w katalogu Src/Utils.

<sr>*

<txt>Tym razem odcinek jest krótszy niû zwykle, stwierdziîem, ûe
nie ma sensu mëczyê Was na plaûy duûâ porcjâ informacji. W
nastëpnym numerze zacznie sië prawdziwe miësko: wbudowane funkcje
graficzno-intuicyjne (tzn. takie, które uûywajâ Intuition).
Postaram sië wyjaôniê tajniki programowania systemu, chociaû polecam
teû lekturë kursu (tfu!) C.