algoritmi de cautare

Cândea I. Ovidiu-Radu Algoritmi de căutare

CUPRINS

CAPITOLUL 1. Introducere

CAPITOLUL 2. Căutarea în structuri de date

2.1 Despre căutare 2.2 Căutarea în baze de date 2.3 Căutarea în fişiere externe 2.4 Căutarea în tablouri 2.5 Căutarea în liste înlănţuite 2.6 Căutarea în arbori 2.7 Căutarea în tabele de dispersie 2.8 Căutarea în grafuri

CAPITOLUL 3. Căutarea pe internet

CAPITOLUL 4. Prezentarea aplicaţiei

BIBLIOGRAFIE

1


CAPITOLUL 1

INTRODUCERE

Scopul acestei lucrării intitulată “Algoritmi de căutare” este studiul operaţiilor de

căutare, analizei complexităţii şi eficienţei diferiţilor algoritmi de căutare, precum şi

implementarea lor concretizată prin obţinerea unei aplicaţii care unifică toate metodele de

căutare prezentate din punct de vedere teoretic.

Am ales această temă deoarece în această eră a informaţiei în care noi ne aflăm, când

informaţia reprezintă puterea, căutarea, respectiv regăsirea unor anumte informaţii din cadrul

unei colecţii imense de date într-un timp foarte scurt reprezintă un factor important în buna

desfăşurare a oricărei activităţi.

Informaţia (stocată pe suport magnetic sau optic) poate lua diferite forme de

organizare numite generic structuri de date. Indiferent dacă informaţia noastră se află

memorată într-o bază de date, fişier extern, tablou, listă înlănţuită, tabelă de dispersie etc. este

de dorit să se poată avea accesul cât mai rapid la respectiva informaţie, deci timpul de căutare

să tindă către 0.

Realizarea aplicaţiei denumită “Căutare în structuri de date” precum şi organizarea

prezentei lucrări a fost făcută în funcţie de diferitele structuri de date. Ceea ce am încercat să

realizez a fost să scot în evidenţă caracteristicile diferitelor structuri prezentând modalităţile în

care se poate căuta o anume înregistrare în respectiva structură, dar şi să fac o analiză pentru

determinarea algoritmului de căutare cu cel mai mare randament într-o anumită situaţie.

Lucrarea este structurată pe patru mari capitole.

Capitolul “Căutarea în structuri de date” cuprinde opt subcapitole. După o scurtă

trecere în revistă, în subcapitolul “Despre căutare” a diferitelor noţiuni (algoritm, timp de

execuţie ş.a.) care aveau să apară pe parcursul întregii lucrari s-a trecut la analiza algoritmilor

de căutare pe structuri de date. S-au analizat atât colecţiile de date de pe suport extern (baze

de date, fişiere externe) precum şi cele memorate în memoria RAM a calculatorului.

Am rezervat un capitol înterg căutării pe Internet, dorind să subliniez importanţa

reţelei care acum în secolul XXI reprezintă una din cele mai mari resurse pentru informaţii.

Rezultatul căutării, găsirea deci a informaţiilor necesare într-un domeniu atât de vast cum este

Internetul ar fi putut deveni o adevărată problemă, dacă nu era să-şi facă apariţia motoarele

2


de căutare. Capitolul “Căutarea pe Internet” cuprinde descrierea structurii şi funcţionalităţii

acestor motoare de căutare care reprezintă calea cea mai uşoară de găsire a informaţiilor pe

Web, ele putând fi văzute de fapt ca nişte importante instrumente de acces rapid la informaţie.

Capitolul final reprezintă descrierea aplicaţiei ataşate acestei lucrări, aplicaţie care a

fost realizată în limbaj Java folosind KawaPro cu pachetul JDK 1.3.0.

Aplicaţia cuprinde mai multe ferestre, corespunzătoare unei anumite structuri de date,

accesul la aceste ferestre făcându-se dintr-o fereastră meniu.

Este o aplicaţie originală, partea cea mai utilă a ei în viaţa de zi cu zi fiind cea de

căutare în bază de date, putându-se constitui ca un ghid pentru găsirea informaţiilor despre

orice societate comercială din Sibiu, căutarea putându-se face după mai multe criterii.

Înregistrările acestei baze de date s-au folosit şi pentru popularea celorlalte structuri de

date pentru care au fost mai apoi implementaţi şi testaţi diferiţi algoritmi de căutare.

3


CAPITOLUL 2

2.1 DESPRE CĂUTARE

Apăruta iniţial ca un instrument matematic, gândirea algoritmică s-a transformat într-o

modalitate fundamentală de abordare a problemelor care nu au nimic de-a face cu matematica.

O definţie a noţiunii de algoritm este destul de greu de dat, însa este clar că ceea ce dă

generalitate noţiunii de algoritm este că el poate opera nu numai cu numere. Există algoritmi

algebrici, algoritmi logici, algoritmi genetici etc.

Universalitatea gândirii algoritmice este rezultatul conexiunii dintre algoritm si

calculator.

Un algoritm este reprezentat de o mulţime finită de reguli de calcul care indică

succesiunea de operaţii necesare rezolvării unui tip de problemă.

Ca o definiţie mai generală dată algoritmului s-ar putea spune ca acesta este o metodă

generală de rezolvare a unui anumit tip de problemă, metodă care se poate implementa pe

calculator. În acest context un algoritm este esenţa unei rutine.

Algoritmul mai poate fi văzut si ca o procedură care execută o anumita activitate.

Un algoritm se caracterizeaza prin două componente:

domeniul algoritmului

descrierea propriuzisă a algoritmului

Orice algoritm operează asupra unor date de intrare (Input), care sunt prelucrate

obţinându-se datele de ieşire (Output) sau altfel spus rezultatul scontat. Domeniul

algoritmului este reprezentat chiar de mulţimea obiectelor asupra cărora algoritmul lucrează

(această mulţime trebuie să fie cel mult numărabilă). În acest domeniu al algoritmului vor fi

incluse si rezultatele (datele de iesire).

Exemple de domenii de algoritmi:

mulţimea numerelor naturale

submulţimile unei mulţimi finite

mulţimea şirurilor finite de elemente dintr-o mulţime finită

4


Algoritmul este alcătuit din instrucţiuni, fiecare instrucţiune este formată din operaţii

elementare care se efectueaza asupra elementelor din domeniul algoritmului. Mulţimea

instrucţiunilor formează descrierea algoritmului. Instrucţiunile sunt executate de un agent

uman, mecanic sau in cazul lucrului cu calculatorul de către un agent electronic.

Operaţiile care constituie un algoritm trebuie să fie precizate foarte clar si pe deasupra

trebuie sa poată fi executate în timp finit.

Caracteristicile unui algoritm sunt:

generalitate - algoritmul trebuie să rezolve o întreaga clasă de probleme;

finititudine - algoritmul trebuie să cuprindă un număr finit de pasi, indiferent de datele de

intrare (Input);

determinism sau unicitate - la un moment dat se efectuează o singură operaţie bine

specificată si neambiguă

La executarea unui algoritm nu este necesar să se atingă toate operaţiile prevăzute în

ansamblul lor, dar cu seturi de date iniţiale alese corespunzător şi un număr corespunzător de

execuţii se vor putea atinge toate operaţiile prevăzute in algoritm.

Parcurgerea algoritmului de la început (start) la sfârsit (stop) se numeşte executarea

algoritmului.

Studiul algoritmilor presupune:

modelarea problemei (stabilirea cerinţelor) – trebuiesc riguros stabilite cerinţele

algoritmului şi care sunt datele de intrare si ieşire;

proiectarea algoritmilor - se face în general pe hârtie cu ajutorul unor reprezentări grafice

numite scheme logice, sau in pseudocod (un fel de limbaj de programare mult simplificat);

codificarea (exprimarea algoritmilor) - se face cu ajutorul instrucţiunilor unui limbaj de

programare, obţinandu-se un program care constituie implementarea algoritmului;

validarea algoritmilor - constă in demonstrarea corectitudinii cu care algoritmul rezolvă

problema. Algoritmul nu trebuie neaparat transpus într-un program pentru a demonstra că

funcţioneaza corect în orice situaţie (pentru orice set de date de intrare), deci trebuie avut în

vedere că pentru date din cele mai variate algoritmul să poată da nişte date de ieşire, cu alte

cuvinte algoritmul să poată da rezultate pentru orice date de intrare luate din domeniul

algoritmului;

5


analiza algoritmilor - de obicei se caută dacă există şi alţi algoritmi care să rezolve

problema cu pricina iar dacă există atunci se vor compara algoritmii intre ei in cea ce priveşte

funcţiile de operaţii, de locaţii, uşurinţa în înţelegere, etc; există un set de metrici bine stabilite

care măsoară diferiţi indicatori ai unui algoritm, metrici numite metrici software

- în cadrul acestei etape se au în vedere:

i)volumul datelor de pe calculator

ii)complexitatea algoritmilor

iii)convergenţa algoritmului respectiv;

- testarea programelor - această etapă are de obicei trei subfaze şi anume:

1)demonstrarea corectitudinii (de cele mai multe ori se face matematic)

2) testarea funcţionării programului cu date de intrare diferite

3) depanarea (identificarea erorilor de proiectare şi îndepărtarea lor)

În prezent algoritmii sunt elaboraţi folosind principiul programării structurate care

conduce la programarea procedurală structurată care presupune utilizarea a trei tipuri de

structuri de date:

structura liniara (:=)

structura alternativa (If then else)

structura repetitiva (While do, Do while, Repeat until, Do for)

Eficienţa unui algoritm poate fi exprimată in trei moduri (prin trei metode):

apriori sau teoretic - se face înainte de implementarea într-un program a algoritmului, prin

determinarea teoretică a resurselor necesare (timp, memorie) funcţie de mărimea cazului

considerat;

posterior sau empiric - se face după implementarea algoritmului prin rularea lui pentru

diferite cazuri;

metode hibrid - se determină teoretic forma funcţiei care descrie eficienţa algoritmului

(funcţie de mărimea cazului); această metodă depinde de nişte parametrii care se vor

determina dupa rularea programului;

Pentru a vedea ce algoritm este mai util să fie folosit într-o anumită problemă va trebui

să comparăm aceşti algoritmi. S-ar putea crede că atunci când se compară doi algoritmi care

6


rezolvă acelaşi tip de problemă, se pot face aprecieri de felul: “Algoritmul A este de doua ori

mai rapid decât algoritmul B”, dar în realitate acest tip de afirmaţie nu-şi prea are rostul.

Aceasta se întamplă din cauză că raportul se poate schimba radical atunci când se modifică

dimensiunea problemei (numarul elementelor prelucrate efectiv de cei doi algoritmi). Este

posibil ca, dacă numarul elementelor creşte cu 50%, algoritmul A să devină de trei ori mai

rapid decât B sau chiar să devină egal cu acesta.

Deci, pentru a putea compara timpul de execuţie a doi algoritmi vom avea nevoie de o

măsură legată direct de numărul de elemente asupra cărora acţionează algoritmii.

Într-un caz real timpul efectiv necesar pentru executarea instrucţiunilor unui algoritm,

notat cu T (exprimat in microsecunde sau în altă unitate de masura) este legat de viteza

microprocesorului, de eficienţa codului generat de compilator şi de alţi factori. Atunci însă

când comparăm doi algoritmi, nu ne interesează în mod deosebit performanţele

microprocesorului sau ale compilatorului; esenţial este să comparăm variaţiile duratei T

pentru diferite valori ale numărului de elemente asupra cărora acţionează algoritmii, nu să

calculăm efectiv valorile acesteia.

Principiul invarianţei spune că două implementări diferite ale aceluiaşi algoritm nu

diferă în eficienţă cu mai mult de o constantă multiplicativă. Spunem că un algoritm necesită

un timp de ordinul t, unde t este o funcţie dată (având ca argument mărimea cazului), dacă

există c>0 şi o implementare a algoritmului capabilă să rezolve orice caz al problemei într-un

timp de cel mult ct(n), unde n este mărimea cazului.

2.2 CĂUTAREA ÎN BAZE DE DATE

Sintagma bază de date reprezintă din punct de vedere informatic un set de date stocate

într-un mod organizat. Comparaţia cea mai simplă este biblioraftul (un loc fizic în care se pot

stoca date), în care însa pentru păstrarea datelor în ordine se vor folosi şi dosare, astfel datele

asociate se vor afla tot timpul într-un acelaşi dosar pentru o mai bună gestionare a acestora.

În domeniul bazelor de date, baza de date propriuzisă este reprezentată de biblioraft,

iar aceasta bază de date va fi compusă din unul sau mai multe tabele reprezentate în exemplul

dat de dosare.

Aşadar tabelul este un fişier structurat care poate stoca date de un anumit tip: o listă de

cumpărători, un catalog de produse, sau orice altă listă de informaţii. Esenţial este că datele

stocate într-un tabel sunt de acelaşi tip sau de pe aceeaşi listă.

7


Fiecare tabel dintr-o bază de date are un nume care-l identifică. Acest nume este unic,

el nu mai poate fi deţinut de nici un alt tabel din baza de date.

Tabelele au caracteristici şi proprieţati ce definesc felul în care datele sunt stocate în

ele precum şi ce fel de date sunt acceptate. Acest set de informaţii care descrie un tabel poartă

denumirea de schemă a tabelului.

Tabelele sunt formate din coloane care vor conţine câte o anumită informaţie din

tabelul respectiv. Prin prezenţa unui număr sporit de coloane se contribuie la divizarea datelor

care este un concept extrem de important. Prin divizarea datelor devine posibilă sortarea sau

filtrarea datelor dupa coloane specifice.

Fiecare coloana dintr-o bază de date are asociat un tip de date, care defineşte ce fel de

date să conţină coloana (număr, dată, text, însemnări etc.). Un altfel de tip de dată decât cel

predefinit nu va fi acceptat pentru o anumită coloană.

În tabele, datele sunt stocate pe linii, fiecare înregistrare fiind stocată pe propria ei

linie. Aşadar numărul înregistrărilor dintr-un tabel va fie egal cu numărul liniilor.

Fiecare linie dintr-un tabel trebuie să aibă o coloană (sau o serie de coloane) care o

identifică în mod unic. Această coloană (coloane) va fi cheia primară a tabelului. Ea va fi

utilizată pentru a face referire la o singura linie în cadrul tabelului. Cheia primară are o

importanţa deosebită pentru că în absenţa ei actualizarea sau ştergerea de linii specifice devine

foarte dificilă deoarece nu există nici o modalitate garantat sigură pentru a face referire numai

la liniile ce vor fi afectate.

Orice coloană dintr-un tabel poate fi stabilită drept cheie primară pentru acel tabel

dacă respectă următoarele condiţii:

Două linii nu pot avea aceeaşi valoare a cheii primare

Fiecare linie trebuie să aibă o valoare a cheii primare (coloana nu poate admite valori

NULL)

Coloana care conţine valorile cheilor primare nu poate fi nicidată modificată sau

actualizata

Valorile cheilor primare nu vor fi niciodata refolosite (daca o linie este ştearsa din tabel,

cheia ei primară nu poate fi atribuită altor linii noi)

Un alt tip de cheie foarte important este cheia externă care este o coloană dintr-un

tabel ale cărei valori trebuie declarate într-o cheie primara într-un alt tabel. Cheile externe

reprezintă o parte foarte importantă din asigurarea integritaţii referenţiale dar slujesc şi unui

alt scop foarte important. După ce o cheie externă este definită, sistemul de gestionare a bazei

de date (SGBD-ul) nu permite ştergerea de linii care au asociate linii în alte tabele. Practic

8


cheile externe stau la baza modelului relaţional pentru bazele de date reprezentând legăturile

(relaţiile) dintre tabele folosite în cadrul interogărilor pe două sau mai multe tabele (aici va

interveni şi noţiunea de JOIN).

Pornind de la premisa că majoritatea bazelor de date (cele cu adevărat importante)

acceptă limbajul SQL, în acest capitol numit “Căutarea în baze de date” mă voi rezuma la

cautarea în baze de date folosind limbajul neprocedural SQL.

SQL este abrevierea de la Structured Querry Language (limbaj structurat de

interogare) un limbaj conceput în mod specific pentru comunicarea cu bazele de date. Acest

limbaj a fost introdus pentru prima oară de IBM pentru a face feed-backul cu SGBD-ul

relaţional System R aflat la stadiul de prototip.

SQL este un limbaj neprocedural care a fost creat special pentru operaţii de acces la

înregistrările dintr-o bază de date relaţionala normalizată. Primul SGBD relaţional cu

adevarat comercial a fost introdus în 1979 de Oracle Corporation. Astăzi SQL a devenit un

standard industrial şi a fost declarat limbajul standard pentru sistemele de gestiune a bazelor

de date relaţionale.

Pentru a demonstra cât de răspândită este în ziua de azi folosirea limbajului SQL, iata

o listă cu unele din cele mai cunoscute aplicaţii/limbaje cu suport pentru limbajul SQL:

Allaire Cold Fusion, Allaire JRun 3.x, DB2, Informix Dynamic Server 7.x, Microsoft Acces,

Microsoft ASP, Microsoft Query, Microsoft SQL Server (6.x, 7, 2000), Microsoft Visual

Basic, Microsoft Visual C++, Oracle, Query Tool, Sybase, Java etc.

Pentru că SQL este un limbaj neprocedural, pot fi manipulate seturi întregi de date

deodată. Reducând codul de programare necesar pentru accesul la datele dintr-o bază de date,

costul pentru dezvoltarea şi menţinerea porţiunilor în care se face accesul la date într-o

aplicatie se reduce de asemenea. Şi asta este ceea ce face limbajul SQL pentru că acesta

lucrează pe câte un set de date deodată spre deosebire de celelalte modalitaţi convenţionale de

acces la date care prelucrau datele dintr-o baza de date (respectiv tabel) rând cu rând.

Sintaxa este foarte uşoară, bazată pe foarte puţine cuvinte numite cuvinte cheie care

sunt din limba engleză. Aşadar limbajul SQL este conceput pentru a face un lucru şi a-l face

bine şi anume să asigure o modalitate simplă şi eficientă de a citi şi a scrie o bază de date.

Aşa cum am mai precizat aproape toate bazele de date importante accepta limbajul

SQL şi în ciuda aparentei simplitaţi acesta este un limbaj foarte puternic care utilizat cu

inteligenţa poate efectua operaţii din cele mai complexe pe bazele de date.

Scrierea instrucţiunilor SQL necesită o buna înţelegere a felului în care a fost

proiectată baza de date. Fară a se ştii ce informaţii sunt stocate în fiecare tabel, cum sunt

9


asociate tabelele între ele şi care este divizarea reala a datelor într-o linie face imposibila

scrierea unui cod eficient în limbaj SQL.

Cele mai importante patru instrucţiuni din limbajul SQL sunt: SELECT, INSERT,

UPDATE şi DELETE care sunt folosite în următoarele situaţii:

SELECT: folosită pentru regăsirea informaţiilor memorate într-o bază de date (respectiv

într-unul sau mai multe dintre tabelele bazei de date)

INSERT: folosită pentru inserarea (adăugarea) de linii într-un tabel dintr-o bază de date

UPDATE: folosită pentru actualizarea (modificarea) datelor dintr-un tabel

DELETE: folosită pentru ştergerea datelor dintr-un tabel

Având în vedere tema lucrării de faţa vom studia instrucţiunea SELECT folosită dupa

cum s-a precizat mai sus la căutarea unor anumite date memorate în unul sau mai multe

tabele.

Pentru a putea fi folosita această instrucţiune este necesar să se precizeze cel putin

două lucruri şi anume: ce date doresc a fi regăsite şi de unde anume.

Ex: SELECT nume_coloana FROM nume_tabel;

În exemplul dat se vor regăsi datele de pe o singură coloana aflată în tabelul

nume_tabel de la toate înregistrarile tabelului (mai precis vor fi întoarse toate datele care au

fost introduse în tabelul nume_tabel în coloana nume_coloana). Se observă un nou cuvânt

cheie FROM care specifică numele tabelului din care vor fi regăsite datele.

Pentru a regăsi mai multe coloane dintr-un tabel vom avea o instrucţiune de tipul:

SELECT nume_coloana1, nume_coloana2 FROM nume_tabel;

unde în dreptul instrucţiunii SELECT pot fi scrise oricâte coloane din nume_tabel.

Dacă se doreşte regăsirea tuturor coloanelor dintr-un tabel se pot enumera toate

coloanele tabelului în dreptul instrucţiunii SELECT sau mai simplu se poate scrie o

instrucţiune de tipul:

SELECT * FROM nume_tabel; (se va regasi întreg tabelul nume_tabel)

Daca se vor încerca instrucţiunile prezentate mai sus se va putea observa că datele

returnate nu vor fi afişate într-o ordine anumită (vor fi afişate după cum se găsesc în tabelele

de bază).

10


Pentru a sorta în mod explicit datele regăsite folosind o instrucţiune SELECT se

foloseşte clauza ORDER BY. Această clauză sortează rezultatele după numele uneia sau mai

multor coloane.

Ex:

SELECT nume_coloana1, nume_coloana2,nume_coloana3 FROM nume_tabel ORDER BY nume_coloana4, nume_coloana2;

Astfel în exemplul de mai sus vor fi afişate datele din coloanele nume_coloana1,

nume_coloana2, nume_coloana3 aflate în tabelul nume_tabel, aceste date vor fi ordonate

dupa nume_coloana4 (trebuie să existe), iar dacă vor fi înregistrări care vor avea aceeaşi

valoare în această coloană, acestea vor fi afişate ordonat dupa nume_coloana2.

La fel ca în dreptul instrucţiunii SELECT şi în dreptul clauzei ORDER BY pot fi puse

oricâte nume de coloane cu condiţia ca ele să existe.

Este bine de ştiut că sortarea datelor nu se limitează la ordinea de sortare ascendentă,

care este ordinea de sortare prestabilită. Pentru a sorta în ordine descendentă, trebuie

specificat cuvântul cheie DESC.

Ex:

SELECT * FROM nume_tabel ORDER BY nume_coloana1 DESC, nume_coloana2;

! Cuvantul cheie DESC se aplică doar numelui de coloană care îl precede direct. Deci

în exemplul de mai sus datele vor fi sortate descrescător dupa nume_coloana1 şi crescător

după nume_coloana2.

De obicei, tabelele bazelor de date conţin volume mari de date şi rareori trebuie să

regăsim toate înregistrarile din tabel. Frecvent vom dori regăsirea unui subset de date care

respecta anumite condiţii. Regăsirea numai a datelor dorite implică specificarea condiţiilor

(sau condiţiei) de filtrare.

Într-o instrucţiune SELECT datele sunt filtrate prin specificarea criteriilor de căutare

în clauza WHERE. Aceasta este precizată imediat după numele tabelului (clauza WHERE) şi

înainte de clauza ORDER BY care este opţională.

Ex:

SELECT * FROM nume_tabel WHERE nume_coloana1=25 ORDER BY nume_coloana2;

11


O instrucţiune de tipul celei de mai sus va găsi toate coloanele tabelului nume_tabel

dar nu va întoarce decât acele înregistrări care vor avea pe coloana nume_coloana1 valoarea

25. Datele vor fi afişate sortate ascendent după coloana nume_coloana2.

În exemplul de mai sus am testat egalitatea care determina dacă o coloană conţine o

valoare specificată. Limbajul SQL acceptă mai mulţi operatori condiţionali enumerati mai

jos:

= Egalitate

<> sau != Non-egalitate

< Mai mic decât

<= Mai mic sau egal cu

Mai mare decât

>= Mai mare sau egal cu

BETWEEN Intre două valori specificate

IS NULL Este valoarea NULL

Pentru un grad superior de control al filtrării, limbajul SQL permite specificarea mai

multor clauze WHERE. Acestea pot fi folosite în două modalitaţi, sub forma de clauze AND

sau clauze OR (operatori logici).

Dacă este folosită clauza AND vor fi returnate doar înregistrările care vor satisface

ambele condiţii legate prin AND. Operatorul OR este exact opusul operatorului AND. El

instruieste SGBD-ul să returneze liniile ce corespund oricăreia dintre condiţii.

Clauzele WHERE pot contine oricât de mulţi operatori AND şi OR. Combinarea celor

două tipuri de operatori va permite să fie efectuate filtrări complexe. Vor trebui însă folosite

parantezele rotunde pentru a specifica SGBD-ului care dintre condiţii au precedenţa de

evaluare mai ridicată.

Ex:

SELECT * FROM nume_tabel WHERE (nume_coloana1 IS NULL OR nume_coloana2=’Sibiu’)

AND nume_coloana3 BETWEEN 5 AND 10 ORDER BY nume_coloana2;

Instrucţiunea SQL de mai sus va returna înregistrarile din toate coloanele tabelului

ordonate dupa nume_coloana2 care vor satisface condiţiile de la ambele puncte:

nu există trecută nici o valoare în dreptul coloanei nume_coloana1 (IS NULL) sau

valoarea din dreptul coloanei nume_coloana2 este Sibiu (una sau ambele condiţii trebuie

satisfacute)

valoarea din dreptul coloanei nume_coloana3 este în intervalul [5,10]

12


Pe lânga operatorii AND şi OR mai există operatorul NOT a cărui funcţie este de a

nega orice condiţie care îl urmeaza. El este folosit înaintea coloanei după care se face

filtrarea:

Ex:

SELECT nume_coloana1 FROM nume_tabel WHERE NOT nume_coloana2 = ‘Sibiu’;

O caracteristica puternica a limbajului SQL este ca poate filtra folosind caractere de

înlocuire (caractere speciale folosite pentru a corespunde unor parţi dintr-o valoare). Astfel

prin utilizarea operatorului LIKE se pot construi nişte modele de cautare pe baza cărora

SGBD-ul va cauta în baza de date folosind o tehnică de căutare bazată pe o potrivire după

caractere de înlocuire, nu o simpla potrivire de egalitate.

Iata lista caracterelor de înlocuire:

% înlocuieşte orice caractere indiferent de numărul acestora

_ înlocuieşte un singur caracter

[] specificarea între aceste paranteze drepte a unei liste de caractere din interiorul căreia

poate să corespundă orice caracter

Ex:

SELECT nume_coloana1

FROM nume_tabel

WHERE nume_coloana2 LIKE ‘%bi%’

