П ОИСК ДАННЫХ Выполнил: преподаватель информатики Осинцева О.С. Министерство общего и профессионального образования Свердловской области государственное. - презентация

1 П ОИСК ДАННЫХ Выполнил: преподаватель информатики Осинцева О.С. Министерство общего и профессионального образования Свердловской области государственное бюджетное образовательное учреждение среднего профессионального образования Свердловской области «Екатеринбургский техникум химического машиностроения»

2 П ОИСК ДАННЫХ – ОСНОВНОЙ ВИД ОБРАБОТКИ ИНФОРМАЦИИ

3 Набор данных – вся совокупность данных, среди которых осуществляется поиск Ключ поиска - поле записи, по значению которого происходит поиск. Критерий поиска – условие, которому должно удовлетворять значение ключа поиска в искомой записи.

4 Н АБОР ДАННЫХ Элементы набора данных называются записями. Запись может состоять из одного или нескольких полей. Например, запись в записной книжке состоит из полей: фамилия, адрес, телефон Фамилия АдресТелефон Сидоров А.Г.Печорская Иванов О.М.Ленина Иванов К.М. Лесная

5 К ЛЮЧ ПОИСКА Например, поле ФАМИЛИЯ, если мы ищем номер телефона определенного человека Фамилия АдресТелефон Сидоров А.Г.Печорская Иванов О.М.Ленина Иванов К.М. Лесная

6 К РИТЕРИЙ ПОИСКА Например, если вы ищите телефон Сидорова, то критерий поиска заключается в совпадении фамилии Сидоров с фамилией, указанной в очередной записи в книжке Фамилия АдресТелефон Сидоров А.Г.Печорская Иванов О.М.Ленина Иванов К.М. Лесная

7 Набор данных Структура данных Лесная Петров «куча» Елфинов Поиск осуществляется последовательным или случайным перебором

8 П ОСЛЕДОВАТЕЛЬНЫЙ ПОИСК Алгоритм поиска последовательным перебором

9 П ОИСК ПОЛОВИННЫМ ДЕЛЕНИЕМ Возьмем для примера игру в угадывание целого числа в определенном диапазоне. Например, от 1 до 8. Один играющий загадывает число, второй пытается его угадать, задавая вопросы, на которые ответом может быть «Да» или «Нет». Если вопросы задавать такие: «Число равно единице?». Ответ: «Нет». Вопрос: «Число равно двум?» и т.д., то это будет последовательный перебор

10 П ОИСК ПОЛОВИННЫМ ДЕЛЕНИЕМ Если максимальное число диапазона N не равно целой степени двойки, то оптимальное количество вопросов не будет постоянной величиной, а будет равно одному из двух значений: X или X+1, где Например, если число ищется в диапазоне от 1 до 7, то его можно угадать за 2 или 3 вопроса, поскольку

11 Б ЛОЧНЫЙ ПОИСК Индекс – это часть ключа поиска Например, в записной книжке имеется алфавитный индекс в виде вырезанной «лесенки» или в виде букв вверху страницы. Несколько страниц, помеченных одной буквой, назовем блоком. Имеется блок «А», блок «Б» и т.д. до блока «Я» Записная книга А Б В Г Д Е Д БЛОКИ

12 Б ЛОЧНЫЙ ПОИСК Записи в книжке мы ведем в порядке поступления. При такой организации данных поиск нужного телефона будет происходить блочно – последовательным методом: 1. с помощью алфавитного индекса выбирается блок с нужной буквой 2. внутри блока поиск производится путем последовательного перебора Списки с указанием на блоки данных называются списками указателей Разбиение данных на блоки может быть многоуровневым. В толстых словарях блок «А», например, разбивается на блоки по второй букве: блок от «АБ» до «АЖ», такой порядок называется лексикографическим

13 П ОИСК В ИЕРАРХИЧЕСКОЙ СТРУКТУРЕ ДАННЫХ Многоуровневые блочные структуры хранения данных называются иерархическими структурами. В файловой системе блоки называется каталогами или папками. Графическое изображение структуры блоков – папок называется деревом

14 Каталог Иерархическая структура Д ЕРЕВО КАТАЛОГОВ

15 П ОИСК В ИЕРАРХИЧЕСКОЙ СТРУКТУРЕ ДАННЫХ Что бы найти файл, нужно знать путь к файлу по дереву каталогов. Операционная система поможет найти запрашиваемый вами файл по команде Поиск Результат поиска представляется в виде пути к файлу, начиная от корневого каталога последовательно по уровням дерева до каталога (папки), непосредственно содержащего файл. Например, при поиске файла с именем ke.exe будет выдан следующий ответ: E:\GAME\GAMES\ARCON\ke.exe

16 С ИСТЕМА ОСНОВНЫХ ПОНЯТИЙ Поиск данных Атрибуты поиска Набор данных – вся совокупность данных, среди которых осуществляется поиск Ключ поиска – поле записи, по значению которого происходит поиск Критерий поиска – условие, которому должно удовлетворять значение ключа поиска в искомой записи Организация набора данных Неструктурированны й Структура данных Линейная упорядоченность Блочная одноуровневая структура Блочная многоуровневая (иерархическая) структура Алгоритмы поиска Случайный перебор. Последовательный перебор Поиск половинным делением Блочно – последовательный поиск. Использование индексов и списков указателей Поиск методом спуска по дереву. Использование многоуровневых списков указателей

17 В ОПРОСЫ И ЗАДАНИЯ 1. Что относится к атрибутам поиска? 2. Что такое список указателей? 3. Посмотрите свои учебники по разным предметам. Определите, какие списки указателей там использованы: простые или многоуровневые? 4. Можно ли каталок библиотеки назвать списком указателей?