Teorie liste simplu inlantuite
Listele liniare(secventiale) au aparut din necesitatea de a pastra si prelucra date de acelasi tip, aranjate intr-o ordine secventiala, avand proprietatea de a se actualiza permanent (adica au loc tot timpul inserari de noi date acolo unde le e locul pentru a pastra ordinea secventiala si eleminiari de elemente, in functie de necesitati). O lista se mai numeste si lant.
Liste simplu inlantuite
O lista liniara este o secventa finita de n elemente(componente) de acelasi tip numite si noduri, aflate intr-o relatie de ordine.
In cadrul unei liste sunt puse in evidenta:
-un element numit primul element,
-un element numit ultimul element,
-cate un singur element succesor pentru fiecare elemnt al listei(cu exceptia ultimului element care nu are succesor adica u->urm=NULL)
-cate un singur element predecesor pentru fiecare element(cu exceptia primului elemnt care nu are predecesor)
Pentru a pune in evidenta succesiunea nodurilor, putem reprezenta o lista astfel:
Componentele listei pot fi date elementare sau date structurate.
Intrucat o lista contine mai multe componente de acelasi tip (structurate sau nu), putem spune ca ea este o data structurata.
De exemplu, putem avea o lista a elevilor unei clase. Aceasta lista se poate modifica in timp prin plecarea elevilor sau prin venirea altor elevi de la alte scoli sau clase. Daca lista contine numele elevilor si numarul lor matricol, putem spune ca toate componentele sunt de tip inregistrare. Un alt exemplu de lista ar putea fi aceea a numerelor extrase dintr-o urna, aceasta fiind o lista in care toate componentele sunt date elementare(numere naturale).
Operatiile cele mai importante definite pe liste sunt:
- crearea unei liste;
-adougarea(inserarea) unui nod in lista;
-stergerea(eliminarea) unui nod din lista;
-modificarea valorii pentru un nod din lista;
-parcurgerea unei liste;
-determinarea numarului de noduri dintr-o lista;
- cautarea in lista a nodului(nodurilor) cu o valoare particulara a unui anumit camp;
-sortarea nodurilor unei liste in ordinea crescatoare(descrescatoare) a continuturilor anumitor campuri ale nodurilor;
-suprimarea(stergerea) unei liste;
-salvarea unei liste;
-restaurarea unei liste.
Variante bac SII V62-64
-liste-
Varianta 62 (Subiectul II)
4. Se consideră o stivă S1, iniţial vidă, în care s-au introdus, în această ordine, valorile 10, 12, 3 şi o altă stivă, S2, iniţial vidă, în care au fost introduse, în această ordine, valorile 6, 5, 4. Care va fi elementul din vârful stivei S1 după următoarele operaţii: se extrag toate elementele din stiva S2 şi se adaugă, în ordinea extragerii, în stiva S1?
Elementul din varful S1 dupa ce s-au extras toate elementele din stiva S2 si s-au extras in ordinea extragerii in S1 este 6.
Varianta 63 (Subiectul II)
2. Într-o listă simplu înlănţuită circulară, alocată dinamic, fiecare element reţine în câmpul adr adresa elementului următor din listă. Dacă p şi q sunt adresele a două elemente distincte din listă astfel încât să fie îndeplinite condiţiile p= q->adr şi q = p->adr , atunci lista are:
a. un numar impar de elemente
b. exact 2 elemente
c. cel putin 3 elemente
d. exact 1 element
Raspunsul corect este b.
Nodul care urmeaza dupa p este q si nodul care urmeaza dupa q este p. Deci lista are exact 2 elemente.
Varianta 64 (Subiectul II)
2. Într-o listă simplu înlănţuită cu cel puţin 1000 de elemente identificate prin adrese, fiecare element reţine în câmpul adr adresa elementului următor din listă. Dacă q este adresa unui element din listă şi p o variabilă de acelaşi tip cu q, ce reţine adresa unui alt element, care nu face parte din listă, atunci inserarea elementului de la adresa p, în listă, imediat după elementul de la adresa q se realizează cu ajutorul secvenţei de instrucţiuni:
a. p->adr=q->adr; q->adr=p;
b. p=q; q->adr= p->adr;
c. q->adr=p; p->adr=q;
d. q=p->adr; p->adr= q->adr;
Raspunsul corect este a.
Nodul p ia adresa nodului care era initial dupa q si q ia adresa nodului p.
