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 © 2019 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE Clasa: I Matematica - Adunarea si scaderea numerelor naturale de la 0 la 30, fara trecere peste ordin
 Proiect didactic Grupa: mijlocie - Consolidarea mersului in echilibru pe o linie trasata pe sol (30 cm)
 Redresor electronic automat pentru incarcarea bateriilor auto - proiect atestat
 Proiectarea instalatiilor de alimentare ale motoarelor cu aprindere prin scanteie cu carburator

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 Proiect diploma Finante Banci - REALIZAREA INSPECTIEI FISCALE LA O SOCIETATE COMERCIALA
 Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”

Lucrari licenta

vezi toate lucrarile de licenta
 CONTABILITATEA FINANCIARA TESTE GRILA LICENTA
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 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
 Proiect atestat informatica- Tehnician operator tehnica de calcul - Unitati de Stocare
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 Proiect atestat tehnician in turism - carnaval la venezia




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