ATPATabloul = structura de date de acelasi tip care ocupa o zona continua de memorie.* in limbajul JAVA acelasi tip poate fi si clasa Object

int tab[]=new int[10];* pt String trebuie utilizata conversia castAVANTAJE:- accesul rapid la elementele tabloului prin index[]DEZAVANTAJE:-manipularea (adaugare,inserare,stergere) se realizeaza prin deplasarea elementelor sau modificarea structurii.

Lista = set de noduri, intre noduri existand legatura.Legaturile pot fi unidirectionale si bidirectionale.* informatia stocata in cadrul unui nod poate sa aiba orice natura, de asemenea in cadrul unui nod exista obligatoriu legatura catre nodul urmator = referinta* in cazul legaturii bidirectionale exista referinta si catre nodul precedentAVANTAJE:* nu necesita zone continue de memorie* alocarea dinamica a unui nod (new) distribuie nodul intr-o zona libera.* in limbajul C++ stergerea nodului dintr-o lista presupune si invocarea metodei delete care bifeaza acea zona ca fiind libera* in JAVA nu exista operatia delete, eliminarea nodurilor sterse (bifarea nodurilor sterse ca fiind libere) fancandu-se automat.* manipulare facila a nodurilor (inserare, adaugare, stergere)DEZAVANTAJE:* accesul dificil la elementele listei* de obicei exista o referinta catre capul listei (t)* accesul catre alte elemente facandu-se secvential, lista se va parcurge de la t pana la final.In functie de legatura dintre noduri:1) liste simplu inlantuite (legatura intr-un sens)2) liste dublu inlantuite (legatura in ambele sensuri)O lista se poate termina cu legatura catre un nod special sau referinta catre "null" sau catre primul nod (t) => liste circulare.

Nod.javaStructura.javaTestare.java

class Nod {Object val;Nod urmator;

// Nod precedent;public Nod (Object val) {

this.val = val;urmator = null;

precedent = null;} //constructor

//fiind vorba de campuri publice nu e necesar sa definim metodele specifice (get/set)}

Fie urmatoarea lista:

class Nod {int val;Nor urmator;public Nod (public Nod) {

this.val=val;urmator=null;

}}

Testare.javaNod t = new Nod(3);t.urmator = new Nod(5);t.urmator.urmator = new Nod(7);t.urmator.urmator.urmator = new Nod(9);

* este esential sa cunoastem modul in care incheie lista deoarece parcurgerea secventiala trebuie sa se incheie.* in cazul aceste "null" e conditia de incheiere.

Parcurgerea secventiala:Nod x=t;//x are rolul variabilei increment cauta i din//for (int i=0;i<N;i++)//pentru parcurgerewhile (x != null) {

x=x.urmator; //i++}

Inserarea pentru o lista simpla inlantuita:

Nod z = new Nod(9);z.urmator = t.urmator.urmator;t.urmator.urmator = z;

Obs: la operatia de inserare intr-o lista se conecteaza mai intai elementul nou creat.

Problema:Fie o lista de noduri de dimensiune data. Lista reprezinta memoria disponibila pentru program. Se vor implementa operatii de creare, inserare, stergere, pt o lista folosind nodurile din lista memoriei.

Liste dublu inlantuiteINSERARE

Nod z = new Nod(9);z.urmator = t.urmator.urmator;t.urmator.urmator.precedent=z;z.precedent=t.urmator;t.urmator.urmator=z;

Obs: * pentru inserare intr-o lista simplu inlantuita sunt necesare 2 operatii* pentru inserare intr-o lista dublu inlantuita sunt necesare 4 operatii* elementul 5 este un nod care nu mai poate fi accesat* la un anumit moment masina virtuala il va sterge

STERGEREA1) lista simpla

t.urmator=t.urmator.urmator;

2) lista dublu inlantuita

t.urmator=t.urmator.urmator;t.urmator.precedent=t;

* pentru operatia de adaugare nodul nou creat se trece in capul listei* operatie intalnita in cadrul stivei.

Problema lui JOSEPHUSSe da un numar de N noduri (9) si se va elimina fiecare al M nod. (5)N=9M=5* numaratoarea se face numarand si nodul curent* se utilizeaza o lista circulara simplu inlantuita

int N = integer.parseint (st.nextToken());int M = integer.parseint (st.nextToken());Not t = new Nod(1);Nod x = t;for (int i=2; i<=N; i++) {

x.urmator = new Nod(i);x = x.urmator; //incrementare

}x.urmator=t; //lista circularawhile (x!=x.urmator) {

