Algoritmi și Structuri de Date

Curs
9/10 (6 voturi)
Domeniu: Calculatoare
Conține 22 fișiere: doc
Pagini : 59 în total
Cuvinte : 15606
Mărime: 288.90KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Daniela Joita
Algoritmi si structuri de date

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.

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

Alții au mai descărcat și

Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim

“Diferența dintre școală și viață? În școală, înveți o lecție, apoi dai un test. În viață, ai de dat un test care te învață o lecție.” (Tom...

Proiect Structuri de Date - Orar

1. INTRODUCERE 1.1 Obiectivul problemei : Aceasta aplicatie informatica are ca obiectiv gestionarea cat mai buna a orarului unei facultati pentru...

Gestiunea Bazei de Date a unei Librării

Introducere Aplicaţia realizează gestiunea activităţii unei librării: - Înregistrează într-o bază de date cărţile care se găsesc în librărie; -...

Algoritmi și Structuri de Date

Introducere: Semiotica se ocupã cu studiul semnelor în natura si în societate. Semnul nu este o calitate în sine a unui obiect, ci o functie pe...

Baza de Date a unui Catalog Scolar Limbajul de Programare C

1. Tema proiectului Se cere sa se realizeze o baza de date care sa simuleze un catalog scolar. Pentru realizarea bazei de date se vor folosi: o...

Operatii cu Matrici - Turbo Pascal

I. ELEMENTE DE LIMBAJ PASCAL 1. TIPURI DE DATE În limbajele evoluate de programare, fiecare argument, fiecare variabila are un anumit tip bine...

Arbori

1.1.ASPECTE GENERALE LEGATE DE TEMA LUCRARII . DOMENIUL (N CARE SE (NCADREAZA LUCRAREA (n momentul de fata prelucrarea informatiilor de orice...

Principalele Componente ale unui Calculator

Orice sistem de calcul este alcătuit din două componente, componenta hardware-reprezentată de totalitatea resurselor fizice, şi componenta software...

Ai nevoie de altceva?