OR (nume_coloana1 LIKE ‘_ibiu’ AND nume_coloana3 LIKE [SLP]%);

%bi% = orice succesiune de caractere care să conţina şi grupul “bi”.

_ibiu = un cuvânt ce începe cu o litera necunoscută şi se temină în “ibiu”

[SLP]% = o succesiune de caractere care începe cu S, L sau P

Ca aproape toate limbajele pentru calculatoare, SQL acceptă folosirea funcţiilor de

manipulare a datelor. Funcţiile sunt operaţii care, de obicei se efectueaza asupra datelor, în

general pentru a facilita transformarea şi manipularea acestora. Aceste funcţii sporesc puterea

limbajului ajutând la construirea unor interogări mult mai apropiate de ceea ce se doreste de

fapt.

Iată câteva exemple de astfel de funcţii:

ABS ( n ), AVG (DISTINCT | ALL n), ASCII(c), CHR (n), CONCAT (1,2), COS (n),

COUNT (DISTINCT|ALL e), EXP (n), GREATEST(e [,e]...), HEXTORAW (c),

LENGTH(c), LOG (b,n), LOWER (c), MAX (DISTINCT|ALL e), MIN (DISTINCT|ALL e),

13


MOD (r,n), REPLACE (c, s1 [, r2]), SIGN (n), SIN (n), SQRT (n), SUM (DISTINCT|ALL

n), UPPER(c).

Datele obţinute în urma unor introgari pot fi grupate după unul sau mai multe câmpuri

folosind două noi clauze şi anume GROUP BY şi HAVING. Folosind aceste clauze se pot

calcula diferite valori şi aplica anumite funcţii pentru subseturi de date.

Ex:

SELECT nume_coloana1,COUNT(*) AS alias FROM nume_tabel GROUP BY nume_coloana1

HAVING nume_coloana1=’Sibiu’;

Se poate observa construcţia aşaziselor aliasuri folosind clauza AS pentru a denumi

anumite coloane care nu există fizic în baza de date ci sunt obţinute prin combinarea datelor

din celelalte coloane.

Pentru a folosi clauza GROUP BY trebuie să se respecte anumite reguli:

clauza GROUP BY poate conţine oricâte coloane, atunci când se stabileşte gruparea, toate

coloanele specificate sunt evaluate împreuna (astfel ca să nu fie returnate date la fiecare nivel

de coloană individuală)

orice coloană enumerată în clauza GROUP BY trebuie să fie coloană regăsită (aflata în

dreptul instrucţiunii SELECT). Nu pot fi folosite aliasuri

pe langă instrucţiunile de calcule agregat orice coloană din instrucţiunea SELECT trebuie

să fie prezentă în clauza GROUP BY (nu se acceptă coloane conţinând datele de lungime

variabilă)

clauza GROUP BY trebuie plasată după toate clauzele WHERE şi înainte de orice clauză

ORDER BY

Clauza HAVING este analoagă celei WHERE fiind însa folosită pentru filtrarea

grupurilor. În cadrul interogării urmează imediat după GROUP BY iar principala diferenţa

între HAVING şi WHERE este că ultima filtrează datele înainte ca acestea să fie grupate iar

prima filtrează datele gata grupate. Această diferenţă nu este nesemnificativă deoarece liniile

eliminate de clauza WHERE nu vor fi incluse în grup, acest lucru putând schimba valorile

calculate (spre exemplu o medie).

Limbajul SQL permite şi crearea de subselecţii, care sunt un fel de interogări înglobate

în alte interogări. Subselecţiile se folosesc pentru combinarea mai multor selecţii din mers,

astfel în loc să se folosească o interogare pentru returnarea unor date care să populeze o altă

interogare s-ar putea scrie o construcţie de tipul:

SELECT nume_coloana1

14


FROM nume_tabel1 WHERE nume_coloana1 în (SELECT nume_coloana1 FROM nume_tabel2

WHERE nume_coloana2=’Sibiu’)

Astfel de sub selecţii sunt prelucrate începand cu instrucţiunea SELECT cea mai

interioara şi deplasându-se spre exterior. Atunci când este prelucrată instrucţiunea SELECT

precedentă, practic sistemul de gestionare a bazei de date execută doua operaţii, instrucţiunea

interioara returnează un domeniu în care instrucţiunea exterioară caută valori pentru

nume_coloana_1.

La fel cum am folosit şi în exemplul de mai sus, utilizările cele mai uzuale pentru

subselecţii sunt în operatorii în ai clauzei WHERE şi în popularea coloanelor calculate

astfel:

SELECT nume_coloana1, (SELECT COUNT(*)

FROM nume_tabel WHERE nume_coloana1=’Sibiu’ AS total) FROM nume_tabel

Una din caracteristicile extrem de puternice din limbajul SQL este capacitatea de a uni

tabelele din mers (aceasta unire nu este una fizică), în interogările de regăsire a datelor.

Unirile constituie unele din cele mai importante operaţii care se pot efectua folosind

instrucţiunile SELECT, o buna întelegere a lor şi a sintaxei pentru unire reprezintă o parte

esenţială din învaţarea limbajului SQL.

Se ştie că divizarea datelor în mai multe tabele permite o stocare mai eficientă, o

manipulare mai uşoara şi o scalare mai bună. Unirea tabelelor este de fapt un mecanism

folosit pentru asocierea tabelelor într-o instrucţiune SELECT care în final va returna liniile

corecte din fiecare tabel.

Crearea unei uniri este foarte simplă. Tot ceea ce trebuie facut este să se specifice

numele tuturor tabelelor (dupa clauza FROM) ce vor fi incluse şi felul în care sunt asociate

reciproc (dupa clauza WHERE).

SELECT nume_coloana1, nume_coloana2, nume_coloana3 FROM nume_tabel1, nume_tabel2

WHERE nume_tabel1.nume_coloana1= nume_tabel2.nume_coloana2;

În exemplul de mai sus se vor uni tabelele nume_tabel1 şi nume_tabel2. Clauza

WHERE instruieşte SGBD-ul să potrivească nume_coloana1 din tabelul nume_tabel1 cu

valoarea nume_coloana2 din nume_tabel2 (se observa constructia cu “.”).

15


Atunci când are loc unirea a doua tabele se împerecheaza de fapt toate liniile din

primul tabel cu toate liniile din al doilea tabel. Clauza WHERE acţioneaza ca un filtru, pentru

ca să includă numai linii ce corepund condiţiei de filtrare specificate – în acest caz condiţia

unirii. Aşadar clauza WHERE este foarte importantă, dacă aceasta ar fi lipsit interogarea de

mai sus ar fi returnat produsul cartezian cu elementele din coloanele returnate.

Unirea folosită mai sus poartă denumirea de ECHI-JOIN. Pentru a folosi un alt fel de

unire (INNER-JOIN sau OUTER-JOIN) va trebui specificat modul de unire în clauza FROM

(FROM nume_tabel1 INNER JOIN nume_tabel2), iar clauza de unire se va face cu ON nu cu

WHERE.

Se pot crea şi aşa-numitele auto-uniri (se uneşte tabelul cu el însusi). Unirile exterioare

(OUTER-JOIN) pot fi drepte sau stângi (RIGHT OUTER-JOIN sau LEFT OUTER-JOIN).

Spre deosebire de unirile interioare care asociaza linii în ambele tabele, unirile exterioare

includ şi liniile care n-au linii asociate. Se precizeaza tabelele care se doresc a returna toate

liniile incluse prin LEFT respectv RIGHT. Se va afişa NULL pentru câmpurile care se doresc

întoarse şi nu au înregistrări.

Ori de câte ori tabelele sunt unite, cel puţin o coloană va apărea în mai multe tabele

(cheia externă). Unirile standard (cele interne= INNER) returnează toate datele chiar şi

apariţiile multiple a aceleiaşi coloane. O unire naturală va elimina apariţiile multiple astfel că

este returnată numai câte o coloana de acelaşi tip. O astfel de unire se va face prin folosirea

unui caracter de înlocuire (SELECT *) pentru un tabel şi subseturi explicite ale coloanelor

pentru toate celelalte tabele.

Limbajul SQL în sine nu are restricţii privind numărul maxim de tabele ce pot fi unite,

totuşi multe SGBD-uri impun limitări.

Acestea sunt principalele construcţii pe care limbajul SQL, cel mai folosit limbaj

pentru gestionarea, prelucrarea şi interogarea bazelor de date le pune la dispoziţie pentru

regăsirea informaţiilor (căutare) în baze de date, iar cunoaşterea acestor construcţii este

obligatorie pentru oricine care va lucra în domeniul IT.

2.3 CĂUTAREA ÎN FIŞIERE EXTERNE

Orice sistem de operare ar fi folosit, toate operaţiile de intrare şi de ieşire se

efectuează prin citirea sau scrierea fişierelor, deoarece toate dispozitivele periferice, chiar şi

tastatura şi ecranul sunt fişiere ce aparţin sistemului de fişiere. Acest lucru înseamnă că o

16


singură interfaţă unitară are în sarcină toate operaţiile de comunicare dintre un program şi

dispozitivele periferice.

În cazul cel mai general, înainte de a lucra cu un fişier sistemul va trebui informat cu

privire la această intenţie, proces denumit deschiderea fişierului care se face printr-un apel

sistem open. Acest apel primeşte în lista de argumente numele fişierului pe care se va lucra,

indicatori cu privire la modul de deschidere (pentru citire, pentru scriere, ambele) precum şi o

valoare întreagă care este intotdeauna 0 (reprezintă opt sau nouă biţi care dau permisiunile ce

controlează accesul la operaţiile de citire, scriere şi executare pentru proprietarul fişierului,

pentru grupul proprietarului şi pentru toti ceilalţi). Sistemul verfică dacă aveţi dreptul să

deschideti fişierul specificat (Există fişierul? - Dacă nu trebuie mai întâi creat prin apelul

sistem creat care primeşte în lista de argumente numele fişierului şi valoarea întreaga cu

privire la permisiuni. Aveţi permisiunea de a-l accesa?) şi dacă totul este în regulă, returnează

programului un întreg poziţiv mic, numit descriptor de fişier.

! Dacă se face apelul funcţiei sistem creat primind numele unui fişier deja existent, nu

se va considera eroare, creat va trunchia fişierul respectiv la dimensiunea 0, ştergând astfel

conţinutul anterior al acestuia.

Funcţia close care primeşte în lista de argumente descriptorul unui fişier va fi apelată

la sfârşitul lucrului cu fişierul respectiv pentru a rupe legătura dintre un descriptor şi un fişier

deschis şi pentru a elibera descriptorul de fişier pentru a putea fi folosit cu un alt fişier. Dacă

cumva un program este terminat prin intermediul funcţiei exit() sau prin returnarea din

programul principal închide toate fişierele deschise.

Ori de câte ori urmează să se execute operaţii de intrare/ieşire asupra fişierului,

descriptorul de fişier este folosit în locul numelui pentru a identifica fişierul. (Un descriptor de

fişier este analog cu pointerul de fişier folosit de biblioteca standard în C/C++, sau cu

identificâtorul de fişier din MS-DOS). Toate informaţiile despre un fişier deschis sunt

gestionate de sistem; programul utilizator face referire la fişier doar prin intermediul

descriptorului de fişier.

Deoarece operaţiile de intrare/ieşire care implică tastatura şi ecranul sunt atât de

frecvente, există facilităţi speciale care să le facă accesibile. Când interpretatorul de comenzi

(“shell-ul”) execută un program sunt deschise trei fişiere, având descriptorii 0, 1 şi 2 numite

intrarea standard (tastatura), ieşirea standard şi ieşirea standard (ecranul monitorului) şi ieşirea

standard pentru erori (de asemenea ecran). Dacă un program citeşte din 0 şi scrie în 1 şi 2,

acesta poate realiza operaţii de citire şi scriere fară a se preocupa de deschiderea fişierelor, în

17


caz contrar intrarea standard şi ieşirea standard vor trebui redirecţionate către fişierele sau

canalele de transfer dorite prin metode specifice limbajului de programare în care se lucrează.

În acest caz shell-ul înlocuieste destinaţiile obişnuite ale descriptorilor de fişiere 0 şi 1

cu fişierele precizate. În mod normal descriptorul de fişier 2 rămâne atribuit ecranului, pentru

că mesajele de eroare să poată ajunge acolo. Observaţii asemănătoare sunt valabile şi pentru

operaţiile de intrare şi de ieşire prin intermediul unui canal de transfer. În toate cazurile

atribuirile fişierelor sunt modificâte de către shell, şi nu de către program. Programul nu stie

de unde provin datele sale de intrare şi nici unde merg datele sale de ieşire, atât timp cât

foloseşte fişierul 0 pentru operaţii de intrare şi fişierele 1, 2 pentru operaţii de ieşire.

Operaţiile de intrare şi ieşire folosesc apelurile sistem read şi write care sunt accesate

din cadrul unui program. La un apel pot fi citiţi sau scrişi un număr oricât de mare de octeţi.

Se va utiliza o aşanumită zonă tampon (buffer) de o anumită mărime ce poate fi schimbată

unde vor fi stocate datele sau de unde urmează să fie preluate. Cum lucrează acest buffer ?

Indiferent dacă este vorba despre o citire sau o scriere datele sunt depuse în buffer de unde vor

fi preluate de aplicaţie (la citire) sau de unde vor fi luate şi scrise în fişier (la scriere).

De cele mai multe ori numărul de octeţi folosiţi la operaţii de intrare/ieşire este 1 care

înseamnă caracter cu caracter (fără a trece prin buffer). Când se doreşte citirea sau scrierea

unei cantitati mari de informaţie se preferă folosirea bufferului pentru că vor fi efectuate mai

puţine apeluri sistem.

Operaţiile de citire şi de scriere au în mod normal un caracter secvenţial: fiecare

operaţie read sau write se efectuează la o poziţie din fişier aflată imediat După cea

precedentă. Totuşi atunci când este necesar, dintr-un fişier se poate citi sau scrie în acesta într-

o ordine arbitrară. Apelul sistem lseek furnizează o modalitate de deplasare într-un fişier fără

a citi sau a scrie o dată. Bineînţeles ca această funcţie trebuie să primeasca în lista sa de

parametrii descriptorul fişierului pe care se lucrează şi deplasamentul faţă de o anumită

origine de asemenea precizată. Operaţiile următoare de scriere sau citire vor începe la acea

poziţie la care s-a ajuns prin apelul lui lseek.

Originea poate fi precizată cu ajutorul valorilor întregi 0, 1, 2 pentru a preciza ca

deplasamentul (tot o valoare întreaga) se va masura de la început, de la poziţia curentă sau de

la sfârşitul fişierului. Această funcţie lseek va returna un long care precizează noua poziţie din

fişier.

Prin intermediul funcţiei lseek este posibil ca fişierele sa fie tratate într-o masura mai

mare sau mai mică precum nişte tablouri mari, cu preţul unei viteze de acces mai mici.

18


Toate aceste funcţii sistem precizate vor putea fi apelate din cadrul programelor prin

rutine specifice fiecărui limbaj de programare în parte. Mai jos vom analiza cum se face acest

apel în limbaj C/C++ şi Java.

Aşadar înainte de a citi dintr-un anumit fişier sau a scrie în acesta, fişierul trebuie

deschis prin intermediul unei funcţii de bibliotecă (fopen() în C/C++) specifică limbajului în

care se programează. Această funcţie preia un nume extern, al fişierului pe care se va lucra,

efectuează câteva operaţii de economie interna şi negociere cu sistemul de operare şi

returnează un pointer (sau o referinţa) care să fie folosită la operaţiile ulterioare de citire şi

scriere în fişier.

Pointerul de fişier (sau referinţa) returnat indică spre o structură care conţine

informaţii despre fişier cum ar fi locaţia bufferului, poziţia caracterului curent din fişier, dacă

se citeşte din sau se scrie în fişier şi dacă au apărut erori sau dacă s-a întâlnit sfârşitul de fişier

notat de cele mai multe ori cu eof (end-of-file).

Singura declaraţie necesară pentru un pointer la fişier în limbaj C++ este:

FILE *pf;FILE *fopen (char *nume, char *mod);

Cele de mai sus precizează că dacă pf este un pointer spre tipul FILE (fişier) şi ca

funcţia fopen returnează un pointer spre tipul FILE. De reţinut este faptul că FILE este un

nume de tip precum de exemplu int, nu un nume generic de structura; acesta este definit prin

intermediul lui typedef.

Apelul către funcţia fopen dintr-un program este: pf = fopen (nume, mod); Primul

argument al funcţiei fopen este un şir de caractere ce conţine numele fişierului. Al doilea

argument este modul, de asemenea un şir de caractere, care precizează cum să fie folosit

fişierul. Printre modurile premise se numără citirea – read(“r”), scrierea – write (“w”) şi

adăugarea – append (“a”). Pentru că unele sisteme fac distincţie între fişierele text şi cele

binare, pentru cele din urmă, trebuie adăugata litera “b” la şirul de caractere care specifică

modul.

Dacă se deschide pentru operaţii de scriere sau adăugare un fişier care nu există, acesta

va fi creat automat. Deschiderea unui fişier pentru operaţii de scriere duce la pierderea

vechiului conţinut, în timp ce deschiderea pentru operaţii de adăugare păstreaza conţinutul

anterior. Încercarea de a citi un fişier care nu există constituie o eroare (excepţie în Java).

Dacă apare o astfel de eroare sau oricare alta (eroare va fi şi când se încearcă deschiderea

unui fişier la care nu aveţi permisiune) Funcţia fopen returnează NULL.

19


Fişierele sunt folosite pentru a prelua sau a scrie date în ele. Bineînţeles că datele vor

fi prelucrate înainte în cazul scrierii şi după în cazul citirii dintr-un fişier.

Aşadar un lucru absolut necesar este o modalitate de a citi din fişier sau de a scrie în

acesta o dată ce a fost deschis. Citirea precum şi scrierea se vor face cu funcţii specifice

limbajului de programare folosit (în C++: getc, putc,getchar, putchar, fscanf, fprintf).

După terminarea lucrului cu fişiere trebuie apelată o funcţie fclose() (în C/C++) pentru

întreruperea legăturii dintre pointerul de de fişier şi numele extern, eliberând pointerul de

fişier pentru a putea fi folosit de un alt fişier (această legatură a fost făcută prin apelul

funcţiei fopen()- în C/C++). Deoarece majoritatea sistemelor de operare impun o anumită

limită numărului de fişiere pe care un program le poate deschide simultan, este o idee bună

eliberarea pointerilor de fişier atunci când aceştia nu mai sunt necesari.

Mai există un motiv pentru folosirea funcţiei fclose() pentru un fişier de ieşire –

goleşte bufferul în care se trimit datele de ieşire.

Într-un program Java pentru operaţiile de scriere şi citire se folosesc aşanumitele

fluxuri.

Pentru a aduce informaţii dintr-un mediu extern cum este şi un fişier, un progam Java

trebuie să deschida un canal de comunicaţie (flux) către sursa informaţiilor şi să citească serial

informaţiile respective:

Similar, un program poate trimite informaţii către o destinaţie externă deschizând un

canal de comunicaţie (flux) către acea destinaţie şi scriind serial informaţiile respective:

Indiferent de tipul informaţiilor, citirea/scrierea informaţiilor de pe/către un mediu

extern respectă următorii algoritmi:

Citirea Scrierea

20


deschide canal comunicaţie

while (mai sunt informaţii) {

citeşte informaţie

}

închide canal comunicaţie;

Deschide canal comunicaţie

while (mai sunt informaţii) {

scrie informaţie

}

închide canal comunicaţie;

Un flux este un canal de comunicaţie unidirectional serial pe 8 sau 16 biţi între două

procese. Un flux care citeşte date se numeşte flux de intrare. Un flux care scrie date se

numeşte flux de ieşire.

Există trei tipuri de clasificare a fluxurilor:

După "direcţia" canalului de comunicaţie deschis fluxurile se împart în:

fluxuri de intrare (pentru citirea datelor)

fluxuri de ieşire (pentru scrierea datelor)

După tipul de date pe care operează:

fluxuri de octeţi (comunicare seriala realizată pe 8 biţi)

fluxuri de caractere (comunicare seriala realizeată pe 16 biţi)

După acţiunea lor:

fluxuri primare de citire/scriere a datelor (se ocupa efectiv cu citirea/scrierea datelor)

fluxuri pentru procesarea datelor

Fluxurile pentru lucrul cu fişiere sunt cele mai uşor de înteles. Clasele care

implementează aceste fluxuri sunt următoarele:

FileReader, FileWriter - caractere

FileInputStream, FileOutputStream - octeţi

Constructorii acestor clase acceptă ca argument un obiect care să specifice un anume

fişier. Acesta poate fi un şir de caractere, un obiect de tip File sau un obiect de tip

FileDesciptor.

Constructorii clasei FileReader: (fluxuri pentru citirea din fişier)

public FileReader(String fileName) throws FileNotFoundExcepţion

public FileReader(File file) throws FileNotFoundExcepţion

public FileReader(FileDescriptor fd)

Constructorii clasei FileWriter: (fluxuri pentru scrierea într-un fişier)

public FileWriter(String fileName) throws IOExcepţion

public FileWriter(File file) throws IOExcepţion

public FileWriter(FileDescriptor fd)

21


public FileWriter(String fileName, boolean append) throws IOExcepţion

Cei mai uzuali constructori sunt cei care primesc ca argument numele fişierului.

Aceştia pot provoca excepţii de tipul FileNotFoundExcepţion în cazul în care fişierul cu

numele specificat nu există. Din acest motiv orice creare a unui flux de acest tip trebuie

facută într-un bloc try sau metoda în care sunt create fluxurile respective trebuie să arunce

excepţiile de tipul FileNotFoundExcepţion sau de tipul superclasei IOExcepţion.

Ca şi în C/C++ se poate scrie şi cu ajutorul unei zone tampon.Clasele pentru

citirea/scrierea cu zona tampon sunt:

BufferedReader, BufferedWriter - caractere

BufferedInputStream, BufferedOutputStream - octeţi

Sunt folosite pentru a introduce un buffer în procesul de scriere/citire a informa-tiilor,

reducând astfel numărul de accese la dispozitivul ce reprezinta sursa originală de date. Sunt

mult mai eficiente decât fluxurile fară buffer şi din acest motiv se recomanda folosirea lor ori

de câte ori este posibil.

Clasele BufferedReader şi BufferedInputStream citesc în avans date şi le memo-rează

într-o zona tampon (buffer). Atunci când se execută o operaţie read(), octetul citit va fi preluat

din buffer. În cazul în care buffer-ul este gol citirea se face direct din flux şi, odată cu citirea

octetului, vor fi memoraţi în buffer şi octeţii care îi urmeaza.

Similar, se lucreaza şi cu clasele BufferedWriter şi BufferedOutputStream.

Fluxurile de citire/scriere cu buffer sunt fluxuri de procesare şi sunt folosite prin

suprapunere cu alte fluxuri.

Exemplu:

BufferedOutputStream out = new BufferedOutputStream( new FileOutputStream("out.dat"), 1024) unde out.dat este fişier extern

Constructorii acestor clase sunt următorii:

BufferedReader BufferedReader(Reader în)

BufferedReader(Reader in, int dim_buffer)

BufferedWriter BufferedWriter(Writer out)

BufferedWriter(Writer out, int dim_buffer)

BufferedInputStream BufferedInputStream(InputStream în)

BufferedInputStream(InputStream in, int dim_buffer)

BufferedOutputStream BufferedOutputStream(OutputStream out)

BufferedOutputStream(OutputStream out, int dim_buffer)

22


În cazul constructorilor în care dimensiunea buffer-ului nu este specificata, aceasta

primeşte valoarea implicită de 512 octeţi.

Metodele acestor clase sunt cele uzuale de tipul read şi write. Pe lângă acestea,

clasele pentru scriere prin buffer mai au şi metoda flush care goleşte explicit zona tampon

chiar dacă aceasta nu este plină.

Există şi o metoda de citire a informaţiilor dintr-un fişier linie cu linie. Aceasta este readline() şi se foloseşte ca în exemplul de mai jos:

BufferedReader br = new BufferedReader(new FileReader("in")) String input; while ((input = br.readLine()) != null) {

... }

Pentru căutarea într-un fişier de pe disc eu am folosit analiza lexicală pe fluxuri,

respectiv (clasa StreamTokenizer).

Clasa StreamTokenizer parcurge un flux de intrare de orice tip şi îl împarte în "atomi

lexicali". Rezultatul va consta în faptul că în loc sa se citească octeţi sau caractere se vor citi,

pe rând, atomii lexicali ai fluxului respectiv.

Printr-un atom lexical se înţelege în general:

un identificator (un şir care nu este între ghilimele)

un număr

un şir de caractere

un comentariu

un separator

Atomii lexicali sunt despartiti între ei de separatori. Implicit aceşti separatori sunt cei

obisnuti(spatiu, tab, virgula, punct şi virgula), însa pot fi schimbaţi prin diverse metode ale

clasei.

Constructorii acestei clase sunt:

public StreamTokenizer(Reader r)public StreamTokenizer(InputStream is)

Identificarea tipului şi valorii unui atom lexical se face prin intermediul variabilelor:

TT_EOF - atom ce marchează sfârsitul fluxuluiTT_EOL - atom ce marchează sfârsitul unei liniiTT_NUMBER - atom de tip numărTT_WORD - atom de tip cuvântnval - valoarea unui atom numericsval - şirul conţinut de un atom de tip cuvântttype - tipul ultimului atom citit din flux

Citirea atomilor din flux se face cu metoda nextToken(), care returnează tipul

atomului lexical citit şi scrie în variabilele nval sau sval valoarea corespunzătoare atomului.

23


Mai jos este dat un un exemplu de program în care se caută un anumit String într-un

fişier memorat pe disc prin despărţirea datelor din fişier în fluxuri:

import java.io.*;public class TestTokenizer {

public static void main(String args[]) throws IOExcepţion{ String cuvCautat=”unCuvant”; int nr =25;

FileInputStream fis = new FileInputStream("test.dat");BufferedReader br = new BufferedReader(new InputStreamReader(fis));StreamTokenizer st = new StreamTokenizer(br);int tip = st.nextToken(); //citesc primul atom lexicalwhile (tip != StreamTokenizer.TT_EOF) {

switch (tip) { case StreamTokenizer.TT_WORD: // cuvânt

if (st.sval.equals(cuvCautat)) System.out.println(st.sval);break;

case StreamTokenizer.TT_NUMBER: // numărif (st.nval= =25) System.out.println(st.nval);

}tip = st.nextToken();// următorul atom

}}

}

