Programarea Calculatoarelor, seria CC

Laborator 10

Structuri, uniuni, enumerări. Pointeri la funcții. Directive de preprocesare. Operatori pe biți

În acest laborator veţi învăţa să:


Structuri ( Recapitulare )

Definirea unei structuri:

struct A {
    int a, b, c;
}; // se va folosi: "struct A x" pentru a declara o variabila de acest tip

typedef struct A B; // asa se poate folosi "B x"

// intr-un singur pas:
typedef struct C {
    int x, y;
} C;

Membrii unei structuri se accesează folosind .. Pentru pointerii la structuri, se poate folosi mai întai * pentru a accesa structura și apoi . sau folosind direct ->. Exemplu:
 1 #include <stdio.h>
 2
 3 typedef struct {
 4     int x, y, z;
 5 } POINT;
 6
 7 int main()
 8 {
 9     POINT p, *pp;
10     pp = &p; // pp va fi un pointer catre p
11     p.x = 1;
12     (*pp).y = 2;
13     pp->z = 3;
14     printf("%d %d %d\n", pp->x, p.y, p.z);
15     return 0;
16 }

Uniuni

Uniunile permit accesarea aceleiași zone din memorie ca fiind de mai multe tipuri de date. Toate elementele declarate într-o uniune ocupă aceeași zonă de memorie, dimensiunea ei fiind maximul dintre dimensiunile membrilor. Declararea unei uniuni are aceeași sintaxă cu declararea unei structuri.
Exemplu:

union number {
    long int l;
    struct {
        short int lo;
        short int hi;
    }
}; // permite accesarea acelorasi 4 bytes fie ca un intreg lung, fie ca 2 short int, prin obtinerea celor 2 jumatati componente

Un exemplu de folosire a uniunilor se gasește mai jos:

 1 #include <stdio.h>
 2
 3 int main()
 4 {
 5     union data
 6     {
 7         char a;
 8         int x;
 9         float f;
10     } myData;
11
12     myData.a = 'A';
13     printf("Here is the Data:\n%c\n%i\n%.3f\n", myData.a, myData.x, myData.f );
14
15     myData.x = 42;
16     printf("Here is the Data:\n%c\n%i\n%.3f\n", myData.a, myData.x, myData.f );
17
18     myData.f = 101.357;
19     printf("Here is the Data:\n%c\n%i\n%.3f\n", myData.a, myData.x, myData.f );
20
21     return 0;
22 }

Enumerări

Folosite pentru a da nume simbolice. Sintaxa:

enum nume_enumeratie { val1, val2, val3, ... };

Exemplu:
 1 #include <stdio.h>
 2
 3 int main()
 4 {
 5     int a, b, rez;
 6     enum operatii { adunare, scadere, inmultire } op;
 7     scanf("%d%d%d", &a, &b, &op);
 8     switch (op) {
 9         case adunare: rez = a + b; break;
10         case scadere: rez = a - b; break;
11         case inmultire: rez = a * b; break;
12     }
13     printf("%d\n", rez);
14     return 0;
15 }

Pointeri la funcții

Declararea unei variabile de tip pointer la funcție are următoarea sintaxă: tip_returnat (*nume_pointer) (lista_argumente).
Exemplu de utilizare:

 1 #include <stdio.h>;
 2
 3 int cmp_cresc ( const int x, const int y )
 4 {
 5     if ( x == y )
 6         return 0;
 7     return x > y ? 1 : -1;
 8 }
 9
10 int cmp_desc ( const int x, const int y )
11 {
12     if ( x == y )
13         return 0;
14     return x > y ? -1 : 1;
15 }
16
17 void swap ( int *x, int *y)
18 {
19     int aux;
20     aux = *x;
21     *x = *y;
22     *y = aux;
23 }
24
25 void sort(int v[], int n, int (*cmp) ( const int x, const int y) )
26 {
27     int i, j;
28     for ( i = 0; i < n - 1; i++ )
29         for ( j = i + 1; j < n; j++ )
30             if ( cmp ( v[i], v[j] ) == 1 )
31                 swap( &v[i], &v[j] );
32 }
33
34 int main()
35 {
36     int v[100], n, ord;
37     int (*cmps[2]) ( const int, const int ) = { cmp_cresc, cmp_desc };
38     // citire n si vector ...
39     printf("Alegeti tipul de sortare: 0 - crescator; 1 - descrescator.\n");
40     scanf("%d", &ord);
41     sort(v, n, cmps[ord]);
42     // afisare vector sortat ...
43     return 0;
44 }

