Zreťazená voľná pamäť

Z Wikipédie

Niektorý z redaktorov požiadal o revíziu tohoto článku. Redaktor si napríklad nie je istý, či neobsahuje pravopisné alebo iné chyby. Prosím opravte a vylepšite tento článok. Po úprave článku môžete odstrániť túto poznámku. Viac informácií....

Zreťazená voľná pamäť (ZVP) je jeden z nástrojov slúžiacich na implementovanie abstraktných údajových typov. Zreťazená voľná pamäť je pamäťový priestor rozdelený na úseky rovnakej dĺžky, ktoré sú navzájom explicitne zreťazené.

[úprava] Realizácia

Prvok je realizovaný variantným záznamom (record) (Pascal), kde sa podľa atribútu voľný typu boolean určí, či je daný prvok voľný, v tom prípade je jeho dátová časť využitá ako referencia na ďalší voľný prvok, alebo je obsadený, a v tom prípade sa jeho dátová časť skutočne využije na uloženie potrebných dát.

Pre uloženie jedného prvku v pamäti sa vždy rezervuje maximum možného počtu bytov.

Napr. :

 TData=string[10];
 TPrvokZVP=record
   case volny: boolean of
     true: (dalsi:integer);
     false: (data:TData);
   end; 
 end; 

Veľkosť Prvku bude rovná veľkosti premennej voľný (1 B) + maximum z veľkostí ďalší (2 B) a data (11 B), teda 12 B.

Zreťazená voľná pamäť pri vytvorení vyalokuje v heape (halde) pole o veľkosti počet prvkov * sizeof(TPrvokZVP) a nastaví všetkým prvkom v poli hodnotu voľný na true a hodnotu ďalší na jeho nasledovníka.

[úprava] Základné operácie ZVP sú :

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

[úprava] 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)