Date definite recursiv

10.7. Date definite recursiv

2020/02/13 in Programare in C

Fie declaratia:

struct nume {
    declaratii
};

Declaratiile incluse intre acolade definesc componentele datelor structurate de tip nume, tip definit prin declaratia struct. Aceste declaratii pot defini date de diferite tipuri predefinite sau utilizator, dar diferite de tipul nume. In schimb, se pot defini pointeri spre date de tipul nume. Deci, o declaratie de forma:

struct nume {
    declaratii
    struct nume *nume1;
    declaratii
};

este corecta, in vreme ce declaratia:

struct nume {
    declaratii
    struct nume nume1;
    declaratii
};

este eronata.

Un tip utilizator se spune ca este direct recursiv daca el are cel putin o componenta care este de tip pointer spre el insusi.

Exemplu:

struct tnod {
    char cuvant[100];
    int nr;
    struct tnod *urm;
};

Tipul utilizator tnod contine 3 componente:

tabloul cuvant de tip char de 100 de elemente;
variabila nr de tip int;
pointerul urm de tipul tnod.

tnod este de tip direct recursiv deoarece contine un pointer pre el insusi.

In continuare, putem defini obisnuit date de tipul tnod.

Evident, tipurile direct recursive pot fi denumite folosind constructia typedef. Tipul de mai sus il vom numi TNOD folosind declaratia:

typedef struct tnod {
    char cuvant[100];
    int nr;
    struct tnod *urm;
} TNOD;

In continuare putem defini date folosind tipul TNOD:

TNOD nod, *p;

O alta posibilitate in definirea tipurilor utilizator este acela in care un tip t1 contine un pointer spre tipul t2, iar acesta, la randul lui, contine un pointer spre tipul t1. In acest caz, se spune ca tipul t1 este indirect recursiv.

Sa observam ca la declararea tipului t1 se utilizeaza o declaratie de forma:

struct t2 *nt2;

Aceasta este posibil daca tipul t2 este definit inainte de tipul t1. Sa presupunem ca acest lucru are loc. Dar la declararea tipului t2 constatam ca acesta contine o declaratie de forma:

struct t1 *nt1;

Aceasta, la randul ei, poate fi scrisa daca inaintea declaratiei tipului t2 este prezenta declaratia care defineste tipul t1. Se ajunge, in felul acesta, la o contradictie. Pentru a o elimina, s-a introdus in limbajul C declaratia de tip incompleta.

Aceasta are formatul:

struct nume;

Aceasta declaratie poate fi plasata intr-un fisier sursa inainte de a defini tipul nume sau in orice fisier sursa in care tipul nume nu este inca definit. Dupa declaratia de tip incompleta, se pot declara pointeri spre tipul respectiv. In felul acesta, tipuril t1 si t2 de mai sus se vor declara astfel:

struct t1; /* - declaratie incompleta spre tipul t1;
              - in continuare se poate declara tipul t2 */
struct t2 {
    declaratii
    struct t1 *nt1;
    declaratii
};
struct t1 { /* - declaratia completa a lui t1 */
    declaratii
    struct t2 *nt2;
    declaratii
};

Un tip se spune ca este recursiv daca el este direct sau indirect recursiv.

O data este recursiva daca ea este o data de un tip recursiv.

In general, un tip t este indirect recursiv daca exista un sir de tipuri ti:

t1, t2, t3, ..., tn

asa incat tipul ti contine cel putin o componenta care este pointer spre tipul tj(j = i + 1), pentru i = 1, 2, ..., n-1, iar t1 si tn sunt ambele de tipul t.

Datele recursive se utilizeaza intr-o serie de aplicatii bazate pe definirea si prelucarea listelor, arborilor, tabelelor de dispersie, etc.

Ele sunt folosite cu succes in prelucrarea dinamica a datelor.

In multe aplicatii se utilizeaza date structurate de un anumit tip, care se repeta de un numar variabil de ori, numar care se precizeaza la fiecare executie a programului.

