Стр. 72 - Основы алгоритмов и структур данных

70 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4.9.6. Внешнее разрешение коллизий
В этом случае каждая ячейка M основной таблицы либо пуста, либо
содержит ссылку на подтаблицу, которая и содержит все ключи,
коллизирующие на данной ячейке.
Фактически в ячейке M содержится либо λ, либо адрес подсписка. Для
поиска каждая подтаблица может быть организована либо последовательно,
либо для логарифмического поиска.
Зебра
Жираф Питон
Варан
Жираф
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
A M
Пример.
Организация таблиц с внешним разрешением коллизий, подтаблицы –
связные списки.
Каждая ячейка таблицы представлена структурой :
struct name
{
char *key; - само имя
name *next; - указатель на следующий элемент,
содержащий имя коллизирующее с данным