for (int i=1; i<M;i++){x=x.urmator;

}x.urmator = x.urmator.urmator;

}ta.append(x.val);

STIVE SI COZIStiva:

- structura de date de tip LIFO- structura fundamentala avand implementari atat la nivel hardware cat si la nivel software- structuri de tip stiva se regasesc la nivelul arhitecturii microprocesoarelor, la masini virtuale si programe software.Ex: in limbajele OOP anumite portiuni de program pot fi executate de functii specifice:- controlul din programul principal e transferat catre o functie- punctul (pozitia) de intoarcere in programul principal fiind stocat intr-o stiva* in cazul in care stiva nu este implementata eficient sau limbajul de programare nu este unul functional in cazul recursivitatii stiva se umple foarte repede.Se mai compara in limbajul JAVA din punct de vedere al timpului de executie acelasi program in varianta recursiva si iterativa.* in varianta recursiva se autoapeleaza functia:N!=N*(N-1)!f(N)=n*f(n-1)* diferenta este data de implementarea stivei* limbajele functionale: ERLANG, F# sunt optimizate pentru cod recursiv

Operatiile principale asupra stivei:1) PUSH - adauga un element in varful stivei2) POP - extrage elementul din varful stivei3) PEEK - vizualizeaza elementul din varful stivei4) ISEMPTY - stiva are sau nu elemente5) ISFULL - stiva este plina

Dpdv al implementarii stiva poate fi constituita pe o structura de tip tablou sau pe o structura de tip lista.

Implementarea pe structura de tablou* pentru implementare este necesara cunoasterea varfului stivei* conventii:+ consideram varful stivei ca fiind pozitia libera din stiva+ elementul ne va adauga in stiva la pozitia indicata de varf:

Tab[varf];varf++;

- stiva este vida (isEmpty == true ) daca varf=0;- stiva este plina (isFull == true ) daca varf=tab.length- in cadrul pachetului Java.Util exista o implementare de tip stivaObs: verificarile de tip isEmpty/isFull se pot realiza in cadrul clasei Stiva sau extern in cadrul clasei Test. De asemenea isEmpty/isFull se pot implementa folosind exceptii.

Stiva.javaclass Stiva {

int tab[]=new int[10];int varf=0;public Stiva() {}public void push (int z) {

if (!isFull()) {tab[varf++]=z;}}

public int pop () {if (!isEmpty()) { return tab[--varf];}return null;

}public int peak() {

if (!isEmpty()) {return tab[varf-1];}return null;

}public boolean isEmpty() {

return (varf==0);}public boolean isFull() {

return (varf==tab.length);}

}

Testare.javaStiva stv = new Stiva();stv.push(3);stv.push(5);stv.pop();

Implementarea stivei pe o structura de tip lista

(t==null) => stiva goala* stiva implementata pe o structura de tip lista poate avea ca si conditie de vid (isEmpty) elementul null sau specialStivaL.javaclass StivaL {

Nod t = null;public StivaL() {}public void push (int z) {

Nod y = new Nod(z);y.urmator = t;t = y;

}public int pop() {

if (t!=null) {int val=t.val;t=t.urmator;return val;

}}public int peek() {

return t.val;}

}

Coada* structura de tip FIFO* se intalneste in cazul Bufferelor (memorii tampon)* scopul principal: a stoca si a livra coerent informatia.Ex: se poate construi o zona de memorie de tip coada care acumuleaza o serie de actiuni sosite la diverse momente de timp si pe care le srie o data pe HDD-SSD.Baze de date in memorie 1 cache.* un serviciu de conversie a filmelor dintr-un format in altul se poate construi pe o structura de tip coada.* serviciul AMAZON pune la dispozitie un sistem de cozi care preiau informatia de la utilizatori si o distribuie catre alte servicii SQS.Implementare:1) pe structura de tip tablou2) pe structura de tip lista

CoadaT.java* sunt necesari 2 indecsi:a) K - cap - introducereb) capat - coada - extragere

* in cazul implementarii pe o structura de tip tablou apare fenomenul de migrare a cozii in tablou.cap+1==coada* conditia isFull are loc atunci cand indexul cap se afla pe ultima pozitie si indexul coada pe prima. Sau cand cap+1==coadaOperatii specifice:1) put - adauga2) get - extrage* structurile de stiva si coada se vor folosi in cazul arborilor ca structuri ajutatoare