In astfel de situatii se poate defini un tablou de structuri al carui numar de elemente sa fie egal cu o valoare maxima precizata de utilizator. Acest mod de lucru nu este cel mai indicat atunci cand numarul datelor difera mult de la o executie la alta. De asemenea, pot sa se iveasca situatii in care acest maxim este greu de evaluat, sau chiar evaluat gresit. De aceea, in astfel de cazuri, este mult mai util sa se pastreze datele respective in memoria heap, rezervandu-se memorie pentru ele la executie, pe masura ce este nevoie. Prelucrarea datelor respective implica posibilitatea de a trece simplu de la o data la alta. In cazul tablourilor, acest lucru se face cu ajutorul indicilor. In aceasta noua situatie, se poate trece de la o data pastrata in memoria heap la o alta data de acelasi tip, daca se utilizeaza un pointer spre spre tipul comun datelor respective si care sa fie componenta a datei respective. Deci, se ajunge la un tip de forma:

typedef struct nume {
    declaratii
    struct nume *urm;
    declaratii
} nume_tip;

In felul acesta se ajunge la necesitatea de a utiliza date recursive.

Gestiunea dinamica a lor mai are inca un avantaj si anume: astfel de date pot fi eliminate usor din memoria heap cand nu mai este nevoie de ele si zona eliberata in acest fel poate fi realocata altor date de acelasi tip sau in alte scopuri.

Exercitii:

1. Sa se scrie o functie care citeste un cuvant si-l pastreaza in memoria heap. Prin cuvant intelegem o succesiune de litere mici sau mari.

Functia returneaza adresa de inceput a zonei din memoria heap in care se pastreaza cuvantul citit, sau zero la intalnirea EOF.

FUNCTIA117A.C - Citire cuvant

char *citcuv()
/* - citeste un cuvant si-l pastreaza in memoria heap;
   - returneaza pointerul spre cuvantul respectiv, sau 0 la intalnirea EOF */
{
  int c, i;
  char t[255];
  char *p;

/* salt peste caractere care nu sunt litere */
  while ((c=getchar()) < 'A' || (c > 'Z' && c < 'a') || c > 'z')
    if (c == EOF)
      return 0; // s-a tastat EOF

/* se citeste cuvantul si se pastreaza in t */
  i = 0;
  do {
    t[i++] = c;
  } while ((c=getchar()) >= 'A' && c<='Z' || c>='a' && c<='z');

  if (c == EOF)
    return 0;
  t[i++] = '\0';

/* se pastreaza cuvantul in memoria heap */
  if ((p = (char *)malloc(i)) == 0) {
    printf("memorie insuficienta\n");
    exit(1);
  }
  strcpy(p, t);
  return p;
}

2. Sa se scrie o functie care citeste cuvintele dintr-un text si determina numarul de aparitii al fiecarui cuvant din textul respectiv.

Aceasta problema poate fi rezolvata in mai multe moduri. Mai jos este prezentata o metoda simpla, care nu este si eficienta. Metode mai eficiente vor fi prezentate in alte capitole.

Inainte de toate, sa observam ca problema se poate rezolva folosind un tablou de elemente spre char, daca putem indica o valoare maxima pentru numarul de cuvinte diferite din text. In acest caz se defineste tabloul:

char *tp[maxcuv];

si un indice itp care are ca valoare indicele primului element liber din tablou.

De asemenea, vom utiliza un tablou pentru a numara aparitiile fiecarui cuvant:

int nc[maxcuv];

Procesul de calcul se desfasoara astfel:

1. itp = 0;

2. se apeleaza functia citcuv pentru a citi cuvantul curent: p = citcuv();. Daca p = 0;, s-a intalnit EOF si procesul de calcul se intrerupe. Altfel, se trece la pasul urmator.

3. Se stabileste daca cuvantul citit (spre care pointeaza p) a fost deja intalnit in text. In acest scop se compara cuvintele spre care pointeaza elementele: tp[0], tp[1], ..., tp[itp-1] cu cel spre care pointeazaa p. In caz afirmativ, se trece la pasul 4, altfel la pasul 5.

4. Daca cuvantul spre care pointeaza p coincide cu cel spre care pointeaza tp[j], atunci se incrementeaza nc[j] (numarul de aparitii al cuvantului respectiv); apoi se elimina cuvantul, citit la pasul 2, din memoria heap si procesul se reia de la pasul 2.

