Tablice z haszowaniem - haszowanie otwarte

Funkcje haszujące dla haszowania otwartego

Funkcja i ciąg jej możliwych wartości (tzw. ciąg kontrolny):

procedury

Przykłady funkcji (c1,c2 - stałe liczby, h',h1,h2 - zwykłe funkcje haszujące (z łańcuchowego))

procedury

Procedury potrzebne do "obsługi" tablicy z haszowaniem otwartym:

procedury

Trzeba też zaimplementować funkcję usuwającą, ale uwaga:

procedury

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.