liste liniare simple

Liste liniare simpluinlantuite

Adaugarea si stergerea

nodurilor

Glodeanu Natali cls. a XI - A

Adaugarea nodurilor

Adaugare 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 nod

Pasii:

1. Se aloca memorie pentru primul nod

2. Se scrie informatia in nodul prim

3. Adresa de legatura a nodului va fi nula4. Nodului ultim i se atribuie adresa nodului prim

void adaugp(nod *& prim,nod *&ultim,int x)

{ nod *prim=new nod;

prim->info=x;

prim->urm=NULL;

ultim=prim;

}

prim->info prim->urm

X 0

prim si ultim

Primul nod din lista :

tip int tip pointer la adresa

Adaugare inainte de primul nod

Pasii: • Se aloca memorie nodului

• Se scrie informatia in nodul p

• Nodul p se leaga de nodul prim

• Nodul p inserat devine prim

void ainfata(nod *&prim, int x)

{ nod *p=new nod;

p->info=x;

p->urm=prim;

prim=p;

}

primprimp

primx

Adaugare dupa ultimul nodPasii:

1. Se aloca memorie nodului

2. Se scrie informatia in nod

3. Adresa de de legatura a nodului p devine NULL

4. Nodul ultim se leaga de nodul p adaugat

5. 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;

}

ultim p

0p 0

ultim

X

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 p

pq->urm x q->urm

Adaugare inainte de nod qPasii:

1. Se aloca memorie nodului

2. Copiem informatia din q in p

3. Nodul p se leaga de succesorul nodului q

4. Se scrie in q info. care trebuia adugata

5. Nodul q se leaga de nodul p adugat

6. 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;

}

X p

q pp q

q->info q->urm q->info q->urm

Stergerea unui nod

Se poate sterge :• Primul nod din lista

• Ultimul nod din lista

• Un nod dintr-o pozitie intermediara

• Toata lista

Stergerea primului nod dinlista

Pasi:

1. Se salveaza adresa pointerului prim in q

2. Succesorul nodului devine prim

3. Se elibereaza zona de memorie

ocupata de pointerul q

void eliminprim(nod *&prim)

{ nod *q=prim;

prim=prim->urm;

delete q;

}

prim prim

Stergerea ultimului nod din lista

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

void 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;

}

ultimq

0 0

ultim

Stergerea unui nod din interiorul listei

Pasii:1. Se salveaza adr. succesorului lui p in q

2. Copeim in p informatia din q 3. Copiem in p adresa din q

4. Se elibreaza spatiu de mem. ocupat de q

5. Daca suceesorul lui p a fost ultim,

atunci p devine ultim

void elimina(nod *p, nod *&ultim)

{ nod *q=p->urm;

p->info=q->info;

p->urm=q->urm;

delet q;

if(p->urm==NULL)

ultim=p;

}

p q

q->info q->urmq->info q->urm

Stergerea unei liste intregi

Pasii:1.Se initializeaza p cu adresa nodului prim

2.Cat timp p diferit de NULL se parcurge lista3.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;

}

primp q p pq q

0

ultim0

The end