Aşadar, modul de utilizare tipic pentru un analizor lexical este într-o buclă "while" în

care se citesc atomii unul câte unul cu metoda nextToken pâna se ajunge la sfârsitul fluxului

(TT_EOF). În cadrul buclei "while" se află tipul atomului curent (întors de metoda

nextToken) şi apoi se află valoarea numerica sau şirul de caractere corespunzător atomului

respectiv.

În funcţie de necesitaţi în cadrul unui program se pot folosi una din clasele

următoare:

DataInputStream, DataOutputStream BufferedInputStream, BufferedOutputStream LineNumberInputStream PushbackInputStream PrintStream (flux de ieşire)

Toate acestea sunt clase pentru filtrarea datelor. Un flux de filtrare se ataşează

altui flux pentru a filtra datele care sunt citite/scrise de către acel flux. Clasele pentru fluxuri

de filtrare au ca superclase clasele abstracte FilterInputStream (pentru filtrarea fluxurilor de

intrare) şi FilterOutputStream (pentru filtrarea fluxurilor de ieşire).

Se observă că toate aceste clase descriu fluxuri de octeţi.

Filtrarea datelor nu trebuie văzută ca o metoda de a elimina anumiti octeţi dintr-un

flux ci de transformă aceşti octeţi în date care să poata fi interpretate sub alta forma.

Aşa cum am văzut la citirea/scrierea cu zona tampon clasele de filtrare

BufferedInputStream şi BufferedOutputStream grupează datele unui flux într-un buffer,

urmând ca citirea/scrierea sa se facă prin intermediul acelui buffer.

Aşadar fluxurile de filtrare nu elimină date citite sau scrise de un anumit flux, ci

24


introduc o noua modalitate de manipulare a lor. Din acest motiv fluxurile de filtrare vor

conţine anumite metode specializate pentru citirea/scrierea datelor, altele decât cele commune

tuturor fluxurilor (metode de tip read/write).

Folosirea fluxurilor de filtrare se face prin ataşarea lor de un flux care se ocupă

efectiv de citirea/scrierea datelor:

FluxFiltrare numeFlux = new FluxFiltrare (referinţaAltFlux)

Cele mai importante clase din aceasta categorie sunt DataInputStream şi

DataOutputStream.

Clasele DataInputStream şi DataOutputStream

Aceste clase oferă metode prin care un flux nu mai este văzut ca o înşiruire de octeţi,

ci ca o sursa de date primitive. Prin urmare vor furniza metode pentru citirea şi scrierea

datelor la nivel de tip de data şi nu la nivel de octet. Constructorii şi metodele cele mai

importante (altele decât read/write) sunt date în tabelul de mai jos:

DataInputStream DataOuputStream

//Constructor

DataInputStream(InputStream in)

//Constructor

DataOutputStream(OutputStream out)

ReadBoolean()

ReadByte()

ReadChar()

ReadDouble()

ReadFloat()

ReadInt()

ReadLong()

ReadShort()

ReadUnsignedByte()

ReadUnsignedShort()

String readUTF()

writeBoolean(boolean v)

writeByte(int v)

writeChar(int v)

writeDouble(double v)

writeFloat(float v)

writeInt(int v)

writeLong(long v)

writeShort(int v)

writeBytes(String s)

writeChars(String s)

writeUTF(String str)

Aceste metode au denumirile generice de readXXX şi writeXXX specificate de

interfetele DataInput şi DataOutput. Pot provoca excepţii de tipulIOExcepţion.

Trebuie avută în atenţie că un fişier în care au fost scrise informaţii folosind metode

writeXXX nu va putea fi citit decât prin metode readXXX.

Clasa RandomAccesFile (fişiere cu acces direct)

25


Fluxurile sunt, aşa cum am văzut procese secvenţiale de intrare/ieşire. Acestea sunt

adecvate pentru scrierea/citirea de pe medii secvenţiale de memorare a datelor cum ar fi banda

magnetica,etc. deşi sunt foarte utile şi pentru dispozitive în care informaţia poate fi accesată

direct.

Clasa RandomAccesFile permite accesul nesecvenţial (direct) la conţinutul unui fişier.

Ea este o clasa de sine statătoare, subclasa directă a clasei Object, se gaseşte în pachetul

java.io şi implementeaza interfetele DataInput şi DataOutput, ceea ce înseamna că sunt

disponibile metode de tipul readXXX, writeXXX (permite atât citirea cât şi scriere din/în

fişiere cu acces direct).

Ceea ce este mai important este că această clasă permite specificarea modului de acces

al unui fişier (read-only, read-write)

Constructorii acestei clase sunt:

RandomAccessFile(String numeFişier, String mod_acces) throws IOExcepţion

RandomAccessFile(String fişier, String mod_acces) throws IOExcepţion

unde mod_acces poate fi:

"r" - fişierul este deschis numai pentru citire (read-only)

"rw" - fişierul este deschis pentru citire şi scriere (read-write)

Exemple:

RandomAccesFile f1 = new RandomAccessFile("fişier.txt", "r"); //deschide un fişier pentru citire

RandomAccesFile f2 = new RandomAccessFile("fişier.txt", "rw"); //deschide un fişier pentru scriere şi citire

Clasa RandomAccesFile suporta noţiunea de pointer de fişier. Acesta este un indicator

ce specifică poziţia curentă în fişier. La deschiderea unui fişier pointerul are valoarea 0,

indicând începutul fişierului. Apeluri la metode readXXX sau writeXXX deplasează pointerul

fişierului cu numărul de octeţi citiţi sau scrişi de metodele respective.

În plus faţă de metodele de citire/scriere clasa pune la dispoziţie şi metode pentru

controlul poziţiei pointerului de fişier. Acestea sunt:

26


int skipBytes (int n) Mută pointerul fişierului înainte cu un număr specificat de octeţi

void seek (long poziţie) Poziţioneaza pointerul fişierului înaintea octetului specificat.

long getFilePointer () Returnează poziţia pointerului de fişier (poziţia de la care se citeşte/la care se scrie)

2.4 CĂUTAREA ÎN TABLOURI

Tablourile reprezintă structurile de date cel mai frecvent utilizate, fiind incluse în

majoritatea limbajelor de programare.

În limbajul Java tablourile nu sunt tratate că un tip primitiv de date ci ca nişte obiecte.

De aceea trebuie utilizat operatorul new pentru crearea unui tablou.

Exemplu:

int[] intArray; // defineşte o referinţă la un tablou inArray = new int [100]; // creează tabloul şi defineşte pe intArray // (cel care indică tabloul)

Aceste instrucţiuni pot fi înlocuite de instrucţiunea unică echivalentă:

int[] intArray = new int[100];

Cel mai simplu algoritm pentru căutare într-un tablou este cel de căutare secvenţială,

care se face parcurgând structura de date de la început spre sfârsit, comparându-se cheia

căutată cu valorile găsite în şir la poziţia în care ne aflăm.

Căutarea secvenţială în principiu, rezolvă următoarea problemă:

Problemă:

Fie M={x1,x2,...,xn} o mulţime de valori dispuse într-o structură de date oarecare şi x o

valoare dată. Se cere să se găseasca poziţia pe care se află x în M. Algoritmul este simplu şi

presupune o parcurgere secvenţială a elementelor, începând de la primul element şi se

continuă până când este găsit elementul x. Dacă nu este găsit, mulţimea este parcursă în

întregime, codul va lua valoarea “Eşec” iar poz va deveni –1. Atunci când x este găsit codul

va lua valoarea “Succes” iar poz va indica poziţia pe care se află elementul cautat în cadrul

mulţimii M.

Căutarea secvenţială poate fi implementata în mai multe feluri:

căutare secvenţială

căutare secvenţială rapidă

căutare secvenţială într-un tablou ordonat

27


Pentru căutarea secvenţială algoritmul în pseudocod s-ar putea scrie aşa:

Procedure CăutareSecv(n,M,x,cod,poz) i:=1; While (M[i]<>x) And (i<=n) Do i:= i+1; EndWhile If i >n then cod=”Eşec”; poz:= -1; Else cod = “Succes”; poz:= i; EndIf

În algoritmul mai sus prezentat vom avea:

n = numărul elementelor din mulţimea M

M = mulţimea în care se face căutarea

x = elementul cautat

cod = codul returnat în funcţie de succesul său insuccesul cautarii

poz = poziţia pe care va fi găsit elementul cautat în cadrul mulţimii M. când apare

valoarea; dacă poz:= -1 vom avea eşec în căutare (elementul cautat nu a fost găsit) deci codul

va fi “Eroare”

Căutare secvenţială rapidă: acest tip de căutare reduce la jumătate numărul de condiţii

testate de ciclul While, prin introducerea, la sfârşit de fişier, a unei înregistrări oarbe, egale

chiar cu cheia de intrare.

Algoritmul în pseudocod pentru căutarea secvenţială rapidă este:

Procedure CăutareSecvRapidă (n,M,x,cod,poz) i:= 1; M[n+1]:= x; While M[i]<>x do i:=i+1; EndWhile If i >n then cod:= ”Eşec”; Poz:= -1; Else cod:= “Succes”; Poz:= i-1; Endif

În această procedură notaţiile se păstrează că la căutarea secvenţială.

În continuare va fi prezentată o metodă Java pentru căutare unui element searchkey în

cadrul unui tablou a[], metoda care va întoarce fals sau adevărat după cum căutarea a avut

său nu succes.

public boolean find (double searchkey); { // caută o valoare precizată de tip double int j; for (j = 0; j < nElems; j++) // pt fiecare element if (a[j] == searchkey) // am găsit elementul ? break; // ieşire forţată din ciclu if (j == nElems) // am ajuns la sfârşit ?

28


return false; // da, elementul nu a fost găsit else return true; // s-a găsit valoarea }

Mai departe căutarea secvenţială rapida va fi:

public boolean find (double searchkey); { // caută o valoare precizata de tip double int j; a[nElems+1] = searchkey; for (j = 0; j < nElems+1; j++) // pt fiecare element if (a[j] == searchkey) // am găsit elementul ? break; // ieşire forţată din ciclu if (j == nElems+1) // am ajuns la sfârşit ? return false; // da, elementul nu a fost găsit else return true; // s-a găsit valoarea }

Căutare secvenţială într-un tablou ordonat: faptul că elementele tabloului în care

se face căutarea sunt ordonate ne conduce la testarea condiţiei x >M[i] în loc de x = M[i].

Daca se ajunge că x >M[i], vom ştii sigur că nu mai există în şir nici o valoare care să fie

egală cu x.

Pentru reducerea timpului de execuţie a algoritmului (reducerea numărului de

comparaţii din condiţia ciclului While), introducem o înregistrare oarbă, M[n+1], care să ne

asigure că ciclul While se opreşte după parcurgerea mulţimii ordonate. Trebuie că M[n+1] să

fie o valoare care să asigure îndeplinirea condiţiei x <M[n+1]. Notăm formal M[n+1] = ,

adica o valoare despre care ştim că este mai mare decât orice valoare din domeniul lui x.

Algoritmul în pseudocod pentru căutarea secvenţială într-un tablou ordonat este:

Procedure CăutareSecvTabOrd (n,M,x,poz,cod) i:= 1; M[n+1]:=; While v>=M[i] do If v = M[i] then cod = “succes”; poz:= -1; Break; Else i:=i+1; EndWhilecod:= “Eşec”;poz:= -1;

Şi în această procedură notaţiile se păstrează că la căutarea secvenţială.şi la cea

secvenţială rapidă.

Căutarea secvenţială într-un tablou ordonat se face aproximativ la fel că la un tablou

neordonat, diferenţa constând în faptul că în tabloul ordonat căutarea se opreşte atunci când

este întâlnit un element cu o cheie mai mare.

29


În cazul cel mai nefavorabil atunci când elementul cautat nu este în mulţimea M,

mulţimea va fi parcursă în întregime, numărul de comparaţii fiind n. Deci, în cazul cel mai

nefavorabil vom avea T(n)O(n).

Probabilitatea că x să se afle pe poziţia i este P(x = x i) =1/(n+1) deoarece s-ar putea că

x să nu fie în M. Dacă x = xi atunci se vor parcurge exact i elemente până la găsirea lui x.

Aşadar timpul de căutare va fi dat de formula:

Targ(n)= i = n/2

unde P(x = xi+1) = P(xM) = 1/n+1

Căutarea binară

Acest tip de căutare este mult mai rapid decât cel liniar (prin selecţie), însă se poate

face doar atunci când tabloul în care se face căutarea este ordonat. Totuşi atunci când

procesul de căutare este foarte frecvent pe aceeaşi mulţime M şi aici vorbim de cazul în care

mulţimea M este memorată într-un tablou, ne vom putea folosi de beneficiile cautării binare,

mult mai avantajoasă din punct de vedere al timpului de execuţie. Pentru aceasta va trebui să

realizăm o sortare a elementelor tabloului, operaţie ce poate lua cel mult O(n log n) şi apoi

aplicarea algoritmului de căutare binară cu timpul de O(log n).

Sortarea elementelor se poate face cu oricare dintre algoritmii de sortare cunoscuţi şi

anume:

Sortarea prin selecţie

Sortarea prin inserţie

Sortarea prin distribuţie

Sortarea prin interclasare

Sortarea rapidă

Shellsort-ul (o variantă a celei prin distribuţie)

Sortarea topologica

Heapsortul

Sortarea cu găleti

Acest algoritm de căutare este mult mai rapid decât cel liniar (prin selecţie), îndeosebi

pentru tablouri mari.

Căutarea binară utilizează aceeaşi strategie pe care o folosesc şi copiii în jocul

"Ghiceşte numărul" în acest joc unul dintre copii va cere altuia să ghiceasca numărul la care

el se gândeşte, număr cuprins între 1 şi 100. De fiecare dată când se încearca ghicirea

numărului primul copil va da indicii de forma: "Nu, numărul la care m-am gândit este mai

30


mare "sau " numărul la care m-am gândit este mai mic " până în clipa în care numărul va fi

ghicit. Scopul acestui joc este de a ghici numărul din cât mai puţine încercari.

Pentru aceasta trebuia să se înceapă de la numărul 50 (jumătatea lui 100) iar apoi se va

încerca numărul 75 daca numărul cautat este mai mare său 25 daca numărul cautat este mai

mic. Se observă că fiecare încercare permite înjumătăţirea domeniului valorilor posibile (daca

numărul cautat este mai mic se va cauta numărul între 1 şi 50, iar daca acesta este mai mare

se va caută numărul între 50 şi 100, încercându-se valoarea din mijloc a acestui interval). în

final domeniul se reduce la un singur număr care este chiar numărul cautat.

Aşadar se citeşte valoarea din mijlocul tabloului; daca elementul cautat este mai mare,

căutarea se restrânge la jumătatea superioară a tabloului; analog, daca elementul este mai

mic, căutarea se va continua în jumătatea inferioară (de aici apare şi posibilitatea că acest

algoritm să poata fi scris folosind o metodă recursivă).

Algoritmul de căutare are următoarea idee la bază:

mulţimea în care se caută este M={x1,...,xn} cu x1<x2<...<xn;

se ia elementul xM=x[n/2] şi se compară x cu xM;

i) daca x=xM atunci returnează elementul xM şi algoritmul se încheie;

ii) altfel, daca x<xM se repetă algoritmul pentru mulţimea M'={x1,...,x[n/2]-1}

iii) altfel, daca x>xM se repetă algoritmul pentru mulţimea M"={x[n/2]+1,...,xn}

Se observă că la fiecare pas, numărul de elemente în care se face căutarea se

înjumătăţeşte, deci T(n)=c+T([n/2]), T(0)=0, T(1)=1, c=constantă, de unde rezultă că T(n)=c

log n, deci T(n)=O(log n).

Acest algoritm de căutare (binară) poate fi implementat în două feluri: iterativ şi

recursiv.

În continuare vor fi prezentate cele două implementări în limbaj Java.

public int caută (double searchkey) //varianta iterativa { int stânga = 0; int dreapta = nElems – 1; int pivot; while (true) { pivot = (stânga + dreapta) / 2; if (a[pivot] == searchkey) return pivot; // am găsit elementul else if ( stânga > dreapta) return nElems // nu s-a găsit elementul else // înjumătăţim domeniul {

31


if (a[pivot] > searchkey) stânga = pivot + 1; // este în jumătatea superioară else dreapta = pivot – 1; // este în jumătatea inferioară } // închidere else } // închidere while} // sfârşitul metodei caută ()

Pentru simplificare am considerat un tablou a[] cu elemente de tipul double în care se

caută un element searchkey.

Este posibil să transformăm destul de uşor metoda iterativă într-una recursivă. În

varianta iterativă, se modifica valorile lui stânga şi dreapta, pentru a preciza un nou domeniu,

după care se trece la o nouă iteraţie. Fiecare nouă iteraţie realizează astfel o împărţire

aproximativă în jumătate (putem introduce aici noţiunea de " divide et impera ").

În soluţia recursivă, modificarea variabilelor stânga şi dreapta este înlocuita cu apelul

recursiv al metodei căutare() cu valori noi pentru stânga şi dreapta, că parametrii. Ce se

întâmplă de fapt: se verifica în care jumătate a domeniului sortat se află cheia cautată şi apoi

se aplica recursiv căutare() asupra acelei jumătăţi. Ciclul while dispare locul său fiind deci

luat de apelurile recursive. Iată noua variantă a metodei caută():

