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







.com Copyright © 2022 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 Proiect didactic Clasa: a-IX-a, Luarea deciziilor
 PROIECT DIDACTIC 3-5 ani dezvoltarea limbajului si a comunicarii orale - „Cine face, ce face”
 PROIECT MOTOR ASINCRON - Determinarea parametrilor schemei echivalente si a caracteristicilor de functionare in regim stabilizat de la gol la sarcina
 TEMA DE PROIECTARE - arbore de masina rotativa

Lucrari de diploma

vezi toate lucrarile de diploma
 PROIECT DE DIPLOMA CHIRURGIE ORO-MAXILO-FACIALA - SUPURATIILE LOJELOR PROFUNDE DE ETIOLOGIE ODONTOGENA
 Relatiile diplomatice dintre Romania si Austro- Ungaria din a doua jumatate a secolului al XIX-lea
 LUCRARE DE DIPLOMA MANAGEMENT - MANAGEMENTUL CALITATII APLICAT IN DOMENIUL FABRICARII BERII. STUDIU DE CAZ - FABRICA DE BERE SEBES
 Lucrare de diploma tehnologia confectiilor din piele si inlocuitor - proiectarea constructiv tehnologica a unui produs de incaltaminte tip cizma scurt

Lucrari licenta

vezi toate lucrarile de licenta
 Lucrare de licenta contabilitate si informatica de gestiune - politici si tratamente contabile privind leasingul (ias 17). prevalenta economicului asupra juridicului
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta - cercetare si analiza financiara asupra deseurilor de ambalaje la sc.ambalaje sa
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 Atestat la informatica cu tema “gestionarea unui magazin de confectii”
 Proiect atestat electrician constructor - tehnologia montarii instalatiilor electrice interioare
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 ATESTAT PROFESIONAL TURISM SI ALIMENTATIE PUBLICA, TEHNICIAN IN TURISM

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