3. házi feladat kiíráshoz 2. példa

Kezdőkulcs: 856, kulcsnövekmény: 153. A beszúrandó kulcsok lesznek a beszúrás sorrendjében:

856, 109, 262, 415, 568, 721, 874, 127, 280, 433, 586, 739, 892, 145, 298

A 415 beszúrása után törölni kell a 856-os kulcsot,

A 127 beszúrása után a 109-est és a 739 beszúrása után a 262-est.

Adatstruktúrák, algoritmusok			3. házi feladat
NEPTUN kód:			Beadás dátuma:
Név (Nyomtatott nagybetűk):			Sajátkezű aláírás:
Megoldások
táblaméret	kezdőkulcs	kulcsnövekmény	Lineáris	Kvadratikus	Dupla hasítás
19	856	153	10	5	2

Hasító függvények: h₀(k) = k mod 19

Lineáris kipróbálás	h(k,i) = (h0(k)+i) mod 19, i=0,1,2,…,18
Kvadratikus kipróbálás	h(k,i) = (h0(k)+i*(i+1)/2) mod 19, i=0,1,2,…,18
Dupla hasítás	h(k,i) = (h0(k)+i*h1(k)) mod 19, i=0,1,2,…,18 ahol h1(k) = 1+(k mod 18)

Kipróbálási sorozatok

Kulcs	Lineáris	Kvadratikus	Dupla	Megjegyzés
856	6	6	6
109	7	7	7
262	7 8	7 8	7 14
415	7 8 9	7 8 10	7 6 5
				856 törlése
568	7 8 9 10	7 8 10 13	7 16
721	7 8 9 10 11	7 8 10 13 0	7 9
874	7 8 9 10 11 12	7 8 10 13 0 5	7 1
127	8 9 10 11 12 13	8 9	8
				109 törlése
280	8 9 10 11 12 13 14	8 9 11	8 0
433	8 9 10 11 12 13 14 15	8 9 11 14	8 10
586	8 9 10 11 12 13 14 15 16	8 9 11 14 1	8 2
739	8 9 10 11 12 13 14 15 16 0	8 9 11 14 1 6	8 12
				262 törlése
892	8	8	8 4
145	9 10 11 12 13 14 15 16 0 1	9 10 12	9 11
298	9 10 11 12 13 14 15 16 0 1 2	9 10 12 15	9 3

Hasító táblák

Rés	Lineáris		Kvadratikus		Dupla
0	+	739	+	721	+	280
1	+	145	+	586	+	874
2	+	298		0	+	586
3		0		0	+	298
4		0		0	+	892
5		0	+	874	+	415
6	-	856	+	739	-	856
7	-	109	-	109	-	109
8	+	892	+	892	+	127
9	+	415	+	127	+	721
10	+	568	+	415	+	433
11	+	721	+	280	+	145
12	+	874	+	145	+	739
13	+	127	+	568		0
14	+	280	+	433	-	262
15	+	433	+	298		0
16	+	586		0	+	568
17		0		0		0
18		0		0		0