Liste (1-7) Flashcards
Definitia listelor ordonate liniar
Listele ordonate liniar sunt structuri de date alcătuite dintr-o mulţime A de elemente (de obicei identice), între care există o relaţie determinată de poziţia lor relativă. Astfel, fiecare element A k are un predecesor A k-1 şi
un succesor A k+1
Cum se poate realiza reprezentarea în memorie?
Reprezentarea în memorie se poate realiza:
* secvenţial;
* prin înlănţuirea elementelor.
Cum sunt dispuse elementele in reprezentarea secventiala si comparatia acesteia cu un tablou?
În acest tip de reprezentare, elementele sunt dispuse succesiv, într-o zonă contiguă de memorie. Reprezentarea este similară cu cea a unui tablou (nu trebuie făcută identificarea listei cu obiectul tablou în care sunt memorate elementele ei). (Un tablou este un caz particular de listă, acela în care elementul i al listei se află memorat în tab [i]).
Avantajele reprezentarii secvenţiale
Avantaje:
-accesul la oricare element din listă,
-parcurgerea listei şi adăugarea unui element la sfârşitul listei se fac cu uşurinţă.
Clasificarea listelor in funcţie de locul de acces la liste
În funcţie de locul de acces la liste
* Lista FIFO (First In First Out ) – (coada) inserarea se face la un capăt al listei (la sfârşit), extragerea de la celălalt capăt (din faţă).
* Lista LIFO (Last In First Out) - (stivă) - operaţiile de inserare / extragere se fac de la acelaşi capăt al listei, numit vârful stivei.
Cum se realizează lista FIFO în reprezentare secvenţială si relatia de calcul reprezentativa?
Lista FIFO se realizează în reprezentare secvenţială (folosind un tablou) ca un “tampon circular”,
Folosind notaţiile:
prim = indexul primului element
ult = indexul ultimului element
ncrt = numărul de elemente din listă
n = numărul de elemente din tablou
ult = (prim + ncrt) modulo n
Ce trebuie verificat înaintea unor operaţii de extragere si de adăugare
Înaintea unei operaţii de extragere trebuie verificat dacă există elemente în listă deci ncrt > 0.
Înaintea unei operaţii de adăugare se verifică dacă există spaţiu în tablou, deci dacă ncrt < N.
Dezavantajele reprezentarii secvenţiale
Dezavantaje:
- inserarea si ştergerea de elemente din mijlocul listei sunt operaţii costisitoare, (deoarece presupun deplasarea unor elemente.)
- memoria nu este utilizată eficient dacă numărul componentelor variază în limite largi în timpul execuţiei programului, (deoarece spaţiul alocat pentru tablou (static sau dinamic) este fix şi dimensiunea alocată trebuie să fie acoperitoare.)
