11.4.3. Stergerea unui nod dintr-o lista dublu inlantuita (LDI)

2020/03/11 in Programare in C

Dintr-o LDI se pot sterge noduri. Se vor avea in vedere urmatoarele cazuri:

  1. stergerea primului nod al LDI;
  2. stergerea unui nod precizat printr-o cheie;
  3. stergerea ultimul nod al LDI.

11.4.3.1. Stergerea primului nod dintr-o lista dublu inlantuita

void dspn() { /* sterge primul nod al listei */
  extern TNOD *prim, *ultim;
  TNOD *p;

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

11.4.3.2. Stergerea unui nod dintr-o lista dublu inlantuita precizat printr-o cheie

Vom presupune ca cheia este de tip int. Tipul TNOD se declara ca in paragraful 11.4.2.2.

void dsnci(int c) /* sterge nodul pentru care cheie = c */
{
   extern TNOD *prim, *ultim;
   TNOD *p;

   if (prim == 0) /* lista vida */
      return;
   if ((p = dcnci(c)) == 0) {
      printf("lista nu contine nodul de cheie = %d\n", c);
      return;
   }
   if (prim == p && ultim == p){ /* lista are un singur nod; devine vida */
      prim = ultim = 0;
      elibnod(p);
      return;
   }
   if (prim == p){ /* se sterge primul nod din lista */
      prim = prim -> urm;
      prim -> prec = 0;
      elibnod(p);
      return;
   }
   if (ultim == p){ /* se sterge ultimul nod */
      ultim = ultim -> prec;
      ultim -> urm = 0;
      elibnod(p);
      return;
   }
/* se sterge un nod diferit de capete */

/* urmatorul nodului care se sterge are ca precedent precedentul nodului 
care se sterge */
   p -> urm -> prec = p -> prec;
/* precedentul nodului care se sterge are ca urmator urmatorul nodului 
care se sterge */
   p -> prec -> urm = p -> urm;
   elibnod(p);
}

11.4.3.3. Stergerea ultimului nod al unei liste dublu inlantuite

In acest caz, tipul TNOD nu necesita prezenta unei chei. Se poate utiliza declaratia indicata in paragraful 11.4.2.4.

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

   if (prim == 0) /* lista vida */
      return;
   p = ultim;
   ultim = ultim -> prec;
   if (ultim == 0){
      prim = 0; /* lista devine vida */
   else
      ultim -> urm = 0;
   elibnod(p);
}

Observatii:

  1. Functia dsun, spre deosebire de functia sun relativa la LSI, devine eficienta deoarece ea nu mai necesita parcurgerea nodurilor listei.
  2. Functiile de inserare inainte si dupa un nod precizat printr-o cheie numerica intreaga sunt mai simple in cazul LDI, in comparatie cu analoagele lor pentru LSI, deoarece ele folosesc functia dcnci pentru localizarea nodului in raport cu care se face inserarea.
  3. Functia de stergere a unui nod precizat printr-o cheie numerica intreaga este mai simpla in cazul LDI in comparatie cu functia corespunzatoare pentru LSI, deoarece ea foloseste functia dcnci pentru localizarea nodului care se sterge.
  4. O LDI devine o lista circulara dublu inlantuita (LCDI) dac se fac atributiile:
    ultim -> urm = prim
    si
    prim -> prec = ultim.

Pentru a gestiona o astfel de lista nu mai sunt necesare variabilele prim si ultim, pentru ca lista nu mai are capete. In locul lor se utilizeazaun pointer spre un nod arbitrar al listei, ca in cazul LCSI.

Un exercitiu propus spre rezolvare ar fi construirea functiilor de baza asupra LCDI:

Exercitii:

11.15. Se considera tipul utilizator:

typedef struct tnod {
char *cuvant;
int frecventa;
struct tnod *prec;
struct tnod *urm;
} TNOD;

Sa se scrie functia dadauga, care permite adaugarea la o LDI a unui nod de tipul TNOD definit ca mai sus.

Se observa ca functia dadauga definita in paragraful 11.4.2.4. este dependenta numai de componentele prec si urm din TNOD. De aceea, functia dadauga de mai jos este identica cu cea din paragraful 11.4.2.4.

TNOD *dadauga()
/* - adauga un nod la o LDI;
   - returneaza pointerul spre nodul inserat 
   sau 0 daca nu are loc inserarea */
{
   extern TNOD *prim, *ultim;
   TNOD *p;
   int n;
   
   n = sizeof(TNOD);
   if (((p = (TNOD *)malloc(n)) != 0) && (incnod(p) == 1)) {
      if (prim == 0) {
         prim = ultim = 0;
         p -> prec = p -> urm = 0;
      }
      else {
         ultim -> urm = p;
         p -> prec = ultim;
         p -> urm = 0;
         ultim = p;
      }
      return p;
   }
   if (p == 0) {
      printf("memorie insuficienta\n");
      exit(1);
   }
   elibnod(p);
   return 0;
}

11.16. Sa se scrie o functie care sterge ultimul nod al unei LDI de noduri TNOD definit ca in exercitiul precedent.

Aceasta functie este definita in paragraful 11.4.3.3.

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

   if (prim == 0) /* lista vida */
      return;
   p = ultim;
   ultim = ultim -> prec;
   if (ultim == 0)
      prim = 0; /* lista devine vida */
   else
      ultim -> urm = 0;
   elibnod(p);
}

11.17. Sa se scrie un program care citeste cuvintele dintr-un text si afiseaza numarul de aparitii al fiecarui cuvant din textul respectiv.

Aceasta problema a mai fost rezolvata in exercitiile 10.50. si si 11.6. In exercitiul 11.6. s-a creat o LSI ale carei noduri contin pointeri spre cuvintele diferite din text, precum si frecventa lor de aparitie.

