Creeaza.com - informatii profesionale despre


Cunostinta va deschide lumea intelepciunii - Referate profesionale unice
Acasa » referate » informatica
Cautarea tabelara (Table search)

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) <= Ei:0i<m:((Aj:0j<i:xj=yj)&(xi<yi)) [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 = so,s1,s2,,sn-1 unde s1,,sn-1 sunt caracterele sirului iar so 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]:

Aj:0j i:xj=yjchr(0)  [4.3.1.e]

((x yi)OR(xi=yi=chr(0)))&(Aj:0 j<i:xj=y chr(0))   [4.3.1.f]



Aceasta conditie stabileste:

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

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

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

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

Intrucat in aceasta situatie xi este cel mai mic caracter, aceasta echivaleaza cu x< y, 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.







Politica de confidentialitate







creeaza logo.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Comentarii literare

ALEXANDRU LAPUSNEANUL COMENTARIUL NUVELEI
Amintiri din copilarie de Ion Creanga comentariu
Baltagul - Mihail Sadoveanu - comentariu
BASMUL POPULAR PRASLEA CEL VOINIC SI MERELE DE AUR - comentariu

Personaje din literatura

Baltagul caracterizarea personajelor
Caracterizare Alexandru Lapusneanul
Caracterizarea personajelor negative din basmul
Dialogul- mijloc de caracterizare a personajelor - d-l goe, de i. l. caragiale

Tehnica si mecanica

Determinarea indicilor Micuum (rezistentei), a reactivitatii, umiditatii, si analizei granulometrice a cocsului
Principii de calcul al instalatiei de ungere
Rectificarea - Pietrele abrazive - Masini de rectificat

Economie

Studiul comportamentului de cumparare de apa minerala in randul populatiei din bucuresti
Piata si politica financiara - Definirea si continutul pietei financiare
Bursele de valori

Geografie

Turismul pe terra
Vulcanii Și mediul
Padurile pe terra si industrializarea lemnului



Operatiile de inmultire si impartire in virgula flotanta
E-mail-ul ca instrument al cercetarii
Forum-ul de discutii online ca instrument de e-marketing
SISTEMUL DE OPERARE MS-DOS
PROCESE
Evolutia calculatoarelor
VARIABILE
UTILIZAREA CONCEPTELOR SPECIFICE ORGANIZATIILOR VIRTUALE IN PRACTICA MEDICALA DIN ROMANIA



Termeni si conditii
Contact
Creeaza si tu