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 

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)

Kategória:Údajové štruktúry