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; aPriezvisko:string; aTelefonneCislo:string; 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