Inserarea si stergerea unui element din lista
Inserarea unui element nou in lista se poate face inainte sau dupa un nod care retine o valoare data (continut util). Evident s-ar putea realiza si inserare pe o pozitie data astfel incat toate elemantele de la acea pozitie incepand se vor deplasa mai la "dreapta".
In cazul in care inserarea se face "dupa" se avanseaza cu un nod intermediar c in lista pana la nodul dupa care se va face inserarea, se creaza un nou nod (nodul a) apoi se genereaza legaturile: mai intai de la a la c->next apoi de la c la a. Exista posibilitatea ca ultimul nod sa retina valoarea dupa care se realizeaza inserarea caz in care se modifica ultimul.
In
cazul in care inserarea se face "inainte"
se avanseaza cu un nod intermediar c in lista pana la un nod situat inaintea
celui cautat , se creaza un nou nod (nodul a)
apoi se genereaza legaturile: mai intai de la a la c->next apoi de la c la
a. Exista posibilitatea ca primul nod sa retina valoarea inainte de care se
realizeaza inserarea caz in care se modifica primul.
In cazul in care se realizeaza stergerea se avanseaza cu un nod intermediar c in lista pana la un nod situat inaintea celui cautat (nodul de sters), se genereaza noule legaturi intre precedentul si urmatorul nodului de sters, se elibereaza spatiul de memorie.
Iata o solutie pentru implementarea functiilor anterioare:
#include<conio.h>
#include<fstream.h>
struct Nod
{int info;
Nod *next;
};
Nod *prim, *ultim;
/*************************************************************************
functiile de creare si
adaugare se pot comprima intr-o singura functie
care poate testa daca
exista un prim nod si in functie de rezultatul testului
va realiza alocarea
primului nod sau se va adauga un nou nod la sfarsit
*************************************************************************/
void creare_adaugare()
{if(prim==NULL)
{prim=new Nod;
cout<<"introduceti
valoarea retinuta in primul nod:";
cin>>prim->info;
prim->next=0; //la crearea listei va
exista un singur nod, primul
// si prin urmare
adresa urmatoare lui este 0
ultim=prim; //evident, avand un
singur element acesta va fi si primul
// si ultimul
}
else
{Nod *c;
c=new Nod;
cout<<"valoarea de adaugat
in lista ";
cin>>c->info;
ultim->next=c; //se "agata" noul nod c, dupa ultimul din lista
ultim=c; //evident
noul nod e ultimul...
ultim->next=0;//...si dupa ultimul
nu e nimic, deci nici o adresa
}
}
void listare()
{Nod *c;
c=prim;
while(c!=0)//cat timp mai sunt in lista
{cout<<c->info<<"
";
c=c->next;//avansez in lista trecand la urmatoarea adresa
}
cout<<endl;
}
/**************************************************************************
functia inserare_dupa()
va insera dupa o valoare val transmisa din main()
***************************************************************************/
void inserare_dupa(int val)
{Nod *c,*a;
//Nod *a retine
adresa nodului ce se va insera in lista
//cu *c se face avansarea in lista pana la
nodul ce contine valoarea dupa
//care se face inserarea; evident se porneste
de la primul;
c=prim;
while(c->info!=val &&c)
c=c->next;
a=new Nod;
cout<<"valoarea de
inserat ";
cin>>a->info;
a->next=c->next;
c->next=a;
if(c==ultim) ultim=a;//pentru ca exista si posibilitatea ca valoarea
//dupa care se
face inserarea sa fie retinuta de ultimul element
}
/**************************************************************************
functia
inserare_inainte() va insera inainte de o valoare val transmisa din main()
***************************************************************************/
void inserare_inainte(int val)
{Nod *c,*a;
//Nod *a retine
adresa nodului ce se va insera in lista
//cu *c se face avansarea in lista pana la
nodul ce contine valoarea //inainte
//care se face inserarea; evident se porneste
de la primul;
c=prim;
//pentru ca
exista si posibilitatea ca valoarea inainte de care se face //inserarea
// sa fie retinuta de primul nod se va face un test si in caz
afirmativ se va
//stabili un nou prim element
if(prim->info==val)
{c=new Nod;
cout<<"valoare
de inserat ";
cin>>c->info;
c->next=prim;
prim=c;}
else
{while(c->next->info!=val
&&c) //c se pozitioneaza inainte de elementul
//cautat
c=c->next;
a=new Nod;
cout<<"valoarea
de inserat ";
cin>>a->info;
a->next=c->next;
c->next=a;}
}
/******************************************************************************
functia realizeaza
stergerea unui element dupa continutul transmis ca parametru
******************************************************************************/
void stergere(int val)
{Nod *c,*a; //a se sterge, c este precedentul
sau.Se va genera o noua //legatura intre c si a->next
c=prim;
if(prim->info==val)
//daca primul nod retine val se sterge primul
{a=prim; //se retine
in a
prim=prim->next;
//primul va deveni urmatorul element
delete a;} //se
elibereaza memoria
else
{while(c->next->info!=val &&c)//se pozitioneaza pe elementul ce urmeaza a //fi sters
c=c->next;
a=c->next;
c->next=a->next;
if(a==ultim)
ultim=c;
delete a;}// se elibereaza memoria
}
void main()
{int i,n,val_info;
cout<<"n=";cin>>n;
for(i=1;i<=n;i++)
creare_adaugare();
listare();
cout<<"dupa
ce valoare din lista se realizeaza inserarea ";
cin>>val_info;
inserare_dupa(val_info);
listare();
creare_adaugare();
listare();
cout<<"valoarea
inainte de care se face inserarea ";
cin>>val_info;
inserare_inainte(val_info);
listare();
cout<<endl<<"valoarea
ce urmeaza a fi stearsa: ";
cin>>val_info;
stergere(val_info);
listare();
}
Probleme propuse
1. Sa se testeze functiile de mai sus
2. Fie o lista de numere intregi distincte. Sa se insereze valoarea 4 dupa 3.
3. Fie o lista de numere intregi. Sa se insereze dupa oricare valoare 3 valoarea 4
4. Fie o lista de numere reale. Sa se insereze intre oricare doua valori media aritmetica a elementelor alaturate.
5. O lista contine titlul si autorul unei carti, precum si editura.
a. Sa se stearga cartile cu titlul “Poezii”. Afisati continutul listei.
b. Sa se insereze un nou volum in lista: “Rascoala –Rebreanu-All” dupa “Ion-Rebreanu –All”. Afisati continutul listei.
c. Sa se insereze un nou volum in lista “Padurea spanzuratilor –Rebreanu-All” inainte de “Rascoala –Rebreanu-All”. Afisati continutul listei.
6. Sa se stearga elementele egale cu x dintr-o lista. Solutie
7. Sa se stearga elementele prime dint-o lista
8. Sa se stearga elementul (elementele) minim dintr-o lista
9. Sa se genereze o lista ordonata (numerica)
10. Sa se genereze o lista care contine numele unor persoane astfel incat sa fie ordonata
11. Sa se genereze permutarile circulare ale unei liste de intregi. De ex pt o lista cu 4 valori:
2 6 8 10
permutarile circulare vor fi:
10 2 6 8
8 10 2 6
6 8 10 2
12. Sa se elimine elementele (elementul) din mujlocul unei liste