Adatszerkezetek 2:

4. Láncolt lista:

A láncolt lista olyan adatszerkezet, amely dinamikusan szabályozott mennyiségű, azonos típusú elemet tárol. Ilyen a tömb, de az nem dinamikus és maximális mérete van, ilyen a sor, de annak is maximális mérete van, valamint a verem, de az is maximalizált méretű.

A láncolt lista dinamikus adatszerkezet, és a méretét csak a fizikai memória szabja meg (32Mbyte-nál max. 32Mbyte-os lehet).

A tömb indulási mérete fix, és használat közben ugyanannyi marad. A sor és a verem is ilyen, hiába dinamikus, a teljes mérete fix. A láncolt lista indulási mérete minimális, menet közben a mérete „alkalmazkodó”.

A tömb elemei tetszőleges (direkt) elérésűek. A sor elérése FIFO (amit elsőnek be, elsőnek ki). A verem elérése LIFO (amit utolsónak be, elsőnek ki). A láncolt lista elérése soros (szekvenciális). Az elejétől a kiválasztott elemig sorrendben kell feldolgozni.

A láncolt lista elemei két részből állnak: értékből és mutatóból. A lista elején egy fej áll.

Fej(mutató) -> 1. elem, mutató -> 2. elem, mutató -> utolsó elem, NIL

A fej megmutatja, hogy az első elem a memóriában hol helyezkedik el, az első elem egy értéket tartalmaz, valamint egy mutatót, ami a második elem címét mutatja. Az utolsó elem muatatója NIL értékű.

Az üres lista feje NIL. Egy elemű lista feje mutat az elemre, elem mutat NIL-re.

Beszúrás:

Egy új elem beszúrása 2 mutató átállításába kerül (8 byte).


Törlés:

Egy elem törlése 1 mutató átállításába kerül (4 byte).


Hozzáadás a végéhez:

Egy új elem hozzáadása a végéhez 2 mutató átállításába kerül (8 byte).


Algoritmusok:

TYPE

  PRekord=^TRekord;

  TRekord=Record

    Nev:String;

    Kov:PRekord;

  end;

Var

  Start:PRekord;

{Inicializáló eljárás - NIL-re állítja a fejet:}

Procedure ListaInit;

begin

  GetMem(Strart,SizeOf(TRekord));

  Start^.Nev:=’’;

  Start^.Kov:=NIL

end;

{Új elemet hoz létre - nem illeszti be, csak létrehozza az új elemet:}

Fuction Ujelem(Nev:String):PRekord;

begin

  GetMem(P,SizeOf(TRekord));

  P^.Nev:=Nev;

  P^.Kov:=NIL;

  Ujelem:=P;

end;

{A következő elemet adja vissza:}

Function Kovetkezo(P:PRekord)PRekord;

begin

  If P=NIL then Kovetkezo:=NIL

  else Kovetkezo:=P^.Kov;

end;

{Lista kiírása:}

Procedure Listakiir;

var

  P:PRekord;

begin

  P:=Start;

  While Kovetkezo(P)<>NIL do

  begin

    P:=Kovetkezo(P);

    Writeln(P^.Nev);

  end;

end;

{Hozzáadás a végéhez:}

Procedure Vegehezad(S:String);

var

  P:PRekord;

begin

  P:Start;

  While Kovetkezo(P)<>NIL do P:=Kovetkezo(P);

  P^.Kov:=Ujelem(S);

end;

{Egy elem beszúrása egy adott elem mögé: (probléma, ha nagyobb elemet adunk meg, mint a lista elemeinek száma)}

Procedure Adotthelyrebeszur(S:String;I:Integer);

var

  P,Puj:PRekord;

begin

  P:=Start;

  While (Kovetkezo(P)<>NIL) and (I>0) do

  begin

    P:=Kovetkezo(P);

    I:=I-1;

  end;

  Puj:=Ujelem(S);

  Puj^.Kov:= P^.Kov;

  P^.Kov:=Puj;

end;

{Elem törlése:}

Procedure Torol(I:Integer);

var

  B,P:PRekord;

begin

  P:=Start;

  I:=I-1;

  While (Kovetkezo(P)<>NIL) and (I>0) do

  begin

    P:=Kovetkezo(P);

    I:=I-1;

  end;

  B:=Kovetkezo(Kovetkezo(P));

  If P^.Kov<>NIL then FreeMem(P^.Kov,SizeOf(TRekord));

  P^.Kov:=B;

end;

{Hely keresése rendezett beszúráshoz:}

Function Helyetkeres(S:String):Integer;

var

  P:PRekord;

  I:Integer;

begin

  P:Start;

  I:=0;

  While (Kovetkezo(P)<>NIL) and (Kovetkezo(P) ^.Nev<S) do

  begin

    I:=I+1;

    P:=Kovetkezo(P);

  end;

  Helyetkeres:=I;

end;

{Rendezett beszúrás:}

Procedure Helyrebeszur(S:String);

var

  I:Integer;

begin

  I:=Helyetkeres(S);

  Adotthelyrebeszur(S,I);

end;

{Gyors rendezett beszúrás:}

Procedure Helyrebeszurgyors(S:String);

var

  P,Puj:PRekord;

begin

  P:=Start;

  While (Kovetkezo(P)<>NIL) and (Kovetkezo(P) ^.Nev<S) do

    P:=Kovetkezo(P);

  Puj:=Ujelem(S);

  Puj^.Kov:=P^.Kov;

  P^.Kov:=Puj;

end;

{A lista elejétől a végéig törli az elemeket:}

Procedure Teljeslistatorol;

var

  P,Puj:PRekord;

begin

  P:Start;

  While Kovetkezo(P)<>NIL do

  begin

    Puj:=Kovetkezo(P);

    FreeMem(P^.Kov,SizeOf(TRekord));

    P^.Kov:=NIL;

    P:=Puj;

  end;

  Start^.Kov:=NIL;

end;

Begin

  Listainit;

  Vegehezad(‘Alma’);

  Vegehezad(‘Barack’);

  Adotthelyrebeszur(‘Balazs’,1);

  Helyrebeszur(‘Csongor’);

  Helyrebeszurgyors(‘Tibor’);

  Torol(2);

  Listakiir;

  Teljeslistatorol;

end;

Szűcs Tamás - szucs_t@freestart.hu