ADT
TABUĽKA
údajová štruktúra nad množinou L ( lineárne usporiadaná množina prvkov )
množina prvkov s vlastnosťami
•
prístup k prvku podľa hodnoty kľúča
KLUC
kľúč - zvolená položka, ktorá prvok jednoznačne identifikuje
( napr. : ŠPZ, Id.č.osoby, RČ ??? , ... , Id.č. knihy, ... )
údajový typ kľúča - ľub. typ, na ktorom sú definované operácie porovnávania
•
prvok obsahuje : kľúč, ďalšie informácie
špecifikácia
ADT
TABUĽKA
Prvky s kľúčom ( bližšie neurčené )
************************************************************
Prvky tohto ADT
Vytvor
Zruš
Mohutnosť
JePrázdna
Prehliadka
Hľadaj
Pridaj
Odober
(
(
(
(
(
(
↑
↑
↓
↓
↓
↓
PočetPrvkov )
ÁnoNie )
Typ, ↓ Činnosť )
Kľúč, ↑ Prvok )
Prvok )
Kľúč, ↑ Prvok )
************************************************************
Zjednotenie
( ↓ Tab1, ↓ Tab2, ↑ Tabuľka )
možnosti implementácie - zložitosti pre základné činnosti :
Hľadaj
•
Odober
pole ( statické, dynamické ) - implementácia s implicitnými vzťahmi
neutriedené
utriedené
•
Pridaj
O(n)
O( log n )
O(1)
bez kontroly kľúča
O(1)
bez hľadania
/ posl. -> vol./
O(n)
s kontrolou
O(n)
s hľadaním
O(n)
O(n)
lin. zreť. zoznam - implementácia s explicitnými vzťahmi
neusporiadaný
O(n)
O(1)
bez kontroly kľúča
O(n)
s kontrolou
O(1)
bez hľadania
O(n)
s hľadaním
/ záver : dtto ako pole /
usporiadaný
O(n)
O(n)
O(1)
bez hľadania
O(n)
s hľadaním
/ záver : usporiadanosť nič nezlepšila /
algoritmy vyhľadávania - ukážky pre pole, obdobne pri iných realizáciách
/ úloha : hľadanie hodnoty X v poli A /
•
sekvenčné
skúmanie celej množiny - !!! neefektívne, laický prístup !!!
Nasiel = FALSE;
cyklus FOR I :
1 - N
AK A[I] == X
POTOM
KTO POUŽÍVA :-))
Nasiel = TRUE;
cyklus s dvoma podmienkami, napr. :
I = 0;
// pred prvý
OPAKUJ
I = I+1;
POKIAL ( A[I] == X ) OR ( I == N );
{ podmienka existencie : A[I] == X }
Pozn. : uvedené riešenie predpokladá N>0, inakšie "drobná" úprava
programovacia technika - tzv. zarážka
I = 0; A[ N+1 ] = X;
OPAKUJ
I = I+1;
POKIAL A[I] == X;
{ podmienka existencie : I <= N }
Pozn. : vyhovuje aj pre N=0
predpokladáme jedno "voľné" miesto
•
binárne hľadanie pri utriedených prvkoch - zložitosť O ( log n )
I:=1; J:=N;
{ Pascal }
REPEAT
K:= (I+J) DIV 2;
IF X>A[K] THEN I:=K+1
ELSE
UNTIL ( A[K]=X ) OR ( I>J );
{ podmienka existencie : A[K]=X }
J:=K-1;
CIEĽ - spôsob realizácie s "dobrou" zložitosťou všetkých operácií
•
•
binárny vyhľadávací strom, vyvážený strom
transformácia kľúča ( hašovanie )
•
kosoštvorcová vyhľadávacia sieť ( kosoštvorcové triedenie )
- samostatná téma
- samostatná téma
príklad
pre každý vrchol platí
•
•
•
vpravo ( DOLE i HORE ) sú prvky s väčšou hodnotou kľúča
vľavo
-"-"menšou
-"v i-tom bloku ( okrem posledného bloku ) je i prvkov
dôsledok
•
•
v smere šikmo doprava ( HORE i DOLE ) sú prvky utriedené
prvky v jednej úrovni ( tzv. blok ) sú utriedené
realizácia v poli
1
22
B1
2
19
3
30
B2
4
13
5
25
B3
6
42
7
8
8
15
9
28
B4
10
50
11
4
12
10
13
18
B5
14
15
i-B+1
i - tý prvok má nasledovníkov
i+B+1
i-B
i - tý prvok má predchodcov
i+B
! ! ! TREBA ŠPECIÁLNE OŠETRIŤ HRANICE BLOKOV ! ! !
napr. prvok
25
i = 5, B = 3
indexy nasledovníkov
predchodcov
3,9
2,8
hľadanie
traverzovanie od koreňa zostupne podľa výsledku porovnávania s kľúčmi
ak KHLADANE < KI , potom
I := I + B
I := I + B + 1
KHLADANE
> KI , potom
iterácia ( cyklus ) pokiaľ ( KHLADANE < > KI )
zložitosť O ( n 1 / 2 )
AND ( I < = N )
***********
podmienka úspechu
( odmocninová )
lepšia ako O(n)
horšia ako O( log n ) - dokonale vyvážený binárny vyhľadávací strom
pridanie
•
•
O( 1 )
prvok dáme za posledné miesto
"stratégia"
odoberanie
•
•
prvok z posledného miesta dáme na rušené miesto
"stratégia"
O( 1 )
“stratégia“ je založená na porovnaní s predchodcami a nasledovníkmi
•
•
ak K <
niektorý
predchodca
, tak výmena s VÄČŠÍM z nich
•
ak K >
niektorý
nasledovník
, tak výmena s MENŠÍM z nich
rádová zložitosť činnosti “stratégia“
:
O ( n 1/2)
Záver :
všetky činnosti
hľadaj, pridaj, odober
:
odmocninová zložitosť
Download

ADT TABUĽKA