5. Deoarece cuvantul spre care pointeaza p nu a fost inca intalnit in textul de intrare, pointerul p se pastreaza si numarul de aparitii al cuvantului respectiv se face egal cu 1:

tp[itp] = p;
nc[itp] = 1;

apoi se mareste itp cu o unitate:

itp = itp + 1;

procesul de calcul se reia de la pasul 2.
Functia utilizeaza un tablou de structuri de tipul T declarat astfel:

typedef struct {
    char *tp;
    int nc;
} T;

Ea are un parametru care este un tablou de tipul T. Un alt parametru al ei este maxcuv. Functia returneaza numarul cuvintelor distincte citite (itp).

FUNCTIA117B.C - Frecventa unui cuvant intr-un text

int frecvcuv(T t[], int maxcuv)
/* - citeste un text si determina frecventa de aparitie a fiecarui cuvant citit;
   - se admit cel mult maxcuv diferite;
   - functia returneaza numarul cuvintelor distincte intalnite in text */
{
  char *p;
  int itp;
  int i;  

  for (itp = 0; itp < maxcuv; ) {
/* citeste cuvantul curent */
    if((p = citcuv()) == 0)
/* s-a intalnit EOF */
      return itp;
/* se stabileste daca cuvantul citit a fost deja intalnit */
  for (i=0; i < itp; i++)
    if (strcmp(t[i].tp, p) == 0)
      break;
    if (i < itp) {
/* cuvant deja intalnit */
      t[i].nc++;
      free(p);
    }
    else { /* cuvant nou */
      t[itp].tp = p;
      t[itp++].nc = 1;
    }
  }
  return itp;
}

3. Sa se scrie un program care afiseaza frecventa de aparitie a cuvintelor unui text.

Programul 117 - Frecventa cuvintelor intr-un text

// testat cu compilatorul gcc
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

typedef struct {
    char *tp;
    int nc;
} T;

#include "FUNCTIA117A.C"
#include "FUNCTIA117B.C"

#define MAXCUV 100

int main () {
  T tab[MAXCUV];
  int ncuv, i;

  ncuv = frecvcuv(tab, MAXCUV);
  for (i=0; i < ncuv; i++) {
    printf("%s\t%d\n", tab[i].tp, tab[i].nc);
    if ((i+1) == 0) {
      printf ("actionati o tasta pentru a continua\n");
      getch();
    }
  }
}

4. Sa se modifice functia frecvcuv definita la Exercitiul 3, in asa fel incat in loc de tabloul de tip T sa se utilizeze date de tip recursiv.

In acest caz vom folosi tipul recursiv:

typedef struct tr{
    char *tp;
    int nc;
    struct *tr urm;
} TR;

Pentru fiecare cuvant se va pastra, in memoria heap, o data de tip TR. Pointerului urm i se atribuie adresa de inceput a zonei din memoria heap in care se pastreaza cuvantul urmator citit din textul de la intrare. El are valoarea 0 pentru data corespunzatoare ultimului cuvant citit.

Pentru a gestiona simplu datele pastrate in memoria heap, va fi util sa existe doua variabile de tip pointer spre TR, una sa pointeze spre prima data pastrata in memoria heap, iar cealalta spre ultima. Vom numi prim si ultim aceste variabile.

Functia realizeaza pasii de mai jos:

1. prim = ultim = 0

2. Se apeleaza functia citcuv pentru a citi cuvantul curent: p = citcuv();
Daca p = 0, atunci se revine din functie cu valoarea variabilei prim, altfel se trece la pasul urmator.

3. Se stabileste daca cuvantul citit (spre care pointeaza p) a fost deja intalnit in text. I acest scop, se compara cuvintele spre care pointeaza pointerul tp din datele de tip TR pastrate in memoria heap cu cel spre care pointeaza p. In caz afirmativ se incrementeaza numaratorul cuvantului respectiv, se elibereaza zona ocupata de cuvantul curent citit si procesul se reia de la pasul 2.
Astfel, se rezerva o zona pentru o data de tip TR; fie q adresa ei de inceput.
Pointerului urm, corespunzator ultimei date de tip TR pastrate in memoria heap, i se atribuie valoarea lui q.
Apoi nc = 1 si urm = 0 pentru data spre care pointeaza q.
Cum aceasta devine ultima data pastrata in memoria heap, se face ultim = q si apoi se revine la pasul 2.

