Algoritmi de Cautare

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

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 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.

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ă

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;

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 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 domenie 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ă.

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 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 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ă).

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;

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]

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), 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

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 “.”).

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 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 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.

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.

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:

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)

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:

Î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 fluxului

TT_EOL – atom ce marchează sfârsitul unei linii

TT_NUMBER – atom de tip număr

TT_WORD – atom de tip cuvânt

nval – valoarea unui atom numeric

sval – șirul conținut de un atom de tip cuvânt

ttype – 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.
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 lexical

while (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ăr

if (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 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:

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)

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:

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

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 ?

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;

EndWhile

cod:= “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.

Î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 = xi) =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 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

{

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.

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 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+ “}”);

}

}

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 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

Ș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

}

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.

Î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ă)

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).

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.

Î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

––––––––––––––––––––––––

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 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.

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ă:

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ă

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ă cheia

while (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 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.

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:

DataItem find(int key) // caută elementul cu cheia key

// vom presupune ca tabela nu este plina

{

int hashval = hashFunc1(key); // calculează indicele

int stepSize = hashFunc2(key); // calculează pasul

while (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ă.

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).

Î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.

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ă.

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.

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, 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.

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 aij=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 j-lea să zicem (i,j) se va face punând aij = 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.

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.

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 while

for (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ă

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.

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);

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

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ă.

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:

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

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.

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 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

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

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.

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 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 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 conexiunii

Statement 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();

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

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 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 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.

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 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 ferestrei

String 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;

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 dialog

setLocation(screenSize.width/2 – w/2, screenSize.height/2 – h/2);

// se fixeaza locația ferestrei dialog

show(); // 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 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);

}

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

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)

{

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, "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))

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();

System.out.println("Eroare de transformare de tip parseInt()");

}

while (st<=dr)

{

mij=(st+dr)/2;

switch (optiune)

{

case 1:

{

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

{

s1=s1.concat(a[mij].displayLink());

return s1;

}

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

{

s1=s1.concat(a[mij].displayLink());

return s1;

}

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

{

s1=s1.concat(a[mij].displayLink());

return s1;

}

break;

}

case 5:

{

if (ine.intValue()>a[mij].getNr()) st=mij+1;

else if (ine.intValue()<a[mij].getNr()) dr=mij-1;

else

{

s1=s1.concat(a[mij].displayLink());

return s1;

}

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

{

s1=s1.concat(a[mij].displayLink());

return s1;

}

break;

}

}//end switch

}//end while

return 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();

System.out.println("Eroare de transformare de tip parseInt()");

}

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;

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).

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();

System.out.println("Eroare de transformare de tip parseInt()");

}

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;

}

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:

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:

{

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.

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;

}

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:

Î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.

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

{

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 while

for (int j=0;j<nVerts;j++) vertexList[j].wasVisited=false; // restabilim indicatorii

return s;

}

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

[10] A.V. Aho, J.E. Hopcraft, J.D. Ullman , The Design And Analysis of Computer Algorithms Ed. Addison Wesley, Reading Massachutes, 1973