1.5 Блочный поиск

Снова вспомним пример с записной книж­кой. Пусть в вашей записной книжке имеется алфавитный индекс в виде вырезанной «лесен­ки» или в виде букв вверху страницы. Несколько страниц, помеченных одной буквой, назовем блоком. Имеется блок «А», блок «Б» и т. д. до блока «Я».

Индекс – это часть ключа поиска (например, первая буква).

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

1) с помощью алфавитного индекса выбирается блок с нужной буквой;

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

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

Списки с указанием на блоки данных называются списками указателей.

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

В поисковом множестве с многоуровневой блочной структурой происходит поиск методом спуска: сначала отыскивается нужный блок первого уровня, затем второго и т.д. Внутри блока последнего уровня может про­исходить либо последовательный поиск (если данных в нем относительно немного), либо оптимизированный поиск типа половинного деления. По­иску методом спуска часто помогают многоуровневые списки указателей.

1.6 Поиск в иерархической структуре данных

Многоуровневые блочные структуры хранения дан­ных называются иерархическими структурами. По такому принципу организовано хранение файлов в фай­ловой системе компьютера. То, что мы называли выше блоками, в файловой системе называется каталогами или папками, а графическое изображение структуры блоков-папок называется деревом каталогов.

Чтобы найти файл, нужно знать путь к файлу по де­реву каталогов. Операционная система поможет найти Отпрашиваемый нами файл по команде Поиск. Резуль­тат поиска представляется в виде пути к файлу, начиная от корневого каталога последовательно по уровням -дерева до каталога (папки), непосредственно содержащего ваш файл. Например, при поиске файла с именем ke.exe будет выдан следующий ответ: E:\GAME\GAMES\ARCON\ke.exe

Здесь указан полный путь к файлу на логическом диске Е: oт корневого каталога до самого файла. Имея такую подсказку, вы легко отыщете нуж­ный файл на диске методом спуска но дереву каталогов. Каталог иерархи­ческой структуры файловой системы компьютера является многоуровневым списком указателей.