Cuprins
- Cuprins
- Modulul 0. Alocare dinamica in limbajul C
- 0. Pointeri si alocare dinamica. Tipul de date struct
- 0.1 Pointeri si alocare dinamica
- 0.2 Tipul struct
- Modulul I. Structuri de date liniare
- 1. Liste liniare
- 1.1 Alocarea secventiala
- 1.2 Alocarea inlantuita
- 2. Stive
- 2.1 Alocarea secventiala
- 2.2 Alocarea inlantuita
- 3. Cozi
- 3.1 Alocarea secventiala
- 3.2 Alocarea inlantuita
- 4. Liste circulare
- 5. Liste dublu inlantuite
- Modulul II. Structuri de date neliniare
- 6. Grafuri
- 6.1 Notiuni generale
- 6.2 Reprezentarea grafurilor
- 7. Arbori
- 7.1 Reprezentare
- 7.2 Traversare
- 8. Arbori binari
- 8.1 Notiuni generale
- 8.2 Reprezentare
- 8.3 Traversare
- Modulul III. Analiza algoritmilor
- 9. Analiza eficientei algoritmilor
- Modulul IV. Algoritmi de sortare
- 10. Sortare prin numarare
- 11. Sortare prin inserare
- 12. Sortare prin interschimbare
- 12.1 Bublesort
- 12.2 Quicksort
- 13. Sortare prin selectie
- 14. Mergesort
- Modulul V. Algoritmi de cautare
- 15. Cautare secventiala
- 16. Cautare binara
- 17. Arbori binari de cautare.
- 17.1 Cautare in arbori binari de cautare
- 17.2 Inserare si stergere arbori binari de cautare
Extras din curs
Modulul 0. Alocare dinamica in limbajul C
Capitolul 0. Pointeri si alocare dinamica. Tipul de date struct
0.1 Pointeri si alocare dinamica
O problema care apare in momentul declararii unui sir era aceea ca dimensiunea sirului trebuia sa fie constanta, iar daca doream sa rulam programul pentru siruri de dimensiuni diferite atunci trebuia sa definim o dimensiune suficient de mare a sirului si in program sa folosim numai un numar de elemente ale sirului, numar introdus de utilizator la fiecare rulare a programului, celelalte elemente nefiind folosite si deci ocupand inutil un spatiu de memorie. Pentru rezolvarea acestei probleme exista o modalitate de alocare a memoriei ce se numeste alocare dinamica, adica alocare a memoriei in momentul rularii, permitand programului sa isi ajusteze capacitatea de memorare a datelor in functie de necesitatile utilizatorului.
In C sunt disponibile patru functii care pot aloca atat spatiu cat este dorit, pot modifica dimensiunea unui sir existent sau pot elibera zone de memorie alocate anterior. Aceste functii sunt:
- malloc
- calloc
- realloc
- free
Toate apartin bibliotecii stdlib.h.
Prototipul functiei malloc este:
void *malloc(size_t dimensiune);
malloc rezerva un numar de octeti specificat de catre parametrul dimensiune, in locatii de memorie consecutive returnand un pointer la primul octet sau pointerul NULL (adica pointerul 0, care nu puncteaza nimic) daca nu poate aloca memoria solicitata. Functia returneaza un pointer de tip void adica in momentul in care acest pointer este atribuit unui pointer de un anumit tip atunci valoarea pointerului returnat de catre functia malloc se va transforma in tipul corespunzator. size_t corespunde tipului intreg fara semn, fiind tipul rezultatului pe care il returneaza operatorul sizeof. Acest tip este definit in stddef.h.
Exemplu:
int *p;
p = malloc(5 * sizeof (int) );
malloc va aloca 5*4=20 de octeti (am presupus ca dimensiunea int este de patru octeti) va returna un pointer la primul octet si este transformat in pointer de tip int memorat in pointerul p de tip int.
Deci p este de fapt un pointer la un sir de 5 variabile int. Putem initializa elementele sirului, putem efectua orice prelucrare a elementelor sirului ca si cum ele ar fi fost alocate in momentul alocarii.
Prototipul functiei calloc este:
void *calloc(size_t n, size_t dimensiune);
Functia calloc aloca spatiu de memorare pentru n elemente, fiecare de marimea dimensiune. Fiecare element este initializat cu zero. Functia returneaza un pointer la spatiul alocat si NULL daca nu este spatiu suficient in memorie sau daca n = 0 sau dimensiune = 0.
Exemplu:
float *p;
p = calloc(10, sizeof(float) );
Prototipul functiei realloc este:
void *realloc(void *p, size_t dimensiune);
Functia realloc modifica marimea unui spatiu pentru date deja existente. p este un pointer catre o zona de memorie deja alocata. Daca p este NULL functia realloc functioneaza ca si malloc, alocand un bloc de atatia octeti cati sunt precizati de dimensiune. Daca p nu este NULL atunci p trebuie sa fie un pointer returnat de un apel anterior al uneia din functiile malloc, calloc sau realloc. Parametrul dimensiune determina noua marime in octeti a blocului de memorie alocat. Acest proces are loc fara sa se stearga datele existente. Daca zona de memorie existenta nu poate fi extinsa fara sa se suprapuna cu alte date, intreaga zona este copiata la o alta locatie iar zona veche este eliberata. Functia returneaza un pointer la noua zona de memorie alocata sau NULL.
Exemplu:
alocdinam.C
Prototipul functiei free este:
void free(void *p);
Functia free elibereaza blocul de memorie indicat de pointerul p, unde p trebuie sa fie un pointer returnat de un apel anterior al uneia din functiile malloc, calloc sau realloc. Functia free nu poate fi utilizata pentru eliberarea memoriei alocate de variabile in momentul compilarii. Dupa apelarea functiei free blocul eliberat este disponibil pentru alocare. Un pointer NULL ca argument este ignorat.
Conținut arhivă zip
- Algoritmi si Structuri de Date
- Cuprins.doc
- Cuvant inainte.doc
- Modulul 0 - capitolul0.doc
- Modulul I - capitolul1.doc
- Modulul I - capitolul2.doc
- Modulul I - capitolul3.doc
- Modulul I - capitolul4.doc
- Modulul I - capitolul5.doc
- Modulul II - capitolul6.doc
- Modulul II - capitolul7.doc
- Modulul II - capitolul8.doc
- Modulul III -capitolul9.doc
- Modulul IV - capitolul10.doc
- Modulul IV - capitolul13.doc
- Modulul IV - capitolul14.doc
- Modulul IV -capitolul12.doc
- Modulul IV- capitolul11.doc
- Modulul V - capitolul15.doc
- Modulul V - capitolul16.doc
- Modulul V - capitolul17.doc
- Probleme propuse.doc
- ~$uprins.doc