BPC-ALD - Skripta_rev2019_2
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
Úkoly k textu
Máte vytvořit hašovací tabulku s určitými záznamy o osobách. Součástí záznamů jsou rodná
čísla, která slouží jako klíč. Zkuste se zamyslet, jak byste z rodného čísla vytvořili hašovací
funkci.
Řešení
1. Hodnoty hašovací funkce jsou
h(Marta) = (13+5) mod 7 = 4
h(Petr) = (16+4) mod 7 = 6
h(Irena) = (9+5) mod 7 = 0
Hašovací tabulka je:
0
Irena
1
2
3
4
Marta
5
6
Petr
2. Hašovací funkce pro řešení konfliktů je:
7
mod
))
6
mod
)
)
(
(
1
(
)
(
(
)
,
...
(
1
1
2
1
k
z
w
i
k
z
w
i
z
z
z
H
k
+
+
∗
+
+
=
Vypočítáme hodnotu hašovací funkce pro jméno Jiří
h(Jiří) = (10+4) mod 7 = 0
Pozice 0 je v tabulce již obsazena jménem Irena. Vypočítáme další pozici
H(Jiří,1) = (10+4+1
∗(1+(10+4) mod 6)) mod 7 = 3
− 90 −
Ta je již volná a jméno Jiří lze na ni uložit:
0
Irena
1
2
3
Jiří
4
Marta
5
6
Petr
− 91 −
5 Rejstřík
AVL stromy, 64
běh, 50
binární strom, 17
binární vyhledávání, 60
B-stromy, 73
bublinkové třídění, 25
časová složitost, 4
fronta, 14
halda, 41
hašování, 81
otevřené adresování, 83
zřetězení, 86
paměťová složitost, 4
pole, 10
polyfázové třídění, 53
polynomická složitost, 7
Quicksort, 34
seznam, 11
obousměrný, 12
Shellovo třídění, 31
složitost
časová, 4
paměťová, 4
polynomická, 7
strom, 16
vyvážený, 18
stromy
AVL, 64
binární, 17
B-stromy, 73
vyhledávací, 63
třídění
bublinkové, 25
polyfázové, 53
Quicksort, 34
Shellovo, 31
úloha, 21
vnější, 21
vnitřní, 21
třídění haldou, 41
třídění přímou výměnou, 25
třídění přímým vkládáním, 22
vnější třídění, 21, 50
vnitřní třídění, 21, 53
vyhledávací stromy, 63
vyhledávání
AVL stromy, 64
binární, 60
B-stromy, 73
hašování, 81
úloha, 59
v nesetříděném poli, 59
v setříděném poli, 60
vyvážený strom, 18
zásobník, 13