Coada implementata pe o structura de tip lista:* trebuie tratate urmatoarele cazuria) niciun elenentb) un singur elementc) mai multe elemente

* vaianta de implementare:- introducerea nodurilor speciale care sa delimiteze coada

while (x.urmator!=coada)

a) isEmpty() - coada vida cap.urmator = coada

b) introducere:Nod z = new Nod(3);z.urmator = cap.urmator;cap.urmator = z;

c) extragere: se parcurge pana la ultimul sau se va crea o lista dublu inlantuita.

Aplicatii1) Inversarea unui sir de caractere:

String str="abcdef";for (int i=0; i<str.length();i++)

strcharcat(i);2) Verificarea unei expresii matematice

"{7 + [5 - (3+4)]}"* folosind o structura de tip stiva in care se va trece parantezele deschise.

Algoritmi simpli de sortare- sunt potriviti pentru seturi reduse de date- in cazil unui se redus de date este preferabil sa utilizam unul dintre algoritmii simpli de sortare deoarece timpul de sortare este la fel sau chiar mai bun decat in cazul unui algoritm mai complex.- algoritmi complecsi de sortare se folosesc in cazul seturilor uriase de date sau a unor configuratii deosebite a datelor.- pe seturi mari de date algoritmii complecsi garanteaza un timp de sortare mic- de obicei sortarea este o etapa care pregateste setul de date pentru alte operatii (cautare liniara)- operatii de sortari frecvente in cadrul BD sunt ASC, DESC.

Sortarea prin selectie* este selectat un element si se considera a fi minimul (K)* se cauta in restul tabelului un element care sa aiba o valoare mai mica (< K)* daca se gaseste un astfel de element se schimba pozitia celor 2 elemente intre ele* se parcurge de fiecare data tot tabloul ramas pentru a gasi minimul* dupa o prima parcurgere pe prima pozitie avem garantat cel mai mic element- tabloul tab -> introdus StringToken

public void sortare_selectie() {for (int i=0; i<n-1;i++) {

int k=i; //mem pozitia elementului presupus minimfor (int j=i+1; i<n; j++) {

if (tab[j]<tab[k]) k=j;if (k != i) {int t=tab[i];

tab[i]=tab[k];tab[k]=t;

}}

}}

tab[j]<tab[k] k=j

Sortarea prin insertie* se considera ca pana la pasul i-1 toate elementele sunt sortate* elementul de pe pozitia i se verifica cu elementul de la stanga pana cand se intalneste un element cu o valoare mai mica decat elementul de pe pozitia i* elementele comparate se vor deplasa cu o pozitie la dreapta

for (int i=1; i<n-1;i++) {int k=i; //mem pozitiaint p = tab[i]; //mem valoarewhile (tab[k-1]>p && k>0) {

tab[k]=tab[k-1];k--;

}tab[k]=p;

}

Sortarea prin metoda bulelor- la o prima parcurgere a tabelului metoda garanteaza ca pe ultima pozitie se va afla elementul cel mai mare.- la parcurgere se compara elementele vecine si se schimba pozitia intre ele.

for (int i=n-1; i>0; i--) {for (int j=1; j<=i; j++)

if tab[j-1]>tab[j] {int t=tab[j];tab[j]=tab[j-1];tab[j-1]-t;

}}

Metodele complexe de sortare se bazeaza pe recursivitate.* este dificil de scris si de inteles un algoritm complex de sortare sub forma iterativa

Recursivitatea* presupune rezolvarea unei probleme prin rezolvarea unor dimensiuni mici ale aceleiasi probleme.* un algoritm recursiv contine o dimensiune suficient de mica a problemei pentru care se cunoaste raspunsul* presupunem apelul aceleiasi metode cu o valoare mai mica a dimensiunii problemei

1) triunghiularf(k) = k + f(k-1)f(3) = 3 + f(2)f(2) = 2 + f(1)f(1) = 1*la algoritmi recursivi => sunt functii ce intorc o valoare

public int triunghi(int val) {if (val==1) return 1;return val+triunghi(val-1);

}

2) factorialpublic int factorial (int val) {

if (val==0) return 1;return val*factorial(val-1);

}

Interclasarea a doua tablouri- se obtine un al 3-lea tablou care are dimensiunea data de suma dintre cele doua tablouritab3.length=tab2.length+tab1.length;

