Zreťazená voľná pamäť

Zreťazená voľná pamäť (ZVP) je základný implementujúci typ (využíva sa pri implementácii abstraktných údajových typov). Je tvorený dynamicky alokovaným poľom prvkov, ktoré sú variantným záznamom. Prvok obsahuje príznak, či je voľný a potom v závislosti od toho či je voľný obsahuje buď informáciu o ďalšom voľnom (keď je voľný), alebo dátovú časť (keď nie je voľný), čim vznikne pamäťový priestor rozdelený na úseky rovnakej dĺžky, ktoré sú navzájom explicitne zreťazené. Celá ZVP obsahuje okrem poľa prvkov ešte aj informáciu o prvom voľnom.

Pekný nákres: http://img03.picoodle.com/img/img03/8/4/24/f_zvpm_ec5d6de.jpg Archivované 2007-09-28 na Wayback Machine

Príklad
const max=200; type TIndexy=array[1..max] of integer; type Tktory=0..max;

    TPrvokZVP=record
                case Volny:boolean of
                     true:(DalsiVolny:Tktory);
                     false:(Zaznam:oOsoba);
              end;

type oOsoba=object

             private
               aMeno:string[15];
               aPriezvisko:string[20];
               aTelefonneCislo:string[15];
               aChyba:boolean;
             public
               procedure setMeno(paMeno:string);
               procedure setPriezvisko(paPriezvisko:string);
               procedure setTelefon(paTelefon:string);
               function getMeno:string;
               function getPriezvisko:string;
               function getTelefon:string;
               function getChyba:boolean;
           end;

oZVP=object

           private
             aPrvyVolny:Tktory;
             aPole:^TPoleZVP;
             aPocetPrvkov:integer;
             aExistuje:boolean;
           public
             constructor create;
             procedure vytvorZVP(paPocet:integer);
             procedure zrusZVP;
             procedure vlozPrvok(paData:oOsoba);
             procedure zrusPrvok(paIndex:integer);
             function najdiPrvok(paData:oOsoba;var paIndexy:TIndexy):integer;
             procedure ukazPrvok(paIndex:integer;var paData:TPrvokZVP);
             function existuje:boolean;
             destructor done;
             function volnych:integer;
             function getPrvyVolny:Tktory;
         end;

Vytvorenie ZVP

Spočíva v dynamickom alokovaní poľa, nastavenia prvého voľného na 1 a inicializovanie každého prvku v poli na voľný.

procedure oZVP.vytvorZVP(paPocet:integer);

 var i:integer;
 begin
   aPocetPrvkov:=paPocet;
   aPrvyVolny:=1;
   aExistuje:=true;
   getMem(aPole,aPocetPrvkov*sizeOf(TPrvokZVP));
   for i:=1 to aPocetPrvkov do
     begin
       aPole^[i].Volny:=true;
       if i= paPocet then aPole^[i].dalsiVolny =0
                    else aPole^[i].dalsiVolny:=i+1;
     end;
 end;

Zrušenie ZVP

Je to dealokovanie pamäti, ktorá bola pridelená poľu a nastavenie prvého voľného na 0.

procedure oZVP.zrusZVP;

 begin
   aExistuje:=false;
   aPrvyVolny:=0;
   freeMem(aPole,aPocetPrvkov*sizeOf(TPrvokZVP));
   aPole:=nil;
   aPocetPrvkov:=0;
 end;

Vloženie prvku

Vloženie prvku znamená, vloženie prvku na prvú voľnú pozíciu, toto miesto označiť ako obsadené (čiže voľný:=false) a nastavenie prvý voľný na hodnotu ktorý mal predchádzajúci voľný ako ďalší voľný.

procedure oZVP.vlozPrvok(paData:oOsoba);

 var pom:Tktory;
 begin
   pom:=aPole^[aPrvyVolny].DalsiVolny;
   aPole^[aPrvyVolny].Zaznam:=paData;
   aPole^[aPrvyVolny].Volny:=false;
   aPrvyVolny:=pom;
 end;

Rušenie prvku

Treba nastaviť rušený prvok na voľný. Jeho hodnote ďalší voľný priradiť prvý voľný a prvý voľný nastaviť na rušený prvok.

procedure oZVP.zrusPrvok(paIndex:integer);

 begin
   aPole^[paIndex].dalsiVolny:=aPrvyVolny;
   aPole^[paIndex].volny:=true;
   aPrvyVolny:=paIndex;
 end;

Nájdi prvok

Prejdeme všetky obsadené prvky a hľadáme daný prvok, keď ho nájdeme tak vrátime jeho index.

(v tomto príklade vraciam indexy nájdených prvkov, pre prípad že ich je viac rovnakých a počet nájdených ako návratovú hodnotu funkcie..)

function oZVP.najdiPrvok(paData:oOsoba; var paIndexy:TIndexy):integer;

 var poc,i:integer;
 begin
   poc:=0;
   for i:=1 to aPocetPrvkov do
     if not aPole^[i].volny
       then
         if (paData.getMeno=aPole^[i].zaznam.getMeno)or
            (paData.getPriezvisko=aPole^[i].zaznam.getPriezvisko)or
            (paData.getTelefon=aPole^[i].zaznam.getTelefon)
            then
              begin
                poc:=poc+1;
              end;
   najdiPrvok:=poc;
 end;

Základné operácie ZVP sú

• vlož prvok do ZVP
• nájdi prvok v ZVP
• vymaž prvok zo ZVP

Zložitosť algoritmov

Vytvorenie ZVP	O (1)
Zrušenie ZVP	O (1)
Vlož Prvok do ZVP (↓ Dáta)	O (1)
Nájdi prvok v ZVP (↓ Dáta ↑ Index)	O (N)
Vymaž prvok zo ZVP (↓ Index)	O (1)