Directive de preprocesare

Sunt precedate întotdeauna de # și se termină la sfârșitul liniei. Pentru a extinde o directivă și pe linia următoare se folosește \. Preprocesarea se execută înainte de compilarea efectivă a programului.

Exemple directive de preprocesare: #define, #include, #if, #ifdef, #else, #line, #error

Exemple macrodefiniții (#define):

 1 #include <stdio.h>
 2
 3 #define NMAX 100 
 4 #define MAX(a,b) ((a) > (b) ? (a) : (b))
 5
 6 int main()
 7 {
 8     int v[NMAX], n, i, maxim;
 9     printf("n = ");
10     scanf("%d", &n);
11     for (i = 0; i < n; i++)
12     scanf("%d", (v+i));
13
14     maxim = v[0];
15     for (i = 1 ; i < n ; i++)
16         maxim = MAX(maxim, v[i]);
17     
18     printf("%d\n", maxim);
19     return 0;    
20 }

Operatori pe biți

  • & - și
    Ex.: 11001100 & 10101010 = 10001000
  • | - sau
    Ex.: 11001100 | 10101010 = 11101110
  • ^ - sau exclusiv
    Ex.: 11001100 ^ 10101010 = 01100110
  • ~ - complement
    Ex.: ~11001100 = 00110011
  • << - deplasare la stânga (înmultire cu 2)
    Ex.: 0000100 << 2 = 0010000
  • >> - deplasare la dreapta (împărțire la 2)
    Ex.: 00001000 >> 2 = 00000010

Un exemplu de utilizare a operațiilor pe biți pentru diverse funcționalități:

 1 #include <stdio.h>
 2
 3 /* Functie care intoarce 1 daca X este o putere a lui 2 */
 4 int power_of_two(int X)
 5 {
 6     if (!X) return 0;
 7     return !(X & (X-1));
 8 }
 9
10 /* Functie care intoarce numarul de biti de 1 din reprezentarea
11    binara a lui X. ( "parcurgand" toti bitii si facand testul )
12 */
13 int count_bits(int X)
14 {
15      int i;
16      int nrbiti = 0;
17      for (i = 0; i < 32; i++)
18          if ( (1<<i) & X ) nrbiti++;
19
20      return nrbiti;
21 }
22
23 /* Functie care intoarce numarul de biti de 1 din reprezentarea
24    binara a lui X. ( "parcurgand" doar bitii de '1' )
25 */
26
27 int count_bits2(int X)
28 {
29     int nrbiti = 0;
30     while (X)
31     {
32         X = X & (X-1);
33         nrbiti++;
34     }
35     return nrbiti;
36 }
37
38 int main()
39 {
40     int N;
41     printf("N = ");
42     scanf("%d", &N);
43
44     printf("%d %s o putere a lui 2.\n", N, power_of_two(N) ? "este": "NU este" );
45     printf("%d are %d bit(i) de 1 în reprezentarea sa binară.\n", N, count_bits(N));
46     printf("%d are %d bit(i) de 1 în reprezentarea sa binară.\n", N, count_bits2(N));
47
48     return 0;
49 }

[Tips & Tricks]:

  • Există vreo metodă care calculează mai rapid numărul de biți de 1 dintr-un întreg ? (întrebare interviu - nVidia [2008, 2009])
  • Se poate găsi o metodă de interschimbare a două valori fără o funcție de swap definită în prealabil ? (pentru exemplul de la pointeri la funcții !)

Problema 1.

A.

Fie tipul struct multime:

struct multime {
    unsigned char a;
};
ce poate reprezenta mulțimi cu numere din intervalul [0..7] astfel: bitul i din a este 1 dacă numărul face parte din mulțime și 0 altfel. Considerăm biții numerotați de la dreapta spre stânga.

De exemplu, dacă a = 99 = (01100011)2 atunci mulțimea va fi {0, 1, 5, 6}.

Să se scrie următoarele funcții (0 <= x <= 7):
  • void init(struct multime *m) - inițializează mulțimea m cu mulțimea vidă
  • void add(struct multime *m, int x) - adaugă pe x la mulțimea m
  • void del(struct multime *m, int x) - șterge pe x din mulțimea m
  • void print(struct multime *m) - afișează mulțimea m
  • int contains(struct multime *m, int x) - returnează 1 dacă x se află în mulțimea m și 0 altfel
Să se scrie un program ce testează funcțiile definite mai sus.

B.

Să se modifice structura și funcțiile definite anterior pentru a putea reprezenta mulțimi de numere întregi, din intervalul [0, n], n întreg.

Se va folosi un vector de unsigned char, fiecare reprezentând câte 8 numere din mulțime: v[0] - [0..7], v[1] - [8..15] etc. Va trebui să modificați struct multime astfel încât să se poată aloca dinamic memorie pentru vector, de exemplu:

struct multime {
    unsigned int n; // numărul maxim de elemente
    unsigned char *a;
};

Problema 2.

Să se scrie o funcție pentru calculul integralei definite, pe un interval dat [a,b] a unei funcții oarecare (cu rezultat real) f(x), prin metoda trapezelor, cu un număr dat de pași n.

Funcția primește ca argument adresa funcției de integrat și numărul de pași și va avea antetul double integrala( double (*func) (double x), double a, double b, int n );.

Programul principal va apela funcția de calcul a integralei pentru două funcții diferite și un n suficient de mare. Se pot integra functiile sin(x) si cos(x) pe intervalul [0, PI].

Problema 3.

Să se definească tipul structură MATERIA care conține cămpurile:

  • nume - șir de 15 caractere
  • ore_curs - intreg
  • tip_examen - tip enumerare, putând avea valorile C, S, A (colocviu, examen de semestru sau de an)
Scrieți funcția citire_MAT, care citește informațiile despre o variabilă de tip MATERIA.

Se va face validarea tuturor câmpurilor:
  • nume - conține doar litere sau blancuri
  • ore_curs - întreg strict pozitiv
  • tip_examen - doar unul din caracterele de mai sus
Definiți tabloul PROGRAMA de MAX elemente de tip MATERIA, MAX fiind o constantă predefinită.

Scrieți funcția citire_PROGRAMA, de tip void, care inițializează tabloul PROGRAMA, prin apelul funcției citire_MAT.

Scrieți funcția afișare care primește ca parametru un caracter, un întreg și tabloul PROGRAMA și tipărește informațiile despre materiile din PROGRAMA care au tip_examen corespunzător caracterului și ore_curs egal cu întregul primit.

Scrieți un program care apelează funcțiile de mai sus.

Problema 4.

Să se definească o structură MATRICE care să conţină următorii membrii:

  • n - numărul de linii (int)
  • m - numărul de coloane (int)
  • a - adresa tabloului care va contine matricea (int**)
Se vor scrie următoarele funcţii:
  • MATRICE* creaza_MATRICE(int n, int m) - crează o matrice de dimensiuni n x m. Funcţia va aloca memorie pentru o nouă variabilă de tip MATRICE şi pentru tabloul conţinut în această structură (referit prin membrul a). Funcţia va returna adresa noii variabile de tip MATRICE create.
  • MATRICE* citeste_MATRICE(MATRICE* a) - citeşte de la tastatură o matrice. Dimensiunile se regăsesc în cadrul matricei transmise ca parametru, urmând a se citi de la tastatură doar elementele tabloului. Funcţia va returna tot adresa a.
  • void scrie_MATRICE(MATRICE* a) - afiseaza pe ecran matricea transmisă ca parametru.
  • MATRICE* aduna_MATRICE(MATRICE* a, MATRICE* b) - dacă matricile a şi b au aceleaşi dimensiuni, atunci funcţia returnează adresa unei noi matrici care va conţine suma matricelor a şi b. În caz contrar, funcţia va returna NULL (adunarea nu se poate face, deci rezultatul nu există).
  • MATRICE* inmulteste_MATRICE(MATRICE* a, MATRICE* b) - dacă matricile a şi b se pot înmulţi, atunci funcţia returnează adresa unei noi matrici care va conţine produsul matricelor a şi b. În caz contrar, funcţia va returna NULL (înmulţirea nu se poate face, deci rezultatul nu există).