Tablouri-Liste

Liste simplu înlănțuite

 Liste simplu înlănțuite  

     Listele simplu înlănțuite sunt structuri de date dinamice omogene. 
    Spre deosebire de  masive, listele nu sunt alocate ca blocuri omogene de memorie, ci ca elemente  
 separate de memorie. Fiecare nod al listei conține, în afară de informația utilă, adresa  următorului element. Aceasta organizare permite numai acces secvențial la elementele  listei.  
    Pentru accesarea listei trebuie cunoscută adresa primului element (numită capul listei); elementele următoare sunt accesate parcurgând lista.  

 Lista simplu înlănțuită poate fi reprezentată grafic astfel: 

Probleme propuse

Probleme propuse:

    1. Într-o stivă au fost introduse în această ordine, numerele 5, 7, 3, 8. Precizaţi numărul minim de 
elemente care trebuie extrase din stivă pentru a fi siguri că s-a extras inclusiv elementul cu valoarea 3 şi care este elementul aflat în vârful stivei după extragerea acestui element? 
    2. Care va fi valoarea elementului aflat în vârful unei stive iniţial vidă şi care este numărul de elemente rămase în stivă, după efectuarea, în această ordine, a următoarelor operaţii: se introduce valoarea 3; se introduce valoarea 7; se introduce valoarea 5; se extrage un element; se introduce valoarea 2; se introduce valoarea 4; se extrage un element. 
    3. Se consideră o stivă în care iniţial au fost introduse, în această ordine, elementele 1,2,3,4,5,6. Dacă se notează cu PUSH x operaţia prin care se adaugă un element cu informaţia x în stivă şi cu POP operaţia prin care se elimină un element din stivă, care este elementul aflat în mijlocul stivei după executării secvenţei de operaţii: POP; PUSH 7; PUSH 8; POP; POP;? 

Stiva

 

    Stiva e un tip special de listă la care toate inserțiile și suprimările se execută la un singur capăt, numit vârful stivei. Stiva e o listă tip LIFO (Last In First Out). 

 Asupra tipului abstract de date stivă sunt definiți următorii cinci operatori: 

 1.INIȚIALIZARE(S) - face stiva S vidă ( inițializează lista corespunzătoare ) 

 2.VIRFST(S) - furnizează elementul din vârful stivei ( deci primul nod al listei ) 

 3.POP(S) - suprimă elementul din vârful stivei 

 4.PUSH(x,S) - inserează elementul x în vârful stivei pe care îl actualizează 

 5.STIVID(S) - funcție booleană ce e adevărată dacă stiva este vidă. 

     Cele mai avantajoase implementări ale structurii de date stivă sunt cele cu ajutorul tipului pointer și al tipului tablou. 

Despre ultimul element pus pe stivă se spune că este vârful stivei, despre primul că este baza stivei.

Vârful stivei se modifică de fiecare dată când punem/eliminam un element din stiva.

Cu alte cuvinte accesul este permis doar la vârful stivei:

· un element se poate pune în stivă numai după elementul aflat în vârful stivei şi după aceasta operație el ajunge vârful stivei;

· se poate scoate de pe stiva numai elementul aflat în vârful stivei şi după aceasta operație în vârful stivei rămâne elementul care a fost pus pe stiva înaintea lui. 

Stiva poate fi implementată atât static, folosindu-ne de un vector unidimensional cât şi dinamic, folosindu-ne de o listă simplu înlănțuită.

Coada

      Coada e tot un tip special de listă în care elementele sunt inserate la un capăt ( spate ) și sunt suprimate la celălalt ( față ); se mai numesc liste FIFO ( First In First Out ), adică de tip primul venit, primul servit. 

 Se definesc următorii operatori: 

 1.INIȚIALIZARE(C) - face coada ( lista ) vidă 

 2.FATZA(C) - funcție ce returnează primul element al cozii C 

 3.ADAUGĂ(x,C) - inserează elementul x în spatele cozii 

 4.SCOATE(C) - suprimă primul element al lui C 

 5.VID(C) - funcție ce e adevărată dacă coada este vidă. 

     Cele mai uzuale implementări ale cozii sunt cu ajutorul tipului pointer și al tablourilor circulare. 

     Coada bazată pe prioritate e structura de date abstractă care permite inserția unui nou element și suprimarea celui mai mare element dintre cele existente. Structura diferă de coadă ( din care se suprimă primul venit, deci elementul cel mai vechi ) și de stivă ( din care se suprimă ultimul venit, deci cel mai nou ). 

 Asupra acestei structuri de date, ale cărei elemente sunt articole cu chei ( sau priorități ), se definesc operațiile : 

 GENEREAZĂ - o coadă bazată pe priorități, pornind de la N elemente ( succesiune de inserții ) 

 INSEREAZĂ - un nou element 

 EXTRAGE - cel mai mare element 

 ÎNLOCUIRE - a celui mai mare element cu unul nou, mai puțin prioritar ( inserție + suprimare ) 

 SCHIMBĂ - prioritatea unui element ( suprimare + inserție ) 

 SUPRIMĂ - un element oarecare, precizat 

 REUNEȘTE - două cozi în una singură. 

 Ca implementări a acestei structuri de date, sînt mai uzuale cele ce folosesc liste neordonate, liste ordonate după prioritate, ansamble.