Стр. 66 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
64
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Алгоритм поиска
:
A = h(z);
while (M(A) < >
λ
) && (M(A) < > z)
{
A = A+
1
;
}
if xA = z then <успех>
else < неуспех >
Дома доопределить алгоритм таким образом, чтобы он учитывал
конечность размера таблицы
Алгоритм удаления написать самостоятельно!
Пример.
Допустим, в таблицу включены имена, имеющие коды:
|
x
1
|=00010110;
|
x
2
|=00100100;
|
x
3
|=00111010;
|
x
4
|=10100000.
Пусть
h
(
x
) использует три последних бита:
h
(
x
1
)=(110)
2
=6;
h
(
x
2
)=4;
h
(
x
3
)=2;
h
(
x
4
)=0;
h
(
x
) – указывает номера ячеек.
Пусть в таблицу включается новое имя |
x
5
|=10101100 с хэш-значением
h
(
x
5
)=4.
Но ячейка 4 уже занята именем
x
2
. Поэтому
x
5
будет помещена в ячейку
A
=4+1=5.
Таблица примет вид
Если нужно включить
x
2
. Если
x
2
удален и при удалении просто записан в
ячейку λ, то ключ
x
5
уже никогда не будет найден (по алгоритму, описанному
выше). Поэтому при удалении любого ключа в ячейку следует писать
специальный знак, означающий “удалено” (например *) .
0 1 2 3 4 5 6 7 8 9
x
4
λ
x
3
λ
x
2
x
5
x
1
λ λ λ