In cazul de fata se utilizeaza o LDI. Prin aceasta, eficienta programului este mai mare, deoarece functia dsun, care sterge ultimul nod dintr-o LDI, este mult mai eficientadecat functia sun care realizeaza acelasi lucru pentru o LSI.

Programul de fata utilizeaza o parte din functiile apelate de Programul 119 si anume:

Functiile adauga si sun se inlocuiesc cu functiile dadauga si respectiv dsun. De asemenea, TNOD se declara ca in exercitiul 11.15.

// needs debugging
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tnod {
   char *cuvant;
   int frecventa;
   struct tnod *prec;
   struct tnod *urm;
} TNOD;

#include "FUNCTIA117A.C" /* citcuv  */
#include "FUNCTIA119A.C" /* incnod  */
#include "FUNCTIA119B.C" /* elibnod */
#include "FUNCTIA119D.C" /* cncs    */
#include "FUNCTIA124A.C" /* dadauga */
#include "FUNCTIA124B.C" /* dsun    */

TNOD *prim, *ultim;

int main () {
   TNOD *p, *q;

   prim = ultim = 0; /* la inceput lista este vida */
   while ((p = dadauga()) != 0)
      if ((q = cncs(p -> cuvant)) != ultim) {
         q -> frecventa++;
         dsun();
      }
   for (p = prim; p; p = p -> urm)
      printf("cuvantul: %-51s are frecventa: %d\n", p -> cuvant, p -> frecventa);
}

11.18. Sa se scrie un program care citeste cuvintele dintr-un text si scrie numarul de aparitie al fiecarui cuvant, in ordinea alfabetica a cuvintelor respective.

Aceasta problema a fost rezolvata la exercitiul 11.7., unde s-a definit functia ordlist, care s-a apelat inainte de a afisa frecventa cuvintelor citite. Ea a modificat inlantuirile nodurilor LSI dreate prin citirea cuvintelor textului, in asa fel incat cuvintele corespunzatoare nodurilor listei sa fie ordonate alfabetic.

In exercitiul de fata se defineste functia dordlist care realizeaza acelasi lucru ca si functia ordlist, adica modifica inlantuirile nodurilor unei LSI.

Amintim ca functia dordlist parcurge lista analizand ordinea cuvintelor corespunzatoare nodurilor vecine. Daca doua cuvinte, care corespund la noduri vecine, nu sunt in ordine alfabetica, atunci se schimba inlantuirile nodurilor respective, asa incat ele sa fie inlantuite invers in lista.

Inversarea inlantuirilor se realizeaza cu ajutorul pasilor descrisi mai jos.

Presupunem ca p pointeaza spre nodul curent din lista si q = p -> urm, deci q pointeaza spre nodul urmator din lista.

Daca p -> cuvant pointeaza spre un cuvant care este in ordine alfabetica dupa cuvantul spre care pointeaza q -> cuvant, atunci nodurile p si q se inlantuiesc invers, deci p devine urmatorul lui q. Aceasta implica pasii:

  1. daca p -> prec != 0, atunci p -> prec -> urm = q, deoarece urmatorul precedentului lui p devine q;
  2. daca q -> urm != 0, atunci q -> urm -> prec = p, deoarece precedentul urmatorului lui q devine p;
  3. p -> urm = q -> urm, deoarece urmatorul lui q devine urmatorul lui p;
  4. q -> urm = p, deoarece p devine urmatorul lui q;
  5. q -> prec = p -> prec, deoarece precedentul lui p devine precedentul lui q;
  6. p -> prec = q, deoarece q devine precedentul lui p.
// needs debugging
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tnod {
   char *cuvant;
   int frecventa;
   struct tnod *prec;
   struct tnod *urm;
} TNOD;

#include "FUNCTIA117A.C" /* citcuv  */
#include "FUNCTIA119A.C" /* incnod  */
#include "FUNCTIA119B.C" /* elibnod */
#include "FUNCTIA119D.C" /* cncs    */
#include "FUNCTIA124A.C" /* dadauga */
#include "FUNCTIA124B.C" /* dsun    */

void dordlist() {
/* ordoneaza nodurile listei de tip TNOD in asa fel incat cuvintele 
corespunzatoare nodurilor sa fie in ordine alfabetica */

   extern TNOD *prim, *ultim;
   TNOD *p, *q;
   int ind;
   if (prim == 0)
      return;
   ind = 1;
   while (ind) {
      ind = 0;
      for (p = prim; p -> urm; ) {
         q = p -> urm; /* q este urmatorul lui p */
         if (stricmp(p -> cuvant, q -> cuvant) > 0) {
/* se inverseaza inlantuirile nodurilor p si q */
            if (p -> prec)
               p -> prec -> urm = q;
            if (q -> urm)
               q -> urm -> prec = p;
            p -> urm = q -> urm;
            q -> urm = p;
            q -> prec = p -> prec;
            p -> prec = q;
            if (p == prim)
               prim = q;
            if (q == ultim)
               ultim = p;
            ind = 1;
      }
      else
/* se trece la nodul urmator, deoarece cuvintele sunt in ordine 
alfabetica */
         p =q;
      }
   }
}

TNOD *prim, *ultim;

int main () {
   TNOD *p, *q;

   prim = ultim = 0; /* la inceput lista este vida */
   while ((p = dadauga()) != 0)
      if ((q = cncs(p -> cuvant)) != ultim) {
         q -> frecventa++;
         dsun();
      }
   dordlist();
   for (p = prim; p; p = p -> urm)
      printf("cuvantul: %-51s are frecventa: %d\n", p -> cuvant, p -> frecventa);
}

12. Arbori