In acest capitol sint descrise functii care rezolva probleme legate de alocarea dinamica a memoriei, sortare si cautare, clasificare, operatii cu blocuri de memorie si siruri de caractere, functii matematice.

12.1. Alocarea dinamica a memoriei

Nume calloc, malloc, realloc - aloca memoria in mod dinamic free - elibereaza memoria alocata in mod dinamic

Declaratie s9b18bh
#include <stdlib.h> void *calloc(unsigned nel, unsigned size); void *malloc(unsigned size); void *realloc(void *ptr, unsigned size); void free(void *ptr);

Descriere
Functia calloc aloca memorie pentru un tablou de nel elemente, fiecare de marime size octeti si returneaza un pointer la memoria alocata. Continutul memoriei este pus la zero.
Functia malloc aloca size octeti si returneaza un pointer la memoria alocata. Continutul memoriei nu este sters.
Functia free elibereaza spatiul de memorie indicat de ptr, care trebuie sa fi fost returnat de un apel anterior malloc, calloc sau realloc. In caz contrar, sau daca a existat deja un apel anterior free(ptr), comportamentul programului este imprevizibil.
Functia realloc schimba marimea blocului de memorie indicat de ptr la size octeti. Continutul ramine neschimbat la marimea minima dintre marimea veche si cea noua; noul spatiu de memorie care este eventual alocat este neinitializat. Daca ptr este NULL apelul este echivalent cu malloc(size); daca size este egal cu zero apelul este echivalent cu free(ptr). Cu exceptia cazului cind ptr este NULL, acesta trebuie sa fi fost returnat de un apel precedent malloc, calloc sau realloc.

Valori returnate
Pentru calloc si malloc valoarea returnata este un pointer la memoria alocata, care este aliniata in mod corespunzator pentru orice tip de variabile, sau NULL daca nu exista suficienta memorie continua.
Functia free nu returneaza nimic.
Functia realloc returneaza un pointer la noua zona de memorie alocata, care este aliniata in mod corespunzator pentru orice tip de variabile, si poate fi diferita de ptr, sau poate fi NULL daca nu exista suficienta memorie continua sau daca valoarea size este egala cu 0. Daca realloc esueaza, blocul original ramine neatins - nu este nici eliberat nici mutat.

12.2. Sortare si cautare

Nume qsort - sorteaza un tablou bsearch - cautare binara intr-un tablou sortat

Declaratie
#include <stdlib.h> void qsort(void *base, unsigned nel, unsigned size, int (*comp)
(const void *, const void *)); void *bsearch(const void *key, const void
*base, unsigned nel, unsigned size, int
(*comp)(const void *, const void *));

Descriere
Functia qsort sorteaza un tablou de nel elemente, fiecare de marime size. Argumentul base indica spre inceputul tabloului.
Elementele tabloului sint sortate in ordine crescatoare in concordanta cu functia de comparare referita de comp, apelata cu doua argumente care indica spre obiectele ce se compara. Functia de comparare trebuie sa returneze un intreg mai mic decit, egal cu, sau mai mare decit zero daca primul argument este considerat a fi mai mic decit, egal cu, respectiv mai mare decit al doilea. Daca cele doua elemente comparate sint egale, ordinea in tabloul sortat este nedefinita.
Functia bsearch cauta intr-un tablou de nel elemente, fiecare de marime size, un membru care coincide cu obiectul indicat de key. Argumentul base indica spre inceputul tabloului.
Continutul tabloului trebuie sa fie sortat crescator in concordanta cu functia de comparare referita de comp, apelata cu doua argumente care indica spre obiectele ce se compara. Functia de comparare trebuie sa returneze un intreg mai mic decit, egal cu, sau mai mare decit zero daca primul argument este considerat a fi mai mic decit, egal cu, respectiv mai mare decit al doilea.

Valoare returnata
Functia bsearch returneaza un pointer la un membru al tabloului care coincide cu obiectul indicat de key, sau NULL daca nu se gaseste nici un membru. Daca exista mai multe elemente care coincid cu key, poate fi returnat oricare element cu aceasta proprietate.

12.3. Rutine de clasificare

Nume isalnum, isalpha, isascii, iscntrl, isdigit, isgraph, islower, isprint, ispunct, isspace, isupper, isxdigit - rutine de clasificare tolower - conversie in litera mica toupper - conversie in litera mare