Este format astfel:- se compara pozitia curenta din primul tablou cu pozitia curenta din al 2-lea tablou, iar valoarea mai mica se trece in tablou- pozitia curenta din tabloul cu val mai mica se incrementeaza- daca pozitiile comparate au aceeasi valoare, valorile se vor trece in tab3 incrementand valorile in ambele tabele- operatia continua pana cand se parcurge unul sau ambele tabele, restul valorilor ramase fiind copiate in aceeasi ordine in tab3- prin interclasarea a 2 tablouri ordonate se obtine un tablou ordonat (Merge Sort)

public void interclasare() {int tab3[] = new int[tab1.length + tab2.length];int i=0,j=0,k=0;while (i<tab1..length && j<tab2.length) {

if (tab1[i]< tab[j]) {tab3[k]= tab1[i]; i++; k++;}if (tab2[i]<tab[j]) {tab2[k]= tab2[i]; j++; k++;}

}while (i<tab1.length) {tab3[k]=tab1[i]; i++; k++;}

while (j<tab2.length) {tab3[k]=tab2[j];j++;k++;}}

Reursivitate. Cautare liniara (iterativa, recursiva)Cautarea liniara presupune cautarea unei valori intrun set de date dat. Daca datele nu sunt sortate este posibl sa trebuiasca parcurs intregul set de date. Daca datele sunt ordonate nu mai este necesara parcurgerea tuturor datelor din set.

Cautare liniaraMetoda (functia) de cautare liniara afla pozitia pe care se regaseste elementul cheie.

public int cautaB (int ch, int i1, int i2) {//in cazul alg de cautare si ordonare recursivi se obisnuieste sa se foloseasca//mijlocul internaluluiint k=(i1+i2)/2;if (tab[k]==ch) return k;

//cond de oprire pt alg recursivif (i2<i1) return -1; //eroare

else {if (tab[k]<ch) cautaB(ch,k+1,i2);if (tab[k]>ch) cautaB(ch,i1,k);

}}

Divide et imperaTehnica de programare (stil de programare)* presupune descompunerea unei probleme de o dimensiune N in probleme de dimeniune mai mica si rezolvarea acestora individuala

Sa se afle maximul unui set de date in mod recursiv:public int max (int tab[], int i1, int i2) {

if (i1==i2) return tab[i1];int k=(i1+i2)/2;int u=max(tab,i1,k);int v=max(tab,k+1,i2);if (u>v) return u;

else return v;}

Sortarea MergeSort* utilizeaza tehnica divide et impera, descompunand problema initiala pana la dimensiunea 1.* cele 2 tablouri de dimensiune 1 sunt interclasate obtinandu-se un tablou de dimensiune 2 ordonat.public int MergeSort(int tab[],int i1,int i2) {

if (i2-i1>1) {int k=(i1+i2)/2;MergeSort(tab,i1,k-1);MergeSort(tab,k,i2);

interclasare(tab,i1,k,i2);} else if (i1-i2==1) {

if (tab[i1]>tab[i2]) {int t=tab[i2];tab[i2]=tab[i1];tab[i1]=t;

}}

}

QuickSort* algoritmul de sortare foloseste tehnica divide et impera:

- este aleasa o valoare oarecare din tablou (pivot)- valorile mici sunt trecute in stanga- valorile mari sunt trecute in dreapta

* se poate face o sortare folosind o structura auxiliara* sau o sortare in place (pe loc) in tablou

