блоковий пошук

Знову згадаємо приклад із записником. Нехай у вашій записній книжці є алфавітний індекс у вигляді вирізаної «драбинки» або у вигляді букв у верхній частині сторінки. Несколькостраніц, позначених однією буквою, назвемо блоком. Є блок «А», блок «Б» і т. Д. До блоку «Я».

Індекс - це частина ключа пошуку (наприклад, перша буква).

Записи телефонів і адрес розставлялися в записнику по блокам відповідно з першою літерою. Однак всередині блоку записи не впорядковані в алфавітному порядку наступних букв, як це робиться в словниках та енциклопедіях. записи вкнижці ми ведемо в порядку надходження. При такій організації даних пошук потрібного телефону буде відбуватися блочно-послідовним методом:

1) за допомогою алфавітного індексу вибирається блок з потрібною буквою;

2) всередині блоку пошук проводиться шляхом послідовного перебору.

Більшість книг на початку або в кінці тексту містять змісту: список назв розділів із зазначенням сторінок, з яких вони починаються. Розділи - це ті ж блоки. Пошук потрібної інформації в книзі починається з перегляду змісту, з подальшим переходом до певного розділу, який потім проглядається послідовно. Очевидно, це той же блочно-послідовний методпоіска.

Списки з зазначенням на блоки даних називаються списками покажчиків.

Розбиття даних на блоки може бути багаторівневим. У товстих словниках блок на букву «А» розбивається, наприклад, на блоки по другій букві: блок від «АБ» до «АЖ», наступний від «AЗ» до «АН» і т.д. Такий порядок називається лексикографічним.

У пошуковому безлічі з багаторівневою блокової структурою відбувається пошук методом спуску:спочатку відшукується потрібний блок першого рівня, потім другого і т.д. Усередині блоку останнього рівня може відбуватися або послідовний пошук (якщо даних в ньому відносно небагато), або оптимізований пошук типу половинного ділення. Пошуку методом спуску часто допомагають багаторівневі списки покажчиків.

Попередня 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Наступна