Algoritmi si Structuri de Date

Imagine preview
(9/10 din 6 voturi)

Acest curs prezinta Algoritmi si Structuri de Date.
Mai jos poate fi vizualizat cuprinsul si un extras din document (aprox. 2 pagini).

Arhiva contine 22 fisiere doc de 59 de pagini (in total).

Profesor: Daniela Joita

Iti recomandam sa te uiti bine pe extras si cuprins iar daca este ceea ce-ti trebuie pentru documentarea ta, il poti descarca.

Fratele cel mare te iubeste, acest download este gratuit. Yupyy!

Domeniu: Calculatoare

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 document

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.

Fisiere in arhiva (22):

  • 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

Alte informatii

Algoritmi si structuri de date