INFORMATICA/C/C++

ALOCAREA DINAMICA A MEMORIEI

- dinamic
- static
Limbajul C permite utilizatorului sa aloce date atat pe stiva(date automatica), cat si in zone de memorie care nu apartin stivei(dare globale sau statice).
Alocarea datelor pe stiva se face la executie si nu este permanenta.Astfel, daca declaratia : tip_nume se utilizeaza in corpul unei functii, atunci variabila nume se aloca pe stiva la fiecare apel al functiei.La revenire din functie, stiva se curate(se reduce la starea avuta inaintea apelului) si prin aceasta variabila nume nu mai are alocata o zona de menmorie, se spune ca este dinamica.
Pentru datele globale sau statice, memoria se aloca inainte de executie si alocarea ramane valabila pe tot parcursul executiei programului, de aceea pentru datele de acest fel se spune ca alocarea este static.
Alocarea unei zone de memorie in heap se poate realiza cu mai multe functii.o functie frecvent utilizata este functia malloc, cu prototipul:
void*malloc(unsigned n);



LISTE SIMPLU INLANTUITE
struct nod
{
int info;
nod*urm;
};
nod *prim,*ultim,*p;
int x;
- initializare
int este_vida(nod *prim)
{
return prim==NULL;
}
- creare
pas1. se adauga primul nod la lista
pas2. cat timp mai exista informative,executa: se adauga un nod la lista
- adaugarea(primului nod)
void adaug_nod(nod *&prim, nod *&ultim)
{
prim=new nod;
prim->info=x;
prim->urm=NULL;
ultim=prim;
}
- adaugarea(unui nod la lista)
1. in fata primului nod
void adaug_prim(nod *&prim)
{
nod*p=new nod;
p->info=x;
p->urm=prim;
prim=p;
}
2. dupa ultimul nod
void adaug_ultim(nod *&ultim)
{
nod*p=new nod;
p->info=x;
p->urm=NULL;
ultim->urm=p;
ultim=p;
}
- adaugarea(in interiorul listei)
• dupa nodul cu adresa q
void adaug_dupa(nod *q, nod *&ultim)
{
nod*p=new nod;
p->info=x;
p->urm=q->urm;
q->urm=p;
if(q==ultim)
ultim=p;
}
• inainte de nodul cu adresa q
void adaug_in_fata(nod *q,nod *&ultim)
{
nod*p=new nod;
p->info=q->info;
q->info=x;
p->urm=q->urm;
q->urm=p;
if(q==ultim)
ultim=p;
}
- parcurgerea
void parcurge(nod *prim)
{
for(nod *p=prim;p!=NULL;p=p->urm)
………..// se prelucreaza p->info
}
- cautarea
• nodul care indeplineste o anumita conditie
nod *caut(nod *prim)
{
for(nod *p=prim; p!=NULL && !conditie; p=p->urm)
return p;
}
• nodul care se gaseste intr-o anumita pozitie
nod *caut(nod *prim, int poz)
{
nod *p=prim;
int nr=1;
for(p!=NULL && nr<poz; p=p->urm;nr++)
return p;
}
- eliminarea
• primului nod
void elimin_prim(nod *&prim)
{
nod *q=prim;
prim=prim->urm;
delete q;
}
• ultimului nod
void elim_ultim(nod *prim, nod *&ultim)
{
for(p=prim;p->urm->urm!=NULL;p=p->urm)
p->urm=NULL;
ultim=p;
delete q;
}
• unui nod din interiorul listei
void elimin(nod *p, nod *&ultim)
{
nod *q=p->urm;
p->info=p->urm->info;
p->urm=p->urm->urm;
delete q;
if(p->urm==NULL)
ultim=p;
}
LISTE DUBLU INLANTUITE

struct nod
{
int info
nod *ant, *urm;
};
nod *prim, *ultim, *p;
• initializarea
void adaug_nod( nod *&prim, *&ultim)
{
prim=new nod;
prim->info=x;
prim->ant=NULL;
prim->urm=NULL;
ultim=prim;
}