public int căutare(double searchkey, int stânga, int dreapta) { // varianta recursiva int pivot; pivot = ( stânga + dreapta) / 2; if (a[pivot] == searchkey) return pivot; // am găsit elementul else if ( stânga > dreapta) return nElems // nu s-a găsit elementul else // înjumătăţim domeniul { if (a[pivot] > searchkey) // este în jumătatea superioară return căutare (searchkey, pivot + 1, dreapta); else // este în jumătatea inferioară return căutare (searchkey, stânga, pivot -1); } // sfarsit else (înjumătăţirea domeniului) } // sfarsitul metodei căutarec ()

Apelul unei metode presupune o anumită întarziere. Trebuie efectuat, transferul

controlului din punctul apelului catre începutul metodei. În plus, valorile parametrilor metodei

şi adresa de întoarcere a acesteia trebuie introduse într-o stiva interna, astfel încât metoda să

poată avea acces la parametrii şi să stie în ce punct să se întoarca.

Chiar daca de cele mai multe ori întarzierea nu este foarte mare, daca în urma utilizării

unei metode recursive rezultă foarte multe apeluri de metode este de preferat renunţarea la

recursivitate.

32


Un alt dezavantaj îl constituie memoria ocupată pentru a păstra toţi parametrii

intermediari şi rezultatele intoarse de apelurile recursive în stiva internă a sistemului. Aceasta

este o problemă serioasă atunci când rezultă o cantitate mare de date, putând conduce la

depăşirea capacităţii stivei.

Recursivitatea se foloseşte, de regulă, din cauză că simplifică problema din punct de

vedere conceptual şi nu pentru că ar reprezenta o soluţie mai eficientă.

Căutarea unui element y într-un şir X, ordonat i { 1, 2,... n } se poate face şi pe un

sistem folosind spre exemplu un număr de p procesoare în felul următor:

Se împarte şirul X în P subşiruri de lungimi aproximativ egale, fiecare procesor având în

sarcină realizarea căutării în unul din aceste subşiruri. În urma celor p căutări, fie se gaseşte

elementul egal cu y, fie se restricţionează căutarea într-unul din acele p segmente. În plus se

adaugă două elemente santinelă x0 = - şi xn = + .

2.5 CĂUTAREA ÎN LISTE ÎNLANŢUITE

În practica curentă listele înlanţuite sunt probabil cele mai frecvent folosite structuri de

date dupa tablouri.

Lista înlanţuită oferă un mecanism extrem de eficient care poate fi folosit în multe

tipuri de bază de date. Listele pot înlocui tablourile că structuri de baza pentru implementarea

altor structuri cum sunt stivele şi cozile. De fapt se poate utiliza o listă înlanţuită aproape în

orice loc unde se poate utiliza un tablou, iar atunci când trebuie să se aleagă care din aceste

structuri de date să fie folosite va fi nevoie de o analiza a aplicaţiei ce se doreşte a fi

realizată luându-se în calcul faptul că timpii de căutare, inserare, ştergere etc. pot diferi foarte

mult de la o structură de date la alta, respectiv de la un tablou la o lista înlanţuita.

Listele pot fi de doua feluri:

liste simpluînlanţuite sau pur şi simplu înlanţuite

liste dubluînlanţuite

O listă înlanţuită este alcatuită din o înşiruire de noduri care conţin informaţia (la fel

că elementele dintr-un tablou) specifică fiecărui nod în parte dar mai conţine şi o legătură

către nodul următor din lista la listele simpluînlanţuite, sau două legături, una către elementul

din stânga (nodul anterior) şi altul către elementul din dreapta (nodul următor) la listele

dubluînlanţuite. În limbaj Java un nod este reprezentat de fapt de o instanţă a unei clase

33


denumită să presupunem Link. Din cauză că există multe noduri similare în cuprinsul unei

liste (diferite prin informaţia continuta) va trebui creată o clasă separată de obiecte pentru

acestea, distinctă de clasă care descrie lista propriuzisă.

Liste simpluînlanţuite

Vom vorbi deocamdată de listele simpluînlanţuite. Pentru acestea fiecare nod conţine

o referinţa (denumită de obicei next) către următorul nod din listă, aceasta referinţă

reprezentand de fapt legătura. Un câmp din structura care descrie lista va conţine o referinţă la

primul nod din lista.

În continuare va fi prezentată o variantă a unei clase Link, care va contura nodurile

unei anumite liste. Pentru simplificare această clasă va conţine o infomaţie de tip int (care va

reprezenta cheia după care se va face căutarea), o informaţie de tip double, un constructor

(iniţializează datele la construirea unui nou nod), o metodă display() care afişeaza continutul

nodului curent şi o referinţa către urmatoarea legatura. Desigur că în practică un nod va

conţine un obiect al unei clase care va conţine toate informaţiile necesare. De pildă un astfel

de obiect ar putea conţine numele, adresa, codul numeric personal, funcţia, salariul şi multe

alte câmpuri cu privire la angajaţii unei firme. Astfel vom putea tine o evidenţa a personalului

acestei firme folosindu-ne de structura de date numită listă înlanţuită.

În elementele din listă trebuie să existe o informaţie folosita drept “cheie” în cadrul

căreia să existe o relaţie de ordine totală (oricare două elemente să poata fi comparate).

class Link

{

public int iData; // informaţii

public double dData; // informaţii

public Link next; // referinţă către urmatorul nod

public Link (int id,double dd) // constructor

{

iData = id;

dData = dd;

}

public void displayLink () // metoda poate lipsi pt o şi mai mare simplificare

{

System.out.println(“{“+Data+ ”, “ +dData+ “}”);

}

}

34


Observăm că aceasta clasă conţine un câmp (câmpul next) de acelaşi tip că şi clasa,

câmp care este de fapt o referinţă către următorul nod din lista. Asemenea definiţie pentru o

clasă este denumita autoreferinţa. În cadrul constructorului clasei nu este necesar să

iniţializăm şi “next“ acesta fiind automat iniţializat cu valoarea null.

Bineînteles că vom avea nevoie şi de o clasă care să contureze şi lista propriuzisă.

Aceasta, denumită LinkList va conţine numai un singur element şi anume o referinţă către

prima legătura din lista. Această referinţă va fi sugestiv denumita first şi este singura

informaţie permanentă pe care listă o menţine referitor la locaţia oricăreia dintre legaturi.

Celelalte legături vor fi regăsite prin parcurgerea lanţului de referinţe pornind de la first şi

utilizând câmpul next al fiecărei legaturi.

Clasa LinkList ar putea avea următoarea formă:

class LinkList

{

private Link first; // referinţa către primul element din listă

public LinkList () // constructor

{

first = null; // lista nu va conţine nici un element

}

public boolean isEmpty () // întoarce true dacă lista este goala

{

return (first = = null );

}

--------------------------------- // alte metode

}

Constructorul clasei LinkList iniţializează first cu null, deci primul element din listă va

fi null pentru că la ănceput lista este goală. Vedem că atunci când first are valoarea null lista

este goala (dacă lista ar fi continut elemente, first ar fi continut referinţa către primul dintre

acestea). Metoda isEmpty() utilizează acest fapt pentru a determina dacă lista este goală.

Codul metodei prin care se realizează căutarea va fi scris în interiorul acestei clase

LinkList, că de altfel şi celelalte metode obişnuite în lucrul cu structuri de date (inserare,

ştergere, parcurgere...).

Ştim că într-un tablou fiecare element ocupă o anumita poziţie care este direct

accesibilă utilizând un indice numeric. Într-o lista însa singura posibilitate de a găsi un anumit

element este de a urma întreg lanţul de elemente. Va fi nevoie aşadar să traversăm lista de la

35


cap la coada. Aceasta traversare va trebui să fie făcută folosind relatiile dintre elemente,

aşadar legăturile ne vor ajuta pentru a avansa de la un element la altul. Cum vom proceda:

vom începe cu primul element “first” (singurul element accesibil direct), după care continuam

cu al doilea, cu al treilea şi aşa mai departe până vom găsi elementul pe care îl căutăm.

Identificarea elementului se va face prin compararea cheii de căutare cu informaţiile din nodul

curent (nodul la care am ajuns la un moment dat).

Metoda de căutare într-o lista înlanţuita din clasa LinkList este:

Link find (int key) // caută un element cu o cheie data

{

if (first = = null) return null; // cazul când lista e goala

Link current = first; // se începe cu first

while (current.iData != key) // cât timp nu s-a găsit

{

if (current. next = = null) // s-a atins sfarşitul listei

return null; // cheia nu există în listă

else // înca nu s-a ajuns la sfarsit

current = current. next; // avanseaza la urmatorul nod

}

return current; // am gasit elementul

}

Vedem că pentru a căuta într-o listă avem nevoie de o variabilă curent care indică (se

refera către) pe rând spre fiecare dintre noduri, (cu ajutorul ei ne deplasam în lista).

Variabila curent începe prin a-l referi pe first (care conţine o referinţă către prima

legatură din lista). Instrucţiunea current = current. next îl face pe curent să avanseze la

urmatorul element din listă.

Această instrucţiune este pusă într-un ciclu while în care se verifică la fiecare pas dacă

s-a găsit elementul căutat, adică dacă valoarea cheii elementului curent (referit de curent) este

egală cu valoarea căutată.

Dacă acest element s-a gasit metoda va întoarce o referinţa către acel nod. Dacă însa

se atinge sfarşitul listei, adică dacă câmpul next dintr-un nod conţine valoarea null, şi înca nu

s-a gasit valoarea dorită, metoda va întoarce null.

Liste dubluînlanţuite

36


Ştim deja că o lista duluînlanţuita este alcătuita din o înşiruire de noduri care conţin

informaţie precum şi două referinţe (legaturi), unul către elementul din stânga (elementul

anterior) şi altul către elementul din dreapta (elementul următor). Principalul avantaj pe care îl

conferă lista dubluînlanţuita faţa de cea simpluînlanţuita este că aceasta va putea fi parcursă

atât înainte cât şi înapoi. Desigur că implementarea unei astfel de liste este ceva mai

complicată, iar fiecare dintre noduri va ocupa ceva mai multa memorie, însă de multe ori

proprietatea de a fi parcursă în ambele sensuri va avea o importanţa covârşitoare în a alege

lista dubluînlanţuita drept structura de baza a aplicaţiilor noastre.

Pentru o lista dubluînlanţuita clasa Link ar putea avea următoarea formă:

class Link

{

public int iData; // informaţii

public double dData; // informaţii

public Link next; // referinţa către urmatorul nod

public Link previous // referinţa către nodul anterior

public Link (int id,double dd) // constructor

{

iData = id;

dData = dd;

}

public void displayLink () // metoda poate lipsi pt o

// şi mai mare simplificare

{

System.out.print.(“{“+Data+ ”, “ +dData+ “}”);

}

}

Observăm că tot ce are în plus faţa de clasa Link a listei simpluînlanţuite este referinţa

previous spre nodul anterior. La fel clasa LinkList va fi asemănătoare cu clasa LinkList de la

lista simpluînlanţuită, doar că în cadrul constructorului va trebui să adaugăm o variabilă

“last” care va indica spre ultimul element din lista şi să iniţializăm această variabilă cu null,

ca şi pe first deoarece la construirea unei liste aceasta va fi goală.

Class LinkList

{

private Link first; // referinţa către primul element din lista

public LinkList () // constructor

{

first = null; // lista nu va conţine nici un element

37


}

public boolean isEmpty () // întoarce true dacă lista este goală

{

return (first = = null );

}

--------------------- // alte metode printre care şi cea de căutare, inserare, parcurgere, ştergere etc.

}

Operaţia de căutare nu va fi însa mult influenţată de faptul că lista este dublu sau

simpluînlanţuită, atât doar că această căutare va putea fi făcută prin parcurgerea listei

începând de la capatul listei sau de la sfarşitul acesteia.

Eficienţa căutarii în listele înlanţuite: Într-o lista înlanţuita căutarea presupune în

medie, parcurgerea a jumatate din totalul elementelor din lista (făcându-se câte o comparaţie

la fiecare nod parcurs), indiferent dacă lista e simplu sau dubluînlanţuita. Se vor face aşadar

O(N) comparaţii exact ca la un tablou neordonat.

Pentru o lista înlaţuită se vor obţine timpi mult mai buni decât în cazul tablourilor

neordonate la operaţiile de inserare şi ştergere (mai ales atunci când copierea este mullt mai

lentă decat comparatia) deoarece la tablouri aceste operaţii presupune o mutare a mai multor

elemente prin copiere spre stânga sau spre dreapta.

Un alt avantaj important pe care listele înlanţuite îl au faţa de tablouri este că o listă

utilizeaza exact cantitatea de memorie de care are nevoie, pe când dimensiunea unui tablou

este fixata la crearea acestuia ceea ce conduce de cele mai multe ori la ineficienţa.

2.6 CĂUTAREA ÎN ARBORI

Arborii binari reprezintă una dintre structurile fundamentale utilizate în programare.

Structura de arbore oferă multe avantaje faţă de celelalte structuri studiate, putându-se spune

chiar că aceasta structură de arbore combină avantajele oferite de alte două structuri:

tablourile şi listele înlanţuite. Arborii permit pe de o parte executarea unor căutari rapide,

întocmai ca şi tablourile ordonate (căutarea binara), iar pe de altă parte, inserarea şi ştergerea

rapidă a elementelor la fel ca şi o listă înlanţuită.

Un arbore constă din noduri, care sunt unite prin muchii şi reprezintă de fapt o

particularizare a unei categorii mai generale numită graf. Nodurile se vor reprezenta grafic

prin niste cerculeţe conectate prin nişte linii care nu sunt altceva decât muchii.

38


În programare nodurile reprezintă, de regulă, entitaţi din lumea reală (elemente

obişnuite pe care le putem memora în oricare altă structură de date), iar muchiile dintre noduri

reprezintă modul în care muchiile sunt conectate (exact ca legăturile de la listele înlanţuite).

Singurul mod de a ajunge de la un nod la altul este de a urma un drum de-a lungul muchiilor.

În general deplasarea cu ajutorul muchiilor este limitată la o singura direcţie: de la rădăcina

arborelui în jos.

De regulă, nivelul superior, numit nivelul 0 al unui arbore cuprinde un singur nod

(rădăcină), conectat prin muchii cu nodurile sale fiu aflate pe nivelul imediat inferior (nivelul

1). Aceste noduri pot avea şi ele la randul lor noduri fii aflate pe nivelul 2 ş.a.m.d.

Orice nod (cu excepţia radacinii) are exact o muchie orientată în sus spre un alt nod.

Nodul situat mai sus este numit părintele nodului curent.

Un nod fără fii se numeşte frunză şi orice nod poate fi considerat ca fiind rădăcină

pentru un subarbore, care cuprinde fiii acelui nod, fiii fiilor săi ş.a.m.d.

Nodurile unui arbore vor conţine obiecte, instanţe ale unor clase gata construite.

Valoarea elementului de un anumit tip, conţinută de un obiect, poate fi considerată cheie.

Această valoare poate fi utilizată pentru a cauta elementul sau pentru a executa alte operaţii

asupra sa.

Există mai multe tipuri de arbori. Printre aceştia arborele binar (arborele în care orice

nod poate avea cel mult doi fii), este cel mai simplu tip de arbore dar totodata şi cel mai des

folosit.

Cei doi fii ai unui nod se numesc fiu stâng şi respectiv fiu drept în funcţie de poziţia

lor în reprezentarea grafică a arborelui. Pot exista noduri într-un arbore binar cu mai puţin de

doi fii; astfel un nod poate avea doar un fiu stâng, sau doar un fiu drept, ori poate să nu aibă

nici un fiu (caz în care nodul este frunză).

Din punct de vedere tehnic caracteristica esenţială a unui arbore binar de căutare este

că cheia fiului stâng trebuie să fie mai mică decât cea a părintelui, iar cheia fiului drept trebuie

să fie mai mare sau egală cu cea a părintelui.

Ca o definiţie a arborelui de căutare binară am putea spune că acesta este un abore

binar în care fiecare nod conţine o cheie (informaţie importantă cu care se va face comparaţii

în timpul căutarii ) ce satisface următoarele condiţii:

toate cheile din subarborele stâng (dacă există preced cheia din rădăcină)

39


cheia din rădăcină precede toate cheile din subarborele drept (dacă există)

subarborii stâng şi drept sunt la rândul lor arbori de căutare

Căutarea unui nod: această operaţie de căutare a unui nod cu o anumită cheie este cea

mai simplă dintre cele trei operaţii de bază (inserare, ştergere, căutare).

Informaţia din câmpul cheie poate fi de orice tip de dată peste care se poate defini o

relaţie de ordine totala, iar cheile de identificare sunt întotdeauna distincte. Acestea pot

reprezenta la rândul lor spre exemplu persoane, rolul de cheie putând fi jucat de codul

numeric personal, iar printre alte câmpuri figurând numele, adresa, numărul de telefon etc.

Pentru construirea unui arbore binar vom avea nevoie în primul rând de o clasă Nod prin care

să reprezentăm nodurile arborelui. Acestea conţin atât informaţii care reprezintă atât obiectele

memorate cât şi referinţe către cei doi fii. Un exemplu este:

class Node

{

public int iData; // informaţia utilizată cu

// rol de cheie

public float fDate // alte informaţii

Node leftChild; // fiul stâng

Node rightChild; // fiul drept

public void displayNode ()

{

System.out.print(‘{’);

System.out.print(iData);

System.out.print(“,”);

System.out.print(fData);

System.out.print(“}”);

}

}

Vom avea apoi nevoie de o clasă care să reprezinte arborele însusi: acesta va fi

obiectul care va conţine toate nodurile. Un astfel de obiect are nevoie de un singur câmp: o

variabila de tip Node care sa conţină rădăcina arborelui. Nu avem nevoie de câmpuri pentru

celelalte noduri deoarece acestea sunt accesibile pornind din rădăcină. Această clasă va

conţine şi diferite alte metode printre care void find (int key) – pentru căutare; void insert (int

id, float dd) – pentru inserare; void delete (int id).

40


class Tree

{

private Node root; //singurul câmp al clasei Tree

public Node find (int key)

{

..............................

}

public void insert (int id, float dd)

{

.............................

}

public void delete (int id)

{

.............................

}

// diferite alte metode

}

În continuare va fi prezentată metoda Java care permite căutarea unui nod într-un

arbore returnând apoi la sfarşit nodul în care a fost găsită cheia sau null dacă cheia nu se

gaseşte în arbore:

Node find (int key); // caută nodul cu o anumită cheie

{ // presupune arborele nevid

Node current = root; // începand cu rădăcina

while (current. iData != key) // cat timp n-am gasit

{ // elementul

if (key < current. iData) //deplasare la stanga?

current = current. leftChild;

else

current = current. rightChild; // sau la dreapta ?

if (current = = null) // dacă nu exista descendenţi

return Null; // cheia nu este în arbore

}

return current; //am găsit nodul conţinând cheia căutată

}

Aceasta metodă utilizează variabila current pentru a memora nodul curent examinat.

Parametrul key este valoarea căutată. Metoda începe căutarea din rădăcina arborelui (de fapt

numai de acolo se putea deoarece rădăcina este singurul nod accesibil), vedem deci că

valoarea iniţială a lui current va fi chiar nodul rădăcină root.

41


În ciclul while se compară valoarea key cu câmpul iData (cheia) din nodul curent.

Dacă valoarea key este mai mică decât acest câmp, current va avansa în arbore la fiul stang al

nodului curent. Dacă însa valoarea key este mai mare sau egală cu câmpul iData al nodului

curent, current va avansa la fiul drept al acestuia.

Dacă valoarea lui current devine null, înseamnă că nu mai putem avansa în arbore; am

epuizat orice posibilitate de a găsi elementul dorit, deci acesta nu există. Vom întoarce aşadar

valoarea null, pentru a indica aceasta situatie.

Obsevăm însă că ciclul while se poate termina şi atunci când condiţia sa nu mai este

satisfăcută, deci când câmpul iData al lui current este egal cu valoarea key, ceea ce înseamnă

că am gasit elemntul dorit. Vom întoarce în acest caz nodul respectiv astfel încât metoda care

a apelat find () să poată prelucra toate datele pe care acesta le conţine.

Eficienţa operatiei de căutare a unui nod într-un arbore binar de căutare:

Dupa cum se poate observa, timpul necesar pentru găsirea unui nod depinde de

numărul de niveluri parcurse până când acesta a fost gasit.

Într-un arbore complet, aproximativ jumatate de noduri se afla pe ultimul nivel, mai

exact pe ultimul nivel vor fi cu exact un nod mai mult decat în tot restul arborelui. Prin urmare

aproximativ jumătate din operaţiile de căutare vor viza un nod de pe ultimul nivel. (Un alt

sfert dintre operaţii vor implica accesul la un element de pe penultimul nivel).

Pe parcursul unei căutări, vom vizita câte un nod de pe fiecare nivel; prin urmare,

durata necesară operaţiei de căutare va fi direct proporţională cu numărul de niveluri.

Presupunând că arborele este complet, vom avea:

1 nod ----------------------------------------------------1 nivel

3 noduri -------------------------------------------------2 niveluri

7 noduri ------------------------------------------------ 3 niveluri

15 noduri -----------------------------------------------4 niveluri

31 noduri -----------------------------------------------5 niveluri

----------------------------------------------------------------------

1.023 noduri ------------------------------------------10 niveluri

----------------------------------------------------------------------

32.767 noduri -----------------------------------------15 niveluri

-----------------------------------------------------------------------

1.048.576 noduri -------------------------------------20 niveluri

-----------------------------------------------------------------------

33.554.432 noduri ------------------------------------25 niveluri

42


-----------------------------------------------------------------------

1.073.741.824 noduri --------------------------------30 niveluri

Observăm deci că pentru a căuta unul din cele 1.073.741.824 noduri ale unui arbore

binar de căutare complet vom avea de parcurs doar 30 de niveluri deci vom avea de făcut doar

30 de comparaţii.

Vom avea o situaţie similară cu cea de la tablourile ordonate, în care am văzut că

numărul de comparaţii efectuate într-o operaţie de căutare binara este aproximativ egal cu

logaritmul binar (în baza 2) al numărului de celule din tablou. În cazul arborilor, dacă notăm

numărul de noduri N şi numărul de niveluri cu L, observăm că N este inferior cu o unitate

faţă de 2 ridicat la puterea L:

N=2L-1

Adunând 1 în ambii membri ai ecuatiei, rezultă:

N+1=2L

Această notaţie este echivalentă cu:

L=log2(N+1)

Prin urmare, timpul necesar pentru executarea operaţiei de căutare într-un arbore binar

este proporţional cu logaritmul binar al lui N. Utilizând notaţia O, putem afirma că operaţia de

căutare durează un timp de ordinul O(log N).

Dacă arborele nu este plin (complet), analiza se complică. Se observă însă că pentru

un arbore cu un anumit număr de niveluri, timpul mediu de căutare este mai scurt în cazul în

care arborele nu este plin, datorita faptului că se efectuează mai puţine căutări în nivelurile

inferioare.

Ce se va întampla însă dacă în momentul construcţiei arborelui binar de căutare se vor

insera elementele aproape ordonate (crescator sau descrescator) ? În acest caz arborele binar

va fi neechilibrat, sau chiar va degenera de fapt într-o lista înlanţuită, aranjamentul

unidimensional al datelor înlocuindu-l pe cel bidimensional. Din nefericire, ca şi în cazul unei

liste înlanţuite trebuie să parcurgem acum în medie, jumătate din numărul total de elemente

pentru a gasi unul anume. Viteza operatiei de căutare scade de la valoarea O(logN), care

caracterizeaza un arbore echilibrat la O(N), viteză cu care se face căutarea şi într-o lista

înlanţuită oarecare. De aceea s-a cautat o metodă de păstrare a arborelui binar de căutare cât

mai echilibrat şi s-a ajuns la arborii AVL în care apare noţiunea de balans (subarborii stang şi

43


drept ai fiecărui nod să nu aibă înalţime mai mare unul decat celalat o unitate). Arborii AVL

se obţin prin aplicarea anumitor reguli operaţiilor de inserare şi de ştergere a unui nod într-un

arbore. Operaţia de căutare nu va fi schimbată deci nu va fi necesar să o mai analizăm.

Comparând arborii cu celelalte structuri de date de care am vorbit până în prezent,

vom vedea că într-un tablou neordonat sau într-o lista cu 1000000 de elemente, sunt necesare,

în medie, 500000 de comparaţii pentru a cauta un anumit element, în timp ce într-un arbore cu

acelasi număr de noduri, numărul de comparaţii efectuate este însa cel mult 20.

Un arbore se poate implementa şi sub forma unui tablou în interiorul căruia poziţiei

fiecărui nod îi va corespunde poziţiei în arbore. Astfel nodul cu indicele 0 este rădăcina

arborelui, cel cu indicele 1 este fiul stang al radacinii ş.a.m.d., mergând de la stânga spre

dreapta pe fiecare nivel al arborelui.

Celulele care reprezinta poziţii din arbore în care nu se afla noduri vor conţine

valoarea 0 sau null.

Cu această metodă, fii şi părintele unui nod oarecare se pot determina cu ajutorul unei

expresii simple pornind de la indicele nodului curent în tablou. Dacă indicele unui anumit nod

are valoarea index, atunci fiul său stâng va avea indicele 2*index+1, iar cel drept 2* index+2,

în timp ce părintele are indicele (index-1)/2, unde operatorul “/” semnifică împarţirea întreagă,

fără considerarea restului (div în Pascal).

De cele mai multe ori tabloul în care este memorat arborele binar nu este ordonat şi se

poate face căutarea atât ca într-un vector (ceea ce nu va duce la o eficienţă prea mare) cât şi ca

într-un arbore.

În majoritatea cazurilor, reprezentarea unui arbore printr-un tablou nu este foarte

eficientă. Nodurile inexistente produc goluri în tablou şi conduc astfel la un consum inutil de

memorie.

2.7 CĂUTAREA ÎN TABELE DE DISPERSIE

Tabelele de dispersie (hash tables) sunt structuri de date folosite în programe în

care este necesară căutarea într-un timp foarte scurt a unui anumit element prin câteva

zeci de mii de alte elemente.

44


Un exemplu de astfel de program ar fi unul pentru verificarea ortografiei a

cuvintelor dintr-un text, sau altul pentru realizarea unui dicţionar explicativ al limbii

române. O altă aplicaţie des întrebuinţată a tabelelor de dispersie este în cadrul

compilatoarelor limbajelor uzuale de programare, care păstrează o “tabela de

simboluri” implementată printr-o astfel de structură. “Tabela de simboluri” conţine

toate numele variabilelor şi funcţiilor definite de programator, precum şi adresele la

care aceste obiecte pot fi găsite în memorie. Aceste programe au nevoie de un acces

rapid la datele memorate prin urmare structura de date care este preferata va fi tabela

de dispersie.

Tabelele de dispersie sunt semnificativ mai rapide decât arborii care operează

într-un timp relativ scurt O(logN). Aceste tabele sunt totodată şi foarte simplu de

programat.

Din cauza faptului că tabelele de dispersie se bazează pe tablouri (tablourile sunt

greu de expandat dupa ce au fost create), va trebui ca programatorul să fie foarte atent

la implementarea acestora. Astfel programatorul trebuie să aproximeze destul de bine

dinainte numărul de elemente pe care le va insera pentru că în unele tipuri de tabele de

dispersie performanţele se degradează catastrofal la umplerea tabelei peste un anumit

prag. Un alt dezavantaj a tabelelor de dispersie este că nu există o modalitate de a vizita

într-o anumită ordine elementele acesteia ca la alte structuri (tablouri, liste, arbori etc.).

Noţiunea fundamentală în conceptul de dispersie a datelor este transformarea

unui domeniu de valori ale unei anumite chei într-un domeniu de indici dintr-un tablou.

Într-o tabelă de dispersie, această operaţie este realizată cu ajutorul unei aşa-numite

funcţii de dispersie, care însă trebuie bine aleasă astfel încât să genereze suficienţi indici

pentru programul folosit. Totodată această funcţie nu trebuie să genereze mult mai

mulţi indici decât avem nevoie (aici este vorba de un număr mult prea mare, de ordinul

milioanelor) doar astfel tabela de dispersie va putea să funcţioneze aşa cum

programatorul şi-a propus.

Dispersia unui şir de caractere se poate efectua şi se efectuează în general prin

înmulţirea codului Ascii a fiecărui caracter cu o anumită putere a unei baze, adunarea

acestor produse şi aplicarea operatorului modulo (%) pentru a putea obţine un rezultat

în domeniul de indici a tabelei de dispersie.

Pentru a evita depăşirea aritmetica a capacitaţii de memorare a vre-uneia dintre

variabile, se va aplica operatorul modulo la fiecare pas al operaţiei, calculând codul

polinomial cu ajutorul schemei lui Horner dupa cum urmează:

45


var4*n4 + var3*n3 + var2*n2 + var1*n1 + var0*n0 =

= (((var4*n + var3)*n + var2)*n + var1) + var0

O de funcţie de dispersie eficientă pentru conversia şirurilor de caractere

(caracterele folosite în limba engleză ) este:

public static int hashFunc(String key){

int hashVal = 0;for (int j =0; j<key.length(); j++) { int letter = key.charAt(j)-96; hashVal = (hashVal*27+letter) % arraySize; }

return hashVal;}

unde 96 reprezintă codul Ascii pentru litera “a”.

S-a înmulţit cu 27 din pricina faptului că am luat cazul alfabetului englez care

conţine 26 litere mici plus spatiul.

Se pot efectua de asemenea diferite operaţii la nivel de biţi, utilizând baza 32 (sau

o putere mai mare a lui 2) în locul bazei 27, astfel încât înmulţirea să fie înlocuită de

operatorul de deplasare (“>>”), care este mai rapid decât operatorul modulo.

În situaţia în care funcţia de dispersie nu este injectivă vor exista mai multe

valori din domeniul nostru care să genereze acelaşi indice. Dacă la construirea unei

tabele de dispersie ajungem la un moment dat să trebuiască să inseram un element pe

un anumit loc (obţinut prin aplicarea funcţiei de dispersie) şi vom găsi acel loc ocupat de

un alt element vom ajunge la o aşa-zisă coliziune.

Se poate crede că posibilitatea apariţiei coliziunilor face ca metoda dispersiei să

nu aibă utilitate practică, însă problema se poate rezolva în doua moduri.

Luându-se dimensiunea tabloului cam de doua ori mai mare decât numărul

elementelor din imaginea funcţiei de dispersie vom putea ca la apariţia unei coliziuni să

căutam în tablou (într-un mod prestabilit) o celulă liberă, după care să inseram noul

element în în celula respectivă, astfel la o operaţie de căutare vom ştii unde să aflăm

acest nou element. Această metodă poartă numele de “adresare deschisă”.

O a doua metodă de rezolvare a problemei coliziunilor este de a crea un tablou

care să conţină liste înlanţuite. La apariţia unei coliziuni, noul element va fi inserat într-

o listă de cuvinte care au toate acelaşi indice corespunzator tabloului considerat. Metoda

poartă numele de “înlanţuire separata”.

Adresarea deschisă

46


Dacă se încearcă inserarea cât mai multor elemente în tabela de dispersie se va

observa crearea unor fascicule de elemente care pe măsură ce tabela se umple devin din

ce în ce mai mari. Crearea de fascicule lungi conduce la creşterea lungimilor de sondaj.

Prin urmare, accesul la elemente de la sfarşitul secvenţei va deveni foarte lent.

Cu cât tabela este mai plină cu atât efectele creării de fascicule devin mai

neplăcute. Nu este nici o problemă dacă tabela este plină pe jumătate până la o

proporţie de două treimi. Peste aceasta însa, performanţele se degradează serios o data

cu creşterea fasciculelor. Din acest motiv la proiectarea unei tabele de dispersie, trebuie

să ne asigurăm că aceasta nu se umple mai mult de jumătate sau cel mult două treimi.

În continuare este dat codul Java pentru o metodă de căutare într-o tabela de

dispersie utilizând metoda sondajului liniar.

public DataItem find(int key) // caută elementul cu cheia key // vom presupune că tabela nu este plină{

int hashval = hashFunc(key); // transformă cheiawhile (hashArray[hashval] != null)

// este celula curentă o celulă liberă ?{ if (hashArray[hashval].iData == key) // am găsit cheia? return (hashArray[hashval]); // da, întoarce elementul ++hashval; // deplasare la următoarea celulă hashval %= arraySize; // reia de la începutul tabelei dacă este cazul}return null; // elementul nu este în tabelă

}

Această metodă find() va apela mai întâi hashfunc() care nu este altceva decât

funcţia de dispersie care ne va transforma cheia de căutare, obţinând indicele hashval.

În cazul de faţă funcţia de dispersie, respectiv metoda hashfunc() aplică operatorul %

între cheia de căutare şi dimensiunea tabloului. Acest operator “modulo” se va constitui

ca o funcţie eficientă de dispersie în cazul variabilelor numerice.

Într-un ciclu while, metoda find() verifică apoi dacă celula din tablou cu indicele

hashval este sau nu ocupată (dacă nu este ocupat, are valoarea null). Dacă această celulă

este ocupată se va verifica dacă elementul din celulă are sau nu aceeaşi valoare cu cheia

de căutare. În fine, dacă elementul nu se afla în celula curenta, find() va incrementa

indicele hashval şi va relua ciclul while, verificând dacă urmatoarea celulă este sau nu

ocupată.

Pe masură ce hashval parcurge tabela, poate ajunge la sfârşitul acesteia. Atunci

când aşa ceva se întâmplă, vom ajusta hashval, astfel încât să reia parcurgerea tabelei de

47


la început. Putem verifica această condiţie într-o instructiune if, în care hashval va primi

valoarea 0 de fiecare dată când ajunge egal cu dimensiunea tabelei.

Este prudent a nu se presupune implicit că tabela nu este plina, aşa cum am facut

pentru simplificare mai sus. Trebuie să ne asiguram ca tabela nu se umple; în caz

contrar, metoda se va executa la infinit.

O posibilitate de evitare a umplerii tabelei de dispersie este de a expanda tabela

atunci când aceasta se umple prea mult. În aproape toate limbajele de programare

tablourile au dimensiuni fixe şi nu pot fi expandate. Se poate însa crea o nouă tabelă,

mai mare în care să se redistribuie apoi conţinutul vechii tabele. Această operaţie

consumă însa în general foarte mult timp pentru că nu se poate copia pur şi simplu

elemente dintr-un tablou în altul ci trebuie parcursă secvenţial vechea tabela inserând

fiecare element în tabela nouă cu ajutorul unei metode insert(). Acest lucru este necesar

pentru că de cele mai multe ori metoda insert() va calcula poziţia anumitor elemente în

cadrul structurii, funcţie şi de dimensiunea tabelei care însa e diferită de la vechea la

noua tabelă.

