Structuri de date fundamentale

Structuri de date şi algoritmi-laborator-

s.l. dr. ing. Ciprian-Bogdan ChirilăUniversitatea Politehnica Timişoara

2014

Cuprins TDA Tablou

Căutare liniară Căutare binară (logaritmică) Căutare prin interpolare

TDA Articol TDA Mulţime TDA Secvenţă Concluzii

TDA Tablou Secvenţă de elemente de acelaşi

tip numit tip de bază; Accesul se realizează cu ajutorul

unui index asociat de tip ordinal finit; ex. int x=tab[7]

Indexul precizează poziţia unui element în cadrul tabloului; in C primul index al unui tablou este 0

(zero)

Exemplu - cod C#include <stdio.h>int tab[100];int main(){

tab[0]=12;tab[7]=34;printf("%d\n",tab[0]);printf("%d\n",tab[7]);

return 0;}

Căutarea liniară Se compară pe rând elementele

tabloului cu x (elementul căutat) până când fie: se găseşte egalitatea tab[i]=x s-a ajuns la sfârşitul tabloului.

Căutarea liniară – demo

87 12 48 22 69 75 31

i=0 x=69 69=87 ? nu! 87 12 48 22 69 75 31

i=1 x=69 69=12 ? nu! 87 12 48 22 69 75 31

i=2 x=69 69=48 ? nu! 87 12 48 22 69 75 31

i=3 x=69 69=22 ? nu! 87 12 48 22 69 75 31

i=4 x=69 69=69 ? da! 87 12 48 22 69 75 31

0 1 2 3 4 5 6

Căutarea liniară – cod C#include <stdio.h>int tab[8]={12,34,66,1,2,8,92,66};int cautareLiniara(int *tab, int dim, int x){

int i=0;while(tab[i]!=x && i<dim){

i++;}if(tab[i]==x){

return i;}return -1;

}

Căutarea liniară – cod Cint main(){ int poz;

poz=cautareLiniara(tab,8,92);//poz=cautareLiniara(tab,8,93);if(poz!=-1){

printf("Elementul s-a gasit pe pozitia %d\n",poz);}else{

printf("Elementul nu s-a gasit\n"); }

return 0;}

Căutarea binară (logaritmică) Se aplică numai pe tablouri

ordonate Se înjumătăţeşte repetat intervalul

în care se face căutarea Performanţa: O(log2n)

Căutarea binară – demo

s=0 d=6 m=3 x=75 75 ? 48 > ! 12 22 31 48 69 75 87

0 1 2 3 4 5 6

12 22 31 48 69 75 87

s=3 d=6 m=4 x=75 75 ? 69 > ! 12 22 31 48 69 75 87

s=4 d=6 m=5 x=75 75 ? 75 = ! 12 22 31 48 69 75 87

Căutarea binară – cod C#include <stdio.h>int tab[8]={1,2,8,12,34,66,87,92};int cautareBinara(int *tab, int dim, int x){

int s,d,m;s=0; d=dim-1;do{

m=(s+d)/2;if(x>tab[m]){

s=m+1;}else{

d=m-1;}

}while((tab[m]!=x) && (s<=d));

Căutarea binară – cod Cif(tab[m]==x)

{return m;

}return -1;

}int main(){

int poz;poz=cautareBinara(tab,8,66);//poz=cautareBinara(tab,8,33);

if(poz!=-1) { printf("Elementul s-a gasit pe pozitia %d\n",poz); } else { printf("Elementul nu s-a gasit\n"); }

return 0;}

Căutarea prin interpolare Similară cu căutarea binară Foloseşte altă formulă pentru

calculul lui m: m=s+(x-tab[s])*(d-s)/(tab[d]-tab[s])

Inspirată după procedeul căutării într-o carte de telefon

Căutarea prin interpolare#include <stdio.h>int tab[8]={1,2,8,12,34,66,87,92};int cautareInterpolare(int *tab, int dim, int x){

int s,d,m;

s=0;d=dim-1;do{

m=s+(x-tab[s])*(d-s)/(tab[d]-tab[s]);if(x>tab[m]){

s=m+1;}else{

d=m-1;}

}while((tab[m]!=x) && (s<d) && (tab[s]==tab[d]) &&

(x>=tab[s]) && (x<=tab[d]));

Căutarea prin interpolareif(tab[m]==x){

return m;}return 0;

}

int main(){ int poz;

poz=cautareInterpolare(tab,8,66);//poz=cautareInterpolare(tab,8,33);

if(poz!=-1) { printf("Elementul s-a gasit pe pozitia %d\n",poz); } else { printf("Elementul nu s-a gasit\n"); }

return 0;}

TDA Articol Structură alcătuită dintr-o colecţie

finită de elemente numite câmpuri; Câmpurile pot aparţine unor tipuri

diferite; Accesul la câmpuri se face prin

identificatori;

Exemplu - cod C#include <stdio.h>#include <string.h>struct student{

char nume[20];char prenume[20];int varsta;

};struct student s1,s2;int main(){

strcpy(s1.nume,"Nedelcu");strcpy(s1.prenume,"Nicoleta");s1.varsta=21;strcpy(s2.nume,"Dragan");strcpy(s2.prenume,"Cerasela");s2.varsta=21;printf("%s %s %d\n",s1.nume,s1.prenume,s1.varsta);printf("%s %s %d\n",s2.nume,s2.prenume,s2.varsta);

return 0;}

TDA Mulţime Structură alcătuită din elemente ce

aparţin unui tip ordinal finit (tip de bază);

Sunt membre ale unei mulţimi matematice;

TDA Mulţime – operaţii elementare DepuneMultime(S,

T) EgalitateMultime(S

,T) ApartineMultime(S,

e) Submultime(S,T) Reuniune(S,T) Intersectie(S,T) Diferenta(S,T) MultimeVida(S) CreazaMultime(e)

Notaţii:

S, T, V – mulţimi

e – obiect (valoare) de tip de bază

TDA Secvenţă Structură formată din elemente de

acelaşi tip (tipul de bază); Accesul la elemente este

secvenţial şi se efectuează cu ajutorul unui pointer;

La un moment dat este accesibil un singur element;

TDA Secvenţă – operaţii elementare

Rescrie(f) DepuneSecventa(f,e) ResetSecventa(f) EOF(f) FurnizeazaSecventa(f,e

)

Notaţii:

f – secvenţa

e – obiect (valoare) de tip de bază

Exemplu - cod C#include <stdio.h>FILE *f;char buf[20];int main(){

if((f=fopen("fisier.txt","wt"))==NULL){

printf("Eroare la creare fisier..."); return -1;}fprintf(f,"Buna_ziua_domnule_student!");fclose(f);if((f=fopen("fisier.txt","rt"))==NULL){

printf("Eroare la deschidere fisier..."); return -2;}while(!feof(f)){

fscanf(f,"%s",buf); printf("%s",buf);}fclose(f);return 0;

}

Recapitulare

Despre ce am discutat azi ? 4 TDA:

tablou, articol, multime, secventa 3 algoritmi de cautare pe tablouri:

liniara, binara, interpolare ultimii 2 functioneaza numai pe

tablouri sortate