Plan

Funcţii

Definiția unei funcții

  • Apelul unei funcţii:

  • Argumentele sunt expresii ce substitue parametrii la un apel: parametrii funcţiei sunt iniţializaţi cu valorile argumentelor.

Exemplul 1:

Definim o funcție care să calculeze (returneze) pentru un număr natural n dat suma primelor n numere naturale.

Variana iterativă (repetitivă): suma: Z -> Z, suma(n)=1+2+3+…+n

int suma(int n)
{
  int s = 0;
  int i;
  for(i=1; i<=n; ++i)
    s += i;
  return s;
}

Variana recursivă: suma: Z -> Z, suma(n)=1+2+3+…+n

int suma(int n)
{
  if (n==0) 
     return 0;
  else
     return n+suma(n-1);
}

Exemplul 2 – Ce se întâmplă?

void swap(int x, int y){
   int temp = x; x = y; y = temp;
   cout << "x=" << x<< ",y=" << y<< "\n";
}

int main(void){
   int a = 2, b = 3;
   swap(a, b);   // x = 3, y = 2
   cout << "a=" << a<< ",b=" <<b <<"\n";
   // a = 2, b = 3

Exemplul 2 – Ce se întâmplă?

void swap(int& x, int& y){
   int temp = x; x = y; y = temp;
   cout << "x=" << x<< ",y=" << y<< "\n";
} 
int main(void){
   int a = 2, b = 3;
   swap(a, b);   // x = 3, y = 2
   cout << "a=" << a<< ",b=" <<b <<"\n";
   // a = 3, b = 2

Transmiterea parametrilor

Variabile globale și variabile locale

Explicații pe un exemplu, în clasă

Parametri transmiși prin valoare

Parametri transmiși prin referință

Returnarea unei valori prin parametrul transmis prin referință – „proceduri”

Returnarea unei valori cu return „prin tipul funcției”

Exemple:

  1. Scrieți o funcție care verifică dacă reprezentarea binară a unui număr x dat ca parametru este palindrom: bool isPalindrome(unsigned int x).
#include<iostream>
 using namespace std;

// Această funcție returnează true dacă al k lea bit din x este 1 (este setat).
 // De exemplu dacă number este (0010) este 2 și k este 2, atunci se returnează true
 bool isKthBitSet(unsigned int number, unsigned int k)
 {
    return (number & (1 << (k-1)))? true: false;
 }

// Această funcție returnează true dacă reprezentarea binară a lui x este
 // palindrom. De exemplu, (1000...001) este paldindrom.
 bool isPalindrome(unsigned int number)
 {
    int left = 1; // Initializează poziția din stânga.
    int right = sizeof(unsigned int)*8; // Inițializează poziția din dreapta.

    // Compară biții unul câte unul.
    while (left < right)
    {
       if (isKthBitSet(number, left) != isKthBitSet(number, right))
          return false;
       left++; right--;
    }
    return true;
 }

// Programul de test al funcției de mai sus
 int main()
 {
    unsigned int x = 1<<15 + 1<<16;
    cout << isPalindrome(x) << endl;
    x = 1<<31 + 1;
    cout << isPalindrome(x) << endl;
    return 0;
 }

2) Scrieți o funcție recursivă pentru a calcula factorialul unui număr natural n.

 

Plan

  • Tablouri unidimensionale, declarare, nume, inițializare
  • Memorarea tablourilor, folosirea lor ca argumente ale funcțiilor
  • Șiruri de caractere, macro-uri și funcții pentru șiruri
  • Tablouri bidimensionale
  • Pointeri, expresii cu pointeri, aritmetica pointerilor

Tablouri

  • Colecție de variabile de același tip, apelate cu același nume –  componentele tabloului
  • Componentele sunt identificate și accesate cu ajutorul indicilor
  • Un tablou ocupă locații de memorie contigue, în ordinea indicilor
  • Tablouri:
    • Unidimensionale (1 – dimensionale): șiruri de caractere
    • Bidimensionale (2 – dimensionale)

Tablouri unidimensionale

tip numeTablou[dimensiune];

octeți_necesari = sizeof(tip)* dimensiune

#define NMAX 25

int a[NMAX]; // int a[25];

  • Ordinea de memorare – ordinea indicilor: 0, 1, …, NMAX-1;
  • Elementele tabloului – în zone de memorie contigue (una langa alta);
  • Operaţiile se realizează prin intermediul componentelor, prin iterații for, while sau do-while:
   for (i=0; i<n; i++) a[i]=0; 
   for (i=0; i<n; i++) c[i]=a[i]+ b[i];

Numele unui tablou

  • Numele unui tablou:
    • nume de variabilă;
    • pointer către primul element din tablou:

       a       echivalent cu &a[0]      *a   echivalent cu  a[0]

       a+1 echivalent cu &a[1]       *(a+1) echivalent cu  a[1]

       a+2 echivalent cu &a[2]      *(a+2) echivalent cu  a[2]

       a+i echivalent cu &a[i]         *(a+i) echivalent cu  a[i]

Iniţializarea unui tablou unidimensional

Memorarea unui tablou

Parcurgerea unui tablou

Avem un tablou a de numere. Dorim sa calculam suma elementelor sale, dupa ce am initializat suma cu 0. Avem mai multe modalitati de a parcurge tabloul a.

Tablourile ca argumente ale funcțiilor

  • Un tablou NU poate fi transmis ÎN ÎNTREGIME ca argument al unei funcții.
  • Tablourile se transmit ca argumente folosind un pointer la un tablou.
  • Parametrul formal al unei funcții ce primește un tablou poate fi declarat ca:
    • Pointer
    • Tablou cu dimensiune
    • Tablou fără dimensiune
  • Exemplul 1
    • Sa consideram ca avem un tablou i si apelam o functie functia cu argumentul i.
    • In acest caz, functia va putea avea una din urmatoarele antete, in care argumentul poate fi: pointer la un numar intreg, un tablou cu un numar specificat de elemente intregi, un tablou cu un numar nespecificat de elemente intregi.

  • Exemplul 2
    • In acest exemplu, fimctia insert_sort are ca argument un tablou cu un numar nespecificat de elemente intregi.
    • Deoarece argumentul a[] este echivalent cu pointerul *a, functia va modifica elementele tabloului a, realizand, de pilda, sortarea prin insertie a elementelor vectorului a, avand n elemente.

  • Exemplul 3
    • In acest exemplu, presupunem ca functia suma doreste sa realizeze suma celor n elemente din tabloul a.
    • Putem avea antetul functiei in doua feluri, in care primul argument este fie a[], fie *a, deci un pointer la inceputul tabloului.
    • In primul apel, suma(v,100), functia va calcula suma celor 100 elemente din tablou, incepand cu elementul de pe pozitia 0 (si terminand cu elementul de pe pozitia 99).
    • In al doilea apel, suma(v,8), se va calcula suma v[0]+v[1]+…+v[7].
    • In al treilea apel, primul argument este adresa elementului de pe pozitia 4 din tablou, deci suma care va fi calculata va fi v[4]+v[5]+… + v[k-6-1+4] (total k-6 elemente).
    • In al patrulea apela, primul argument (v+4) este echivalent cu argumentul &v[4], reprezentand faptul ca se calculeaza tot v[4]+v[5]+… .

Șiruri de caractere

  • Sirurile de caractere sunt tablouri unidimensionale de tip char.
    • Fiecare element al tabloului este un caracter.
    • Ultimul caracter al șirului este caracterul nul ‘\0’. Acesta marchează sfârșitul șirului.
  • Exemplu:
    • char sir[10];
    • Aceasta este o declaratie pentru un șir de 9 caractere (sir[0], sir[1]…, sir[8]), la care se adaugă sir[9], ce va marca sfarsitul sirului.
    • Al 10-lea caracter va fi caracterul nul ‘\0’ (sau NULL sau 0).

Declarare şiruri

Declarare șiruri cu inițializare

Asignare și comparare la șiruri de caractere

  • Asignarea “=” doar la declarare:
    char sir[10];
    sir = "Hello";// gresit
    char sir[10] = "Hello";// OK
  • Compararea nu e posibilă prin operatorul “==”
    char sir_unu[10] = "alba";
    char sir_doi[10] = "neagra";
    sir_unu == sir_doi;   // warning: operator has no effect
  • Se folosește o funcție strcmp
    strcmp(s,t) va returna 0, daca s si t sunt identice, un numar <0, daca s este lexicografic inaintea lui t, respectiv un numar >0, daca s este lexicografic dupa t.

Macrouri şi funcţii pentru şiruri

Tablouri bidimensionale

tip numeTablou[m][n];
int a[m][n];
  • Memorie contiguă de m×n locaţii
  • Componentele sunt identificate prin 2 indici:
    • Primul indice are valori {0, 1, …, m -1}
    • Al doilea indice are valori {0, 1, …, n -1}
    • Variabilele componente : a[0][0], a[0][1], …, a[0][n-1], a[1][0], a[1][1], …, a[1][n-1], …, a[m-1][0], a[m-1][1], …, a[m-1][n-1]
  • Ordinea de memorare a componentelor este dată de ordinea lexicografică a indicilor

  • In figura de mai sus, a este de tip int[2][3], a[0] este de tip int[3], a[1] este de tip int[3], iar fiecare element din matrice este de tip int.

Parcurgerea unui tablou bidimensional

double a[MMAX][NMAX]; // declarare tablou bidim. 

double suma;  // suma elementelor din tablou 

/* . . . */

for (i = 0; i < m; i++)
    for (j = 0; j < n; j++)
        cin >> a[i][j];

suma = 0;
for (i = 0; i < m; i++)
    for (j = 0; j < n; j++)
         suma += a[i][j];

Tablouri bidimensionale

  • Cu analogia de la matrice, un tablou 2-dimensional poate fi privit ca un tablou 1-dimensional în care fiecare componentă este un tablou 1-dimensional.
  • Notaţie:
a[0][0], a[0][1], …, a[0][n-1],…, a[m-1][0], a[m-1][1],…, a[m-1][n-1]

Tablouri bidimensionale văzute ca tablouri uni-dimensionale

Accesarea elementelor unui tablou bidimensional 

 

Expresii echivalente cu a[i][j]

Tablouri bidimensionale ca argumente

int minmax(int t[][NMAX], int i0, int j0,
        int m, int n)
{
  //...
}

/* utilizare */
if (minmax(a,i,j,m,n))
{
   // ... 
}

Iniţializarea tablourilor (vectori, siruri, matrice)

int a[] = {-1, 0, 4, 7};
/* echivalent cu */
int a[4] = {-1, 0, 4, 7};
char s[] = "un sir";         /* echivalent cu */
char s[7] = {'u', 'n', ' ', 's', 'i', 'r', '\0'};
int b[2][3] = {1,2,3,4,5,6}  /* echivalent cu */
int b[2][3] = {{1,2,3},{4,5,6}} /*echivalent cu*/
int b[][3] = {{1,2,3},{4,5,6}}

Pointeri

  1. Pointer = variabilă care conține o adresă din memorie, adresă care este localizarea unui obiect (de obicei altă variabilă)
  2. Oferă posibilitatea modificării argumentelor de apelare a funcțiilor
  3. Permit alocarea dinamică
  4. Pot îmbunătăți eficiența unor rutine
  5. Pointeri neinițializați
  6. Pointeri ce conțin valori inadecvate

Declararea unei variabile pointer:

tip *nume_pointer;

  • nume_pointer este o variabilă ce poate avea valori adrese din memorie ce conţin valori cu tipul de bază tip.
  • Exemple:
int *p, i;  // int *p; int i;
p = 0;
p = NULL;
p = &i;
p = (int*) 232;

Semnificația lui p = &i;

  • p “pointează la i”, “conţine / primește adresa lui i”, “referenţiază la i”.

Operatorul de dereferenţiere (indirectare) * :       int *p;

  • p este pointer, *p este / primește valoarea variabilei ce are adresa p

Valoarea directă a lui p este adresa unei locaţii iar *p este valoarea indirectă a lui p: ceea ce este memorat în locaţia respectivă

int a = 1, *p;

p = &a;

  • pentru că memorează adrese, lungimile locaţiilor de memorie nu depind de tipul variabilei asociate

sizeof(int*) = sizeof(double*) = …

  • afişarea unui pointer:


Expresii cu pointeri
 

#include <iostream>
using namespace std;
int main(void){
    int i=5, *p = &i;
    float *q;
    void *v;
    q = (float*)p;
    v = q;
    cout << "p = " << p << ", *p = " << *p << "\n";
    cout << "q = " << q << ", *q = " << *q << "\n";
    cout << "v = " << v << ", *v = " << *((float*)v)<<"\n";
    return 0;
}

Aritmetica pointerilor

Video de prezentare a legăturii dintre pointeri și tablouri

https://youtu.be/ASVB8KAFypk

https://youtu.be/ASVB8KAFypk