Liste Inlantuite Curs12

Liste inlantuite Operatii de baza cu LsI-inserare nod la inceput;inserare nod inaintea altui nod precizatprim cheie dupa ,inserare nod la sfarsit(append);stergerea primului nod;toata lista;sortarea ,ordonarea LSIC lost-next-first;au un rol delicat in aplicatii:numere intregi mari,operatii cu polinoame,alocare dinamica LDI sunt liste care permit accesul in ambele sensuri;gestionarea se face folosind doua variabile globale first,last Pasii pentru adaugarea unui element nou pe stiva sunt urmatorii:1)crez un nou elem. Cu alocarea dinamica-newp;2)asignez datele la noul elem. Creat newp-datadi;3)stabilesc legaturile ai acestui nou element sa pointeze la urmatoarele elemente din lista adica newp-next-heap Pasii pentru scoaterea unui element(pop)-se declara link temp-pointeaza pe modul current din varf;face ca head sa pointeze pe urmatoarele elemente din stiva;elibereaza spatiu elementelor temporare delete temp; Cozi alocate dynamic- FIFO Daca elemental este primul tre sa ne asiguram ca si elemental head va point ape acesta.Cand adaugam oricare alt element vom adauga la baza astfel ca tail va point ape noul element de asemmeneavom lega noul element la acela care il precede in coada actualizand pointerul predecesorului Astfel elem cozii sunt legate si putem accesa orice element de la varf la baza Algaritmul de agaugare este: 1)Se creaza un nou element referit de new_a;2)se asigneaza data noului element obtinut;3)facem ca aceste element san u pointeze nicaieri;4)daca coada e goala facem ca noul element sa pointeze pe elem referit;5)fac ca baza sa poiteze o pe new_o. LIste inlantuite ordonat Pentru a pastra si actualize o lista tre sa fim in stare sa inseram un element in pozitia logica sau sa stergem un elem sau sa modificam continutul unui element.Pentru fiecare operatie avem nevoie de o procedura care va determina pozitia in lista a unui element cu o valoare cheie data chiar daca valoarea cheie exista sau nu in lista. Algoritm de gasire a pozitiei care poate fi un element din lista cu o cheie specificata: 1)lista va fi ordonata official dupa valoarea cheii;2)se considera ca head sa fie pozitia initiala a elementului current;3)prev=NULL;4)folosesc un flag exit pt ca nu stiu ca re din element e in lista;5)setez pozitia si consider urmatoarea pozitie in lista ca si element current 6)daca cheia specificata este aceasi cu cheia curenta flag ia valoarea 1 Algoritm de inserare : GAseste pozitia unde elemental a fost introdus;daca nu e intrare duplicata aloc memorie pentru noul element ,asignez datele noului element,daca inserarea se face la inceput fac ca noul lement sa pointeze pe elemental current,fac ca noul element sa fie pointer de head,altfel fac ca noul element sa pointeze pe successor,fac ca precedentul sa pointeze pe noul element,altfel dau mesaj de cheie duplicata