Cautarea tabelara (Table search)

Cautarea tabelara (Table search)

O cautare intr-un tablou se numeste si cautare tabelara ('table search'), cu deosebire in situatia in care cheile sunt la randul lor obiecte structurate spre exemplu tablouri de numere sau de caractere.

Cazul mai des intalnit este acela in care cheile tablourilor sunt siruri de caractere sau cuvinte.

In continuare, pentru obiectivele acestui paragraf se definesc tipul sir respectiv relatia de ordonare (lexicografica) a doua siruri x si y dupa cum urmeaza [4.3.1.a,b,c]:

TYPE TipSir = ARRAY[0..m-1] OF char;  [4.3.1.a]

(x<y) <= E_i:0i<m:((A_j:0j<i:x_j=y_j)&(x_i<y_i)) [4.3.1.c]

Pentru a stabili coincidenta, este necesara stabilirea egalitatii tuturor caracterelor corespunzatoare din sirurile comparate.

Presupunand ca lungimea acestora este mica, (spre exemplu mai mica decat 30), in acest scop se poate utiliza cautarea liniara.

In cele mai multe aplicatii se lucreaza cu siruri de lungime variabila, asociindu-se fiecarui sir o informatie suplimentara referitoare la lungimea sa.

Utilizand tipul sir anterior definit, lungimea nu poate depasi valoarea maxima m.

Desi este limitativa, aceasta schema permite suficienta flexibilitate evitand alocarea dinamica a memoriei.

Sunt utilizate in mod frecvent doua moduri de reprezentare a lungimii sirurilor:

(1) Lungimea este specificata implicit, plasand pe ultima pozitie a sirului (dupa ultimul caracter) un caracter prestabilit (de exemplu caracterul avand codul 0 (CHR(0)).

Pentru aplicatiile ce urmeaza este important ca acesta sa fie cel mai mic caracter al setului de caractere.

In limbajul C este chiar codul cu valoarea zero.

(2) Lungimea sirului este memorata in mod explicit ca si prim element al tabloului.

Astfel un sir are forma s = s_o,s₁,s₂,,s_n-1 unde s₁,,s_n-1 sunt caracterele sirului iar s_o memoreaza lungimea sirului de caractere.

Avantajul acestei solutii: lungimea sirului este direct disponibila;

Dezavantajul: lungimea este limitata la valoarea maxima reprezentabila pe unitatea de informatie alocata unui caracter, de regula un octet (255).

In continuare, pentru precizarea lungimii unui sir se va utiliza modalitatea (1), respectiv cea bazata pe caracterul marker, definit drept caracterul al carui cod are valoarea 0.

In aceste conditii, compararea a doua siruri va lua forma [4.3.1.d]:

VAR x,y: TipSir;

[4.3.1.d]

i:= 0;

WHILE (x[i]=y[i]) AND (x[i]<>chr(0)) DO i:= i+1;

Caracterul corespunzator codului 0 actioneaza ca si   fanion.

Invariantul buclei, adica conditia a carei indeplinire determina reluarea buclei (ciclului), este [4.3.1.e], iar conditia de terminare [4.3.1.f]:

A_j:0j i:x_j=y_jchr(0)  [4.3.1.e]

((x_i  y_i)OR(x_i=y_i=chr(0)))&(A_j:0 j<i:x_j=y_j  chr(0))   [4.3.1.f]

Aceasta conditie stabileste:

Coincidenta celor doua siruri x = y daca la terminarea buclei x_i= y_i= chr(0), sau

Inegalitatea x < y(x > y) daca la terminarea buclei x_i < y_i (x_i > y_i).

Se face precizarea ca inegalitatea x_i < y_i poate apare si in situatia in care x coincide cu y dar x e mai scurt decat y.

In acest caz se obtine x_i  y_i dar x_i = chr(0) (s-a ajuns la sfarsitul sirului x).

Intrucat in aceasta situatie x_i este cel mai mic caracter, aceasta echivaleaza cu x_i < y_i , deci x < y, ceea ce este corect inclusiv din punctul de vedere al ordonarii lexicografice.

In acest context, cautarea tabelara este de fapt o cautare incuibata care consta:

Dintr-o parcurgere a intrarilor unei tabele de siruri,

In cadrul fiecarei intrari, dintr-o secventa de comparatii intre componentele individuale ale sirului curent si cele ale sirului cautat.

Se considera urmatoarele structuri de date [4.3.1.g], unde T este tabela de siruri iar x: TipSir, argumentul cautat.

CONST n = ;

m = ;

TYPE TipSir = ARRAY[0..m‑1] OF char;

TipTabela = ARRAY[0..n‑1] OF TipSir; [4.3.1.g]

VAR T: TipTabela;

Presupunand ca n este suficient de mare si ca tabela este ordonata alfabetic, se poate utiliza cautarea binara.

Utilizand algoritmul cautarii binare si compararea a doua siruri, se poate redacta urmatoarea varianta de cautare tabelara [4.3.1.h].

FUNCTION CautareTabelara(VAR T: TipTabela; VAR x: TipSir;

VAR poz: integer): boolean;

VAR i,s,d,mij: integer;

BEGIN

s:= 0;d:= n;

WHILE s<d DO [4.3.1.h]

BEGIN

mij:= (s+d) div 2; i:= 0;

WHILE (T[m,i]=x[i])AND(x[i]<>chr(0)) DO i:=i+1;

IF T[m,i]<x[i] THEN s:= m+1

ELSE d:= m

END;

IF d<n THEN

BEGIN

i:= 0;

WHILE (T[d,i]=x[i])AND(X[i]<>chr(0)) DO

i:= i+1

END;

poz:= d;

CautareTabelara:= (d<n)AND(T[d,i]=x[i])

END;

Functia CautareTabelara primeste ca parametri de intrare tabela T si sirul de cautat x si returneaza true respectiv false dupa cum cautarea este reusita sau nu.

In cazul unei cautari reusite, in variabila de iesire poz se returneaza intrarea corespunzatoare din tabela;

In cazul unei cautari nereusite variabila de iesire poz returneaza valoarea 0.

Se observa ca T si x care sunt siruri, se declara cu VAR, pentru a li se transmite (prin stiva) doar adresa.