Declaratie
#include <ctype.h> int isalnum(int c); int islower(int c); int isalpha(int c); int isprint(int c); int isascii(int c); int ispunct(int c); int iscntrl(int c); int isspace(int c); int isdigit(int c); int isupper(int c); int isgraph(int c); int isxdigit(int c);

int tolower(int c); int toupper(int c);

Descriere
Primele 12 functii verifica daca c, care trebuie sa fie o valoare de tip unsigned char sau EOF, se afla in una din clasele de caractere enumerate mai sus.

isalnum
Verifica daca c este alfanumeric; este echivalenta cu (isalpha(c) || isdigit(c)).

isalpha
Verifica daca c este alfabetic; este echivalent cu (isupper(c) || islower(c)).

isascii
Verifica daca c este o valoare pe 7 biti din setul de caractere ASCII.

iscntrl
Verifica daca c este un caracter de control.

isdigit
Verifica daca c este o cifra (intre 0 si 9).

isgraph
Verifica daca c este un caracter afisabil cu exceptia spatiului.

islower
Verifica daca c este o litera mica.

isprint
Verifica daca c este un caracter afisabil inclusiv spatiu.

ispunct
Verifica daca c este un caracter diferit de spatiu si non-alfanumeric.

isspace
Verifica daca c este un spatiu alb.

isupper
Verifica daca c este o litera mare.

isxdigit
Verifica daca c este o cifra hexazecimala din setul 0 1 2 3 4 5 6 7 8 9 a b c d e f A B C D E F.

tolower
Converteste caracterul c, daca este o litera, la litera mica corespunzatoare.

toupper
Converteste caracterul c, daca este o litera, la litera mare corespunzatoare.

Valoare returnata
Valoarea returnata de functiile is... este nenula daca caracterul c se afla in clasa testata, si zero in caz contrar.
Valoarea returnata de functiile to... este litera convertita daca caracterul c este o litera, si nedefinita in caz contrar.

12.4. Operatii cu blocuri de memorie

Pentru majoritatea functiilor din aceasta categorie compilatorul expandeaza codul acestora folosind instructiuni pe siruri de caractere. Declaratiile acestor functii se obtin cu
#include <string.h>

Nume memcpy - copiaza o zona de memorie

Declaratie void *memcpy(void *dest, const void *src, unsigned n); void *memmove(void *dest, const void *src, unsigned n);

Descriere
Functia memcpy copiaza n octeti din zona de memorie src in zona de memorie dest. Zonele de memorie nu trebuie sa se suprapuna. Daca exista acest risc se utilizeaza memmove.

Valoare returnata
Functiile returneaza un pointer la dest.

Nume memcmp - compara doua zone de memorie

Declaratie int memcmp(const void *s1, const void *s2, unsigned n);

Descriere

Functia memcmp compara primii n octeti ai zonelor de memorie s1 si s2.

Valoare returnata
Returneaza un intreg mai mic decit, egal cu, sau mai mare decit zero daca s1 este mai mic decit, coincide, respectiv este mai mare decit s2.

Nume memset - umple o zona de memorie cu o constanta pe un octet

Declaratie void *memset(void *s, int c, unsigned n);

Descriere
Functia memset umple primii n octeti ai zonei de memorie indicata de s cu constanta c pe un octet.

Valoare returnata
Functia returneaza un pointer la zona de memorie s.

Nume memchr - cauta in memorie un caracter

Declaratie void *memchr(const void *s, int c, unsigned n);

Descriere
Functia memchr cauta caracterul c in primii n octeti de memorie indicati de s. Cautarea se opreste la primul octet care are valoarea c (interpretata ca unsigned char).

Valoare returnata
Functia returneaza un pointer la octetul gasit sau NULL daca valoarea nu exista in zona de memorie.

12.5. Operatii cu siruri de caractere

Pentru majoritatea functiilor din aceasta categorie compilatorul expandeaza codul acestora folosind instructiuni pe siruri de caractere. Declaratiile acestor functii se obtin cu
#include <string.h>

Nume strlen - calculeaza lungimea unui sir

Declaratie unsigned strlen(const char *s);

Descriere
Functia strlen calculeaza lungimea sirului s, fara a include caracterul terminator null.

Valoare returnata
Functia returneaza numarul de caractere din s.

Nume strcpy, strncpy - copiaza un sir de caractere

Declaratie char *strcpy(char *dest, const char *src); char *strncpy(char *dest, const char *src, unsigned n);