public void interclasare (int tab[],int i1, int k, int i2) {int tab3[]=new int[tab.length];while (i<k-1 && q<i2) {

if (tab[i]>=tab[j] { tab3[q]=tab[j]; q++; j++; }if (tab[i]<tab[j] { tab3[q]=tab[i]; q++; i++; }

}while (i1<k-1) { tab3[q]=tab[i]; q++; i++; }while (j<i2) { tab3[q]=tab[j]; q++; j++; }

// se copiaza tab3 in tab}

Obs: sortarea se realizeaza dupa valoarea pivotului si nu dupa pozitia acestuia in tablou

QuickSort pe tablou cu sortare in place* alegerea pivotului consta in alegerea mijlocului tabloului.* se definesc doi indicatori de pozitie

i - pt val mai mici din stangaj - pt valori mai mari din dreapta

* in momentul in care in zona din stanga se intalneste o valoare mai mare decat pivotul, aceasta se va schimba cu valoarea mai mica decat pivotul aflata in dreapta.while (i<j)while (i<pivot) i++;while (j>pivot) j++;schimbare();

ARBORI* structuri de date ierarhizate combinand facilitati oferite:

- de structuri de tip tablou- de structuri de tip lista

* in functie de structura si organigrama arborelui sunt facilitate anumite operatii, structura unui

arbore poate influenta decisiv modul de rezolvare a unei probleme.- Arbori-B (baze de date)- Arbori binari (2-3-4)- Arbori rosu-negru

Tipuri generale de arbori- arbori liberi- arbori radacina- arbori ordonati

- binari- n-ari

Abori liberi* arbori in care toate nodurile au acelasi rol* atat timp cat intre 2 noduri exista o singura cale (drum) structura respectiva este un arbore* daca mai exista un alt drum, structura se numeste graf.

Arbori radacina* prezinta o organizare ierarhica* nodul de pe nivelul 0 = nod radacina* in cazul arborilor radacina se intalnesc noduri parinte, noduri copil, noduri frati, noduri frunza.* nodurile care nu mai au alte noduri copii se numesc noduri terminale sau frunza.* Structura arborelui radacina este o structura recursivaArbori ordonati - arbori radacina la care pentru fiecare nivel exista o ordonare pe nivel.

2 copii => arbori binarin copii => arbori n-ari

Arbori binari de cautareOrdonare:

valoarea nodului copil stanga < valoarea parintelui < valoarea copilului din dreaptaTraversari:1) Recursive -> Adancime (preordine, inordine, postordine)2) Iterative -> Adancime (preordine, inordine, postordine)

-> Latime

Metodele iterative de traversare se fac cu ajutorul structurilor auxiliare:- pt adancime: stiva- pt latime: coada

In cadrul unei traversari se poate realiza operatia de vizitare = posibilitatea executarii unei operatii cu valoarea nodului respectiv.Obs: Un nod poate fi traversat de mai multe ori, dar vizitat o singura data.

Traversarea arborilor liniariclass NodA {

char val;NodA s;NodA d;public NodA (char val) {

this.val=val;

s=null;d=null;

}}

Traversarea in Adancime:

1) Preordine A-B-C-D-E-F-G-H

2) InOrdine D-C-E-B-A-G-H-F

3) Postordine D-E-C-B-H-G-F-A4) Latime (niveluri)

AB FC GD E H

Traversarea adancime (recursiva)public void traversare_recursiv (NodA x) { //x= radacina#1 if (x==null) return;

System.out.println(x.val);#2 if ((x.s)!=null) traversare_recursiv(x.s);#3 if ((x.d)!=null) traversare_recursiv(x.d);}

Pre In Post====================1 2 2

2 1 33 3 1

Traversarea iterativa* in cazul traversarii iterative e necesara folosirea unei structuri auxiliare de tip stiva

public void traversare_interativa(NodA x) {//Stiva stv = new Stiva();stv.push(x);while (!stv.isEmpty()) {

NodA xt=stv.pop();#1 System.out.println(xt.val);// deoarece structura auxiliara e o stiva pt a vizita st apoi dr// acestia trebuie introdusi invers ca ordine#2 if (xt.d!=null) stv.push(xt.d);#3 if (xt.s!=null) stv.push(xt.s);

}}

* pentru adresarea iterativa InOrdine si PostOrdine trebuie sa cunoastem cand traversam un nod si cand e vizitat* este posibil ca un nod sa-l traversez de 2 ori si sa-l vizitez 1 data. (vizitare=afisare)* vom folosi un parametru o variabila care va indica starea nodului

1) este pt prima data in stiva2) a fost anterior in stiva

public void traversare_iterativa(NodA x) {Stiva stv=new Stiva x();stv.push(new Nod(x,0));while (stv.isEmpty()) {

Nod x=stv.pop();if (xt.x.s==null && xt.x.d==null)

System.out.println(xt.x.val);else if (xt.z==1)

System.out.println(xt.x.val);else {

if (xt.t.d!=null) stv.push(new Nod X(xt.x.d,0);if (xt.t.s!=null) stv.push(new Nod X(xt.x.s,0);stv.push(new Nod x(xt.x,1));

}}

}

Pre In Post===================1 1 32 3 13 2 2

Traversarea in latime* se foloseste o structura auxiliara de tip coada- ordinea de introducere a nodurilor in coada este de la stanga la dreapta pe nivelpublic void Traversare_latima(NodA x) {

Coada q=new Coada();q.put(x);while (!q.isEmpty()) {

NodA xt=q.get();System.out.println(xt.val);if (xt.s!=null) q.put(xt.s);if (xt.d!=null) q.put(xt.d);

}}

HEDGCFBA => ABFCGDEH