În limbajul Java dispunem de o clasă numită Vector, care reprezintă o structură

similară unui tablou, cu posibilitatea de a se expanda. Aceasta nu este însă de cele mai

multe ori o soluţie potrivită, deoarece la modificarea dimensiunii tabelei, va trebui

calculate noile poziţii ale elementelor. Aşadar expandarea unei tabele poate fi o soluţie

practică numai dacă se dispune de suficient timp.

Am observat că în cazul tabelelor cu adresare deschisă care utilizează metoda

sondajului liniar, pot apărea fascicule de elemente. După ce se formează fasciculele tind

să crească. Noile elemente, corespunzătoare valorilor din domeniul reprezentat de

fascicul, se vor deplasa inserându-se la sfârşitul secvenţei care prin urmare va creşte. Cu

cât un fascicul are lungimea mai mare cu atât acesta va creşte mai repede.

Raportul dintre numărul de elemente dintr-o tabela şi dimensiunea tabelei se

numeste coeficient de încărcare.

loadFactor = nItems/arraySize;

Fasciculele se pot forma chiar atunci când coeficientul de încărcare are valori

scăzute. O parte din tabelă poate conţine deci fascicule lungi, cealaltă parte ramânând

aproape neocupată. Prezenţa fasciculelor conduce la scăderea performanţei tabelei.

O posibilitate de prevenire a formării fasciculelor este utilizarea sondajului

pătratic. Ideea acestei metode este de a sonda celule distribuite pe o arie mai larga, în

locul celor imediat adiacente locului în care trebuie efectuată inserarea.

48


Metoda sondajului pătratic mareşte pasul de căutare la fiecare iteraţie efectuată.

Într-un sondaj liniar, dacă indicele iniţial de dispersie este x, celulele sondate ulterior

vor fii x+1, x+2, ….etc. Sondajul pătratic presupune examinarea celulelor x+1, x+4, x+9,

x+16 etc. Deci distanţa dintre acestea şi celula iniţiala este egală cu pătratul iteraţiei.

La prima iteraţie, algoritmul alege o celulă adiacentă. Dacă aceasta este ocupată,

algoritmul presupune că se gaseşte într-un fascicul şi sare la o distanţă de 4 celule de

locul iniţial. Dacă şi aici găseşte o celulă ocupată, va presupune că fasciculul în care se

află este ceva mai lung şi va încerca la o distanţă de 9 celule. Algoritmul va căuta cu

disperare un loc liber atunci când tabela este aproape plină reducând timpul acestui

proces faţa de sondajul liniar.

Sondajul pătratic rezolvă problema fasciculelor, care pot apărea în cazul

sondajului liniar; această problemă poartă numele de acumulăre primară. Sondajele

pătratice produc însă un tip diferit (şi mai greu de detectat) de acumulări. Aceste

acumulări poartă numele de acumulări secundare şi apar datorită faptului că pentru

toate cheile asociate unei anumite celule, se parcurge aceeaşi secvenţă în căutarea unui

loc liber (se urmează tot aceeaşi paşi).

Pentru a elimina şi acumularea secundară pe langă cea primară, se utilizează

metoda dublei dispersii sau redispersii. Aceată metodă va trece cheia care urmează a fi

inserată (pentru căutare se va parcurge tabela dupa acelaşi algoritm) prin două funcţii

de dispersie care trebuie să fie diferite una de cealaltă iar rezultatul acestor funcţii nu

trebuie niciodată să fie 0 (se va genera o deplasare nulă în cadrul tabelei).

Astfel se generează secvenţe de sondaj care vor depinde de fiecare cheie în parte,

valorile diferite asociate aceluiaşi indice vor utiliza în consecinţa secvenţe de sondaj

diferite.

Experţii au descoperit că funcţiile de forma următoare dau rezultate bune:

stepSize = constanta – (key % constanta);

unde constanta este primă şi mai mică decât dimensiunea tabloului. Utilizând un număr

prim ca dimensiune a tabelei, ne asigurăm că aceasta nu este un multiplu al pasului de

deplasare, deci secvenţa de sondaj va vizita toate celulele din tabela.

Pentru o cheie dată, toate iteraţiile vor determina o deplasare cu un pas constant,

dar o alta cheie va modifica acest pas.

Pentru căutarea într-o tabelă de dispersie folosind metoda dublei dispersii se va

utiliza o metoda de tipul:

49


DataItem find(int key) // caută elementul cu cheia key// vom presupune ca tabela nu este plina{

int hashval = hashFunc1(key); // calculează indiceleint stepSize = hashFunc2(key); // calculează pasulwhile (hashArray[hashval] != null)

// este celula curentă o celulă liberă ?{ if (hashArray[hashval].iData == key) // am găsit cheia? return (hashArray[hashval]); // da, întoarce elementul hashval += stepSize; // adună pasul hashval %= arraySize; // reia de la începutul tabelei dacă este cazul}return null; // elementul nu este în tabelă

}

Desigur că şi metoda de inserare a datelor în tabela de dispersie va ţine cont de

cele doua funcţii hashFunc1 şi hashFunc2 iar ele vor fi definite în felul următor:

public int hashFunc1{ return key %= arraySize;}//---------------------------------public int hashFunc2{ return 5-key % 5;}//---------------------------------public void insert(int key,DataItem item){ int hashval = hashFunc1(key); // calculează indicele int stepSize = hashFunc2(key); // calculează pasul// până când celula este libera sau egală cu -1 while (hashArray[hashval] != null && hashArray[hashVal].iData != -1) { hashval += stepSize; // adună pasul hashval %= arraySize; }hashArray[hashval] = item; // inserarea propriuzisă}

Înlănţuire separată

Reprezintă o abordare diferită a noţiunii de tabelă de dispersie. Astfel fiecare

celulă din tabelă va conţine câte o listă înlanţuita. Cheia unui anumit element este

transformată într-un indice prin aplicarea funcţiei de dispersie, elementul fiind apoi

inserat în lista înlănţuită din celula cu indicele calculat anterior. Celelalte elemente,

cărora le va corespunde acelaşi indice, vor fi inserate în aceeasi lista; nu va fi deci nevoie

de căutarea unei celule libere în tabela.

Înlănţuirea separată este mai simplă din punct de vedere conceptual decât

adresarea deschisă. Programul va fi însa ceva mai lung, deoarece trebuie să conţină şi

primitivele de lucru cu liste, de regulă grupate într-o clasa suplimentară.

50


Coeficientul de încărcare are valori diferite faţa de cazul adresării directe. În

metoda înlănţuirii separate, este normal ca o tabelă cu N celule să conţină cel putin N

elemente; coeficientul de încărcare va avea deci valori supraunitare. Această încărcare

nu reprezintă însă o problemă. Desigur în momentul în care listele conţin multe

elemente, timpul de acces creşte, din cauză că va trebui să fie parcursă întreaga listă

până la elementul ce se vrea a fi accesat.

Găsirea celulei iniţiale se efectuează într-un timp foarte scurt O(1), dar căutarea

printr-o lista înlănţuită necesită un timp proporţional cu numărul de elemente din lista

O(M). Prin urmare în cadrul procesului de căutare este de preferat ca listele tabelei de

dispersie să nu fie prea încărcate.

În schema adresării directe, performanţele se degradează foarte mult când

coeficientul de încărcare depaşeşte valoarea de 2/3. Înlănţuirea separată permite o

creştere a acestui factor la valori supraunitare, fară a afecta prea mult performanţele

tabelei de dispersie. Din acest motiv, înlănţuirea separată reprezintă o metodă robustă,

în special atunci când numărul elementelor inserate în tabela este greu de anticipat.

Valorile multiple sunt permise şi pot fii generate în procesul de umplere a tabelei.

Toate elementele cu o aceeaşi cheie vor fii inserate în aceeaşi listă. Pentru a le descoperi

este necesar să parcurgem întreaga listă ceea ce conduce la o scădere a performanţelor.

Dimensiunea tabelei nu mai trebuie să fie în acest caz număr prim cum se

recomandă în cazul sondajului pătratic şi dublei dispersii. Nemaiexistând sondaje a

dispărut şi pericolul ca un sondaj să între intr-o bucla infinită, din cauză că dimensiunea

tabelei este divizibilă cu pasul de deplasare.

O altă posibilitate, similară înlănţuirii separate este ca fiecare celulă din tabelă să

conţina un tablou (galeţi sau buckets) în locul listei înlănţuite. Aceasta soluţie este mai

ineficienta decât cea care utilizează liste, din cauza necesitatii de a stabili dimensiunea

tablourilor. Dacă acestea sunt prea mici capacitatea lor ar putea fi depăşită, iar dacă

sunt prea mari determină un consum inutil de memorie. Listele înlănţuite care alocă

memoria în mod dinamic evită acest dezavantaj.

În cazul înlănţirii separate este util să se lucreze cu liste sortate în avantajul

operaţiei de căutare dar în detrimentul celei de inserare. Acest lucru este de preferat nu

pentru că ar creşte viteza unei operaţii reuşite de căutare, dar pentu că în cazul unei

căutari nereuşite timpul este redus la jumătate (căutarea ia sfârşit şi este considerată

nereuşită când se gaseşte o anumită valoare mai mare decât cea cautată ceea ce în medie

se întâmplă după parcurgerea unei jumătăţi din elementele listei).

51


În cazurile în care în care se anticipează un număr mare de căutări nereuşite,

utilizarea listelor sortate este preferat în locul listelor simple. Dacă însa viteza de

inserare contează în primul rând se vor utilize listele nesortate.

Eficienţa tabelelor de dispersie

Adresarea directă

Am observat că inserarea şi căutarea într-o tabelă de dispersie se pot efectua

într-un timp apropiat de cel constant O(1). Daca nu apar coliziuni atât inserarea cât şi

căutarea unuia existent se reduc la un simplu apel al funcţiei de dispersie şi la un singur

acces în tabelă. Acesta este timpul de acces minim.

În cazul apariţiei coliziunilor, timpul de acces depinde de lungimea secvenţelor de

sondaj rezultate. Fiecare acces la o celulă, în procesul de sondaj adaugă un increment la

timpul de căutare pentru o celulă existentă în tabelă (în cazul căutarii). Un acces

presupune detectarea celulelor libere şi comparaţia dintre valoarea din celula curentă şi

valoarea dorită.

Prin urmare timpul unei anumite operaţii de căutare este direct proporţional cu

lungimea sondajului efectuat. Acesta se adună la timpul constant necesar calculului

funcţiei de dispersie.

Lungimea medie a sondajului (aşadar şi timpul mediu de acces) depinde de

coeficientul de încărcare mai ales în cazul adresării directe. Pe măsură ce coeficientul de

încărcare creşte, secvenţele de sondaj devin din ce în ce mai lungi.

În adresarea directă căutarile nereuşite durează mai mult decât cele reuşite. Pe

parcursul unei secvenţe de sondaj, algoritmul se poate opri de îndată ce gaseşte

elementul dorit, ceea ce se întamplă în medie, la jumătate din lungimea totală a

secvenţei. Pe de altă parte, într-o căutare nereuşită, algoritmul trebuie să parcurgă

întreaga secvenţă, nefiind sigur dacă va găsi sau nu elementul.

Sondajul liniar

Daca notăm cu P lungimea sondajului şi cu L coeficientul de încărcare vom avea

relaţia:

P = (1+1/(1-L)2)/2 (Knuth)

în cazul unei căutari reuşite şi:

P = (1+1/(1-L))/2 (Knuth)

în cazul unei căutari nereuşite.

52


Concluzia dupa cum se observă este că factorul de încărcare nu trebuie să

depăşească 2/3 sau dacă este posibil 1/2. Pe de altă parte cu cât factorul de încărcare este

mai mic cu atât se consumă mai multă memorie pentru a stoca un anumit volum de

date. Valoarea optimă a coeficientului de încărcare, într-o anumită situaţie depinde de

compromisul dintre eficienţa utilizării memoriei, care scade la valori mici ale

coeficientului şi viteza care creşte.

Performanţele pentru metodele de sondaj pătratic şi dubla dispersie sunt descrise

prin ecuaţii comune. Acestea indică o superioritate uşoară faţă de sondajul liniar

deoarece sondajul pătratic şi dubla dispersie tolereaza şi valori ceva mai mari ale

coeficientului de încărcare, fără o degradare severă a performanţelor. În cazul unei

căutări reuşite formula dupa lucrarea lui Knuth este:

-log2(1-loadFactor) / loadFactor

În cazul unei căutări nereuşite vom avea:

1/(1-loadFactor)

Înlănţuirea separată

Pentru analiza eficienţei în acest caz vom presupune că timpul necesar pentru

determinarea listei potrivite şi pentru detectarea sfârşitului unei liste este egal cu timpul

necesar unei comparaţii. Cea mai lungă operaţie va fi comparaţia cheii elementului cu

celelalte chei din lista. În medie fiecare listă din tabela de dispersie va avea o lungime

medie egală cu a coefientului de încărcare (nrElem /arraySize).

Într-o operaţie reusită de căutare, algoritmul determină lista potrivită şi apoi

caută elementul dorit în aceasta. În medie, trebuie examinate jumătate din elemente

înainte de a-l găsi pe cel corect. Prin urmare timpul de căutare mediu este:

1+coef_încărcare/2.

Aceasta relaţie este valabilă indiferent dacă listele sunt sau nu sortate. Într-o

căutare nereuşită dacă listele sunt neordonate, trebuie parcurse toate elementele, deci

timpul este: 1+coef_încărcare

În cazul listelor ordonate, o căutare nereuşită va examina, în medie, jumătate

dintre elemente, timpul fiind deci acelaşi ca şi pentru o operaţie reuşită.

În metoda înlănţuirii, se utilizează, de regulă un coeficient de încărcare de

aproximativ 1 (numărul de elemente egalează dimensiunea tabelei). Valorile mai mici

ale factorului de încărcare nu determină îmbunătătiri semnificative ale performanţelor,

timpul necesar tuturor operaţiilor creşte însă liniar în raport cu coeficientul de

încărcare, deci depaşirea valorii 2 nu este recomandată.

53


Dispersia şi memorarea externă

Ca şi arborii tabelele de dispersie pot fi folosite ca structuri de memorare a

informatiei pe suport extern.

Un fisier de date este impartit în blocuri care contin multe inregistrari, timpul de

acces la un bloc de pe disc fiind mult mai mare decât timpul de prelucrare a datelor

aduse în memoria principala. Din aceste motive scopul esential urmarit în proiectarea

unei strategiide memorare externa este minimalizarea numărului de accese la blocuri de

pe disc.

Pe de alta parte, suportul extern este relativ ieftin, deci acesta poate fi utilizat în

cantitati mari pentru memorarea datelor, în scopul creşterii vitezei de acces. Aceasta

creştere se realizeaza utilizand tabelele de dispesie.

Principala facilitate prin care se implementeaza dispersia externa este o tabela

index care conţine pointeri catre blocurile de pe suportul extern. Aceasta tabela de index

poate fi pastrata fie în memoria principala fie daca este prea mare pe suport extern, caz

în care numai o parte a tabelei se va afla în memorie la un anumit element.

Operaţia este eficienta deoarece pentru căutarea unui element dat este suficient

un singur acces la disc. Dezavantajul metodei este consumul considerabil de spatiu pe

disc, provocat de blocurile care prin mediul de proiectare nu sunt complet ocupate.

Chiar şi în cazul unei funcţii de dispersie bune, este posibil ca unele blocuri să se

umple. Problema poate fi rezolvata utilizand variante ale metodelor de rezolvare a

coliziunilor.

2.8 CĂUTAREA ÎN GRAFURI

Grafurile sunt structuri de date asemănătoare cu arborii. De fapt la o privire atentă se

poate observa că arborii reprezinta un tip particular de grafuri. În domeniul programării însă

aceste două structuri sunt utilizate într-un mod total diferit una faţă de alta (spre deosebire de

arbore grafurile nu sunt folosite ca suport de memorare pentru date ci pentru a ajuta la

rezolvarea unor anumite probleme de regulă particulare).

Din punct de vedere matematic un graf neorientat poate fi privit ca o pereche

G=(X,U) unde:

X este o mulţime finită nevidă a cărei elemente se numesc vârfuri sau noduri ale grafului.

54

11

23

3 4


U este o mulţime de perechi neordonate (submulţimi cu două elemente), fiecare din aceste

mulţimi reprezentând o muchie a grafului

Deci implicit dacă avem u aparţine lui U cu u=[x,y] atunci aceasta înseamnă ca există

muchia xy (notata cu u) unde atât x cât şi y sunt elemente din mulţimea X a nodurilor

grafului.

Din punct de vedere geometric un graf poate fi privit ca o figură plana în care fiecărui

vârf I se asociază un punct şi fiecărei muchii [x,y] o linie curbă care uneşte punctele ce

corespund vârfurilor x,y.

Exemplu:

Fie G=(X,U)

U={(1,2);(2,3);(1,4);(4,2)}

X={1,2,3,4}

Fig.1

! Dacă într-un graf neorientat G=(X,U) există muchia [x,y] atunci va exista şi muchia

[y,x] (avem deci de-a face cu o relaţie de simetrie). Acest lucru nu este însă adevărat şi

pentru grafurile neorientate.

Graful desenat în exemplul de mai sus este un graf neorientat. Aceasta înseamnă ca ne

putem deplasa pe ele în orice sens. Dacă însă eram restricţionaţi la o deplasare de-a lungul

unei muchii numai într-un anumit sens atunci am fi avut de-a face cu un graf orientat (din

punct de vedere grafic această restricţionare ar fi fost reprezentată de regulă printr-o săgeata

aflată la sfârşitul muchiei).

Rolul grafului este de a prezenta relaţiile dintre muchii şi vârfuri, cu alte cuvinte

incidenţa muchiilor pentru toate vârfurile grafului.

Vom spune că două vârfuri sunt adiacente dacă sunt conectate direct printr-o muchie.

O alta noţiune des folosită este aceea de drum care nu este altceva decât o secvenţă de

muchii. Între două vârfuri date pot exista două sau mai multe drumuri. Dacă un drum va avea

toate muchiile diferite două câte două şi se va termina în acelaşi vârf din care a început,

55


acesta va purta numele de ciclu. Ciclul se va numi elementar dacă oricare două vârfuri ale sale

cu excepţia primului şi al ultimului sunt diferite două câte două .

Un graf se numeşte conex dacă exista cel puţin un drum de la fiecare nod până la

fiecare alt nod. Aşadar este absolut clar că un graf conex va fi alcătuit doar din componente

conexe.

Memorarea grafurilor

Într-un program extrem de abstract, vârfurile vor fi pur şi simplu numerotate cu indici

de la 0 la N-1 şi memorate într-un tablou putând fi mai apoi referite prin indicele

corespunzător fiecăruia în parte. (N este numărul vârfurilor) în majoritatea situaţiilor însă un

vârf este un obiect din lumea reală, care va fi descris de obicei ca un obiect structurat

aparţinând unei clase predefinite continând toate informaţiile necesare.

Pentru simplitate în exemplele prezentate aici fiecare vârf va cuprinde doar o

etichetă, label de tip char prin care este identificat. Aşadar astfel va arăta clasa Vertex, clasa la

care aparţin toate vârfurile grafului:

class Vertex{ public char label; // etichetă public boolean wasVisited; public Vertex (char lab) // constructor { label=lab; wasVisited = false; }}

Câmpul wasVisited va fi folosit în parcurgerea grafurilor. Pentru a ne asigura ca un

vârf nu va fi vizitat decât o singură dată, în momentul vizitării vârfului respectiv wasVisited

va lua valoarea true. Astfel în momentul în care se va ajunge din nou la nodul vizitat se va

verifica valoarea câmpului wasVisited şi găsindu-se true se va trece la pasul imediat următor.

Aşadar memorarea vârfurilor este foarte simplă folosindu-se pentru aceasta un simplu

tablou. Cum se vor memora însă muchiile ? După cum se poate observa un graf nu are o

organizare atât de riguroasă ca a unui arbore. Spre exempu într-un arbore binar, fiecare nod

avea cel mult doi fii aşadar ne era uşor să facem două referiri la nodurile fii. Într-un graf însă

fiecare vârf poate fi conectat cu un număr arbitrar de alte vârfuri.

Pentru modelarea acestui tip de organizare liberă, se preferă o altă reprezentare a

muchiilor fată de cazul arborilor. Există două modalitaţi de reprezentare folosite mai

frecvent.

56


a) Prima modalitate constă în precizarea numărului N al vârfurilor şi a matricei de

adiacentă a grafului, care este o matrice pătratică de ordinul N având elementele a ij=1 dacă

(i,j) aparţin lui U sau 0 în caz contrar.

! O observaţie care merită a fi făcută este ca matricea de adiacentă va fi simetrică în

cazul în care graful este neorientat.

Exemplu:

Pentru graful din figura următoare

Fig. 2

matricea de adiacentă este:

A doua modalitate constă în precizarea numărului N al vârfurilor şi pentru fiecare vârf

I, a listei Li a vecinilor săi, adica a vârfurilor j pentru care [i,j] aparţine lui U. De fapt o listă de

adiacentă reprezinta un tablou de liste bidimensional (sau o listă de liste)

Exemplu: pentru graful din figura precedentă, avem n=6 iar listele vecinilor sunt:

L1 = {2,3}L2 = {1,3,6}L3 = {1,2,6}L4 = {5,6}L5 = {4,6}L6 = {2,3,4,5}

Pentru adăugarea unui vârf la un graf, se va crea un nou obiect de tipul Vertex, care se

va insera în tabloul de vârfuri vertexList. Adăugarea unei muchii de la vârful al i-ilea la cel al

1

2

3 4 5

6

57


j-lea să zicem (i,j) se va face punând a ij = 1 (şi aji=1 dacă graful e neorientat) în matricea

de adiacentă sau punându-se vârful j în lista de adiacentă a vârfului al i-ilea (şi vârful i în

lista de adiacentă a elementului al j-lea în cazul unui graf neorientat).

Mai jos va fi prezentată o formă simplificată a unei clase de tip Graph, ale cărei

metode permit atât crearea unei liste de vârfuri şi a unei matrice de adiacentă, cât şi adăugarea

vârfurilor şi muchiilor la un obiect de tipul Graph:

