Tipuri structurate

Tipuri structurate

1. Structura tablou. Tipul de date abstract tablou.

Un tablou este o structura omogena el constand dintr-o multime de componente de acelasi tip numit tip de baza.

Tabloul este o structura de date cu acces direct (random-acces), deoarece oricare dintre elementele sale sunt direct si in mod egal accesibile.

Pentru a preciza o componenta individuala, numelui intregii structuri i se asociaza un indice care selecteaza pozitional componenta dorita.

La definirea unui tablou se precizeaza:

o      (1) Metoda de structurare, care este implementata direct de limbaj(ARRAY) ,

o      (2) Numele tipului de date rezultat (TipTablou) ,

o      (3) Tipul de baza al tabloului (TipElement) s

o      (4) Tipul indice (TipIndice).

EXEMPLU:

TYPE TipTablou=ARRAY[1..n] OF TipElement;

VAR x,y:TipTablou;

TDA Tablou

Model matematic: Secventa de elemente de acelasi tip. Indicele asociat apartine unui tip ordinal finit. Exista o corespondenta biunivoca intre indici si elementele tabloului.

Notatii:

TipElement -tipul elementelor tabloului;

a - tablou unidimensional;

i - index;[1.4.1.e]

e - obiect de tip TipElement.

Operatii

DepuneInTablou(a,i,e) - procedura care depune valoarea lui e in cel de-al i-lea element al tablolui a;

e:= FurnizeazaDinTablou(a,i) - functie care returneaza valoarea celui de-al i-lea element al tabloului a.

//Exemplu de implementare - Varianta C /*1.4.1.f*/

#define NumarMaxElem valoareIntreaga

typedef TipElement; /*se defineste tipul elementelor ex.

typedef float TipElement dar poate fi si

un tip definit de programator, sau un tip

incomplet definit*/

typedef TipOrdinal TipIndex; /*unde TipOrdinal este un tip ordinal

(fundamental sau definit anterior)*/

typedef TipElement TipTablou[NumarMaxElem];

TipIndex i;

TipTablou a;

TipElement e;

a[i]=e; /*DepuneInTablou(a,i,e)*/

e=a[i]; /*FurnizeazaDinTablou(a,i)*/

In locul unui indice constant poate fi utilizata o expresie index (de indice). Evaluarea acestei expresii in timpul executiei programului, conduce la determinarea componentei selectate.

Daca tipul de baza al unui tablou este de asemenea ordonat, atunci in cadrul tipului tablou poate fi definita o relatie de ordonare naturala.

Ordonarea naturala a doua tablouri de acelasi tip este determinata de catre acele componente corespunzatoare care sunt diferite si care au cel mai mic indice.             (2,3,5,8,9) >(2,3,5,7,11)

'CAPAC' < 'COPAC'

TYPE TipTablou=ARRAY[1..n] OF TipElement;

VAR x,y:TipTablou; [1.4.1.d]

(x<y) <=> E_k:0<k<=n:((A_i:0<i<k:x[i]=y[i])&(x[k]<y[k]))

Un exemplu clasic in acest sens il constituie ordonarea lexicografica a tablourilor de caractere.

Deoarece toate componentele unui tip tablou TipTablou apartin aceluiasi tip de baza TipElement avem:

Card (TipTablou) = Card (TipElement) ^{Card (TipIndice)} .

Tablouri de o singura dimensiune sau tablouri liniare.

Accesul la oricare element al unui astfel de tablou se realizeaza utilizand un singur indice in mecanismul de selectie.

• TipElement precizat la definirea unui tip de date tablou poate fi la randul sau un tip tablou. Prin acest mecanism se definesc tablourile de mai multe dimensiuni.

Astfel de tablouri se numesc de obicei matrice

Accesul la un element al matricei se realizeaza utilizand un numar de indici egal cu numarul de dimensiuni ale matricei

mat[i,j,k,. ,m,n].

2. Tehnici de cautare in tablouri

Formularea problemei: se presupune ca este data o colectie de date, in care se cere sa se localizeze (fixeze) prin cautare un anumit element.

