// Liste simplu inlantuite - Alocare dinamica// Autor: Popescu Ionut// http://www.rstcenter.com#include<iostream.h>// Structura in care memoram nodurilestruct Nod{ int inf; // Partea de informatie Nod * leg; // Partea de legatura } * v, * sf; // Primul si ultimul nodint i=1,x=1337,y; // Variabile: i-contor pentru noduri, x,y-pentru apeluri de functii char c; // Pentru selectarea metodei de creare a listei// Functia creaza un nod si il adauga in fata primului nod, ordinea nodurilor va fi inversavoid adaugare_inainte(int x){ Nod * p; p = new Nod; // Alocam spatiu pentru nod p -> inf = x; // Punem partea de informatie p -> leg = v; // Facem legatura de la noul nod catre primul v = p; // Primul nod devine cel proaspat creat}// Functia creaza un nod si il adauga dupa ultimul nodvoid adaugare_dupa(int x){ Nod * p; p = new Nod; // Alocam spatiu p -> inf = x; // Partea de informatie sf -> leg = p; // Facem legatura de la ultimul nod, catre cel proaspat creat p -> leg = NULL; // Noul nod va fi ultimul si ii facem legatura catre NULL if (i==1) v = p; // Daca este primul nod pe care il cream ( ne folosim de contorul i ), il memoram in v sf = p; // Primul nod este si ultimul, setam ultimul nod ca acest nod proaspat creat}// Functia creaza un nod cu valoarea y, si il adauga dupa nodul de valoare xvoid adaugare_dupa_o_valoare(int x, int y){ Nod * p, * q; p = new Nod; q = new Nod; // Alocam spatiu p = v; // Incepem de la primul nod while(p -> inf != x) // Si parcurgem lista pana informatia din nodul la care am ajuns este x, ceea ce cautam { p = p -> leg; // Trecem la nodul urmator } // La iesirea din while, nodul cu informatia x, va fi nodul p q -> inf = y; // Punem informatia in noul nod q -> leg = p -> leg; // Facem legatura noului nod, cu nodul care ii urmeaza nodului p p -> leg = q; // Facem legatura nodului p, cu noul nod creat, nodul q}// Functia adauga un nod de informatie y, in fata nodului de valoare xvoid adaugare_inainte_de_o_valoare(int x, int y){ Nod * p, * q; p = new Nod; // Alocam spatiu q = new Nod; p = v; // Pormin de la primul nod if(p -> inf == x) // Verificam mai intai daca nodul cautat este primul { q -> inf = y; // Scriem informatia in noul nod q -> leg = p; // Facem legatura de la noul nod, la primul v = q; // Primul nod devine cel proaspat creat } else { // Daca nu e primul nod, parcurgem lista pana cand nodul urmator nodului curent are valoarea cautata. // Facem asta deoarece trebuie sa stim nodul anterior nodului de valoare cautata pentru a putea face legatura // Deci la iesirea din while, p va fi nodul anterior nodului cautat de noi while(p -> leg -> inf != x && p -> leg != NULL) { p = p -> leg; // Trecem la nodul urmator } q -> inf = y; // Scriem valoarea in noul nod q -> leg = p -> leg; // Facem legatura de la noul nod, catre nodul de valoare cautata, de valoare x p -> leg = q; // Facem legatura de la nodul anterior nodului cautat, catre noul nod creat }}// Functia adauga 0, in fata primului nod de valoare negativavoid adaugare_0(){ Nod * p, * q; p = new Nod; // Alocare de spatiu p = v; // Pormin de la primul nod while(p -> leg) // Parcurgem lista { if(p -> inf < 0) // Daca nodul la care am ajuns este de informatie negativa { q = new Nod; // Alocam spatiul pentru noul nod q -> inf = 0; // Punem informatia 0 in noul nod q -> leg = p -> leg; // Facem legatura de la noul nod catre nodul care urmeaza dupa nodul curent, de valoare negativa p -> leg = q; // Facem legatura de la nodul de informatie negativa catre noul nod break; // Iesim fortat din while, pentru a adauga 0 decat dupa primul nod negativ } p = p -> leg; // Trecem la nodul urmator } }// Functia sterge nodurile de valoare xvoid sterge_nod(int x){ Nod * p, * q; p = new Nod; q = new Nod; // Alocare de spatiu p = v; // Pornim de la primul nod if(p -> inf == x) // Daca primul nod contine valoarea cautata { v = p -> leg; // Facem legatura de la primul nod catre al doilea, cel urmator primului, practic, al doilea nod devine primul delete(p); // Stergem primul nod } else { while(p -> leg) // Parcurgem lista { q = p -> leg; // Nodul q, va fi nodul urmator nodului p if(q -> inf == x) // Daca acesta contine informatia cautata { p -> leg = q -> leg; // Facem legatura de la elementul anterior acestuia catre nodul urmator acestuia delete(q); // Apoi il stergem } p = p -> leg; // Trecem la urmatorul nod } } }// Functia sterge nodul urmator nodului de valoare xvoid sterge_nod_urmator(int x){ Nod * p, * q; p = new Nod; // Alocare de spatiu q = new Nod; p = v; // Primul nod // Parcurgem lista pana ajungem la nodul de informatie dorita // La iesirea din while, p va fi nodul cu informatia cautata while(p -> inf != x && p -> leg != NULL) { p = p -> leg; } q = p -> leg; // Nodul q va fi nodul urmator nodului p, cel pe care vrem sa il stergem p -> leg = q -> leg; // Facem legatura de la nodul anterior acestuia catre nodul urmator acestuia delete(q); // Apoi il stergem}// Functia sterge nodul anterior nodului de valoare xvoid sterge_nod_anterior(int x){ Nod * p, * q; p = new Nod; // Alocare de spatiu q = new Nod; p = v; if(p -> leg -> inf == x) // Daca nodul urmator primului, nodul al doilea e cel cautat ( primul nu poate fi ) { v = p -> leg; // Primul nod devine cel care era al doilea delete(p); // Stergem primul nod } else { p = v; // Plecam de la primul nod // Parcurgem lista pana cand ajungem la valoarea dorita, dar avem nevoie de nodul anterior, nodului anterior celui de valoare cautata // La iesirea din while, p va fi nodul anterior nodului anterior nodului de valoare cautata. Avem nevoie de el pentru a face legaturile // Schema ar fi cam asa: p -> nod_anterior_nodului_cu_valoarea_x -> nod_cu_valoarea_x while(p -> leg -> leg -> inf != x && p -> leg -> leg != NULL) { p = p -> leg; } q = p -> leg; // Nodul q va fi nodul urmator lui p, nodul anterior nodului cu valoarea cautata, nodul pe care vream sa il stergem p -> leg = q -> leg; // Facem legatura de la nodul p, la nodul urmator lui q, nodul cautat delete(q); // Stergem nodul q } }// Functia afiseaza toate nodurile, folosim si niste separatorivoid tiparire(){ Nod * p; p = new Nod; // Alocare de spatiu p = v; cout<<"Afisare:\n-------------------------------------------------------\n"; while(p -> leg) // Parcurgem lista { cout<<p -> inf<<"\n"; // Afisam valoarea din nodul la care am ajuns p = p -> leg; // Trecem la nodul urmator } cout<<"-------------------------------------------------------\n"; }// Main-ul, in care vom apela functiile pentru a le testa. Int si return-ul de la final pentru ca folosesc Dev-C++, puteti folosi void in Borlandint main(){ v = new Nod; // Primul nod sf = new Nod; // Ultimul nod cout<<"Selectati metoda de inserare:\na) Inainte de primul nod ( ordine inversa )\nb) Dupa primul nod\n"; cout<<"-------------------------------------------------------\nOptiune: (a/b): "; cin>>c; cout<<"-------------------------------------------------------\n"; while(x!=0) // Citim noduri pana la introducerea unui nod de valoare 0 { cout<<"Nod "<<i<<" : "; // Numerotam nodurile cin>>x; // Citim valoarea nodului if(c=='a') adaugare_inainte(x); // Daca s-a ales sa se adauge nodul inaintea primului, il adaugam inainte else adaugare_dupa(x); // Daca nu, il adaugam dupa ultimul i++; // Incrementam contorul } tiparire(); // Afisam toate nodurile // Introducem un nod dupa o valoare data cout<<"Introducere nod dupa valoarea: "; cin>>x; // Citim valoarea nodului dupa care vrem sa introducem noul nod cout<<"Valoare de introdus: "; cin>>y; // Citim informatia pe care o va avea noul nod adaugare_dupa_o_valoare(x, y); // Adaugam nodul tiparire(); // Afisam nodurile // Introducem un nod inainte de o valoare data cout<<"Introducere nod inainte de valoarea: "; cin>>x; // Valoarea nodului cautat cout<<"Valoare de introdus: "; cin>>y; // Informatia din noul nod adaugare_inainte_de_o_valoare(x, y); // Adaugam nodul tiparire(); // Afisam nodurile // Adaugam un nod de informatie 0 dupa primul nod negativ cout<<"Se adauga 0 dupa primul element negativ...\n"; adaugare_0(); // Facem adaugarea tiparire(); // Afisam nodurile // Stergem primul nod cu o valoare citita cout<<"Sterge nodul cu valoarea: "; cin>>x; // Valoarea nodului pe care vrem sa il stergem sterge_nod(x); // Stergem nodul tiparire(); // Afisam nodurile // Stergem nodul urmator nodului cu o valoare citita cout<<"Sterge nodul urmator nodului cu valoarea: "; cin>>x; // Citim valoarea sterge_nod_urmator(x); // Stergem nodul tiparire(); // Iar afisam nodurile // Stergem nodul anterior nodului cu o valoare citita cout<<"Sterge nodul anterior nodului cu valoarea: "; cin>>x; // Citim valoarea sterge_nod_anterior(x); // Stergem nodul tiparire(); // Si pentru ultima oara, afisam nodurile cin>>x; // Ca sa nu se inchida fereastra de MS-DOS, sa vedem rezultatele return 0; // EXIT_SUCCESS}