• adaugarea
1. in fata primului nod
void adaug_prim(nod *&prim)
{
nod *p=new nod;
p->info=x;
p->ant=NULL;
p->urm=prim;
prim=p;
}
2. dupa ultimul nod
void adaug_ultim(nod *&ultim)
{
nod*p=new nod;
p->info=x;
p->ant=ultim;
p->urm=NULL;
ultim->urm=p;
ultim=p;
}
3. in interiorul listei

a) dupa nodul cu adresa q
void adaug_dupa(nod *q, nod *&ultim)
{
nod*p=new nod;
p->info=x;
p->urm=q->urm;
p->ant=q;
if(q==ultim)
ultim=p;
else
q->urm->ant=p;
p->urm=p;
}


b) inainte de nodul cu adresa q
void adaug_in_fata(nod *q)
{
nod*p=new nod;
p->info=x;
p->urm=q;
p->ant=q->ant;
q->ant->urm=p;
q->ant=p;
}

• parcurgearea

1. pornind de la primul nod, pana la ultimul nod, in ordinea de inlantuire a nodurilor- furnizata de adresa urmatoare in nodul vizitat
2. pornind de la ultimul nod, pana la primul nod, in ordinea de inlantuire a nodurilor-furnizata de adresa ant erioara din nodul vizitat
• eliminarea

1. primului nod
void elim_prim(nod *&prim)
{
nod*q=prim;
prim->urm->ant=NULL;
prim=prim->urm;
delete q;
}

2. ultimului nod

void elim_ultim(nod *&ultim)
{
nod *q=ultim;
ultim->ant->urm=NULL;
ultim=ultim->ant;
delete q;
}

3. unui nod din interiorul listei

void elimin(nod *p)
{
nod*q=p;
p->ant->urm=p->urm;
p->urm->ant=p->ant;
delete q;
}
STIVA
Cele doua extremitati ale stivei se numesc varf si baza.Accesul la nodurile stivei(adaugarea si extragerea) este permis numai printr-o singura extremitate numita varf si ultumul nod inserat este primul extras(se extrage cea mai noua informative adaugata).

int este_vida(nod *varf)
{
return varf==NULL;
}

• initializarea
void init(nod *&varf)
{
varf=NULL;
}

• adaugarea
void adaug(nod *&varf)
{
nod *p=new nod;
p->info=x;
p->urm=varf;
varf=p;
}

• extragerea
void extrage(nod *&varf)
{
nod *p=varf;
varf=varf->urm;
delete p;
}
• prelucrarea
void prelucrare(nod *&varf)
{
while(varf!=NULL)
{
// se prelucreaza varf->info;
extrage (varf);
}
}
Enunt:
Se citesc dintr-o stiva cifrele unui numar care are o valoare foarte mare. Citirea cifrelor se va face pana cand numarul citit nu este o cifra. Sa se afiseze inversul acestui numar.

COADA
Cele doua extremitati se numesc cap si baza.Adaugarea se face prin baza, iar extragerea si consultarea unui nod este permisa numai prin extremitatea cap.

• initializare
void init(nod *&cap, nod *&baza)
{
cap=new nod;
cap->info=x;
cap->urm=NULL;
baza=cap;
}
• adaugarea
void adaug(nod *&baza)
{
nod*p=new nod;
p->info=x;
p->urm=NULL;
baza->urm=p;
baza=p;
}

• extragerea
void extrage(nod *&cap)
{
nod *p=cap;
cap=cap->urm;
delete p;
}
• prelucrarea
void prelucrare(nod *&cap)
{
while(cap!=NULL)
{
// se prelucreaza ca->info;
extrage(cap);
}
}
Enunt:
Se adauga si se extrag din coada mai multe caractere

ARBORELE BINAR