Se considera ca multimea celor n elemente este organizata in forma unui un tablou liniar: a: ARRAY[1..n] OF Tip Element;

De regula TipElement are o structura de articol cu un camp specific pe post de cheie.

Sarcina cautarii este aceea de a gasi un element al tabloul a, a carui cheie este identica cu o cheie cautata x .

Indexul i care rezulta din procesul de cautare satisface relatia a[i].cheie=x, si el permite accesul si la alte campuri ale elementului localizat.

Vom presupune in continuare ca TipElement consta numai din campul 'cheie', adica el este chiar cheia. Cu alte cuvinte se va opera de fapt cu un tablou de chei.

2.1. Cautarea liniara

Atunci cand nu exista nici un fel de informatii referitoare la colectia de date in care se face cautarea, tehnica evidenta este aceea de a parcurge in mod secvential colectia prin incrementarea indexului de cautare pas cu pas.

/*cautare liniara (while) - varianta C*/

/*1.4.2.1.a*

TipElement a[NumarMaxElem];

TipElement x;   

int i=0;

while ((i<n-1) && (a[i]!=x))

i++;

if (a[i]!=x )

else

Exista doua conditii care finalizeaza cautarea:

Elementul a fost gasit adica a[i] = x ;

Elementul nu a fost gasit dupa parcurgerea integrala a tabloului

Invariantul buclei, care de fapt este conditia care trebuie indeplinita inaintea fiecarei incrementari a indexului i , este:(1<= i < n)&(A_k:1 <= k < i:a[k]<> x) si el exprima faptul ca pentru valori ale lui  k < i , nu exista coincidenta.

Conditia de terminare va fi:

((i = n)OR(a[i]= x))&(A_k:1 <= k< i:a[k]<> x)  

/*cautare liniara (do) - varianta C*/   /*1.4.2.1.b*/

TipElement a[NumarMaxElem];

TipElement x;

int i=-1;

dowhile ((i<n-1) && (a[i]!=x))

if (a[i]!=x )

else

In legatura cu acest algoritm se precizeaza urmatoarele:

La parasirea buclei mai trebuie realizata o comparatie a lui a[i] cu x in vederea stabilirii existentei sau nonexistentei elementului cautat;

Daca elementul este gasit, el este elementul cu cel mai mic indice (daca exista mai multe elemente identice).

Dupa cum se observa fiecare pas al algoritmului necesita evaluarea expresiei booleene (care este formata din doi factori) si incrementarea indexului.

Acest proces poate fi simplificat si in consecinta cautarea poate fi accelerata, prin simplificarea expresiei booleene.

O solutie de a simplifica expresia este aceea de a gasi un singur factor care sa-i implice pe cei doi existenti.

Acest lucru este posibil daca se garanteaza faptul ca va fi gasita cel putin o potrivire.

In acest scop se completeaza tabloul a cu un element aditional a[n+1] caruia i se atribuie initial valoarea lui x (elementul cautat). Tabloul devine:

a: ARRAY[1..n+1] OF TipElement;

Elementul x pozitionat pe ultima pozitie a tabloului se numeste fanion, iar tehnica de cautare, tehnica fanionului.

Evident, daca la parasirea buclei de cautare i > n , rezulta ca elementul cautat nu se afla in tablou.

/*cautare liniara metoda fanionului (while) - varianta C*/

/*1.4.2.1.c*/

TipElement a[NumarMaxElem+1];

TipElement x;

int i=0;

a[NumarMaxElem]=x;   

while (a[i]!=x)

i++;

if (i == NumarMaxElem)

else

Conditia de terminare dedusa din acelasi invariant al ciclului este:

(a[i]= x)&(A_k:1 <= k < i:a[k]<> x)

2.2. Cautarea binara

Procesul de cautare poate fi mult accelerat daca se dispune de informatii suplimentare referitoare la datele cautate.

Este bine cunoscut faptul ca o cautare se realizeaza mult mai rapid intr-un masiv de date ordonate (spre exemplu intr-o carte de telefoane sau intr-un dictionar).