FUNCTIA118.C - Frecventa unui cuvant intr-un text (date recursive)

TR *pfrecvcuv()
/* - citeste un text si pastreaza in memoria heap date de tip TR
pentru cuvintele distincte din text, determina frecventa acestora 
si returneaza pointerul spre data corespunzatoare primului cuvant din text */
{
  TR *prim, *ultim, *q;
  char *p; 

  prim = ultim = 0;
  for ( ; ; ) {
/* citeste cuvantul curent */
    if((p = citcuv()) == 0)
/* s-a intalnit EOF */
      return prim;
/* se stabileste daca cuvantul citit a fost deja intalnit */
    q = prim; /* cautarea se face incepand cu primul cuvant */
    while (q) { /* daca q!=0 inseamna ca pointeaza spre o data din heap */
      if (strcmp(q->tp, p) == 0)
        break; /* cuvantul a mai fost intalnit in text */
/* - se trece la data corespunzatoare cuvantului urmator citit din textul de intrare;
   - adresa acestei date este valoarea pointerului urm al datei spre care pointeaza q; 
   - aceasta se poate exprima cu ajutorul expresiei: 
      q->urm;
   - aceasta adresa se atribuie lui q si in felul acesta se poate relua ciclul */
      q = q->urm;
    }
    if (q) { /* daca q!=0, cuvantul a mai fost intalnit in textul de intrare */
      q -> nc++; /* se incrementeaza numarul de aparitii al cuvantului */
      free(p); /* se elibereaza zona ocupata de cuvant */ 
    }
    else { /* cuvantul este nou */
/* se rezerva zona pentru o data de tip TR */
      q = (TR *)malloc(sizeof(TR));
      if (q == 0) { /* nu se poate aloca memoria heap */
        printf("memorie insuficienta\n");
        exit(1);
      }
/* se pastreaza pointerul spre cuvantul nou */
      q -> tp = p;
/* nc = 1 */
      q -> nc = 1;
      if (ultim) /* daca ultim!=0, cuvantul curent nu este primul cuvant citit */;
/* ultim pointeaza spre data din memoria heap corespunzatoare cuvantului
precedent pastrat, deci ultim -> urm = q */
        ultim -> urm = q;
/* - q->urm = 0, deoarece data spre care pointeaza q corespunde ultimului cuvant citit 
si pastrat in memoria heap;
   - din aceleasi motive, ultim = q */
      q -> urm = 0;
      ultim = q;
      if (prim == 0) /* cuvantul curent este primul cuvant citit */
		  prim = q;
    } /* sfarsit else */
  } /* sfarsit for */
}

4. Sa se scrie un program care citeste si afiseaza frecventa de aparitie a cuvintelor din textul citit, folosind functia pfrecvcuv definita in exercitiul precedent.

In programul de fata nu mai este necesar sa ne limitam la 100 de cuvinte ca la Exercitiul 3. Datele se pastreaza in memoria heap pe masura ce este nevoie de ele.

Programul 118 - Frecventa cuvintelor intr-un text (cu date recursive)

// eroare cu compilatorul gcc
// Functia118.C are nevoie de debugging
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

typedef struct tr{
    char *tp;
    int nc;
    struct tr *urm;
} TR;

#include "FUNCTIA117A.C"
#include "FUNCTIA118.C"

int main () {
  TR *p;
  int i;

  p = pfrecvcuv();
  i = 1;
  
  while (p) {
    printf("%s\t%d\n", p->tp, p->nc)
    if (i%23 == 0) {
      printf("actionati o tasta pentru a continua\n");
      getch();
    }	
    i++;
    p = p->urm;
  }
}

Observatie:

Datele de tip TR, pastrate in memoria heap, sunt structuri recursive care formeaza o multime ordonata. Exista o prima structura si fiecare structura are un element urmator, exceptand ultima. De aceea, intre elementele acestei multimi de structuri este stabilita o relatie de ordine. Relatia respectiva se defineste printr-un pointer care este componenta a tipului comun al acestor structuri.

O astfel de multime se spune ca formeaza o lista simplu inlantuita.

11. Liste