Programarea calculatoarelor 2 - Laborator 7

Indicaţii: Exemple sunt funcţiile de bibliotecă bsearch si qsort (pentru care se solicită implementarea de variante în primele două probleme). Pentru a funcţiona, acestea au nevoie de:

• adresa tabloului de prelucrat -- un pointer void *, deoarece aceste functii generice trebuie să funcţioneze pentru tablouri cu tip arbitrar de elemente (necunoscut la compilarea funcţiei)
• numărul de elemente din tablou -- necesar deoarece prin transmiterea doar a adresei tabloului (un pointer) funcţia nu primeşte nici un fel de informaţii despre câte elemente urmează la acea adresă
• dimensiunea unui element de tablou -- necesar deoarece tipul adresei transmise (void *) nu poartă nici un fel de informaţii privind dimensiunea unui element (spre deosebite de un pointer la un tip definit: char *, double *, etc.)
• un pointer la o funcţie care prelucrează unul sau mai multe elemente de tablou. Pentru a putea scrie un tip generic de (pointer la) funcţie, informaţia transmisă despre elementele de prelucrat e de asemenea adresa lor, tot ca tip de pointer neprecizat, void *. O instanţiere a unei astfel de funcţii, scrisă de un programator care vrea să folosească prelucrarea pentru un anumit tip de tablou, poate fi scrisă în două variante:
  • conform tipului declarat pentru parametrul pointer la funcţie. De exemplu, funcţia qsort cere un parametru int(*compar)(const void *, const void *). Pentru a sorta tabloul de întregi int t[20]; scriem funcţia

    int intcmp1(const void *p, const void *q) { return *(int *)p - *(int *)q; }
    

    Deoarece intenţionăm să o folosim în sortarea unui tablou de întregi, ştim că într-un apel, cei doi pointeri daţi ca argumente de implementarea funcţiei qsort vor fi de fapt pointeri la întregi, şi îi folosim ca atare, dereferenţiindu-i cu operatorul * doar după ce au fost convertiţi la tipul int *. (Dereferenţierea directă a unui void * nu este permisă deoarece nu ştim spre ce tip indică el de fapt). Putem atunci apela
    qsort(t, 20, sizeof(int), intcmp1);
  • scriind direct funcţia pentru tipul de parametri intenţionat:

    int intcmp2(const int *p, const int *q) { return *p - *q; }
    

    Putem folosi pointerii direct, fără a mai fi necesară conversia de tip. Dar tipul funcţiei (mai precis, al argumentelor ei) nu mai corespunde exact cu cel cerut de qsort. Deci trebuie convertit pointerul intcmp2 la apel:
    qsort(t, 20, sizeof(int), (int (*)(const void*, const void*))intcmp2);
    Poate fi mai lizibil sa definim un tip pentru pointerul de funcţie cerut de qsort:
    typedef int (*compar_t)(const void *, const void *); şi putem apela atunci:
    qsort(t, 20, sizeof(int), (compar_t)intcmp2);

În implementarea unor astfel de funcţii e necesară determinarea adresei unui element de tablou, calculând deplasamentul în octeţi faţă de adresa de început a tabloului. Putem aduna un număr de octeţi la un pointer forţându-l întâi la tipul char *, şi ştiind că adunarea cu un întreg are efectul deplasării adresei cu numărul indicat de obiecte, iar dimensiunea unui char e tocmai un octet.

Problema 1: Scrieţi o funcţie care efectuează căutarea binară a unei valori într-un tablou ordonat crescător. Funcţia va returna adresa din tablou a elementului găsit, sau NULL dacă acesta nu există. Unul din parametrii va fi un pointer la o funcţie care ia ca parametri doi pointeri la elemente de tablou şi returnează rezultatul comparaţiei între cele două elemente.
Testaţi funcţia căutând un număr real citit de la intrare într-un tablou de reali daţi ca argumente pe linia de comandă.
Obs: Prin căutare binară se înţelege o cautare cu înjumătăţirea intervalului în funcţie de comparaţia cu valoarea de la mijlocul acestuia (vezi exemplul de la cursul 1).

Problema 2: Scrieţi o funcţie care sortează un tablou. Unul din parametrii va fi un pointer la o funcţie care ia ca parametri doi pointeri la elemente de tablou şi returnează rezultatul comparaţiei între cele două elemente.
Testaţi funcţia sortând crescător şirul realilor daţi ca argumente pe linia de comandă a programului.

Problema 3: Scrieţi o funcţie care prelucrează succesiv toate elementele unui tablou. Funcţia va lua ca argumente adresa tabloului, numărul de elemente, un şir de max. 2 caractere care indică tipul elementelor de tablou, după convenţiile folosite la intrarea/ieşirea formatată (c, d, hd, ld, u, hu, lu, f, lf) şi un pointer la o funcţie care efectuează prelucrarea unui element de tablou, indicat prin adresa sa.
Testaţi funcţia citind de la intrare şi apoi tipărind un tablou. Numărul de elemente din tablou şi tipul lor se solicită de la intrare.