LISTA

tym rozdziale poznamy bardzo prost▒, ale potrzebn▒ do zrozumienia kolejnego rozdzia│u strukturΩ danych - listΩ dynamiczn▒. Opiera siΩ ona na rekordzie, w kt≤rym jedno z p≤l jest wska╝nikiem na kolejny rekord tego samego typu. Rekordy tem mo┐na doczepiaµ z przodu lub z ty│u listy, zale┐nie od konstrukcji algorytmu. Tego typu struktura pozwala na gromadzenie element≤w, bez statycznego przydzielania im pamiΩci. Program przydziela na nie tyle pamiΩci, ile potrzebuj▒. Jest to przydatne, gdy chcemy rozs▒dnie gospodarowaµ pamiΩci▒ komputera, a nie deklarowaµ na przyk│ad sztywn▒, nieelastyczn▒ tablicΩ.

Zacznijmy od zadeklarowania odpowiedniego typu. BΩdzie on wygl▒daµ mniej wiΩcej tak:

type 
  wsk = ^rec;
  rec = record
    wyraz: string[10];
    next: wsk;
  end;

G│≤wn▒ zawarto╢ci▒ rekordu jest zmienna "wyraz", w kt≤rej mo┐na przechowywaµ stringa d│ugiego na 10 liter. Pole "next" s│u┐y do okre╢lania nastΩpnego elementu listy. Poniewa┐ jest ono typu wska╝nikowego, na pocz▒tku, po przydzieleniu zmiennej pamiΩci, ma ona warto╢µ "NIL". Tak wiΩc nie wskazuje ┐adnego nastΩpnego elementu. Aby do│▒czyµ na ko±cu listy nowy element, trzeba przydzieliµ mu pamiΩµ i ustawiµ wska╝nik poprzednika na niego. Przy tworzeniu algorytmu trzeba ustaliµ jak▒╢ zmienn▒, bΩd▒c▒ uchwytem, "g│ow▒" listy, do kt≤rej bΩdziemy do│▒czaµ elementy. Przez ca│y czas musimy mieµ dostΩp do uchwytu, przypisanie mu np. b│Ωdnej warto╢ci oznacza utratΩ kontroli nad danymi. G│owie nie bΩdziemy dopisywaµ warto╢ci pola wyraz, gdy┐ zmienna ta ma tylko znaczenie "robocze", jest niedostΩpna dla u┐ytkownika programu.

Nasza struktura bΩdzie wiΩc wygl▒daµ tak (nie jest to przyk│ad, a schemat uniwersalny!):

Nale┐y jeszcze podkre╢liµ jedn▒ sprawΩ: lista przez nas prezentowana jest struktur▒ sekwencyjn▒!

W zasadzie powinienem wspomnieµ o tym wcze╢niej, ale jako╢ nie by│o okazji. Zaprezentowana przez nas deklaracja typu jest jedyn▒ sytuacj▒, w kt≤rym typ deklarowany odwo│uje siΩ do typu deklarowanego p≤╝niej!
Inicjacja listy wygl▒da w ten spos≤b:

var
  head: wsk; {G│owa struktury}
begin 
  new(head); {Przydzielenie pamiΩci g│owie}
  . {Operacje
  .  dokonywane
  .na strukturze - dodawanie, usuwanie, przegl▒danie element≤w}
  dispose(head)
end. 

Pozostaje tylko pokazaµ procedury wykonuj▒ce operacje na li╢cie. Parametr "g" podawany procedurom to g│owa struktury.

procedure dodaj(s:string;g:wsk); {Dodaje element na ko±cu. s to warto╢µ pola WYRAZ nowego elementu}
var
  nowy: wsk;
  temp: wsk;
begin
  new(nowy);
  nowy^.wyraz:=s;
  nowy^.next:=nil;
  temp:=g;
  while temp^.next<>nil do temp:=temp^.next;
  temp^.next:=nowy
end;

procedure usuwaj(s:string;g:wsk); {Usuwa element o warto╢ci pola WYRAZ r≤wnej s}
var
  poprz,aktual: wsk;
begin
  poprz:=nil;
  aktual:=g;
  repeat
    poprz:=aktual;
    aktual:=aktual^.next;
  until (aktual^.next=nil) or (aktual^.wyraz=s);
  if aktual^.wyraz=s then begin
    poprz^.next:=aktual^.next;
    dispose(aktual)
  end
end;

function czyjest(s:string;g:wsk):boolean; {True je╢li istnieje element o polu WYRAZ r≤wnym s}
var
  temp: wsk;
begin
  temp:=g^.next;
  while (temp<>nil) and (temp^.wyraz<>s) do temp:=temp^.next;
  if temp=nil then czyjest:=false else czyjest:=true
end;

procedure likwiduj(g:wsk); {Usuwa wszystkie elementy listy opr≤cz g│owy}
var
  poprz,aktual: wsk;
begin
  poprz:=g;
  aktual:=g^.next;
  while aktual<>nil do begin
    poprz:=aktual;
    aktual:=aktual^.next;
    dispose(poprz)
  end
end;