Mam nastepujące zadanie:
Dane są zbiór kluczy {a,b,c,d,e} oraz funkcja haszująca h taka, że h(d)=3, h(c)=4, h(b)=4, h(a)=3, h(e)=1.
a) Uzupełnij tablicę haszującą po dodaniu kluczy d, c, b, a, e, zgodnie z metodą liniową:
0 1 2 3 4 5
b) Z tablicy otrzymanej w poprzednim podpunkcie usuń klucz 'd', zgodnie z metodą
liniową:
0 1 2 3 4 5
podpunkt a powinien wygladac chyb a tak:
012345
ae dcb
Moje pytanie, w jaki sposób usuwa sie klucze metoda liniowa??
To zależy od tego co ci na wykładzie podali.
Z tego co ja wiem to w adresowaniu otwartym nie "usuwa" się elementów, tylko oznacza się odpowiednie miejsca w tablicy jako "puste".
No właśnie we wszystkich źródłach jest napisane tak samo jak Ty twierdzisz, a na egzaminie trzeba usuwać:)
Ech, przecież to podstawy podstaw, masz trzy możliwe stany: pusty slot, slot używany (tutaj trzymasz właściwy rekord), slot usunięty, czyli taki ignorowany podczas wyszukiwania i traktowany jako pusty podczas wstawiania. Usuwasz element i oznaczasz to miejsce jako rekord usunięty. To tak jak z normalną praktyką przy pointerach, gdzie robisz delete i zerujesz wskaźnik, tylko tutaj nadajesz mu specjalną wartość zamiast zerować.
Jedyne co można by ewentualnie zrobić przy usuwaniu to odszukać najdalszy element o danym kluczu i wpisać go w miejsce tego usuwanego. W ten sposób skracamy ścieżkę poszukiwań tego elementu. Nic więcej zrobić się nie da. Taka praktyka jest przydatna jeśli często wyszukujemy elementy.
czyli z tego co rozumien rozwiazaniem punku b bedzie nastepujacy
012345
Ne dcb
U
L
deus napisał(a):
Ech, przecież to podstawy podstaw, masz trzy możliwe stany: pusty slot, slot używany (tutaj trzymasz właściwy rekord), slot usunięty
Co nam daje rozróżnienie pomiędzy "pusty" a "usunięty"?
Wyszukiwanie elementów przerywasz jeżeli znajdziesz pasujący element lub natrafisz na puste pole, to oznacza, że więcej rekordów o tym (lub podobnym) hashu już nie ma, tj. elementu nie ma w hashtablicy. Rekordy usunięte oznaczają tylko tyle, że za nim może się znajdować kolejny rekord i ew. mogą stanowić miejsce na wstawienie (cofnięcie) znalezionego elementu, to się nazywa leniwym usuwaniem.
Aha. Rozumiem. Inaczej to implementowałem - zapamiętywałem indeks.