Descriere
Functia strcpy copiaza sirul indicat de src (inclusiv caracterul terminator null) in zona indicata de dest. Sirurile nu trebuie sa se suprapuna, si in plus zona dest trebuie sa fie suficient de mare pentru a primi copia.
Functia strncpy este similara, cu exceptia faptului ca nu se copiaza mai mult de n octeti din src. Astfel, daca caracterul terminator null nu se afla in primii n octeti din src, rezultatul nu va fi terminat cu null. In cazul in care lungimea lui src este mai mica decit n, restul octetilor din dest primesc valoarea null.

Valoare returnata
Functiile returneaza un pointer la sirul dest.

Nume strdup - duplica un sir

Declaratie char *strdup(const char *s);

Descriere
Functia strdup returneaza un pointer la un nou sir care este un duplicat al sirului s. Memoria pentru noul sir se obtine cu malloc, si poate fi eliberata cu free.

Valoare returnata
Functia returneaza un pointer la sirul duplicat, sau NULL daca nu exista memorie suficienta disponibila.

Nume strcat, strncat - concateneaza doua siruri

Declaratie char *strcat(char *dest, const char *src); char *strncat(char *dest, const char *src, unsigned n);

Descriere
Functia strcat adauga sirul src la sirul dest suprascriind caracterul null de la sfirsitul lui dest, si la sfirsit adauga un caracter terminator null. Sirurile nu trebuie sa se suprapuna, si in plus sirul dest trebuie sa aiba suficient spatiu pentru a pastra rezultatul.
Functia strncat este similara, cu exceptia faptului ca numai primele n caractere din src se adauga la dest.

Valoare returnata
Functiile returneaza un pointer la sirul rezultat dest.

Nume strcmp - compara doua siruri de caractere

Declaratie int strcmp(const char *s1, const char
*s2);

Descriere
Functia strcmp compara cele doua siruri s1 si s2.

Valoare returnata
Functia returneaza un intreg mai mic decit, egal cu, sau mai mare decit zero daca s1 este mai mic decit, coincide, respectiv este mai mare decit s2.

Nume strchr, strrchr - localizeaza un caracter

Declaratie char *strchr(const char *s, int c); char *strrchr(const char *s, int c);

Descriere
Functia strchr returneaza un pointer la prima aparitie a caracterului c in sirul s.
Functia strrchr returneaza un pointer la ultima aparitie a caracterului c in sirul s.

Valoare returnata
Functiile returneaza un pointer la caracterul gasit sau NULL daca valoarea nu a fost gasita.

Nume strstr - localizeaza un subsir

Declaratie char *strstr(const char *sir, const char
*subs);

Descriere
Functia strstr gaseste prima aparitie a subsirului subs in sirul sir. Caracterul terminator null nu este luat in considerare.

Valoare returnata
Functia returneaza un pointer la inceputul subsirului, sau NULL daca subsirul nu este gasit.

Nume strspn, strcspn - cauta un set de caractere intr-un sir

Declaratie unsigned strspn(const char *s, const char

*acc); unsigned strcspn(const char *s, const char
*rej);

Descriere
Functia strspn calculeaza lungimea segmentului initial din s format in intregime numai cu caractere din acc.
Functia strcspn calculeaza lungimea segmentului initial din s format in intregime numai cu caractere care nu se gasesc in rej.

Valori returnate
Functia strspn returneaza pozitia primului caracter din s care nu se afla in acc.
Functia strcspn returneaza pozitia primului caracter din s care se afla in rej.

12.6. Biblioteca matematica

1) Functiile din prima categorie sint descrise in <stdlib.h>.

Nume rand, srand - generarea numerelor pseudo-aleatoare

Declaratie int rand(void); void srand(unsigned int seed);

Descriere
Functia rand returneaza un intreg pseudo-aleator intre 0 si RAND_MAX (pentru majoritatea mediilor de programare C aceasta constanta este egala cu valoarea maxima cu semn reprezentabila pe un cuvint al sistemului de calcul).
Functia srand initializeaza generatorul cu valoarea seed pentru o noua secventa de valori intregi pseudo-aleatoare care vor fi returnate de rand. Aceste secvente se repeta daca srand se apeleaza cu aceeasi valoare seed.
Se obisnuieste ca generatorul sa fie initializat cu o valoare data de ceasul sistemului de calcul, ca in exemplul de mai jos:
#include <time.h> srand(time(NULL));

