11.1.4. Stergerea unui nod dintr-o lista simpla inlantuita

2020/02/28 in Programare in C

Dintr-o lista simplu inlantuita se pot sterge noduri. Acest lucru se poate realiza in mai multe moduri. Se vor avea in vedere urmatoarele cazuri:

1. stergerea primului nod al unei liste simplu inlantuite;
2. stergerea unui nod precizat printr-o cheie;
3. stergerea ultimului nod al listei simplu inlantuite.

Functiile de stergere utilizeaza functia elibnod. Aceasta functie elibereaza zona de memorie alocata nodului care se sterge, precum si eventualele zone de memorie alocate suplimentar pin intermediul functiei incnod pentru a pastra diferite componente ale unui nod (de ex. componente de tip sir de caractere).

Alaturi de functiile obisnuite de stergere, se definesc astfel de functii si pentru listele implementate cu ajutorul tabelului tpnod.

11.1.4.1. Stergerea primului nod al unei liste simplu inlantuite

void spn() /* sterge primul nod din lista */
{
   extern TNOD *prim, *ultim;
   TNOD *p;

   if (prim == 0) /* lista vida */
      return;
   p = prim;
   prim = prim -> urm;
   elibnod(p);
   if (prim == 0) /* lista a devenit vida */
      ultim = 0;
}

In cazul in care lista este implementata cu ajutorul tabloului tpnod, se elimina nodul spre care pointeaza elementul tpnod[0], apoi se deplaseaza elementele tabloului tpnod folosind atribuirile: tpnod[i] = tpnod[i+1], pentru i = 0, 1, ....,itpnod-2.

void tpspn() /* sterge primul nod din lista */
{
   extern TTNOD *tpnod[];
   extern int itpnod;
   int i;

   elibnod(tpnod[0]);
   for (i = 0; i < itpnod-1; i++)
      tpnod[i] = tpnod[i+1];
   itpnod--;
}

11.1.4.2. Stergerea unui nod precizat printr-o cheie dintr-o lista simplu inlantuita

Vom considera ca cheia este de tip int. In acest caz, tipul TNOD se defineste ca in paragraful 11.1.2.

void snci(int c) /* sterge nodul pentru care cheie = c */
{
   extern TNOD *prim, *ultim;
   TNOD *q, *q1;
   
   q1 = 0;
   q = prim;

/* - se cauta nodul de cheie = c 
   - la terminarea ciclului, q pointeaza spre nodul respectiv, 
   sau q = 0 daca nu exista un astfel de nod; 
   - q1 pointeaza spre nodul al carui succesor este 
   nodul spre care pointeaza q sau q1 = 0 daca q = prim */
   
   while (q) {
      if (q -> cheie == c)
         break; /* s-a gasit nodul cautat */
      q1 = q;
      q = q -> urm;
   }
   if (q == 0) { /* nu exista in lista un nod pentru care cheie = c */
      printf("lista nu contine un nod de cheie = %d\n", c);
      return;
   }
/* se sterge nodul spre care pointeaza q */
   if (q == prim) { /* se sterge primul nod din lista */
      prim = prim -> urm;
      elibnod(q);
      if (prim == 0)
         ultim = 0; /* lista a devenit vida */
   }
   else {
      q1 -> urm = q -> urm;
/* succesorul nodului spre care pointeaza q1 devine 
succesorul nodului spre care pointeaza q */
      if (q == ultim)
/* se sterge ultimul nod, deci nodul spre care pointeaza q1 
devine ultimul nod al listei */
         ultim = q1;
   elibnod(q);
   }
}

In cazul in care lista este implementata cu ajutorul tabloului tpnod, se cauta nodul pentru care cheie = c. Fie acesta nodul a carui adresa este data de elementul tpnod[i].

Dupa eliminarea nodului respectiv se realizeaza atribuirile:
tpnod[k] = tpnod[k+1], pentru k = i, i+1, ..., itpnod-2.

void tpsnci(int c) {
   extern TTNOD *tpnod[];
   extern int itpnod;
   int i;

   for (i = 0; i < itpnod; i++)
      if (tpnod[i] -> cheie == c)
         break;
   if (i == itpnod) {
      printf("lista nu contine un nod de cheie = %d\n", c);
      return;
   }
   elibnod(tpnod[i]);
   for ( ; i < itpnod-1; i++)
      tpnod[i] = tpnod[i+1];
   itpnod--;
}

11.1.4.3. Stergerea ultimului nod dintr-o lista simplu inlantuita

void sun() /* sterge ultimul nod din lista */
{
   extern TNOD *prim, *ultim;
   TNOD *q, *q1;
   
   q1 = 0;
   q = prim;
   
   if (q == 0)
      return; /* lista vida */
   while(q != ultim) {
      q1 = q;
	  q = q -> urm;
   }  
   
   if (q == prim)
      prim = ultim = 0;
/* lista contine un singur nod, care se sterge */
/* lista a devenit vida */
   else {
/* nodul spre care pointeaza q1 are ca succesor
nodul spre care pointeaza q si acesta este ultimul nod al listei */
/* cum nodul spre care pointeaza q se sterge, nodul spre care 
pointeaza q1 devine ultimul */
      q1 -> urm = 0;
      ultim = q1;
   }
   elibnod(q);
}

In cazul in care se foloseste tabloul tpnod, operatia de stergere a ultimului nod este mult mai eficienta, deoarece nu necesita parcurgerea nodurilor listei.

void tpsum() {
   extern TTNOD *tpnod[];
   extern int itpnod;
   
   if (i == itpnod) {
      return; /* lista vida */
   }
   elibnod(--itpnod);
}

Observatie: Functiile definite in paragrafele precedente realizeaza operatiile cele mai frecvent utilizate asupra listelor. Unele dintre aceste functii necesita parcurgerea nodurilor listei, partial sau in totalitate. Alte functii nu necesita astfel de parcurgeri. Functiile care parcurg nodurile unei liste au o eficienta scazuta in comparatie cu cele care nu fac astfel de parcurgeri. De aceea, se recomanda pe cat posibil, utilizarea functiilor care nu necesita parcurgerea nodurilor ei. Astfel de functii sunt:

In cazul listelor implementate cu ajutorul tabloului tpnod, cele mai eficiente functii sunt cele care nu necesita instructiuni ciclice care sa se execute asupra elementelor tabloului tpnod. Astfel de functii sunt:

De aceste observatii se tine, uneori, seama la alegerea modului de implementare a listelor in aplicatii.

11.1.5. Stergerea unei liste simplu inlantuite