Algorytmy wyszukiwania
1. Wyszukiwanie w tablicach nieposortowanych
Wyszukiwanie liniowe z zastosowaniem zmiennej logicznej lub wartownika
Złożoność:
wstawianie do tablicy O(1)
wyszukiwanie O(N)
usuwanie O(N)
2. Wyszukiwanie w tablicach posortowanych
2.1 Wyszukiwanie binarne
wstawianie do tablicy O(N)
wyszukiwanie O(log(N))
usuwanie O(N)
2.2 Wyszukiwanie interpolacyjne w zbiorze kluczy o rozkładzie jednostajnym
T[l] T[s]=x T[p]
l s p
(s-l)/{p-l)=(x-T[l])/(T[p]-T[l])
s=l+(x-T[l]) *(p-l)/(T[p]-T[l])
3. Wyszukiwanie przez transformacje kluczowe.
Przy dużej nadmiarowości rozmiaru tablicy N, w stosunku do liczby kluczy umieszczanych (do 70 % wypełnienia tablicy)
wstawianie do tablicy O(1)
wyszukiwanie O(1)
usuwanie O(1)
3.1. Funkcje transformujące klucze ( hash coding -mieszające) [Wróblewski Algorytmy, struktury danych i techniki programowania]
i=H(k)
H=f(N,k)
suma wartości znaków klucza modulo N,
suma MOD 2, bitów kodów znaków klucza (różnica symetryczna),
suma MOD 2, bitów kodów znaków klucza przesuniętych w prawo o liczbę pozycji równą numerowi znaku w kluczu,
część całkowita
klucz * stały mnożnik MOD N
mnożnik z przedziału (0,1)
3.2. Rozwiązywanie kolizji
Próbkowanie liniowe
Próbkowanie kwadratowe
h0 = H(k),
hi = (h0 + i2) MOD N, (i > 0). hi = (h0 +di) MOD N, (i > 0).
di+1 := di+2 d0 = 1
Obszary nadmiarowe
Listy elementów o takiej samej wartości funkcji mieszającej
4. Zastosowania
Słowniki, tablice symboli, kartoteki
PROGRAM Szybkie_Przesz;
USES CRT;
CONST
ROZMIAR=100;
TYPE
St20 =STRING[20];
Obiekt=RECORD
zajety :BOOLEAN;
slowo :St20;
czestosc :INTEGER
END;
Tabl =ARRAY[1..ROZMIAR] OF Obiekt;
VAR
slownik :Tabl;
poz,AlgSzuk,ilosc:INTEGER;
slowo :St20;
Tabl_Pelna,wpis :BOOLEAN;
PROCEDURE Inicjuj(VAR spis:Tabl);
VAR
i:INTEGER;
BEGIN
ilosc:=0;
FOR i:=1 TO ROZMIAR DO
BEGIN
WITH spis[i] DO
BEGIN
zajety:=FALSE;
slowo:=' ';
czestosc:=0
END
END
END; {Inicjuj}
PROCEDURE Drukuj(VAR spis:Tabl);
VAR
i:INTEGER;
BEGIN
IF AlgSzuk=3
THEN ilosc:=ROZMIAR;
FOR i:=1 TO ilosc DO
BEGIN
WITH spis[i] DO
WRITELN(slowo:10,' ',czestosc);
IF (i MOD 20)=0
THEN READLN
END
END; {Drukuj}
FUNCTION SzukajLiniowo {wyszukiwanie liniowe}
(VAR spis:Tabl;slwe:St20;VAR pozycja:INTEGER;
VAR pelna:BOOLEAN):BOOLEAN;
VAR
Sl_Znal:BOOLEAN;
BEGIN
pozycja:=1;
Znal:=FALSE;
spis[ROZMIAR].zajety:=FALSE;
WHILE spis[pozycja].zajety AND NOT Znal DO
BEGIN
Znal:=slownik[pozycja].slowo=slwe;
IF NOT Znal
THEN pozycja:=pozycja+1
END;
SzukajLiniowo:=Znal;
pelna:=pozycja=ROZMIAR;
IF pelna AND Znal
THEN spis[ROZMIAR].zajety:=TRUE;
END; {SzukajLiniowo}
PROCEDURE Wprowadz(VAR Nowe:St20;VAR spis:Tabl; pozycja:INTEGER);
BEGIN
WITH spis[pozycja] DO
BEGIN
slowo:=Nowe;
czestosc:=1;
zajety:=TRUE
END
END; {Wprowadz}
FUNCTION SzukajBinarnie {szukanie binarne}
(VAR spis:Tabl;slwe:St20;VAR pozycja:INTEGER;VAR pelna:BOOLEAN):BOOLEAN;
VAR
dolny_index,gorny_index,i:INTEGER;
Znal :BOOLEAN;
BEGIN
dolny_index:=1;
gorny_index:=ilosc;
Znal:=FALSE;
IF gorny_index<>0
THEN
BEGIN
REPEAT
pozycja:=TRUNC((dolny_index+gorny_index) DIV 2);
IF slwe<spis[pozycja].slowo
THEN gorny_index:=pozycja-1
ELSE
IF slwe>spis[pozycja].slowo
THEN dolny_index:=pozycja+1
ELSE Znal:=TRUE
UNTIL Znal OR (dolny_index>gorny_index)
END;
IF NOT Znal
THEN
BEGIN
IF ilosc=ROZMIAR
THEN Pelna:=TRUE
ELSE
IF ilosc<>0
THEN
BEGIN
FOR i:=ilosc DOWNTO pozycja DO
spis[i+1]:=spis[i];
pozycja:=dolny_index;
spis[pozycja].zajety:=FALSE
END
ELSE pozycja:=1
END;
SzukajBinarnie:=Znal
END; {SzukajBinarnie}
FUNCTION SzukajKluczowo {Szukiwanie przez tranformacje klucza}
(VAR spis:Tabl;slwe:St20;VAR pozycja:INTEGER;
VAR pelna:BOOLEAN): BOOLEAN;
VAR
Znal :BOOLEAN;
PozPocz:INTEGER;
FUNCTION Miejsce(VAR slwe:St20):INTEGER;
VAR
hsum,i:INTEGER;
BEGIN
hsum:=0;
FOR i:=1 TO length(slwe) DO
hsum:=hsum+ord(slwe[i]);
Miejsce:=hsum MOD ROZMIAR+1
END; {Miejsce}
BEGIN {SzukajKluczowo}
Znal:=FALSE;
PozPocz:=miejsce(slwe);
Pelna:=FALSE;
pozycja:=PozPocz;
IF spis[PozPocz].zajety
THEN
IF spis[PozPocz].slowo<>slwe
THEN
BEGIN
spis[PozPocz].zajety:=FALSE;
pozycja:=(PozPocz+1)MOD ROZMIAR;
WHILE spis[pozycja].zajety AND NOT Znal DO
IF spis[pozycja].slowo=slwe
THEN Znal:=TRUE
ELSE pozycja:=(pozycja+1) MOD ROZMIAR;
Pelna:=pozycja=PozPocz
spis[PozPocz].zajety:=TRUE
END
ELSE Znal:=TRUE;
SzukajKluczowo:=Znal
END; {SzukajKluczowo}
BEGIN {Program glowny}
WRITELN('Wybierz typ przeszukiwania');
WRITELN('1 - liniowe');
WRITELN('2 - binarne');
WRITELN('3 - losowe');
READLN(AlgSzuk);
IF AlgSzuk=2
THEN ilosc:=0;
Inicjuj(slownik);
TablPelna:=FALSE;
WRITELN('Podaj ciag slow zakonczony slowem koniec -');
WRITELN('dla przeszukiwania binarnego ciag uporzadkowany niemalejaco');
READLN(slowo);
WHILE slowo<>'koniec' DO
BEGIN
CASE AlgSzuk OF
1: wpis:=NOT SzukajLiniowo(Slownik,slowo,poz,TablPelna);
2: wpis:=NOT SzukajBinarnie(Slownik,slowo,poz,TablPelna);
3: wpis:=NOT SzukajKluczowo(Slownik,slowo,poz,TablPelna);
END;
IF wpis
THEN
IF NOT TablPelna
THEN
BEGIN
Wprowadz(slowo,slownik,poz);
IF AlgSzuk<>3
THEN ilosc:=ilosc+1
END
ELSE WRITELN('tablica pelna')
ELSE slownik[poz].czestosc:=slownik[poz].czestosc+1;
WRITELN('poz ',poz,' ',slowo);
READLN(slowo)
END;
Drukuj(slownik)
END.
FUNCTION SzukajInterpolacyjnie {szukanie interpolacyjne}
(VAR T:Tabl;x:klucz;):INTEGER;
VAR
l,p,s:INTEGER;
Znal:BOOLEAN;
BEGIN
l:=1;
p:=ilosc;
Znal:=FALSE;
WHILE (l<=p) AND NOT Znal DO
BEGIN
IF T[l]=T[p]
THEN s:=l
ELSE s:=l+ (x-T[l)*(p-l) DIV T[p]-T[l]);
IF x<T[s]
THEN p:=s-1
ELSE
IF x>T[s]
THEN l:=s+1
ELSE Znal:=TRUE
END;
IF Znal
THEN Interpol:=s
ELSE interpol:=0;
END; {SzukajInterpolacyjnie}
Indeks |
Wartość |
1 |
3 |
2 |
4 |
3 |
8 |
4 |
29 |
5 |
35 |
6 |
44 |
7 |
63 |
8 |
78 |
9 |
89 |
10 |
105 |
11 |
118 |
12 |
123 |
13 |
140 |
14 |
145 |
15 |
149 |
16 |
150 |