Valoare returnata
Functia rand returneaza o valoare intre 0 si RAND_MAX.

Observatie
In lucrarea Numerical Recipes in C: The Art of Scientific Computing - William H Press, Brian P Flannery, Saul A Teukolsky, William T Vetterling / New York: Cambridge University Press, 1990 (1st ed, p 207), se face urmatorul comentariu:
"Daca doriti sa generati o valoare aleatoare intreaga intre 1 si 10, se recomanda sa folositi secventa j=1+(int)(10.0*rand()/(RAND_MAX+1.0)); si nu o secventa de tipul j=1+(int)(1000000.0*rand())%10; care foloseste bitii de rang inferior."

Tot in fisierul <stdlib.h> sint descrise si urmatoarele functii:

int abs(int i); valoare absoluta long labs(long i); valoare absoluta int atoi(char *s); conversie din ASCII in intreg long atol(char *s); conversie din ASCII in intreg lung double atof(char *s); conversie din ASCII in dubla precizie

2) Functiile din a doua categorie sint descrise in fisierul <math.h>.

double fabs(double x); valoare absoluta double floor(double x); parte intreaga inferioara double ceil(double x); parte intreaga superioara double sqrt(double x); double sin(double x); sin(x) double cos(double x); cos(x) double tan(double x); tg(x) double asin(double x); arcsin(x) double acos(double x); arccos(x) double atan(double x); arctg(x) in a-?/2,?/2i double atan2(double y, double x); arctg(y/x) in a-;?,?i double exp(double x); ex double log(double x); ln(x) double pow(double x, double y); xy double sinh(double x); sinh(x) double cosh(double x); cosh(x) double tanh(double x); tgh(x) double ldexp(double x, int e); x ? 2e double fmod(double x, double y); x modulo y

Functia fmod returneaza o valoare f definita astfel: x ? a ? y ? f a este o valoare intreaga (data de x/y) si 0 ? |f | < y; f are semnul lui x.

Urmatoarele doua functii returneaza doua valori: una este valoarea returnata de functie (de tip double), si cealalta returnata prin intermediul unui argument de tip pointer la int respectiv double.

double frexp(double x, int *e);
Functia frexp desparte valoarea x in doua parti: o parte fractionara normalizata (f ? a0.5,1)) si un exponent e. Daca x este 0 atunci f?0 si e?0. Valoarea returnata este f.

double modf(double x, double *n);
Functia modf desparte valoarea x in doua parti: o parte fractionara subunitara f si o parte intreaga n. Valorile f si n au acelasi semn ca si x. Valoarea returnata este f.

12.7. Programe demonstrative

1) Programul prezentat in continuare genereaza un sir de n valori intregi aleatoare in intervalul a0,M?1i pe care le depune in tabloul X (alocat dinamic), si apoi le sorteaza crescator. In continuare se genereaza k valori intregi aleatoare pe care le cauta in tabloul X. Pentru fiecare cautare cu succes se afiseaza pe terminal valoarea cautata si pozitia in tablou.
Valorile n, k si M se iau in aceasta ordine din linia de comanda.

#include <stdlib.h>
#include <stdio.h>
#include <time.h> int cmp(const void *A, const void *B) A return *(int *)A-*(int *)B;
S int main(int ac, int **av) A int *X,*p,M,n,k,i,v; if (ac!=4) A fputs("Trei argumente!\n",stderr); return 1;

S n=atoi(ava1i); k=atoi(ava2i);
M=atoi(ava3i);
X=(int *)malloc(n*sizeof(int)); if (!X) return 1; srand(time(NULL)); for (i=0; i<n; i++)
Xaii=rand()%M; qsort(X,n,sizeof(int),cmp); for (i=0; i<k; i++) A v=rand()%M; p=(int *)bsearch(&v,X,n,sizeof(int), cmp); if (p) printf("Val: %d Pos: %d\n",v,p-X);
S free(X); return 0;
S

