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
Top Related