In continuare se prezinta un algoritm de cautare intr-o structura de date ordonata, adica care satisface conditia:

VAR a:ARRAY[1..n] OF TipElement;

A_k:1 < k <= n:a[k-1]<= a[k] [1.4.2.2.a]

Ideea de baza:

Se inspecteaza un element aleator a[m] si se compara cu elementul cautat x.

Daca este egal cu x cautarea se termina;

Daca este mai mic decat x , se restrange intervalul de cautare la elementele care au indici mai mari ca m;

Daca este mai mare decat x , se restrange intervalul la elementele care au indicii mai mici ca m.

In consecinta rezulta algoritmul denumit cautare binara.

Variabilele s si d sunt de tip indice si ele precizeaza limitele stanga respectiv dreapta ale intervalului in care elementul ar mai putea fi gasit:

/*cautare binara - varianta C*/

/*1.4.2.2.b*/

TipElement a[n]; /*n>0*/

TipElement x;

TipIndice s,d,m;

int gasit;

s=0; d=n-1; gasit=0;

while((s<=d)&&(!gasit))

if(gasit) /*avem o coincidenta la indicele i*/

Invariantul buclei, adica conditia ce trebuie indeplinita inaintea fiecarui pas este

(s <= d)&(A_k:1 <= k < s:a[k]< x)&(A_k:d < k <= n:a[k] > x)

Conditia de terminare este:

gasit OR ((s>d)&(A_k:1<=k<s:a[k]<x)&(A_k:d<k<=n:a[k]>x))

Alegerea lui m este arbitrara in sensul ca ea nu influenteaza corectitudinea executiei algoritmului, in schimb influenteaza eficienta sa.

Solutia optima in acest sens este alegerea elementului din mijlocul intervalului, intrucat ea elimina la fiecare pas jumatate din intervalul in care se face cautarea.

In consecinta rezulta ca numarul maxim de pasi de cautare va fi O(log ₂ n),

Aceasta performanta reprezinta o imbunatatire remarcabila fata de cautarea liniara unde numarul mediu de cautari este n / 2 .

Eficienta cautarii binare poate fi imbunatatita daca se interschimba instructiunile IF intre ele.

O imbunatatire de fond insa a eficientei se poate obtine - ca si in cazul cautarii liniare - prin simplificarea conditiei de terminare.

Acest lucru se poate realiza daca se renunta la ideea de a termina algoritmul de indata ce s-a stabilit coincidenta.

La prima vedere acest lucru nu pare prea intelept, insa la o examinare mai atenta, se poate observa ca castigul in eficienta la fiecare pas este mai substantial decat pierderea provocata de cateva comparatii suplimentare de elemente.

Se reaminteste faptul ca numarul de pasi este log ₂ n .

Solutia cea mai rapida are la baza urmatorul invariant:

(A_k:1<=k<s:a[k]<x)&(A_k:d<k<=n:a[k]>x)

Procesul de cautare continua pana cand intervalul de cautare ajunge de dimensiune banala (0 sau 1 element). Aceasta tehnica este ilustrata in [1.4.2.2.c].

//cautari binare - varianta C

int cautare_binara(int x,int a[],int n)while(a[m]-x && s<=d);

return(a[m]-x)?n:m;

2.3. Tehnica cautarii prin interpolare

O alta imbunatatire posibila a metodei de cautare binara, consta in a determina cu mai multa precizie locul in care se face cautarea in intervalul curent, in loc de a selecta intotdeauna elementul de la mijloc.

Astfel cand se cauta intr-o structura ordonata, spre exemplu cartea de telefon, un nume incepand cu B este cautat la inceputul cartii, in schimb un nume care incepe cu V este cautat spre sfarsitul acesteia.

Aceasta metoda, numita cautare prin interpolare, necesita o simpla modificare in raport cu cautarea binara.

Astfel, in cautarea binara, noul loc in care se face accesul este determinat cu ajutorul relatiei, unde s si d sunt limitele intervalului de cautare:

Urmatoarea evaluare a lui m , numita cautare prin interpolare se considera a fi mai performanta: