Tablice z haszowaniem - haszowanie otwarte
Funkcje haszujące dla haszowania otwartego
Funkcja i ciąg jej możliwych wartości (tzw. ciąg kontrolny):
Przykłady funkcji (c1,c2 - stałe liczby, h',h1,h2 - zwykłe funkcje haszujące (z łańcuchowego))Procedury potrzebne do "obsługi" tablicy z haszowaniem otwartym:
Trzeba też zaimplementować funkcję usuwającą, ale uwaga:Zadanie 1: Haszowanie z adresowaniem otwartym (3 pkt)
Stwórz program, który będzie wstawiał, usuwał i szukał liczb naturalne w tablicy z haszowaniem z adresowaniem otwartym. Wymagania szczegółowe:
- Użytkownik podaje liczbę naturalną, która będzie wielkością tablicy.
- Użytkownik następnie podaje jedną z trzech liter: W - opcja wstawiania do tablicy, S - opcja szukania, U - opcja usuwania oraz liczbą naturalną, którą program ma wstawić, usunąć lub szukać. Należy szczególną uwagę zwrócić na opcję usuwania - komórki tablicy z usuniętymi polami muszą przechowywać unikalną wartość np. -1 (patrz uwaga wyżej).
- Haszujemy z adresowaniem otwartym - liniowym przyjmując za funkcję h'(k) - adresowanie modularne. Po każdej operacji wyświetlany jest stan tablicy z haszowaniem.
Zadanie 2: Ulepszenia (2 pkt)
Ulepsz poprzedni program o następujące rzeczy:
- Użytkownik podaje liczbę naturalną by określić rozmair tablicy. Jednak teraz program znajduje najmniejszą liczbę pierwszą p, która jest większa od podanej przez użytkownika liczby naturalnej. Następnie program tworzy tablicę o wielkości p.
- Wstawiane rekordy oprócz klucza, zawierają też imię i nazwisko.
- Haszujemy z adresowaniem otwartym - dwukrotnym przyjmując za funkcję h1 i h2 - adresowanie modularne. Po każdej operacji wyświetlany jest stan tablicy z haszowaniem.