http://pl.wikipedia.org/wiki/Tablica_mieszaj%C4%85ca albo szybki wstęp: Słowniki: Podstawowe operacje: Member(x,A) - ma jako argumenty słownik A oraz obiekt x. Zwraca wartość true, gdy obiekt należy do słownika i false w przeciwnym wypadku. Insert(x,A) – Czyni x elementem A. Jeśli x już jest w A, to Insert nic nie zmienia. Delete(x,A) – Usuwa x z A. MAKENULL(x,A) – Czyni A słownikiem pustym. Jak można zaimplementować słowniki? • Jako listy posortowane • Jako listy nieposortowane • Jako wektory bitowe (przy założeniu, że elementy są z przedziału (1,..,n) HASZOWANIE • Ważną implementacją słowników jest haszowanie. • Haszowanie daje średnio stały czas dostępu do elementu słownika • W najgorszym przypadku daje czas proporcjonalny do rozmiaru zbioru • T ablica mieszająca (tablica haszująca) to struktura danych służąca do przechowywania informacji, w taki sposób, aby możliwy był do nich szybki dostęp . • Odwołania do przechowywanych obiektów dokonywane są na pods
Komentarze
Prześlij komentarz