11.1.5. Stergerea unei liste simplu inlantuite

2020/02/29 in Programare in C

Se utilizeaza functia elibnod pentru fiecare nod al listei.

void sterglist()
{
   extern TNOD *prim, *ultim;
   TNOD *p;

   while(prim) {
      p = prim;
      prim = prim -> urm;
      elibnod(p);
   }
   ultim = 0;
}

Pentru o lista implementata cu tabloul tpnod functia de stergere va fi:

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

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

Exercitii:

11.1. Se considera tipul utilizator:

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

Se cere sa se scrie functia incnod care incarca datele curente intr-un nod de tip TNOD.

Prin cuvant se intelege un sir de litere mici sau mari, ca in exercitiul 10.48. In acest exercitiu se defineste functia citcuv care citeste un cuvant de la intrarea standard si-l pastreaza in memoria heap. Functia respectiva returneaza adresa de inceput a zonei in care se pastreaza cuvantul citit sau 0 in caz ca se intalneste EOF.

Functia de fata apeleaza functia citcuv si atribuie adresa returnata de ea pointerului cuvant din nodul curent. De asemenea, se atribuie valoarea 1 variabilei frecventa.

Functia incnod returneaza valoarea -1 daca citcuv returneaza valoarea 0 si 1 altfel.

int incnod(TNOD *p) {
   if ((p -> cuvant = citcuv()) == 0)
      return -1;
   p -> frecventa = 1;
   return 1;
}

11.2. Sa se scrie functia elibnod care elibereaza zonele din memoria heap ocupate de nodul de tip TNOD definit in exercitiul precedent.

void elibnod(TNOD *p) {
   free(p -> cuvant);
   free(p);
}

11.3. Sa se scrie functia adauga, care permite adaugarea unui nod de tip TNOD la o lista simplu inlantuita, dupa ultimul nod al listei.

Sa observam ca functia adauga definita in paragraful 11.1.3.4 este dependenta numai de pointerul urm din tipul nodului. De aceea, functia adauga de mai jos este identica cu cea din paragraful amintit mai sus.

Functia de fata apeleaza functiile incnod si elibnod de mai sus.

TNOD *adauga() {
   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 = p;
      else {
         ultim -> urm = p;
         ultim = p;
      }
      p -> urm = 0;
      return p;
   }
   if (p == 0) {
      printf("memorie insuficienta\n");
      exit(1);
   }
   elibnod(p);
   return 0;
}

11.4. Fie o LSI cu noduri de tip TNOD.
Sa se scrie o functie care cauta in lista respectiva nodul pentru care pointerul cuvant are ca valoare adresa unui cuvant dat.

Cu alte cuvinte, pointerul cuvant joaca un rol de cheie si se cere sa se gaseasca nodul a carui cheie pointeaza spre un cuvant dat.

Aceasta functie este asemanatoare cu cnci definita in paragraful 11.1.2.

TNOD *cnsc(char *c) {
   extern TNOD *prim;
   TNOD *p;
   
   for (p = prim; p; p = p -> urm)
   if (strcmp(p -> cuvant, c) == 0)
      return p;
   return 0;
}

11.5. Sa se scrie o functie care sterge ultimul nod al unei LSI de noduri de tip TNOD.

Aceasta functie este definita in paragraful 11.1.4.3. si ea este dependenta numai de pointerul urm din tipul nodurilor.

Ea apeleaza functia elibnod definita la exercitiul 11.2.

void sun() {
   extern TNOD *prim, *ultim;
   TNOD *q1, *q;

   q1 = 0;
   if (prim == 0)
      return;
   for (q = prim; q && q != ultim; q = q -> urm)
      q1 = q;
   if (q == prim)
      prim = ultim = 0;
   else {
      q1 -> urm = 0;
      ultim = q1;
   }
   elibnod(q);
}

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

Cuvantul se defineste ca o succesiune de litere mari si / sau mari. Textul se termina cu EOF.

Aceasta problema a fost rezolvata in exercitiul 10.50. Problema s-a rezolvat folosind un tablou de pointeri ale carui elemente sunt adrese pentru date pastrate in memoria heap. Acest tablou este similar cu tabloul tpnod introdus in acest capitol si utilizat la implementarea listelor.

In exercitiul de fata programul se realizeaza utilizand o LSI cu noduri de tip TNOD, definit in exercitiul 11.1.

Desi programul din exercitiul 10.50 este mai eficient din punct de vedere al timpului de executie decat cel de fata, el are o limitare cu privire la numarul de cuvinte diferite din text.

