Structuri de Date (1CC)

L A B O R A T O R 3a

Stive si cozi ca liste inlantuite

1. Functia recursiva urmatoare realizeaza umplerea prin inundare a unei suprafete dreptunghiulare "a". Matricea de caractere (a) si dimensiunea ei (n)sunt definite ca variabile externe. Functia "inside" verifica daca un punct de coordonate (r,c) este in interiorul conturului (in matrice).

// daca punctul (r,c) este in interiorul ariei [0,n-1,0,n-1]int inside (int r,int c) { if ( r=n || c=n ) return 0; else return 1 ;} // umplere recursivavoid fill (int r,int c) { if (inside(r,c)&& a[r][c]==0) { // daca (r,c) interior si necolorat a[r][c]=u++; // atunci coloreaza (r,c) fill (r,c-1); // continua la stanga fill (r-1,c); // in sus fill (r,c+1); // la dreapta fill (r+1,c); // in jos }}

Sa se scrie:- Functia "show", care afiseaza continutul matricei. - O functie "main" care apeleaza functia "fill" cu un punct interior (2,2) si apoiapeleaza functia "show". Variabile externe functiilor: int n=5; char a[5][5]={0}; char u='a';Sa se observe ordinea de umplere (de modificare a elementelor din matrice) dupasecventa de litere a,b,c,... din matrice. Se va afisa numarul total de apeluri ale functiei "fill" folosind o variabilaexterna incrementata la inceputul functiei "fill" si afisata in "main".

2. Sa se modifice dimensiunile matricei la [400,400] si sa se mareascavaloarea lui n (incepand de la 200) pana cand functia "fill" se blocheaza inainte de umplerea completa datorita depasirii stivei folosite de compilator.

3. Sa se scrie functii pentru operatii cu o stiva de pointeri void* realizata ca lista inlantuita si sa se verifice aceste functii cu programul urmator:

typedef struct { int r,c;} cell; // celula din linia r si coloana cint main () { Stack s; cell * p; initS (s); for (int i=1;ir=p->c=i; push (s, p); } while ( ! emptyS(s)){ p=(cell*) pop(s); printf("%d,%d\n",p->r,p->c); } system("pause");}

4. Functia urmatoare realizeaza umplerea prin inundare a unei suprafetedreptunghiulare folosind o stiva de pointeri la structuri "cell".

void fillS (int r, int c) {// (r,c) = punct initial int k,rv,cv; // (rv,cv)= punct vecin cu (r,c) cell* p, *pv;// adrese de puncte (r,c) Stack s; int dr[4] = {-1,0,1,0}; // pas de modificare nr linie int dc[4] = {0,1,0,-1}; // pas de modificare nr coloana initS(s); p= new cell;// creare element "cell" p->r=r; p->c=c; // pune punctul initial (r,c) in coada push(s,p); while ( ! emptyS(s) ) { // repeta cat timp e ceva in coada p= (cell*)pop(s); // scoate un punct din coada r=p->r; c=p->c; // r,c =coordonate punct curent if ( inside (r,c) && a[r][c]==0){ // daca (r,c) este interior si necolorat a[r][c]=u++; // umplere punct (r,c) cu un caracter for (k=0;kr=rv; pv->c= cv; // punct vecin pe una din directii push (s,pv); // pune adresa punct vecin in coada } } }}

Sa se verifice folosind functia "main" de la pct.1 si sa se observe ordineade umplere (de modificare a elementelor matricei). Sa se verifice daca functia "fillS" functioneaza si peste limitele la care functia recursiva "fill" se bloca datorita umplerii stivei.

5. Sa se scrie si sa se verifice functii pentru operatii cu o coada realizataca lista inlantuita :

initQ // initializare coada vida emptyQ // test de coada goala addQ // adaugare pointer x la coada q delQ // extrage si elimina pointer din coada q

Verificarea functiilor se va face cu programul de la pct 3, inlocuind stiva cu ocoada.

6. Sa se copieze functia "fillS" intr-o functie "fillQ" si sa se inlocuiascaoperatiile cu stiva cu operatii asupra unei cozi. Sa se verifice folosind functia "main" de la pct.1 si sa se observe ordineade umplere (de modificare a elementelor matricei).