2) Sa reluam al treilea exemplu din capitolul precedent. Se citeste un fisier text care contine pe fiecare linie un nume (sir de caractere fara spatiu) si trei valori reale (note). Pentru fiecare linie se calculeaza media aritmetica a celor trei valori si se determina daca elementul este admis (fiecare nota este minimum 5) sau respins (cel putin o nota este sub 5). In final se afiseaza liniile in ordinea urmatoare: mai intii elementele admise in ordinea descrescatoare a mediei, si apoi elementele respinse in ordine alfabetica dupa nume. Se afiseaza doar numele, situatia (A/R) si media.
In acest exemplu punem in evidenta o modalitate comoda de selectare a membrilor unei structuri cu ajutorul macrourilor. Macroul Fld selecteaza din zona referita de pointerul P membrul f. Deoarece pointerul P (care poate fi argumentul A sau B al functiei comp) refera o zona de tip void, este necesar mai intii un cast pentru a preciza tipul concret al acesteia. Membrul f poate fi: nm, ar, md, definiti in cadrul structurii de tip StEl.
Deoarece nu stim de la inceput cite linii are fisierul de intrare, sintem nevoiti sa folosim urmatoarea strategie. La inceput alocam pentru tabloul El o zona care sa memoreze NA elemente. Pe masura ce aceasta zona se completeaza, la un moment dat numarul de linii citite coincide cu NA. In acest moment se aloca o zona noua care sa poata memora un numar mai mare de elemente. Desigur, de fiecare data se va actualiza marimea spatiului alocat.

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define NA 32 typedef struct A char nma10i, ar; float na, nb, nc, md;
S StEl;
#define Fld(P,f) ((StEl *)P)->f int comp(const void *A, const void *B) A float w; int d; if (d=Fld(A,ar)-Fld(B,ar)) return d; if (Fld(A,ar)=='A') A
w=Fld(B,md)-Fld(A,md); if (w>0) return 1; if (w<0) return -1;
S return strcmp(Fld(A,nm),Fld(B,nm));
S int main(int ac, char **av) A int na,ne,i;
StEl *El;
FILE *fi; if (ac!=2) A fputs("Un argument!\n",stderr); return 1;
S fi=fopen(ava1i,"rt"); if (!fi) A perror("Eroare la deschidere"); return 1;
S na=NA; ne=0;
El=(StEl *)malloc(na*sizeof(StEl));
while (fscanf(fi,"%s %d %d %d",
Elanei.nm,&Elanei.na,&Elanei.nb,
&Elanei.nc)!=EOF) A if ((Elanei.na>=5) && (Elanei.nb>=5) &&
(Elanei.nc>=5))
Elanei.ar='A'; else Elanei.ar='R';
Elanei.md=(Elanei.na+Elanei.nb+
Elanei.nc)/3.0; ne++; if (ne==na) A na+=NA;
El=(StEl *)realloc(El,na* sizeof(StEl));
S
S fclose(fi); qsort(El,ne,sizeof(StEl),comp); for (i=0; i<ne; i++) printf("%-12s %c%6.2lf\n",
Elaii.nm,Elaii.ar,Elaii.md); free(El); return 0;
S

3) Se citeste dintr-un fisier text o valoare naturala n. Urmatoarele linii contin n cuvinte, fiecare cuvint avind acelasi numar de litere (cel mult 10). Sa se afiseze cuvintele din fisier ordonate alfabetic.
Pentru a memora lista de cuvinte folosim urmatoarea strategie. In loc sa alocam pentru fiecare cuvint (sir de caractere) citit o zona noua de memorie, alocam de la inceput o zona in care sa putem memora toate cuvintele din lista. Aceasta zona va avea marimea de (l+1)*n octeti, unde l este lungimea fiecarui cuvint (numarul de litere). De ce (l+1)? pentru ca trebuie sa memoram si caracterul terminator null.
Avantaje: memoria este utilizata mai eficient daca se aloca de la inceput o zona contigua de dimensiune mai mare, si se reduce foarte mult fragmentarea memoriei.

#include <stdlib.h>
#include <string.h>
#include <stdio.h> int comp(const void *A, const void *B) A return strcmp((char *)A,(char *)B);
S int main(int ac, char **av) A char *C,sa11i; int n,l,i;
FILE *fi; if (ac!=2) A fputs("Un argument!\n",stderr); return 1;
S fi=fopen(ava1i,"rt"); if (!fi) A perror("Eroare la deschidere"); return 1;
S fscanf(fi,"%d %s",n,s); l=strlen(s);
C=(char *)malloc((l+1)*n);
Strcpy(C,s); for (i=1; i<n; i++) fscanf(fi,"%s",C+(l+1)*i); fclose(fi); qsort(C,n,l+1,comp); for (i=0; i<n; i++) printf("%s\n",C+(l+1)*i); free(C); return 0;
S