Liste Liniare Simple

of 12/12
Liste liniare simplu inlantuite Adaugarea si stergerea nodurilor Glodeanu Natali cls. a XI - A
  • date post

    15-Jun-2015
  • Category

    Documents

  • view

    1.031
  • download

    7

Embed Size (px)

Transcript of Liste Liniare Simple

Liste liniare simplu inlantuiteAdaugarea si stergerea nodurilor

Glodeanu Natali cls. a XI - A

Adaugarea nodurilorAdaugare unui nod se poate face in mai multe feluri: Adaugarea primului nod Inainte de primul nod Dupa ulimul nod In interiorul listei Dupa nodul din pozitia q Inainte de nodul din pozitia q

Adaugare primului nodPasii:1. 2. 3.4.

void adaugp(nod *& prim,nod *&ultim,int x) { nod *prim=new nod; prim->info=x; prim->urm=NULL; }

Se aloca memorie pentru primul nod Se scrie informatia in nodul prim Adresa de legatura a nodului va fi nula

Nodului ultim i se atribuie adresa nodului prim ultim=prim;

Primul nod din lista :

prim->info prim->urm

X

0

tip int

prim si ultim

tip pointer la adresa

Adaugare inainte de primul nodPasii: void ainfata(nod *&prim, int x) { nod *p=new nod; Se aloca memorie nodului p->info=x; Se scrie informatia in nodul p Nodul p se leaga de nodul prim p->urm=prim; Nodul p inserat devine prim prim=p; }

xp prim

prim prim

Adaugare dupa ultimul nodPasii: 1. 2. 3. 4. 5. Se aloca memorie nodului Se scrie informatia in nod Adresa de de legatura a nodului p devine NULL Nodul ultim se leaga de nodul p adaugat Nodul p devine ultim void adupa(nod *&ultim,int x) { nod *p=new nod; p->info=x; p->urm=NULL; ultim->urm=p; ultim=p; }

p 0ultim

Xp ultim

0

Adaugare dupa un nod qPasii: Se aloca memorie nodului Se scrie informatia in nod Nodul p se leaga de succesorul nodului q Nodul q se leaga de nodul p adaugat Daca nodul q a fost ultimul nod in lista, atunci p devine ultim void adupaq(nod *q, nod *&ultim, int x) { nod *p=new nod; p->info=x; p->urm=q->urm; q->urm=p; if(q==ultim) ultim=p; }

q->urm p

x p

q->urm

q

Adaugare inainte de nod qPasii: 1. 2. 3. 4. 5. 6. Se aloca memorie nodului Copiem informatia din q in p Nodul p se leaga de succesorul nodului q Se scrie in q info. care trebuia adugata Nodul q se leaga de nodul p adugat Daca q a fost ultimul nod in lista, nodul p adaugat devine ultim; void ainainteq(nod *&q, nod *&ultim, int x) { nod *p=new nod; p->info=q->info; p->urm=q->urm; q->info=x; q->urm=p; if (purm==NULL) ultim=p; }

q->info q->urm p X p q

q->info q->urm q p

Stergerea unui nodSe poate sterge : Primul nod din lista Ultimul nod din lista Un nod dintr-o pozitie intermediara Toata lista

Stergerea primului nod din listaPasi:1. 2. 3. Se salveaza adresa pointerului prim in q Succesorul nodului devine prim Se elibereaza zona de memorie ocupata de pointerul q void eliminprim(nod *&prim) { nod *q=prim; prim=prim->urm; delete q; }

prim

prim

Pasii:

Stergerea ultimului nod din listavoid eliminultim(nod *prim, nod*& ultim) { nod *p,*q=ultim; for(p=prim; p->urm->urm!=NULL; p->urm); p->urm=NULL; ultim=p; delete q; }

1. Se salveaza adresa ultim in q 2. Se cauta predecesorul ultimului nod, prin parcurgerea listei de la primul nod pana predecesorul nodului terminal (cu adr. 0) 3. Predecesorul va contine adres NULL 4. Predecesorul nodului ultim devine ultim 5. Se elibereaza spatiul de memorie ocupat de q

0 ultim q ultim

0

Stergerea unui nod din interiorul listeiPasii:void elimina(nod *p, nod *&ultim) { nod *q=p->urm; 1. Se salveaza adr. succesorului lui p in q p->info=q->info; 2. Copeim in p informatia din q 3. Copiem in p adresa din q p->urm=q->urm; 4. Se elibreaza spatiu de mem. ocupat de q delet q; 5. Daca suceesorul lui p a fost ultim, if(p->urm==NULL) atunci p devine ultim ultim=p; }

q->info q->urm

q->info q->urm

p

q

Stergerea unei liste intregiPasii:1.Se initializeaza p cu adresa nodului prim 2.Cat timp p diferit de NULL se parcurge lista 3.Se salveaza adresa nodului p in q 4.Se trece la nodul urmator 5.Se elibereaza zona de memorie ocupata de q 6.Se revine la pasul 2 7.Prim devine si ultim void steglista(nod *&prim) { nod *p=prim,*q; while(p!=NULL) { q=p; p=p->urm; delet q; } prim=ultim; }

The endp q prim p q 0 p

0 q ultim