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)