class Graph{ private final int MAX_VERTS=20; private Vertex vertexList[]; // lista vârfurilor private int adjMat[][]; // matricea de adiacentă private int nVerts; // numărul current de vârfuri//----------------------------------------------------------- public Graph() // constructor { // se alocă matricea de adiacentă şi tabloul vârfurilor vertexList = new Vertex[MAX_VERTS]; adjMat = new int[MAX_VERTS][ MAX_VERTS]; nVerts = 0; for (int j = 0; j < MAX_VERTS; j++) for (int k = 0; k < MAX_VERTS; k++) adjMat[j][k] = 0; // iniţializarea matricii de adiacenta cu 0 } //-----------------------------------------------------------public void addVertex(char lab) { vertexList[nVerts++] = new Vertex(lab); }//-----------------------------------------------------------public void addEdge(int start,int end) { adjMat[start][end] = 1; adjMat[end][start] = 1; // lipseşte dacă graful e orientat }//----------------------------------------------------------public void displayVertex (int v) { System.out.println(vertexList[v].label); }//-----------------------------------------------------------}// sfârşitul clasei Graph

Parcurgerea grafurilor

Prin parcurgerea unui graf se înţelege examinarea sistematică a vârfurilor sale, plecând

dintr-un vârf dat i, astfel încât fiecare vârf accesibil din i să fie atins o singură dată (aici este

vorba de existenţa unei muchii între vârful i şi un altul). Trecerea de la un vârf y la un altul se

face prin explorarea într-o anumită ordine, a vecinilor lui y, adică a vârfurilor cu care nodul y

curent este adiacent. Aceasta acţiune numită şi vizitare a vârfurilor are scopul de a prelucra

informaţia asociată vârfurilor. În cazul unei căutari este necesară o simplă parcurgere în

graful pe care se lucrează facându-se la fiecare pas o comparaţie între cheia căutată şi

informaţia memorată în nodul curent.

58


Orice metodă de parcurgere a grafurilor am folosi va trebui în fiecare moment să ştim

dacă vârful curent mai are vârfuri adiacente nevizitate. Această operaţie este implementata

prin metoda getAdjUnvisitedVertex():

// întoarce un vârf nevizitat, adiacent cu v sau dacă acesta nu există întoarce -1

public int getAdjUnvisitedVertex(int v){ for (int j=0; j<nVerts; j++) if ((adjMat[v][i] = = 1) &&(vertexList[j].wasVisited = = false)) return j; // întoarce primul vârf găsit return -1; // nu există astfel de vârfuri}

1)Metoda de parcurgere DF (Depth First) parcurge graful în “adâncime”: întâi se

vizitează vârful iniţial i şi se continuă cu primul dintre vecinii nevizitaţi j; în continuare se

procedează similar cu vârful j, trecându-se la primul dintre vecinii lui j nevizitaţi încă.

Altfel spus, odată ajunşi într-un vârf, alegem primul dintre vârfurile nealese încă şi

continuăm parcurgerea. Când acest lucru nu este posibil, facem un pas înapoi către vârful din

care am plecat ultima dată şi plecăm dacă este posibil spre următorul vârf nevizitat încă.

Avem de-a face deci cu un algoritm de tip backtracking.

Pentru implementarea algoritmului de parcurgere în adâncime se utilizează o stiva

pentru a memora locul în care trebuie să se întoarcă, atunci când nu se poate merge mai

departe.

Pentru simplitate în momentul parcurgerii în adâncime vom urma regulile:

Regula 1: dacă este posibil, vizităm un vârf adiacent încă nevizitat, îl marcăm şi-l

introducem în stivă

Regula 2: dacă nu putem aplica regula 1, extragem un vârf din stiva

Regula 3: Atunci când nu putem aplica niciuna din regulile anterioare parcurgerea s-a

terminat

Pentru exemplul din Fig. 3 în urma unei parcurgeri în adâncime ordinea de

parcurgere a nodurior va fi: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

59


Fig. 3

Codul metodei de parcurgere a grafului în adâncime este:

public void adâncime(){ // se începe parcurgerea de la vârful 0 vertexList[0].wasVisited = true; // se marchează vârful displayVertex(0); theStack.push(0); while (!theStack.isEmpty())//cât timp există stiva nu e goală

{ int v = getAdjUnvisitedVertex(theStack.peek()); if (v = = -1) theStack.pop(); // dacă nu există un astfel de vârf se extrage unul din stivă else { vertexList[v].wasVisited=true; displayVertex(v); theStack.push(v); } }//sfârşit whilefor (int j=0;j<nVerts;j++) vertexList[j].wasVisited=false; // restabilim indicatorii ca la început

}

2)Metoda de parcurgere BF (Breadth First) parcurge graful în “lăţime”: întâi se

vizitează vârful iniţial i şi se continuă cu vecinii acestuia, apoi vecinii nevizitaţi ai acestora şi

aşa mai departe.

După cum am observat în cazul parcurgerii în adâncime algoritmul se comportă ca şi

când ar vrea să se îndepărteze cât mai repede de punctul de pornire. În cazul parcurgerii în

lăţime, pe de altă parte, algoritmul va rămâne cât mai aproape de punctul de pornire.

Algoritmul vizitează toate vârfurile adiacente cu acesta şi numai după aceea se avântă cu un

pas mai departe. Acest algoritm este implementat cu ajutorul unei cozi în locul stivei.

Pentru simplitate în momentul parcurgerii în lătime vom urma regulile:

Regula 1: Vizităm următorul vârf nevizitat (dacă există un astfel de vârf ) adiacent cu cel

curent, îl marcăm şi-l introducem în coadă

1

2

3

4

5

6

7 10

8

9

60


Regula 2: dacă nu putem aplica regula 1, din cauză că nu există vârfuri nevizitate,

ştergem un vârf din coadă (dacă este posibil), nodul şters devenind nodul curent

Regula 3: Atunci când nu putem aplica niciuna din regulile anterioare parcurgerea s-a

terminat

Pentru exemplul din Fig. 3 în urma unei parcurgeri în lăţime ordinea de parcurgere a

nodurior va fi: 1, 2, 7, 10, 3, 4, 6, 5, 8, 9.

Codul metode de parcurgere a grafului în lăţime este:

public void lătime() { // începem cu vârful 0, îl marcăm, îl afişăm şi-l introducem în coadă vertexList[0].wasVisited=true; displayVertex(0); theQueue.insert(0); int v2; while (!theQueue.isEmpty())//până când coada este goală

{ int v1=theQueue.remove(); while ((v2=getAdjUnvisitedVertex(v1)) != -1) // cât timp există vecini nevizitaţi { vertexList[v2].wasVisited=true; displayVertex(v2); theQueue.insert(v2); } }

for (int j=0;j<nVerts;j++) vertexList[j].wasVisited=false; // restabilim indicatorii ca la început }

Pentru a determina ordinul de complexitate a algoritmului de parcurgere în lăţime,

observăm că ciclul descris prin instrucţiunea while (primul while) se executa de cel mult n-1

ori. În corpul primului ciclu while se află un alt ciclu while care şi el se execută de cel mult

n-1 ori. Rezultă că ordinul de complexitate a algoritmului este O(n2).

Aşa cum am menţionat mai sus pentru a căuta într-un graf va fi nevoie de o

parcurgere a grafului. Aceasta se va face prin oricare din cele două metode prezentate mai sus

făcându-se la fiecare pas câte o comparaţie a câmpului după care se face căutarea cu cheia

căutată. Aşadar ordinul de complexitate a unei căutari în vârfurile dintr-un graf va fi acelaşi

cu ordinul de complexitate al algoritmului de parcurgere folosit.

61


CAPITOLUL 3

CĂUTAREA PE INTERNET

Bazat pe hipertext, spaţiul WWW încearcă oferirea unui mecanism facil de a stoca şi

de a pune, ulterior, la dispoziţie informaţii, într-o manieră intuitivă, nesecvenţială.

Studiile recente (efectuate la mijlocul anului 2000) estimează volumul Web-ului ca

fiind de 1-2 miliarde de pagini, utilizatorii care petrec mai mult de cinci ore pe Internet

alocând 70% din timp pentru căutarea de informaţii. Între 85% şi 90% dintre utilizatori se

bazează pe motoarele de căutare pentru a localiza resursele dorite.

Astfel, importanţa acestora se dovedeşte de necontestat, în prezent existând o

multitudine de căutătoare şi meta-căutătoare, generale sau specializate.

Motoarele de căutare pot oferi servicii de căutare pe bază de indecşi (i.e. Altavista) sau

pe baza unor ierarhii de termeni – aşa-numitele servicii director (Yahoo). În ultima perioadă,

aceste servicii au devenit hibride (primul care a adoptat tehnicile mixte fiind Excite).

Regăsirea informaţiilor

Cercetătorii au evidenţiat mai multe activităţi de regăsire a informaţiilor, în funcţie de

intenţiile utilizatorilor:

scanarea (scanning) – utilizatorii acoperă, superficial, o arie largă de informaţii;

răsfoirea (browsing, surfing) – utilizatorii vizitează locaţiile care le captează interesul

(fără a avea stabilit un model mental despre informaţiile dorite);

62


căutarea (searching) – utilizatorii sunt motivaţi să găsească o ţintă particulară de

informaţii (folosind de cele mai multe ori o manieră de căutare bazată pe cuvinte cheie sau

construcţii în limbaj natural, de genul “Unde găsesc documentaţii despre XML?”);

explorarea (exploring) – utilizatorii investighează legăturile referitoare la o anumită

informaţie şi pe cele conexe;

hoinăreala (wandering) – utilizatorii realizează o navigare complet nestructurată.

Atunci când ne aflăm pe Web, de cele mai multe ori nu parcurgem la un moment dat

decât o singură pagină WWW, aparţinând unui server particular, fără a avea o vedere de

ansamblu a modului de structurare a tuturor documentelor de la acea adresă. Astfel, spaţiul

Web prezintă următoarele caracteristici negative:

modelul plat de memorare a datelor

Documentele nu sunt stocate în mod structurat pe serverele Web, ierarhiile putând fi

recunoscute de cele mai multe ori doar examinând URI-urile.În mod uzual, paginile nu au

legături către documentul părinte (“rădăcina” site-ului, /index.html sau /default.htm, în funcţie

de serverul Web folosit, Apache (NCSA) ori IIS, respectiv).

legăturile unidirecţionale

Limbajul HTML nu oferă decât posibilitatea de specificare a hiperlegăturilor

unidirecţionale, simple.Este dificil de a alcătui o hartă locală conţinând toate sursele şi

destinaţiile legăturilor dintre paginile Web ale unui server.Reţelele sofisticate de legături

conduc la o navigare greoaie şi devin surse de confuzie.

lipsa unei hărti globale de navigare

Nu se poate realiza o harta globală de navigare prin întreg spaţiul WWW, într-o manieră

ierarhică.

menţinerea legăturilor

Legăturile fiind stocate în interiorul documentelor, nu există posibilitatea de a adăuga

adnotări sau de a modifica legăturile dintr-o pagină fără a fi proprietarul acesteia. Menţinerea

integrităţii legăturilor pentru site-uri Web conţinând un număr foarte mare de documente se

dovedeşte dificilă. De cele mai multe ori se utilizează programe de verificare a disponibilităţii

legăturilor şi de construire a ierarhiilor de legături între paginile unui site Web (e.g. aplicaţia

ICE scrisă în Perl).

În principiu, un motor de căutare este constituit din trei componente de bază:

robot Web

index

63


ranking mechanism

Robot Web = o aplicaţie numită robot Web (spider, crawler), care parcurge spaţiul

WWW şi vizitează anumite pagini, extragând informaţii despre ele care vor fi păstrate pe

serverul sau serverele motorului de căutare, într-o bază de date sau index.

De cele mai multe ori, fiecare motor de căutare are propriul robot Web care respectă

standardul de excludere a roboţilor.

Standardul de excludere a roboţilor

1.Se accesează un fişier text numit robots.txt stocat în directorul de rădăcină a unui

server WWW de către robotul de explorare, acest fişier specificând ce părţi vor fi evitate de la

parcurgerea automată, acest lucru făcând posibilă excluderea roboţilor din zone Web lipsite de

relevanţă.

Un exemplu de astfel de fişier este:

#/robots.txt pentru http: www.orange.ro

User-agent: * # toţi roboţii

Disallow: / tmp / # date temporare

Disallow: / ionescu/work / # spaţiu privat

În vederea evitării indexării conţinutului unei pagini Web se poate scrie în antetul ei

(între etichetele <head> şi </head>):

<meta name = “robots” content =“noindex”>

De asemenea se poate inhiba traversarea legăturilor prezente într-un document HTML

(cele definite prin <a href=”...”>) prin:

<meta name=”robots” content =”nofollow”>

Anumiţi roboţi pot utilizează tag-uri specifice (ascunse) care să dicteze un anumit

comportament pentru aceea pagină (aşa cum se întâmplă în cadrul programului de oglindire

Teleport)

2. Prin traversarea unui număr mare de hiperlegaturi, roboţii necesită o lărgime bună de

bandă, deoarece ei pot opera continuu perioade lungi de timp (săptămâni sau chiar luni).

Pentru a accelera aceste operaţii mulţi roboţi au implementate tehnici de extragere paralelă a

datelor, metoda denumită operare în foc rapid (rapid fire), rezultând un trafic considerabil (o

încetinire temporară a traficului de date). Mai mult, serverele Web pot fi supraîncărcate de

cereri multiple de accesare venite din partea roboţilor în detrimentul cererilor agenţilor-

utilizator. Aşadar implementarea roboţilor permiţând foc rapid trebuie evitată.

64

http://www.orange.ro/


3. Implementări eronate pot determina roboţii să intre în arii infinite numite găuri negre

(de exemplu atunci când un document are o legătură care se referă la el însuşi, iar programul,

robotul, nu realizează lucrul acesta).

4. Un alt aspect care trebuie luat în considerare este timpul de actualizare a bazelor de

date ale motoarelor de căutare folosind pentru descoperirea resurselor roboţii Web. Roboţii

de căutare a informaţiilor vor trebui aşadar să decidă care informaţii sunt importante a fi

transmise programelor de indexare.

5. Roboţii nu trebuie să acceseze tipuri de date fără relevanţă, având dimensiuni

considerabile cum ar fi arhive, fişiere executabile, fişiere multimedia etc.

Ca exemple de roboţi de căutare aş putea menţiona pe cei de la Excite (Inktomi), Go

(Infoseek) şi Lycos care însă nu pot indexa paginile conţinând cadre, iar cei de la FAST şi

Google au probleme cu hărţile de imagini senzitive (care pot îngloba legături spre alte

documente)

Majoritatea roboţilor de căutare pentru a accelera procesul de traversare a legăturilor

posedă o tabelă internă de perechi (adresa simbolică, adresa IP) evitând interogările DNS

(Domain Name System) care sunt prea lente.

Căutarea se realizează folosind algoritmi de parcurgere locală de tip DFS sau BFS sau

prin parcurgerea într-o ordine inteligentă a legăturilor spre alte documente.

Index = o modalitate de memorare a informaţiilor despre paginile parcurse de robot.

Acest index conţine de obicei o copie a fiecărei pagini şi a identificatorilor URL

corespunzători acestora, iar organizarea informaţiilor în cadrul indexului se face conform unor

criterii specifice.

Aşadar indexul (catalogul) este reprezentat printr-o serie de baze de date memorate pe

discurile unui server (modul) de stocare, constituindu-se un depozit (distribuit) de date de

mari dimensiuni.

Modulul de stocare realizează diverse activităţi importante ca introducerea de noi date

despre paginile parcurse de roboţi, actualizarea conţinutului celor vechi, programarea

diverselor cereri de accesare a informaţiilor despre o serie de documente etc. De cele mai

multe ori acestea sunt comprimate (Google foloseşte biblioteca de compresie bzip) utilizându-

se clustere pentru memorarea lor.

Fiecare pagină va primi un identificator docID stabilit pe baza adresei sale URL.

Aceste adrese vor fi normalizate conform următorului algoritm:

65


Se elimină prefixul protocolului dacă este prezent

http://www.Bancuri.ro:80/ va deveni www.Bancuri.ro:80/

Se elimină numărul portului implicit (: 80) dacă există, dar se

păstrează orice alt număr de port

www.Bancuri.ro:80/ va deveni www.bancuri.ro/

Adresa simbolică a serverului va fi convertită în litere mici

www.Bancuri.ro/ va deveni www.bancuri.ro/

Caracterele “/” de la sfârşitul adresei URL sunt eliminate

www.bancuri.ro/ va deveni www.bancuri.ro

Conform unei funcţii de dispersie alese de proiectantul motorului, textul rezultat va fi

convertit într-o valoare numerică (de dimensiune de 64 sau 128 biţi) care va fi aşa zisul

identificator de document docID.

Indecşii pot cuprinde indecşi de text obişnuit, dar şi indecşi ai metadatelor extrase

(construiţi pe baza docID-urilor şi a altor informaţii ). În mod uzual se folosesc tehnici bazate

pe tabele de dispersie multiple şi pe sortarea eficientă a indecşilor.

Modulul de indexare a metadatelor este responsabil pentru extragerea metadatelor din

paginile colectate şi pentru indexarea atât a metadatelor cât şi a paginilor (documentelor

HTML). Pentru indexarea conţinutului textual al documentelor, uzual vor fi considerate toate

cuvintele, exceptând aşa-numitele cuvinte stop, adică cuvintele de lungime mai mică de trei

caractere (propoziţii, conjuncţii sau interjecţii). Unele motoare de căutare (cum ar fi Google

sau Lycos) vor contoriza şi numărul de apariţii ale celor mai frecvente cuvinte dintr-o pagină

Web şi vor realiza indecşi suplimentari şi/sau vor stabili categoria în care va fi încadrată în

acea pagină. O alta tehnică abordată este cea a indexării semantice.

Extragerea metadatelor variază în funcţie de motorul de căutare. Cea mai populară

tehnică este cea a indexării documentelor pe baza cuvintelor cheie furnizate fie explicit de

creatorul paginilor Web, fie în urma unei catalogări automate realizate de un robot.

Standardul HTML permite autorilor de pagini Web să enumere cuvintele cheie, să

specifice numele autorului, a deţinătorului paginii, precum şi să introducă o scurtă descriere a

paginii respective prin folosirea în antet a etichetelor <meta>, </meta>.

Exemplu:

< meta name = “description” content = “Sportivii români de la Olimpiada de la Atena”> // descrierea succintă< meta name = “keywords” content = “Badea, tricolori, Szekely, campion ”> // cuvinte cheie< meta name = “author” content = “Cândea Radu” > // autorul< meta name = “owner” content = “Cândea Radu”> // proprietarul

66

http://www.bancuri.ro/





http://www.bancuri.ro:80/




Trebuie menţionat că unele motoare de căutare cum ar fi Excite, Google şi Northern

Light ignoră informaţiile conţinute de tagul < meta name = “keywords”>, iar alte motoare ca

FAST, Lycos vor ignora informaţiile din tagul < meta name = “description”>

Metode mai sofisticate includ sumarizări automate, utilizarea de sinonime ale

cuvintelor cheie ori utilizarea algoritmilor genetici sau a reţelelor neuronale. De multe ori

catalogarea se face în funcţie de subiectul care este tratat în documentele respective, această

clasificare ducând la apariţia serviciilor director (Ex: Yahoo). Clasificarea după subiect este

similară reţelei lingvistice WordNet.

De asemenea se contorizează atât numărul de legături care pointează spre o anumită

pagină cât şi cele care sunt conţinute în acea pagină. Aceste valori sunt cunoscute sub numele

de hit-uri.

Metadatele şi indecşii se stochează pe dispozitive separate de cele ale depozitului de

date (deseori se foloseşte un sistem de management al bazelor de date relaţionale)

Depozitul de documente indexate suportă trei moduri de acces:

acces direct (random acces) = se realizează pe baza identificatorului asociat fiecărei pagini

acces bazat pe interogări (querry-based acces) = în acest caz se va formula o interogare

care să se refere la diverse atribute a metadatelor cum ar fi autor, locaţie, titlu, etc., iar în urma

acestei interogări vor fi furnizate toate documentele care satisfac cererea formulată.

acces flux de date (streaming acces) = este folosit atunci când din depozitul de date se

extrage un grup de pagini pentru a fi trimis ca flux de date spre o anumită aplicaţie.

Pentru asigurarea scalabilităţii, depozitul de date poate fi distribuit, constituindu-se o

colecţie de noduri de stocare interconectate, controlul realizându-se prin intermediul unui

server de management al nodurilor. Acest server menţine o tabelă cu starea fiecărui nod de

stocare: capacitatea totală de memorare, spaţiul liber, nivelul fragmentării datelor, numărul şi

tipul de accesări, modul de operare a nodului etc.

Ranking mechanism = un mecanism de evaluare (ranking) a importanţei paginilor din

index în conformitate cu cererea formulată de utilizator. În ordinea importanţei, adresele

paginilor plus alte informaţii sunt returnate clientului-utilizator care a formulat cererea.

Utilizatorul va decide care pagină sau grup de pagini este conform cu preferinţele sale.

67


Nu toate paginile vor avea aceeaşi importanţă pentru robot, aici intervenind mai

mulţi factori fiecare dintre aceştia având o anumită pondere. Se pot lua în calcul:

similaritatea cu posibilele cereri ale utilizatorilor, numărul legăturilor spre pagina

analizată, relevanţa paginii (conţinutul ei), numărul legăturilor pe care îl are pagina

respectivă precum şi metrica locaţiei (o pagină din domeniul “.com” se consideră a fi

mai importantă decât una a domeniului “.ro”)

Paginile vor fi ordonate conform acestor criterii şi vor fi indexate doar primele,

numărul acestora depinzând de capacităţile indexului.

Aceasta abordare a fost experimentată începând cu anul 1997 (proiectul WebBase) şi

în prezent se regăseşte în cadrul popularului motor de căutare Google.

În cadrul depozitului de date este de dorit să se memoreze cea mai recentă versiune a

paginilor traversate de roboţii Web. Trebuiesc avute în vedere aspecte importante precum

consistenţa indecşilor şi eliminarea vechilor pagini care nu mai există pe Web. Astfel pentru

fiecare pagină pot fi ataşate două valori numerice una pentru a specifica timpul de viaţă

permis (diferit de la un motor de căutare la altul) şi alta în care se va contoriza efectiv trecerea

timpului. Timpul de viaţa permis reprezintă perioada de stocare a unui document fără a

necesita ştergerea sau reactualizarea sa din depozit în timp ce contorul este decrementat

periodic până când devine nul, moment în care robotul Web va trebui să aducă noi informaţii

despre acea pagină.

Mai mult, serverul controlează cererile pentru accesări de tip flux de date şi maniera

de stocare a paginilor noi colectate de roboţi. Distribuţia în cadrul nodurilor se face uniform

sau printr-o metodă de tip hash iar organizarea se va realiza tot printr-o metodă de tip hash,

prin fişiere de jurnalizare sau printr-o metodă mixtă. În cazul actualizării se iau în considerare

scheme bazate pe actualizări secvenţiale (batch) ori incrementale. La actualizarea secvenţială

nodurile se partiţionează în două categorii: noduri de actualizare (nu vor mai fi folosite pentru

cereri de acces la pagini) şi noduri de citire. Astfel, se evită apariţia conflictelor între

operaţiunile executate asupra depozitului de date. La actualizarea incrementală nu se mai face

distincţie între noduri, fiecare nod fiind permanent operaţional, cu penalizări de performanţă

şi modificare dinamică a indecşilor locali.

Pentru sporirea eficienţei, nodurile pot conţine pagini grupate pe diverse criterii cum ar

fi: tematică, autor, localizare, cuvinte-cheie etc.

Orice motor de căutare are o interfaţă de căutare (denumită frecvent motor de căutare)

care reprezintă o componentă importantă a sistemului, oferind în funcţie de motor posibilităţi

68


de formulare a cererilor prin intermediul diverşilor operatori logici, în limbaj natural,

explorând ierarhii de domenii catalogate (directoare Web), alegând localizarea paginilor etc.

Majoritatea motoarelor de căutare utilizezează o convenţie de compunere a

interogărilor. Pot fi date şi relaţii create prin intermediul operatorilor AND, OR, NOT şi

NEAR.

Astfel când se doreşte ca pagina să aibă în componenţă ambii termeni se foloseşte

structura “termen1 AND termen2”. Deseori în locul operatorului AND va fi folosit operatorul

“+”: “+ termen1 + termen2”.

Dacă vom dori ca paginile să conţină măcar unul din doi termeni vom avea: “termen1

OR termen2”

Când se doreşte ca o pagină să nu conţină un anumit termen se va folosi structura:

“NOT termen” care are o construcţie echivalentă “- termen ”

În sfârşit dacă vom dori ca paginile să conţină cei doi termeni localizaţi la mică

depărtare unul de celălalt (vecinătate de 20-2000 de cuvinte, în funcţie de motorul de căutare )

vom folosi următoarea structura: “termen1 NEAR termen2”.

Pentru gruparea şi schimbarea precedenţei operatorilor se pot utiliza parantezele. Se

mai poate folosi şi construcţia “ lista de termeni ”, ghilimelele însemnând că se va realiza o

căutare exactă a secvenţei de termeni din lista dată. De exemplu:

“Algoritmi de căutare ” + bibliografie – documente

Un utilizator obişnuit se va sluji foarte rar de aceste facilităţi preferând

formularea unei interogări compusă dintr-un singur cuvânt sau a unei propoziţii în

limbaj natural (în speţa limba engleză).

Tehnologia Ask Jeeves încorporată de Altavista este utilizată pentru procesarea

cererilor în limbaj natural, unele probleme care trebuiesc rezolvate fiind dezambiguizarea

termenilor, eliminarea cuvintelor nerelevante sau expandarea interogării (pot fi formulate

automat noi cereri conţinând sinonime ale cuvintelor furnizate de utilizator, folosindu-se

reţeaua lingvistică WordNet).

Majoritatea serviciilor de căutare oferă posibilitatea de rafinare a interogării, prin

intermediul unor opţiuni advanced search sau refine.

Evaluarea cererii utilizatorului se poate realiza conform următoarelor etape:

analizarea interogării

căutarea în indecşii corespunzători termenilor rămaşi după analiza cererii

69


scanarea tuturor documentelor care întrunesc toate condiţiile de căutare

evaluarea gradului de relevanţă a paginilor în funcţie de interogarea dată de utilizator

eliminarea duplicatelor (nu toate motoarele de căutare trec prin această fază) şi sortarea în

ordinea relevanţei

afişarea adreselor primelor documente în funcţie de gradul lor de relevanţă

Alte abordări includ:

evaluarea relevanţei pe baza contextului de apariţie

determinarea corelaţiei dintre relevanţa calculată de motor şi cea exprimată de operatorul

uman

utilizarea de tehnici adaptive

exploatarea relaţiilor care se pot stabili între diverse pagini Web (Ulixes)

Meta-căutătoare

Prin apelarea unui meta-căutător se pot formula interogări în urma cărora se vor primi

rezultate de la o multitudine de motoare de căutare cărora li se va transmite respectiva cerere.

Funcţia principală a metacăutătorului este aceea de a compila toate listele de pagini rezultate

de la motoarele obişnuite (care sunt interogate în paralel) şi de a prezenta utilizatorului cele

mai relevante documente găsite.

De cele mai multe ori un meta-căutător are implementat propriul sistem de evaluare a

relevanţei paginilor, în funcţie de anumite criterii (ex: Mamma). De asemenea, un meta-

căutător poate oferi o vedere ierarhizată, de genul directoarelor Web, a paginilor găsite.

Nu toate meta-căutătoarele elimină duplicatele (ex: Dogpile). O serie de meta-

căutătoare sunt direcţionate spre domenii specifice, pentru căutarea de:

fişiere – în general aplicaţii şi documentaţii (ex: Filez, FTPSearch)

adrese e-mail şi numere de telefon (ex: Four11)

informaţii în cadrul grupurilor de discuţii (ex: DejaNews)

fişiere audio (ex: MP3Search)

imagini (ex: MetaSEEk)

pagini localizate într-un areal geografic comun (ex: EuroSeek, Cauta.ro)

informaţii specifice unui domeniu: afaceri, comunităţi umane etc. Este şi cazul portalurilor

Web care în plus furnizează şi alte servicii, precum accesarea unui cont de poştă electronică,

cursul valutar, starea meteo şi altele

70


Care este mecanismul de funcţionare a unui meta-căutător ? Este simplu. Utilizatorul

(clientul Web) va completa un formular electronic prezentat de modulul responsabil cu

interfaţă, formular care va fi completat cu interogarea dorită.

Există un dispecer de cereri care poate diviza interogările complexe formulate de

utilizator în sub-cereri, fiecare sub-cerere fiind expediată unui motor de căutare clasic (Nu

toate meta-căutătoarele trimit cereri în manieră concurentă motoarelor de căutare ).

Supravegherea fiecărui motor de căutare în parte se face cu ajutorul unui monitor de

performanţă. Atunci când unul dintre motoare devine inoperaţional sau inaccesibil din raţiuni

legate de reţea, se poate decide automat ca respectiva cerere să fie date spre prelucrare unui alt

motor. Monitorul de performanţă are în responsabilitate şi primirea listelor de adrese ale

paginilor găsite.

După primirea rezultatelor de la motoarele de căutare, listele cu URL-uri vor fi

compilate, eliminându-se informaţiile redundante şi cele contradictorii.

Deoarece fiecare motor în parte va returna o listă de pagini într-un format propriu,

meta-motorul de căutare va realiza şi o convertire la un format comun care în final va fi

prezentat clientului.

Cercetătorii de la Universitatea Stanford au observat că vizitarea tuturor documentelor

prezente pe Web nu se poate realiza din cel puţin două motive:

indexul are o capacitate limitată şi deci motorul nu poate indexa sau analiza toate paginile

Web (Web-ul se dezvoltă în mod alert)

Web-ul se modifică foarte rapid şi robotul nu va avea şansa de a parcurge o serie de pagini

(la fiecare lună se estimează că peste 800 GB de date îşi schimbă conţinutul)

Nici un motor nu poate fi perfect. Pentru testarea seviciilor de căutare se consideră mai

mulţi factori, dintre care pot fi amintiţi: acurateţea, posibilitatea de căutare avansate,

ergonomia în utilizare şi acordarea de alte facilităţi. Astfel fiecare individ în parte îşi poate

alege motorul de căutare care să-i satisfacă cel mai bine cererile sale existând o multitudine

de posibilităţi.

Acum când am ajuns în sec XXI, Internet-ul reprezintă una din cele mai mari resurse

pentru informaţii iar găsirea informaţiilor necesare într-un domeniu atât de vast cum este

Internetul poate deveni o adevărată problemă. O problemă care însă se poate rezolva cu

ajutorul motoarelor de căutare, acestea reprezentând cea mai uşoară cale de găsire a

informaţiilor pe Web constituindu-se totodata ca niste importante instrumente de acces rapid

la informaţie.

71


CAPITOLUL 4

PREZENTAREA APLICAŢIEI

O direcţie de studiu convergentă cu sortarea este cea a căutarii după cheie, cu alte

cuvinte a regăsirii informatiilor (engl. information retrieval).

Pentru căutarea unei înregistrari într-o structură de date (vector, mulţime, listă, arbore,

tabel de dispersie, graf, sau chiar bază de date) trebuie ca unul dintre câmpurile înregistrării

să reprezinte o cheie. Se va căuta astfel o înregistrare cu o cheie bine precizată. Într-un

program complex, orice câmp poate fi ales să reprezinte o cheie. Vom observa astfel că pentru

fiecare structură de date în particular vor exista ceva diferenţe pentru executarea unor căutări

după cheie, mai ales privind parcurgerea acelei structuri.

Programul realizat de mine şi intitulat “Căutări în structuri de date” este realizat în

limbaj Java folosind KawaPro cu pachetul JDK 1.3.0. Aşa cum se deduce din titlu în acest

program am încercat să implementez cele mai frecvente structuri de date, să le populez cu

diferite înregistrări, apoi să testez diverşi algoritmi de căutare specifici fiecărei structuri de

date în parte.

În programul “Căutări în structuri de date” s-au acoperit atât algoritmii de căutare

externă (căutare în fişier extern şi în bază de date)precum şi algoritmii de căutare internă şi

72


aici mă refer la clasicele structuri de date ce sunt memorate în memoria RAM a calculatorului

(tablou, listă înlănţuită, arbore, tabelă de dispersie şi graf).

Prima problemă care s-a pus odată cu începerea lucrului la acest program a fost

găsirea celui mai eficient mod de a popula structurile cu date precum tipul datelor ce aveau să

fiefolosite.

Deoarece datele de tip numeric sunt cele mai uşor de manevrat, iar cele de tip String

sunt cel mai des folosite în programare am ales o soluţie de mijloc şi anume am folosit pentru

popularea structurilor nişte obiecte care conţin în structura lor atât date de tip int cât şi String.

Inserarea datelor de la tastatură în timpul rulării programului mi s-a părut a fi cea mai

proastă idee de aceea a rămas de ales între a prelua informaţiile pentru popularea bazei de date

dintr-un fişier extern sau de ce nu dintr-o bază de date. Ultima variantă mi s-a părut cea mai

interesantă aşa că am creat în Access o bază de date simplă având un singur tabel cu

câmpurile ID, Societate, Localitate, Strada, Nr, Domeniu în care am introdus datele

specificate prin numele câmpurilor pentru aproximativ 600 de firme din judeţul Sibiu.

La crearea structurii de date pentru testarea algoritmilor de căutare are loc un proces

aleator de generare a 20 de numere într-un anumit interval (20 de înregistrări mi s-au părut

relativ suficiente pentru operaţiile ce mi le-am propus pe structurile respective de date, dar

acest număr nu constituie o limitare a programului, el putând fi oricând înlocuit cu o altă

valoare mai mare). Intervalul acesta în care poate lua valori numerele aleatoare este de la 0 la

numărul de înregistrări a bazei de date folosite. Folosind interfaţa ODBC pentru lucrul cu

bazele de date, printr-o instrucţiune SQL de tip SELECT se extrag din baza de date 20 de

înregistrări, fiecare înregistrare fiind memorată într-o instanţă a clasei Link.

SELECT * FROM Tabel WHERE ID="+nraleator+"

Această instrucţiune SQL returnează toate câmpurile înregistrării din tabelul “Tabel”

care respectă condiţia ca în dreptul câmpului ID să fie o valoare egală cu numărul aleator

“nraleator” generat mai devreme.

Dacă cele 20 de numere generate aleator sunt diferite între ele atunci şi cele 20 de

înregistrări întoarse de către instrucţiunea SQL de mai sus vor fi diferite pentru că ID

repreyintă de fapt cheia primară a tabelului “Tabel”.

Aşadar fiecare din structurile de date vor avea câte o metodă insert() în care se

realizează legătura cu baza de date Societăţi aflate pe hardisk, se scot date pe baza unei

interogări SQL apoi, înregistrările aleator alese aşa cum am descris mai sus sunt mai apoi

73


utilizate la crearea unor obiecte de tip Link care vor popula structurile de date. Iată care este

structura acestei metode:

public void insert() { String[] b=new String[10];

/* b este un array de Stringuri în care va fi copiat conţinutul fiecărei înregistrări întoarse de interogarea SQL; String domeniu=""; String strada=""; String societate=""; String localitate=""; String url="jdbc:odbc:Societati"; String user="dba"; String password="sql"; // sunt folosite la crearea conexiunii cu baza de date Societăţi Vector sir =new Vector(); int[] aleat=new int[20]; // array în care se vor înregistra numerele aleatoare for (int i=0;i<MAX_ELEM;i++) // MAX_ELEM este o constantă egală cu 20

{ int n=(int)(java.lang.Math.random()*806);// baya de date are 806 înregistrări aleat [i]=n;} // în acest for aleat este umplut cu numere întregi din intervalul [ 1, 806] generate aleator

try{Class.forName("sun.jdbc.odbc.JdbcOdbcDriver"); // iniţializarea driverului

}catch(ClassNotFoundException e) {

e.printStackTrace();System.out.println("Eroare incarcare driver!\n" + e);

} try{

Connection c=DriverManager.getConnection(url, user, password); // cerearea conexiuniiStatement s= c.createStatement(); // crearea unui "flux" spre baya de date Societăţi

for (int i=0;i<MAX_ELEM;i++) {

ResultSet r=s.executeQuery("SELECT * FROM Table1 WHERE ID="+aleat[i]+" ORDER BY ID");/* în r se pune rezultatul interogării pe tabelul Table1 având criteriul de selecţie ID="+aleat[i]+" adică ID-ul (cheia primară)să fie egal cu al i-ilea număr aleator generat din array-ul aleat */

while (r..next()) { sir.add(r.getString("ID")); sir.add(r.getString("Societate")); sir.add(r.getString("Localitate")); sir.add(r.getString("Strada")); sir.add(r.getString("Nr")); sir.add(r.getString("Domeniu")); sir.add("\n");

}sir.copyInto(b);

/* se copiază vectorul şir în arrayul b, a cărui elemente vor putea apoi fi folosite la crearea unui obiect de tip Integer în grupul de instrucţiuni de mai jos */

try { in1=new Integer(Integer. parseInt(b[0], 10));

in2=new Integer(Integer. parseInt(b[4], 10)); }catch(NumberFormatException v) { v.printStackTrace();

System.out.println("Eroare de transformare de tip parseInt()"); }

int id=in1.intValue();societate=b[1];localitate=b[2];strada=b[3];int nr=in2.intValue();

74


domeniu=b[5];Link link = new Link(id,societate,localitate,strada,nr,domeniu);

// crearea unui obiect de tip Link/*

Aici, nodul nou creat link va fi inserat în structura de date. Fiind inclus într-un ciclu for cu 20 de paşi structura va avea 20 de noduri, conţinând obiecte de tip Link.

La fişier nu se vor mai crea obiectele de tip Link ci se vor insera pur şi simplu elementele vectorului b care sunt de tip String în fişierul nou creat

La baza de date această întreagă metodă va lipsi deoarece baza de date în care se va efectua căutatrea este deja creată şi populată în Microsoft Access

*/System.out.println(i+".este nodul la care s-a ajuns");sir.clear(); // vectorul sir este golit deoarece informaţia conţinută in el a fost deja folosită

} s.close(); // se închide "fluxul" }catch(SQLException e) {e.printStackTrace();} catch (NullPointerException ex) {ex.printStackTrace();};

}

Aşa cum se poate constata din codul metodei insert(), structurile de date sunt populate

cu instanţe ale clasei Link aflată în fişierul Link.java a cărei cod este:

class Link{ public Link right, left; private int id, nr;

private String societate, localitate, strada, domeniu; public boolean wasVisited;

public Link(int nid,String soc,String loc,String adr,int numar,String dom) {

id=nid; societate = soc; localitate=loc; strada = adr; nr=numar; domeniu = dom; left=null; right=null; wasVisited=false; }

public String displayLink() {

String info; info=id+" "+societate+" "+localitate+" "+strada+ " "+nr+""+domeniu+"\n";

return info;}public String getSoc() { return societate; }

public String getDom() { return domeniu; }public String getStr() { return strada; }public int getID() { return id; }public String getLoc() { return localitate; }public int getNr() { return nr; }

} // sfârşit clasă Link

75


După cum se observă clasa Link conţine două atribute numerice (id şi nr)şi patru

atribute de tip String (societate, localitate, strada, domeniu). Celelalte atribute de tip Link (left

şi right)sunt folosite numai în cadrul listelor înlănţuite, iar cele de tip boolean

(wasVisited)sunt folosite doar la grafuri, pentru marcarea nodurilor prin care s-a trecut la o

parcurgere.

Există şi nişte metode publice (pot fi accesate şi din exteriorul clasei)care returnează

diferitele atribute ale obiectului precum şi o metodă care returnează întreg conţinutul

obiectului sub forma unui String care mai apoi poate fi citit pe o supafaţă de afişare (în cazul

programului “Căutări în structuri de date”, într-un textarea).

În ceea ce priveşte structura acestui program, avem de-a face cu un proiect Java

(Project.kpx)care conţine mai multe fişiere.java şi anume: Arbore_Binar.java, Array.java,

Baza_De_Date.java, Fişier.java, Graf.java, Lista_Înlanţuită.java, Tabela_De_Dispersie.java,

Fereastră.java, Link.java, Avertizare.java, Căutare.java şi Pseudocod.java.

În primele dintre fişiere (având numele unor structuri de date)se face implementarea

structurilor respective cu toate operaţiile caracteristice, inclusiv căutarea care constituie

subiectul acestei lucrări, precum şi construcţia a câte unei ferestre din cadrul căreia se va

putea lucra asupra structurii de date (interfaţa şi structura sunt implementate în clase diferite

aflate însă în acelaşi fişier.java).

Aşadar primele şapte fişiere.java menţionate conţin cel puţin două clase, una pentru

creareea interfeţei grafice iar cealaltă pentru lucrul cu structura de date (datorită unei mai mari

simplităţi la secţiunile Baza de Date şi Fişier, deci la structurile memorate extern structura a

fost implementată în cadrul clasei responsabilă cu interfaţa). Bineînţeles că vor exista unele

fişiere cum ar fi Graf.java care au implementate mai multe clase (pentru parcurgerea

grafurilor avem nevoie de o coadă sau o stivă, care fiecare vor avea clasa ei separată).

Un utilizator al programului "Căutare în structuri de date" va interacţiona evident cu o

fereastră, numită generic interfaţă. Acţiunile pe care le face (apăsare buton, selectare buton

radio, inserare text în interiorul textfield-ului etc)vor avea ecou în interiorul clasei structurii

pentru că principiul de funcţionare a acestui program şi în general a programelor complexe cu

interfaţă grafică este chiar această interacţiune dintre interfaţă şi metodele de "subsol".

Pentru o mai mare simplificare a codului ferestrelor structurilor de date şi pentru a

avea un design asemănător, acestea moştenesc clasa Fereastră aflată în fişierul Fereastra.java.

În această clasă sunt declarate şi iniţializate textfieldul ”cheie” unde se introduce valoarea

76


după care se face căutarea, suprafaţa pe care se face afişarea reultatelor (numită “textArea”),

un choice numit ”alege” de unde se pot alege anumite opţiuni specifice fiecărei structuri de

date şi anumite etichete ce conţin informaţii cu privire la utilizarea diferitelor componente

vizibile ale ferestrei.

În plus în clasa Fereastra se declară şi se iniţializează diferite butoane cum ar fi:

butonul "Încarcă structura" (crează şi populează structura de date respectivă),

butonul "Afişează informaţia" (afişează informaţia din întreaga structură)

butonul "Sterge" (curaţă suprafaţa de afişare, respectiv textArea )

butonul "Informatii" (crerează o instanţa a clasei Pseudocod, care conţine informaţii cu

privire la structura de date pe care se lucrează precum şi algoritmul de căutare folosit în

respectiva structură)

Trebuie precizat aici şi ceea ce au în comun interfeţele structurilor de date. În primul

rând este vorba despre toate componentele grafice moştenite din clasa Fereastră inclusiv cele

patru butoane precizate mai sus. Apoi, fiecare fereastră în parte are câte un grup de şase

butoane radio având etichetele: ”ID”, ”Societate”, ”Localitate”, ”Strada”, ”Nr”, ”Domeniu” .

Prin selectarea unuia dintre aceste butoane se comunică programului să caute o egalitate cu

cuvântul cheie căutat (acesta se introduce de către utilizator în textfield)la nivelul câmpului

”id”, ”societate”, ”localitate”, ”strada”, ”nr” sau ”domeniu” al obiectului Link aflat memorat

în cadrul structurii de date pe care se lucrează.

Metoda efectivă de căutare este apelată prin apăsarea butonului ”Caută”. Această

metodă este membră a clasei pentru lucrul cu structura de date şi de obicei returnează către

clasa interfeţei un String care conţine rezultatele căutării. Dacă Stringul returnat este vid

atunci se creează o instanţă a clasei Avertizare (în clasa ferestrei)prin care ni se va comunica

că a avut loc o căutare nereuşită. Cheia după care caută este un şir de caractere introdus de la

tastatură în cadrul textfieldului de unde este preluat în primă instanţă sub forma unui String

(aşadar toate metodele de căutare, indiferent de structura de date folosită primesc ca

parametru un String pe care eu l-am denumit searchkey). Apoi printr-o metodă care va fi

discutată ulterior acest String va putea fi transformat în int în cazul în care vor fi introduse

valori numerice.

Clasa Link aflată în fişierul Link.java a fost deja discutată şi prezentată ca şi cod.

În fişierul Căutare.java se creează o mică fereastră care apare încă de la începutul

rulării programului şi se constituie ca un fel de meniu pentru intrarea în ferestrele structurilor

77


de date. Astfel avem o serie de butoane de tip radio (numai unul poate fi selectat la un

moment dat)şi un buton de unde putem confirma alegerea făcută. O dată ce acest buton a fost

apăsat ne va apare fereastra aferentă structurii de date dorită, urmând să ne întoarcem automat

în fereastra meniu o dată cu închiderea ferestrei structurii de date. Ieşirea din aplicaţie se

poate face numai prin închiderea ferestrei meniu.

Aspectul acestei ferestre este dat în figura următoare:

Fişierul Avertizare.java are o singură clasă în care are loc construcţia unei mici

ferestre de dialog (de tipul celei care semnalizează o anumită eroare în Windows)având un

buton “OK” pentru închidere. Această fereastră dialog dependentă deci de fereastra părinte

apare atunci când are loc spre exemplu o căutare nereuşită, nu s-a introdus cheia de căutare

etc. Un exemplu de instanţă a acestei clase preluată din rularea programului “Căutare în

structuri de date”, mai precis în timpul în care era vizibilă fereastra din Lista_Înlanţuită.java

(fereastra părinte)este prezentată în continuare.

78


Codul acestei clase Avertizare este:

class Avertizare extends JDialog { JLabel label; JLabel atentie = new JLabel(atent); String string; public Avertizare(Fereastra parinte, String titlu, boolean modala, int k) { /* constructor în care parinte este obiectul de tip Fereastra de unde se apelează clasa Avertizare; titlu va deveni titlul ferestrei dialog Avertizare; variabila booleană modală specifică dacă fereastra dialog trebuie neaparat închisă înainte de a se reveni la fereastra părinte sau nu; după valoarea care i se va da lui k se va decide ce mesaj să afişeze fereastra dialog, instanţă a acestei clase */

super(parinte, titlu, modala);this.addWindowListener(new WindowAdapter() {

public void windowClosing(WindowEvent e) {dispose();

// se închide fereastra fără a se ieşi din aplicaţie}

});// adaptor pentru acţiunea butonului de închidere a ferestrei if (k==1) {string = new String("Introduceti cheia de cautare");} if (k==2) {string = new String("Nici o inregistrare continand cheia data");} if (k==3) {string = new String("Nu ati introdus un numar");} if (k==4) {string = new String("Selectati butonul radio corespunzator");}// în funcţie de valoarea parametrului k se decide ce text să conţină fereastra dialog JPanel mesaj = new JPanel(); label = new JLabel(string,JLabel.LEFT); label.setFont(new Font("Arial", Font.BOLD, 13)); mesaj.add(atentie,BorderLayout.WEST); mesaj.add(label,BorderLayout.CENTER); JPanel panou = new JPanel(); JButton inchidere = new JButton("Close"); inchidere.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) {dispose();} });//se fixează acţiunea butonului "Close" prin intermediul unui adaptor panou.add(inchidere,BorderLayout.SOUTH); getContentPane().add(mesaj,BorderLayout.NORTH); getContentPane().add(panou,BorderLayout.SOUTH); int w=320; int h=130; Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize(); setSize(w,h); setLocation(screenSize.width/2 - w/2, screenSize.height/2 - h/2);// se fixează dimensiunea şi locaţia ferestrei dialog

show();}

}

Ultimul fişier numit Pseudocod.java conţine tot o singură clasă Pseudocod în care se

creează o fereastră de dialog modală (va trebui închisă dacă se doreşte să se lucreze în

fereastra părinte)conţinând explicaţii despre algoritmii de căutare folosiţi în structura din a

cărei fereastră se apelează această fereastră dialog. Apelarea acestei ferestre se face prin

apăsarea butonului "Informaţii" aflat în partea din dreapta-jos a fiecăreia dintre ferestrele

structurilor chiar lângă butonul "Şterge" care curăţă fereastra de afişaj (aceste două butoane

sunt moştenite şi ele din clasa Fereastră).

Fereastra clasei Pseudocod.java conţine după cum se vede în imaginea de mai jos

(captură din timpul rulării programului în cadrul ferestrei arborelui binar de căutare)un buton

pentru închiderea ferestrei şi un JEditorPane numit tArea care este un obiect special în cadrul

79


căruia se vor puta încărca pagini html. În constructorul prin care este creată o instanţă a

acestei clase Pseudocod este transmis un parametru (opt)care face posibilă identificarea unui

fişier html aflat în directorul Fişiere. Trebuie făcută precizarea că există căte un fişier html în

care sunt explicaţii despre algoritmii de căutare pentru fiecare structură de date în parte. După

identificarea fişierului corespunzător acesta este încărcat în cadrul obiectului JEditorPane prin

comanda:

tArea.setPage(bookURL)

care primeşte ca parametru calea spre pagina html dorită (sau URL acestei pagini în cazul în

care aceasta se află pe Internet).

Codul acestei clase Pseudocod este:

class Pseudocod extends JDialog { JButton ok; URL bookURL;

public Pseudocod(Fereastra parinte, String titlu, boolean modala,int opt) { /* constructor în care părinte, titlu şi modală au aceeaşi semnificaţie ca şi la clasa Avertizare; după valoarea care i se dă acestei variabile întregi opt la apelarea constructorului se va stabili ce pagină html aflată în directorul Fişiere să fie încărcată în cadrul JeditorPane-ului )*/ super(parinte, titlu, modala); this.addWindowListener(new WindowAdapter() { public void windowClosing(WindowEvent e) {

dispose(); // se închide fereastra fără a se ieşi din aplicaţie

}}); // adaptor pentru acţiunea butonului de închidere a ferestreiString fisier=""; /* Stringul în care se memorează după cum urmează calea spre fişierele html ce conţin informaţii despre structurile de date*/

switch (opt) {

case 1: fisier="Fisiere/baza. htm"; break;

case 2: fisier="Fisiere/fisier. htm"; break;

80


case 3: fisier="Fisiere/tablou..htm"; break; case 4: fisier="Fisiere/lista. htm"; break; case 5: fisier="Fisiere/arbore..htm";

break; case 6: fisier="Fisiere/hash. htm";

break; case 7: fisier="Fisiere/graf..htm"; break; }

getContentPane().setLayout(new BorderLayout()); // fixarea gestionarului de poziţie pentru elementele grafice ale ferestrei dialog

JEditorPane tArea = new JEditorPane();// declararea şi iniţializarea suprafeţei de afişare pentru fisierele html cu explicaţii JScrollPane areaScrollPane = new JScrollPane(tArea); tArea.setEditable(false); // tArea devine needitabilă

areaScrollPane.setBorder( BorderFactory.createCompoundBorder( BorderFactory.createCompoundBorder( BorderFactory.createTitledBorder("Info program"), BorderFactory.createEmptyBorder(9,9,9,9)), areaScrollPane.getBorder()));/* datorită acestui JscrollPane atunci când textul depăşeşte dimensiunea suprafeţei de afişare vor apărea automat benzi pentru derularea textului */Dimension minimumSize = new Dimension(100,50);areaScrollPane.setMinimumSize(minimumSize);ok = new JButton("OK");ok.addActionListener(new ActionListener() {public void actionPerformed(ActionEvent e) {dispose(); });// adaptor pentru acţiunea butonului "OK"

String prefix = "file:" + System.getProperty("user.dir")+System.getProperty("file.separator"); try { bookURL = new URL(prefix + fisier);

System.out.println(prefix + fisier); }catch (java.net.MalformedURLException exc)

{ System.err.println("Incercare de a citi un URL gresit: " + bookURL); bookURL = null; } try { tArea.setPage(bookURL); } catch (IOException e) { System.err.println("Incercare de a citi un Url Rau: " + bookURL); }

JPanel panou = new JPanel();panou.add(ok, BorderLayout.CENTER);getContentPane().add(areaScrollPane, BorderLayout.CENTER);getContentPane().add(panou, BorderLayout.SOUTH);int w=370;int h=445;Dimension screenSize=Toolkit.getDefaultToolkit().getScreenSize(); setSize(w,h);

// se setează dimensiunea ferestrei dialogsetLocation(screenSize.width/2 - w/2, screenSize.height/2 - h/2);

// se fixeaza locaţia ferestrei dialogshow(); // fereastra dialog va deveni vizibilă};

}

Până acum s-a dat codul integral al claselor Link, Avertizare şi Pseudocod. Din

pricina faptului că clasele ce ne interesează au un cod destul de lung, mai departe va fi redat

81


doar codul metodelor de căutare (nu se va insista asupra modului de construcţie a ferestrelor

cu ajutorul cărora se vor face operaţiile de creare, citire şi căutare etc.).

Fişierul Baza_De_Date.java

Baza de date fiind deja creată nu mai este necesară apăsarea butonului "Încarcă

structura". Se poate vizualiza conţinutul bazei de date prin apăsarea butonului "Afişează

informaţia". Fereastra fişierului pentru probarea căutării într-o bază de date este prezentată

mai jos.

Căutarea se face tot prin interogări SQL. Pentru căutare se introduce în textField

cuvântul sau numărul căutat, se ara în vedere ca butonul radio dorit să fie selectat şi apoi se

apăsa butonul "Caută".

Metoda folosită pentru căutatea în baza de date este următoarea:

public void find() {

String url="jdbc:odbc:Societati"; String user="dba"; String password="sql"; String query=""; String aux=""; String[] b=new String[90000]; Vector sir =new Vector();

try{Class.forName("sun.jdbc.odbc.JdbcOdbcDriver");

} catch(ClassNotFoundException e)

{e.printStackTrace();System.out.println("Eroare incarcare driver!\n" + e);

}

82


try{ Connection c=DriverManager.getConnection(url, user, password);

String d=cheie.getText();d=d.toUpperCase();try{in1=new Integer(Integer.parseInt(cheie.getText(), 10));}catch(NumberFormatException v) { v.printStackTrace(); System.out.println("Eroare de transformare de tip parseInt()"); }

Statement s= c.createStatement(); if (cbx.getLabel().equals("ID")) query= "SELECT * FROM Table1 WHERE ID = "+in1.intValue(); if (cbx.getLabel().equals("SOCIETATE")) query= "SELECT * FROM Table1 WHERE Societate = '"+d+"'"; if (cbx.getLabel().equals("STRADA")) query= "SELECT * FROM Table1 WHERE Strada = '"+d+"'"; if (cbx.getLabel().equals("LOCALITATE")) query= "SELECT * FROM Table1 WHERE Localitate = '"+d+"'"; if (cbx.getLabel().equals("NR")) query= "SELECT * FROM Table1 WHERE Nr = "+in1.intValue(); if (cbx.getLabel().equals("DOMENIU")) query= "SELECT * FROM Table1 WHERE Domeniu = '"+d+"'";

ResultSet r=s.executeQuery(query);

while (r.next()) { sir.add(r.getString("ID")); sir.add(" ");

sir.add(r.getString("Societate")); sir.add(" "); sir.add(r.getString("Localitate")); sir.add(" "); sir.add(r.getString("Strada")); sir.add(" "); sir.add(r.getString("Nr")); sir.add(" ");

sir.add(r.getString("Domeniu")); sir.add("\n"); }

s.close(); }catch(SQLException e) { e.printStackTrace(); System.out.println("EROARE la interogarea SQL"); }

textArea.setText(" REZULTATUL CAUTARII D-VOASTRE ESTE:\n");

sir.copyInto(b); for (int i=0;i<sir.size();i++) textArea.append(b[i]);

}

Se poate observa că interogarea SQL folosită diferă în funcţie de butonul radio

selectat. Pentru că aşa cum s-a precizat şirul de caractere introdus de la tastatură în interiorul

textfieldului este memorat întotdeauna ca String atunci când avem nevoie de un număr

(întreg)vom putea transforma Stringul în întreg prin crearea şi apoi folosirea metodei

intValue() a unui obiect de tip Integer. Acesta se construieşte prin instrucţiunea:

Integer in=new Integer(Integer.parseInt(cheie.getText(), 10)),

Aici cheie.getText() este o metodă care returnează Stringul din cadrul textFieldului

cheie,iar această metodă de transformare a unui String în int este folosită şi în cadrul celorlalte

fişiere.java, deci nu se va mai insista mai departe pe reexplicarea acestei chestiuni.

Fişierul Fisier.java

83


Odată cu apăsarea butonului "Încarcă structura" se apeleză metoda insert (). Datele

returnate de interogarea SQL sub formă de Stringuri sunt scrise prin intermediul unui flux de

scriere într-un fişier de pe hardisk denumit “out.txt”. Înainte de a se încerca o căutare se poate

vizualiza conţinutul fişierului prin apăsarea butonului "Afişează informaţia". Fereastra

fişierului pentru probarea căutării într-un fişier este următoarea:

Metoda find(), cea de căutare în fişierul “out.txt” spre deosebire de cea de la baza de

date unde era de tip void, va întoarce de această dată un String care mai apoi va fi preluat de

metoda clasei ce crează interfaţa şi afişat în textArea. Codul metodei find() este:

public String find(String searchkey){ String s=""; // s este Stringul ce va fi returnat cu rezultatul căutării

try{ Integer in=new Integer(Integer.parseInt(searchkey, 10));

}catch(NumberFormatException v){System.out.println("Exceptie de tip parseint");}

try{ FileInputStream fis = new FileInputStream("Fisiere/out.txt"); BufferedReader br = new BufferedReader(new InputStreamReader(fis)); StreamTokenizer st = new StreamTokenizer(br);

// flux care desface fişierul analizat în atomi lexicali (tokene) BufferedReader stdin = new BufferedReader(new FileReader("Fisiere/out.txt"),128);

// flux pt citirea din fişier rând cu rând (se doreşte afişarea întregii informaţii despre o anumită cheie găsită ) String input = stdin.readLine(); st.eolIsSignificant(true); // face simbolul eol signifiant

int tip = st.nextToken();//citesc primul atom lexical while (tip != StreamTokenizer.TT_EOF) // până la sfârşitul fişierului { while (tip != StreamTokenizer.TT_EOL) // până la sfârşitul unui rând

{ switch (tip) {

84


case StreamTokenizer.TT_WORD: // dacă tokenul este cuvant { if (st.sval.equalsIgnoreCase(searchkey)) s=s+input+"\n";

/* dacă cuvîntul reprezentat de token este acelaşi cu cuvântul căutat (cel care se introduce în textfield)întreaga linie în care acesta este scris în fişier va fi concatenată Stringului s */

break; } case StreamTokenizer.TT_NUMBER:// dacă tokenul este numar { if (st.nval==in.intValue()) s=s+input+"\n";

/* dacă numărul reprezentat de token este egal cu numărul căutat întreaga linie în care acesta este scris în fişier va fi concatenată Stringului s */

break; }

} tip = st.nextToken(); // trecere la următorul token pt while-ul de la rând }

input = stdin.readLine(); tip = st.nextToken(); // trecere la următorul token pt while-ul de la întregul fişier } stdin.close();

}catch (IOException e) { System.err.println("Eroare de intrare/iesire!"); } return s; // returnează liniile în care s-a găsit şirul de caractere căutat}

Clasa StreamTokenizer folosită în această metodă parcurge un flux de intrare de orice

tip şi îl împarte în "atomi lexicali". Rezultatul va consta în faptul că în loc să se citească octeţi

sau caractere se vor citi, pe rând, atomii lexicali ai fluxului respectiv. Se ştie că un printr-un

atom lexical se înţelege în general:

un identificator (un şir care nu este între ghilimele)

un număr

un şir de caractere

un comentariu

un separator

Atomii lexicali sunt despărţiţi între ei de separatori. Implicit aceşti separatori sunt cei

obişnuiţi (spaţiu, tab, virgulă, punct şi virgulă), însă pot fi schimbaţi prin diverse metode ale

clasei.

Fişierul Array.java

În cadrul acestui fişier se realizează atât o metodă de căutare liniară cât şi una binară.

Pentru aceasta, fereastra pentru lucrul cu tablouri va avea două butoane pentru căutare numite,

85


"Cauta liniar" respectiv "Cauta binar". Deoarece o căutare binară se poate face doar pe un

tablou ordonat a mai fost introdus un buton separat numit "Sortare". Sortarea tabloului se

poate face după oricare din câmpurile obiectelor de tip Link cu care va fi populat tabloul

(”ID”, ”Societate”, ”Localitate”, ”Strada”, ”Nr”, ”Domeniu”).

Specificarea câmpului după care se sortează se face prin selectarea etichetei

respective în cadrul choice-ului nunit ”alege”, după cum se poate vedea în captura din timpul

rulării programului ”Căutări în structuri de date” în cadrul ferestrei pentru lucrul cu tablouri.

Iată mai întâi codul metodei de căutare liniară:

public String find(String searchkey,int optiune){ String s="";

int j=0; // folosit la parcurgerea tabloului a try

{ Integer in=new Integer(Integer.parseInt(searchkey, 10));

}catch(NumberFormatException v) { v.printStackTrace();

System.out.println("Eroare de transformare de tip parseInt()"); } // se transformă Stringul primit în întreg dacă este posibil

for(j=0;j<nElems;j++) {

switch (optiune) {

case 1: { if(a[j].getID()==in.intValue())

s=s+a[j].displayLink(); break;

} case 2: { if(a[j].getSoc().equalsIgnoreCase(searchkey))

86


s=s+a[j].displayLink(); break; } case 3: { if(a[j].getLoc().equalsIgnoreCase(searchkey)) s=s+a[j].displayLink(); break; } case 4: { if(a[j].getStr().equalsIgnoreCase(searchkey)) s=s+a[j].displayLink(); break; } case 5: {

if(a[j].getNr()==in.intValue()) s=s+a[j].displayLink(); break; } case 6: { if(a[j].getDom().equalsIgnoreCase(searchkey)) s=s+a[j].displayLink(); break; }

}//end switch }//end for return s; }//end find()

Se observă că în această metodă de căutare liniară, ca de altfel şi în cea de căutare

binară se mai transmite un parametru de tip întreg în funcţie de care (vezi switchul)se decide

în care câmp a obiectului Link curent să se caute o echivalenţă cu cheia specificată.

Metoda pentru căutarea binară în tablou este:

public String findb(String searchkey,int optiune) { String s1="";

String s2=""; int st=0;

int dr=nElems-1;int mij;try { Integer ine=new Integer(Integer.parseInt(searchkey, 10)); }catch(NumberFormatException v)

{ v.printStackTrace();


while (st<=dr){mij=(st+dr)/2;switch (optiune) {

case 1:

87


{ if (ine.intValue()>a[mij].getID()) st=mij+1;

else if (ine.intValue()<a[mij].getID()) dr=mij-1; else {

s1=s1.concat(a[mij].displayLink()); return s1;

} break;

} case 2:

{ if (searchkey.compareToIgnoreCase(a[mij].getSoc())>0) st=mij+1; else if (searchkey.compareToIgnoreCase(a[mij].getSoc())<0) dr=mij-1;

else {


} break;

} case 3:

{ if (searchkey.compareToIgnoreCase(a[mij].getLoc())>0) st=mij+1; else if (searchkey.compareToIgnoreCase(a[mij].getLoc())<0) dr=mij-1; else {


} break; }

case 4: {

if (searchkey.compareToIgnoreCase(a[mij].getStr())>0) st=mij+1; else if (searchkey.compareToIgnoreCase(a[mij].getStr())<0) dr=mij-1;

else {


} break; } case 5: { if (ine.intValue()>a[mij].getNr()) st=mij+1; else if (ine.intValue()<a[mij].getNr()) dr=mij-1; else {


} break; }case 6: { if (searchkey.compareToIgnoreCase(a[mij].getDom())>0) st=mij+1; else if (searchkey.compareToIgnoreCase(a[mij].getDom())<0) dr=mij-1; else {


} break; }

}//end switch

88


}//end whilereturn s2;

}

Această metodă utilizează algoritmul clasic, iterativ de căutare binară, căutarea

făcându-se după unul din câmpurile obiectelor de tip Link funcţie de parametrul întreg

optiune.

Fişierul Lista_Inlantuita.java

O captură din timpul rulării programului în fereastra acestei structuri de date a fost

dată în momentul prezentării clasei Avertizare. De data aceasta din cadrul choice-ului alege

se va putea alege tipul de listă înlănţuită (simplu sau dubluînlănţuita)pentru construire şi apoi

probarea corectitudinii funcţionării următoarei metode de căutare:

public String find(String searchkey,int optiune){

String s=""; Link current=first;

try { Integer in=new Integer(Integer.parseInt(searchkey, 10)); }catch(NumberFormatException v) { v.printStackTrace();


while (current.right!=null) {

switch (optiune) { case 1:

{ if(current.getID()==in.intValue()) s=s+current.displayLink(); current=current.right; break; } case 2: { if(current.getSoc().equalsIgnoreCase(searchkey)) s=s+current.displayLink(); current=current.right; break; } case 3: { if(current.getLoc().equalsIgnoreCase(searchkey)) s=s+current.displayLink(); current=current.right; break; } case 4: { if(current.getStr().equalsIgnoreCase(searchkey)) s=s+current.displayLink(); current=current.right;

89


break; } case 5: {

if(current.getNr()==in.intValue())s=s+current.displayLink();current=current.right; break;

} case 6: { if(current.getDom().equalsIgnoreCase(searchkey)) s=s+current.displayLink(); current=current.right; break; }

}//end switch }//end while return s;}//end find

Indiferent dacă lista construită este simplu sau dubluînlanţuită aceasta poate fi

parcursă de la stânga la dreapta. Pentru a se vedea cu care din câmpurile obiectului Link

curent să se facă comparaţie s-a transmis parametrul opţiune.

La fel ca şi la tablou, dacă se gaseşte cheia căutată, întreaga informaţie din nodul

respectiv (vezi displayLink())se concatenează Stringului s care mai apoi va fi returnat.

Fişierul Arbore_Binar.java

Deoarece tema prezentei lucrări este “căutarea” la capitolul arbori m-am oprit la

implementarea strict a arborelui de căutare.

Aspectul ferestrei arborelui binar poate fi văzută în captura luată la prezentarea clasei

Pseudocod. Ce nu se poate vedea în acea imagine este ce anume conţine choice-ul alege şi

anume modul în care se va parcurge arborele binar de căutare la afişare (inordine, preordine

sau postordine) odată creat. Se poate verifica uşor că modul de implementare a arborelui este

corect deoarece la afişarea componentelor arborelui în inordine acestea apar ordonate după

câmpul după care a fost construit arborele (acest câmp va fi câmpul indicat de butonul radio

selectat la momentul apăsării butonului “Încarcă structura”).

Deoarece arborele binar de căutare este construit după un anumit câmp al obiectelor

Link ce vor fi conţinute de acesta, o căutare în arbore se poate face doar după o valoare a

acelui câmp. Acesta este motivul pentru care o dată cu crearea arborelui butoanele radio cu

care deja ne-am obişnuit să ne alegem câmpul de căutare nu vor mai fi active. Instrucţiunea

Java pentru această acţiune este buton_radio.setEnabled(false).

90


Dacă se doreşte ca butoanele radio să devină active, se apăsa butonul “Alt arbore”. În

acel moment butonul “Încarcă structura” va deveni şi el activ şi se va putea construi un alt

arbore binar de căutare după oricare dintre câmpurile specificate prin butoanele radio.

Pentru căutare am făcut şase metode de căutare, câte una pentru fiecare din câmpuri.

Metoda de căutare pentru cazul când câmpul de construcţie a arborelui binar de căutare este

de tip String (Societate, Localitate, Stradă sau Domeniu)este:

public String find (String searchkey){ String s=""; Link current=root; while (!(current.getSoc().equalsIgnoreCase(searchkey)))

{ if (searchkey.compareToIgnoreCase(current.getSoc())<0) current=current.left; else current=current.right; if (current==null) return s; } s=s+current.displayLink(); return s;

}

Dacă este înlocuit în metoda de mai sus (căutare după Societate)getSoc() cu getLoc(),

getStr() sau getDom() se obţin şi celelalte metode de căutare după Localitate, Stradă şi

Domeniu.

Pentru cazul în care câmpul de construcţie a arborelui este de tip int (ID sau Nr)

metoda este prezentată în continuare:

public String find(String searchkey){ String s=""; Link current=root; try

{ Integer in=new Integer(Integer.parseInt(searchkey, 10));

// se creează obiectul Integer primind ca parametru Stringul searchkey transformat într-un nr în baza 10 }catch(NumberFormatException v) { v.printStackTrace();


while (current.getID()!=in.intValue())// intValue returnează valoarea întreag ă a obiectului Integer creat cu ajutorul Stringului searchkey

{ if (in1.intValue()<current.getID()) current=current.left; else current=current.right; if (current==null) return s; } s=s+current.displayLink(); return s;

}

91


La fel ca la metoda pentru căutarea unui String dacă se înlocuieşte în metoda de mai

sus (căutare după ID) getID() cu getNr() se obţine metoda de căutare după Nr. Deosebirea

dintre aceste două metode prezentate este că în cadrul celei de-a doua este nevoie să se

convertească Stringul de numere într-un int prin intermediul metodelor clasei Integer().

Fişierul Tabela_De_Dispersie.java

Cu ajutorul ferestrei construită pentru demonstrarea căutării în tabele de dispersie

aflată în acest fişier se pot construi atât tabele de dispersie cu înlănţuire separată cât şi cu

adresare deschisă. Construcţia unui anumit tip de tabelă de dispersie trebuie decisă încă

dinaintea apăsării butonului “Încarcă structura” prin selectarea în cadrul choice-ului alege a

opţiunii respective (vezi imaginea).

Ca şi la arborele binar de căutare, prin natura ei o tabelă de dispersie se construieşte

după un anumit câmp (cel selectat prin butoanele radio), iar apoi căutarea se poate face numai

după valori aflate în cadrul respectivului câmp (butoanele radio vor deveni inactive odată cu

apăsarea butonului pentru încărcarea structurii).

Deoarece obiectele memorate în tabelă sunt de tip Link, implicit vor avea atât câmpuri

de tip int cât şi de tip String, deci vor exista două metode de dispersie, una pentru Stringuri şi

alta pentru întregi. Cele două metode sunt:

92


public int hashFunc1(int key) { System.out.println("Func1: "+key%arraySize); return key%arraySize; }//========================================================================= public int hashFunc2(String key) { key=key.toLowerCase(); int hashVal=0;

for (int j=0;j<key.length();j++){ int letter = key.charAt(j)-96;//codul ASCII a lui 'a' este 96 hashVal=(hashVal*27+letter)%arraySize;//26 de litere + spatiul (alfabetul englez)} System.out.println("Func2: "+hashVal); if (hashVal>=0) return hashVal;

else return -hashVal; }

În funcţie de modul de construcţie a tabelei de dispersie (adresare deschisă sau

înlănţuire separată)prin apăsarea butonului “Caută” se apelează metode de căutare diferite,

specifice. Metoda pentru căutarea într-o tabelă de dispersie cu înlănţuire separată este:

String find_open(String searchkey,int k){

String s="";int hashVal=0;

try{ if ((k==1)||(k==5)) { Integer in=new Integer(Integer.parseInt(searchkey, 10)); hashVal=hashFunc1(in.intValue()); } else hashVal=hashFunc2(searchkey);}catch(NumberFormatException v) { v.printStackTrace(); System.out.println("Eroare de transformare de tip parseInt()"); }

int key=in2.intValue(); while (hashArray_open[hashVal]!=null)

{ switch (k) { case 1: {

if(hashArray_open[hashVal].getID()==key) s=s+hashArray_open[hashVal].displayLink();

break; } case 2: {

if(hashArray_open[hashVal].getSoc().equalsIgnoreCase(searchkey)) s=s+hashArray_open[hashVal].displayLink();

break; } case 3: {

93


if(hashArray_open[hashVal].getLoc().equalsIgnoreCase(searchkey)) s=s+hashArray_open[hashVal].displayLink();

break; } case 4: {

if(hashArray_open[hashVal].getStr().equalsIgnoreCase(searchkey)) s=s+hashArray_open[hashVal].displayLink();

break; } case 5: {

if(hashArray_open[hashVal].getNr()==key) s=s+hashArray_open[hashVal].displayLink();

break; } case 6: {

if(hashArray_open[hashVal].getDom().equalsIgnoreCase(searchkey)) s=s+hashArray_open[hashVal].displayLink();

break; }

}//sfarsit switch ++hashVal; hashVal%=arraySize;

}//sfarsit while //cauta in lista curenta cheia searchkey dupa valoarea k return s; }}

La fel ca şi la alte structuri de date deja prezentate se observă transmiterea unui

parametru de tip întreg, k în funcţie de care se decide în care câmp a obiectului Link curent să

se caute o echivalenţă cu cheia căutată.

Deoarece această metodă primeşte un String ca parametru, ea îl va transforma în

cadrul blocului try-catch într-un întreg pe care îl memorează apoi în cadrul variabilei key.

Totodată se vor trece valorile celor două prin metodele de dispersie specifice tipului de date

de care aparţin obţinându-se astfel indicele în care se va face căutarea în tabloul tabelei de

dispersie. Pentru cazul căutării după ID sau Nr se face comparaţia cu acest key, iar pentru

restul câmpurilor care sunt de tip String se va folosi Stringul searchkey primit prin apelare.

Ştim că o tabelă de dispersie cu înlănţuire separată este de fapt un tablou de liste (sau

tablouri în unele cazuri), astfel în metoda de căutare folosită în acest caz se va parcurge pur şi

simplu lista de obiecte Link memorată în cadrul locaţiei tabloului obţinută prin trecerea

valorilor searchkey sau key prin metodele de dispersie hashFunc1() sau hashFunc2(),

făcându-se la fiecare pas comparaţia cu searchkey sau key, după caz. Parcurgerea listelor se

face prin metodele unui clase separate specializate pe lucrul cu liste înlănţuite.

94


public String find(String searchkey,int k){String s="";

int hashVal=0;try

{ if ((k==1)||(k==5)) { Integer in=new Integer(Integer.parseInt(searchkey, 10)); hashVal=hashFunc1(in.intValue()); } else hashVal=hashFunc2(searchkey);}catch(NumberFormatException v) { v.printStackTrace(); System.out.println("Eroare de transformare de tip parseInt()"); }s=s+hashArray[hashVal].find(searchkey,k);//cauta in lista curenta cheia searchkey dupa valoarea k

return s; }

Mai jos este prezentată metoda prin care se face căutarea în cadrul listelor care pentru

obţinerea unor timpi mai buni la căutare vor fi ordonate (în cazul unor căutări nereuşite nu va

fi necesară parcurgerea integrală a listei respective).

public String find(String searchkey,int k) {

String s="";int key1=0;try{ if ((k==1)||(k==5)) { Integer in=new Integer(Integer.parseInt(searchkey, 10));

key1=in.intValue(); }}catch(NumberFormatException v) { v.printStackTrace(); System.out.println("Eroare de transformare de tip parseInt()"); }Link current=first;

switch (k) {

case 1: { while ((current != null)&&(key1>=current.getID())) { if (current.getID()==key1) s=s+current.displayLink(); current=current.right; } break; }

case 2: { while ((current != null)&&(searchkey.compareToIgnoreCase(current.getSoc())>=0)) { if (current.getSoc().equalsIgnoreCase(searchkey)) s=s+current.displayLink(); current=current.right;

} break; }

95


case 3: { while ((current != null)&&(searchkey.compareToIgnoreCase(current.getLoc())>=0)) { if (current.getLoc().equalsIgnoreCase(searchkey)) s=s+current.displayLink(); current=current.right;

} break; } case 4: { while ((current != null)&&(searchkey.compareToIgnoreCase(current.getStr())>=0)) { if (current.getStr().equalsIgnoreCase(searchkey)) s=s+current.displayLink(); current=current.right;

} break; } case 5: { while ((current != null)&&(key1>=current.getNr()))

{ if (current.getNr()==key1) s=s+current.displayLink(); current=current.right;

} break; } case 6: { while ((current != null)&&(key1>=current.getNr()))

{ if (current.getNr()==key1) s=s+current.displayLink(); current=current.right; }

break; }

}// end_switch return s;

}

Fişierul Graf.java

Cea mai mare deosebire faţă de celelalte fişiere discutate, în ceea ce priveşte structura,

este faptul că clasa corespunzătoare structurii de date, respectiv grafului conţine şi o fereastă

grafică construită ca fereastră dialog a ferestrei mari (cea care derivă din clasa Fereastra).

Această fereastră dialog reprezintă un mod grafic de a completa matricea de adiacenţă a

grafului pe care se lucrează şi are următorul aspect:

96


În momentul deschiderii acestei ferestre a matricii de adiacenţă (imediat după

popularea tabloului în care va fi memorat graful cu obiecte de tipul Link), se va putea alege

tipul de graf care se doreşte a fi construit (graf orientat sau neorientat). Dacă se va alege graf

neorientat se va observa că la o selectare a checkbox-ului (i,j) va fi selectat automat şi

checkboxul (j,i) pentru că la graful neorientat o muchie poate fi traversată în ambele direcţii.

O dată cu apăsarea butonului “OK” fereastra dialog devine invizibilă, putând fi

revăzută prin apăsarea butonului “Matricea de adiacenţă”.

Graful construit poate fi parcurs în trei moduri:

independent de muchii (se va parcurge pur şi simplu tabloul în care este memorat graful)

în lăţime (se foloseşte o coadă implmentată static într-o clasă separată numită Queue)

în adâncime (se foloseşte o stivă implmentată static într-o clasă separată numită Stackx)

La parcurgerea grafului în lăţime şi adâncime se va folosi pentru prima dată şi câmpul

de tip boolean wasVisited, pentru a marca nodurile care s-au parcurs pentru a evita o

reparcurgere a acestora.

Se poate decide cum să se parcurgă graful în momentul afişării (vezi butonul

“Afişează informaţia”) prin selectarea opţiunii dorite în cadrul choice-ului alege.

Pentru a afla dacă există un câmp din elementul Link (cel selectat prin butoanele radio

aflate în stânga-jos)care să conţină cheia searchkey (cea introdusă în textfield)în graf se va

face pur şi simplu o traversare a grafului în lăţime sau adâncime făcându-se câte o comparaţie

la fiecare pas.

97


Metoda de căutare în care se foloseşte traversarea în adâncime este:

public String find(String searchkey,int k) { String s="";

try { Integer ine=new Integer(Integer.parseInt(searchkey, 10)); }catch(NumberFormatException v) { v.printStackTrace(); System.out.println("Eroare de transformare de tip parseInt()"); }// în cazul în care se caută un întreg se va folosi pt comparţie această valoare ine

try { vertexList[0].wasVisited=true; }catch(NullPointerException e) { e.printStackTrace(); System.out.println("Nici un Link in poz 0"); } // se verifică dacă nodul de unde se începe parcurgerea există

theStack.push(0); // se introduce primul nod în stivăswitch (k) {

case 1: { if(vertexList[0].getID()==ine.intValue())

s=s+displayLink(0); break; }

case 2: { if(vertexList[0].getSoc().equalsIgnoreCase(searchkey)) s=s+displayLink(0); break; }

case 3: { if(vertexList[0].getLoc().equalsIgnoreCase(searchkey)) s=s+displayLink(0); break; }

case 4: {

if(vertexList[0].getStr().equalsIgnoreCase(searchkey)) s=s+displayLink(0); break; }

case 5: { if(vertexList[0].getNr()==ine.intValue()) s=s+displayLink(0); break; } case 6: { if(vertexList[0].getDom().equalsIgnoreCase(searchkey)) s=s+displayLink(0); break; }

} while (!theStack.isEmpty())//cat timp exista stiva nu e goala

{ int v=getAdjUnvisitedLink(theStack.peek());

// se găseşte primul vecin nevizitat al nodului aflat în vârful stivei if (v==-1) theStack.pop(); // dacă nu există un astfel de nod se extrage un nod din stivă else {

98


vertexList[v].wasVisited=true; switch (k) { case 1: { if (vertexList[v].getID()==ine.intValue()) s=s+displayLink(v); break; } case 2: { if (vertexList[v].getSoc().equalsIgnoreCase(searchkey)) s=s+displayLink(v); break; } case 3: { if(vertexList[v].getLoc().equalsIgnoreCase(searchkey)) s=s+displayLink(v); break; } case 4: { if(vertexList[v].getStr().equalsIgnoreCase(searchkey)) s=s+displayLink(v); break; } case 5: { if(vertexList[v].getNr()==ine.intValue()) s=s+displayLink(v); break; } case 6: { if(vertexList[v].getDom().equalsIgnoreCase(searchkey)) s=s+displayLink(v); break; } } theStack.push(v); se introduce nodul v în stivă } }//sfarsit whilefor (int j=0;j<nVerts;j++) vertexList[j].wasVisited=false; // restabilim indicatorii

return s; }

99


BIBLIOGRAFIE

[1] Dana Simian, Algoritmi fundamentali şi tehnici de programare

Ed. Universităţii, Sibiu, 2003

[2] E. M. Popa, Dana Simian, Analiza şi sinteza algoritmilor Ed.

Alma Mater, 2001

[3] D.E. Knuth, The Art of Computer Programming vol.3 Sorting

and searching, Ed. Addison Wesley, Reading Massachutes, 1973

[4] Eugen Creţu, Structuri de date în algoritmi Ed. Pshihomedia,

Sibiu, 2001

[5] Michael Waite & Robert Lafore , Structuri de date şi algoritmi

în Java Ed. Teora, 1999

[6] Sabin Corneliu Buraga , Tehnologii Web Ed. Matrix Rom,

Bucureşti 2001

[7] Ben Forta , SQL pentru începători Ed. Teora, 2002

[8] Brian W. Kernighan & Robert Lafore , Limbajul C, Ed. Teora,

2003

[9] I. Tomescu , Data Structure Techniques, Ed. Universităţii,

Bucureşti 1997

100


[10] A.V. Aho, J.E. Hopcraft, J.D. Ullman , The Design And

Analysis of Computer Algorithms Ed. Addison Wesley, Reading

Massachutes, 1973

101

algoritmi de cautare

Documents