Se numeste arbore binar un arbore cu radacina positional ca are proprietatea ca fiecare nod are cel mult doi descendenti directi(succesori).
Se numeste arbore binar strict un arbore care are proprietatea ca fiecare nod, cu exceptia nodurilor terminale, are exact doi descendenti.
Se numeste arbore binar echilibrat un arbore binar care are proprietatea ca diferenta intre inaltimile celor doi subarbori ai oricarui nod este1.





Se numeste arbore perfect echilibrat un arbore binar care are proprietatea ca diferenta dintre numarul nodurilor celor doi subarbori ai oricarui nod este cel mult 1.

Se numeste asbore bianr complet, un arbore binar strict care are toate nodurile terminale pe acelasi nivel.

















Implementarea structurilor de date de tip arbore binar se poate face:
• static(folosind vectori)
• dinamic(folosind pointeri)



Static: folosind doi vectori in care se memoreaza cei doi succesori ai unui nod:
1. vectorul st in elementul i se memoreaza nodul succesor stang al nodului i
2. vectorul dr in elementul i se memoreaza eticheta nodului succesor drept al nodului i














Nodul i 1 2 3 4 5 6 7 8 9
St 2 3 0 0 0 7 0 9 0
Dr 4 6 0 5 8 0 0 0 0

Dinamic: tipul de data este definit ca o inregistrare care contine trei categorii de campuri:

1. informatia utila
2. adresa subarborelui stang
3. adresa subarborelui drept

struct nod
{
<tip>info
nod *s, *d;
};
nod *r;


Algoritm:

pas1. se citeste informatia utila din nod
pas2. daca nodul nu contine informative utila, atunci se creeaza arborele vid,
astfel:
pas3. se creeaza un nod radacina prin alocarea unei zone de memorie
pas4. se atribuie, campurile cu informatie din nod, informatia utila
pas5. se creaza subarborele stang
pas 6. se creaeaza subarborele drept.












ARBORELE BINAR DE CAUTARE

Se numeste arbore binar de cautare un arbore binar care are proprietatea ca, pentru fiecare nod, cheia din succesorul stang este mai mica decat cheia din nod, iar cheia din succesorul drept este mai mare decat cheia din nod













• crearea
1. se initializeaza arborele cu subarborele vid, atribuind radacinii valoarea NULL
2. se citeste informatia utila, cu valoare v pentru cheie
3. cat timp exista informative utila, executa
4. se initializeaza nodul current cu nodul radacina
5. daca nodul current nu este arbore vid, atunci se trece la pas 9
6. se creeaza un nod prin alocarea unei zone de memorie
7. se atribuie campului cu informatie din nod, informatia utila
8. se atribuie succesorilor nodului arborele vid, se trece la pas11
9. daca v este mai mica decat chie nodului current, atunci nodul curent devine succesorul stang si se revine la pas5
10. daca v este mai mare decat cheia nodului curent, atunci nodul curent devine succesorul drept si se revine la pas5; astfel se afiseaza mesajul “cheia exista deja”;
11 se citeste informatia utila cu valoarea v pentru cheie.
• parcurgerea
1. se citeste cheia k care se cauta
2. se initializeaza pointerul cu adresa radacinii
3. cat timp nu s-a gasit cheia cautata si nu s-a ajuns la arborele vid, executa
4.daca nodul curent are cheia mai mica decat k atunci poiterul
avanseaza la subarborele stang astfel pointerul avanseaza la
subarborele drept.
• stergerea
1. nodul care se strege nu are fii
sterge nod terminal
k=1;
p->s=NULL;
delete q1
sterge nod terminal
p->d=NULL;
delete q2;
2. nodul care se sterge are un fiu
In nodul parinte , adresa lui este inlocuita cu adresa fiului(se stabileste o legatura intre parintele lui si fiul lui)












stergere nod cu fiu stanga
k=5;
p->s=p->s->s
delete q1;
stergere nod cu fiu dreapta
k=11;
p->d=p->d->d;
delete q2;

3. nodul care se sterge are doi fii















stergere cu doi fii
k=7;
q->info=r->info;
p->s=p->s->d;
delete r;