In exercitiul 10.50 s-a limitat maximul cuvintelor diferite la 100. Evident, aceasta limita poate fi schimbata simplu, modificand valoarea lui MAX.

In programul de fata nu mai este necesar sa definim acest maxim. El se executa astfel:

  1. La intalnirea unui cuvant se construieste un nod pentru cuvantul respectiv. Acesta contine pointerul spre cuvant, care este pastrat in memoria heap. Frecventa de aparitie a cuvantului se face egala cu 1.
  2. Nodul construit la pct. 1 se adauga la lista simplu inlantuita care se construieste.
  3. Se cauta in lista un nod care sa corespunda cuvantului curent.
    Daca exista un astfel de nod si acesta nu este ultimul nod al listei, atunci se mareste frecventa din nodul respectiv si apoi se sterge ultimul nod al listei (cel adaugat la pct. 2), deoarece cuvantul exista deja in lista.
    Dupa pasul 3 se revine la pasul 1 si ciclul continua pana cand nu mai sunt cuvinte de citit (s-a ajuns la sfarsitul de fisier). In acest moment se listeaza cuvintele si frecventa lor de aparitie, corespunzatoare nodurilor listei.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

#include "FUNCTIA117A.C" /* citcuv  */
#include "FUNCTIA119A.C" /* incnod  */
#include "FUNCTIA119B.C" /* elibnod */
#include "FUNCTIA119C.C" /* adauga  */
#include "FUNCTIA119D.C" /* cncs    */
#include "FUNCTIA119E.C" /* sun     */

TNOD *prim, *ultim;

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

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

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

Aceast program este asemanator cu cel precedent. Diferenta consta in faptul ca inainte de a lista cuvintele se face o ordonare a nodurilor listei in asa fel incat cuvintele corespunzatoare nodurilor sa fie ordonate alfabetic. Aceast lucru se realizeaza prin functia ordlist.

Ordonarea nodurilor se face pe baza schimbarii inlantuirii acestora.

Se utilizeaza metoda de sortare a bulelor. Potrivit acestei metode, se compara cuvintele corespunzatoare a doua noduri vecine. Daca ele nu sunt in ordine alfabetica, atunci se schimba ordinea de inlantuire in lista a nodurilor respective.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

#include "FUNCTIA117A.C" /* citcuv  */
#include "FUNCTIA119A.C" /* incnod  */
#include "FUNCTIA119B.C" /* elibnod */
#include "FUNCTIA119C.C" /* adauga  */
#include "FUNCTIA119D.C" /* cncs    */
#include "FUNCTIA119E.C" /* sun     */

void ordlist() {
/* ordoneaza nodurile listei de tip TNOD in ordinea
alfabetica a cuvintelor corespunzatoare */

   extern TNOD *prim, *ultim;
   TNOD *p, *p1, *q;
   int ind;

   if (prim == 0)
      return; /* lista vida */
   ind = 1;
   while(ind) {
/* cat timp ind nu este 0, terbuie sa se parcurga lista 
si sa se inverseze inlantuirile nodurilor vecine carora 
le corespund cuvinte care nu sunt in ordine alfabetica */
      ind = 0;
      p = prim; /* p pointeaza spre nodul curent */
      p1 = 0; /* p1 pointeaza spre nodul precedent */
      q = p -> urm; /* q pointeaza spre nodul urmator */
      while (q != 0) /* exista nod urmator */
         if (stricmp(p -> cuvant, q -> cuvant) > 0) {
/* - cuvintele corespunzatoare nodului curent si nodului 
urmator nu sunt in ordine alfabetica;
   - se inverseaza inlantuirile lor. */
            if (p == prim) /* nodul curent nu are precedent */
               prim = q; /* q devine primul nod al listei */
            else
               p1 -> urm = q; /* q devine urmatorul lui p1 */
            p -> urm = q -> urm; /* urmatorul lui p devine urmatorul lui q */
            q -> urm = p; /* urmatorul lui q devine p */
            p1 = q; /* precedentul lui p devine q */
            q = p -> urm; /* q devine urmatorul lui p */
            if (q == 0)
               ultim = p; /* p nu mai are urmator */
            ind = 1;
/* s-a facut o permutare, deci procesul de ordonare nu este terminat */
         }
         else {
/* - nu se schimba inlantuirile nodurilor, deoarece 
cuvintele corespunzatoare sunt in ordine alfabetica;
   - se avanseaza in lista la perechea urmatoare de noduri. */
            p1 = p;
            p = q;
            q = q -> urm;
         }
      }
   }

TNOD *prim, *ultim;

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

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

11.2. Stive si cozi