Structuri de Date (1CC)

L A B O R A T O R 3b

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 structuri "cell" realizata ca lista inlantuita cu santinela 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 x; initS (s); for (int i=1;i