Алгоритмы поиска. Линейный поиск. Двоичный поиск
|
Скачать 1.68 Mb.
|
Линейный поиск. Данный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, т.е.от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершенным. В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только, если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции. Также, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума. Алгоритм последовательного поиска: Шаг1. Полагаем, что значение переменной цикла i=0. Шаг2. Если значение элемента массива x[i] равно значению ключа key, то возвращаем значение, равное номеру искомого элемента, и алгоритм завершает работу. В противном случае значение переменной цикла увеличивается на единицу i=i+1. Шаг3. Если i Двоичный поиск (также известен, как метод деления пополам и метод половинного деления) – алгоритм нахождения заданного значения монотонной (невозрастающей или неубывающей) функции. Поиск основывается на теореме о промежуточных значениях. Используется в информатике, вычислительной математике и математическом программировании. Это поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей. Поиск заканчивается при совпадении искомого элемента с элементом, который является границей между частями множества или при отсутствии искомого элемента. Алгоритм бинарного поиска: Шаг1. Определить номер среднего элемента массива middle=(high+low)/2. Шаг2. Если значение среднего элемента массива равно искомому, то возвращаем значение, равное номеру искомого элемента, и алгоритм завершает работу. Шаг3. Если искомое значение больше значения среднего элемента, то возьмем в качества массива все элементы справа от среднего, иначе возьмет в качестве массива все элементы слева от среднего. Перейдем к Шагу1. В массиве может встречаться несколько элементов со значениями, равными ключу. Данный алгоритм находит первый совпавший с ключом элемент, который в порядке следования в массиве может быть ни первым, ни последним среди равных ключу.
Процесс упорядочивания информации и называют «сортировкой». Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы. Сортировка массива данных занимает одну из самых важнейших проблем современных организаций. Ведь в каждой организации есть свои БД на сотрудников, которые нужно отсортировать, допустим, по фамилии или по зп, по возрастанию или убыванию. Чаще всего сортировка применяется для последующего поиска. Перед тем, как решать вопросы сортировки необходимо знать объем данных, которые необходимо обрабатывать. Есть методы, которые наиболее эффективны при малом количество элементов, но они становятся довольно громоздкими при большом. Постановка задачи такова: есть набор неупорядоченных данных (массив), задача – выдать те же данные, упорядоченные по некоторому полю (ключу) по возрастанию (убыванию). Обычно данные представляются в виде ключа и некоторой связанной с ним информации. Например, год рождения и фамилия. Практически каждый алгоритм сортировки можно разбить на три части: -сравнение, определяющее упорядоченность пары элементов; - перестановку, меняющую местами пару элементов; - собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены. Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти. Время – основной параметр, характеризующий быстродействие алгоритма. Память – ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Классификация алгоритмов сортировки Сортировка вставками. Создается новый массив, в который мы последовательно вставляем элементы из исходного массива так, чтобы новый массив был упорядоченным. На каждом шаге алгоритма мы выбираем один из элементов данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Сортировка вставками эффективна на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшей. Эффективна на наборах данных, которые уже частично отсортированы. Может сортировать список по мере его получения. Сортировка методом выбора. На первом шаге в массиве ищется самый маленький элемент и меняется местами с первым. На втором шаге ищется самый маленький, начиная со второго, и ставится на 2-е место (второй элемент, естественно, не забываем – ставим его на место, где раньше был самый маленький). И так далее, на i-ом шаге ищется самый маленький, начиная с i-го и ставится на i-е место. Метод пузырька. Метод пузырька так же называют «Пузырьковой сортировкой». Суть сортировки методом пузырька вытекает из названия. Мы находим минимальный элемент (пузырек) в массиве и выставляем его первым элементом массива (поднимает на поверхность). Далее находим следующий минимальный элемент и так же его выставляем вслед за первым элементом. И так будем действовать до самого конца. Таким образом, минимальные элементы всплывают. Этот алгоритм в исходном списке ищет пары цифр, которые следуют не по порядку и затем меняет их местами. Процесс повторяется до тех пор, пока весь список не будет отсортированным. Сортировка Шейкером. Когда данные сортируются не в оперативной памяти, а на жестком диске, особенно если ключ связан с большим объемом дополнительной информации, то количество перемещений элементов существенно влияет на время работы. Этот алгоритм уменьшает количество таких перемещений, действуя следующим образом: за один проход из всех элементов выбирается минимальный и максимальный. Потом минимальный элемент помещается в начало массива, а максимальный, соответственно, в конец. Далее алгоритм выполняется для остальных данных. Таким образом, за каждый проход два элемента помещаются на свои места, а значит, понадобится N/2 проходов, где N – количество элементов. 4. Использование списков для моделирования сложных структур данных. Часто в серьезных программах надо использовать данные, размер и структура которых должны меняться в процессе работы. Динамические массивы здесь не выручают, поскольку нельзя сказать, сколько памяти надо выделить – это выясняется только в процессе работы. В таких случаях применяют данные особой структуры, которые представляют собой отдельные элементы, связанные с помощью ссылок. Каждый элемент (узел) состоит из двух областей памяти: поля данных и ссылок. Ссылки – это адреса других узлов этого же типа, с которыми данный элемент логически связан. В языке Си для организации ссылок используются переменные-указатели. При добавлении нового узла в такую структуру выделяется новый блок памяти и с помощью ссылок устанавливаются связи этого элемент с уже существующими. Для обозначения конечного элемента в цепи используются нулевые ссылки (NULL). Линейный список – это конечная последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться. При работе со списками на практике чаще всего приходится выполнять следующие операции: -найти элемент с заданным свойством; -определить первый элемент в линейном списке; -вставить дополнительный элемент до или после указанного узла; - исключить определенный элемент из списка; -упорядочить узлы линейного списка в определенном порядке. Строение списка: набор узлов, объединенных с помощью ссылок. Однонаправленный линейный список- список, который имеет указатель на начало списка, при этом каждый список имеет указатель на следующий список, а последний список принимает указатель NULL, что говорит о том, что он последний. Однонаправленный кольцевой список – список, который имеет указатель на начало списка, при этом каждый список имеет указатель на следующий список, а последний список имеет указатель на начало списка. В зависимости от количества связей между соседними элементами различают односвязные и двусвязные списки. Каждый элемент в списке с двойной связью имеет указатель на следующий элемент списка и указатель на предыдущий элемент списка. Двунаправленный список отличается двумя основными преимуществами. Во-первых, список может просматриваться в обоих направлениях. Это не только упрощает сортировку списка, но также позволяет пользователям БД просматривать данные в обоих направлениях. Во-вторых, список при нарушении одной из связей может быть восстановлен по другой связи. Это свойство имеет смысл использовать при отказах оборудования, приводящих к нарушению списка. Структура узла: struct Node{ char word[40]; //слово int count; //счетчик повторений Node *next; //ссылка на следующий элемент }; Адрес начала списка: PNode Head=NULL; Для доступа к списку достаточно знать адрес его головы. Когда нужны списки? Задача. В файле записан текст. Нужно записать в другой файл в столбик все слова, встречающиеся в тексте, в алфавитном порядке, и количество повторений для каждого слова. Проблемы: - количество слов заранее неизвестно; - количество слов определяется только в конце работы. Решение – список. Алгоритм: - создать список; - если слова в файле закончились, то стоп. - прочитать слово и искать его в списке; - если слово найдено – увеличить счетчик повторений, иначе добавить слово в список; - перейти к шагу 2. При работе со списками необходимо уметь создать новый узел, добавить узел в начало списка, в конец списка, после заданного узла, до заданного узла, искать нужный узел в списке, удалить узел. Функция CreateNode – создает узел.
В зависимости от метода доступа к элементам линейного списка различают разновидности линейных списков называемые стеком, очередью и двусторонней очередью. Очередь – это линейный список, где элементы удаляются из начала списка, а добавляются в конце списка. Двусторонняя очередь – это линейный список, у которого операции добавления и удаления элементов и доступа к элементам возможны как вначале так в конце списка. Добавление элемента в очереди возможно лишь в конец очереди, выборка – только из начала очереди, при этом выбранный элемент из очереди удаляется. Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие. Очередь – информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления – другой, называемый головой. Типовые операции над очередями: -добавление элемента в очередь (помещение в хвост); -удаление элемента из очереди (удаление из головы); - проверка, пуста ли очередь; - очистка очереди. Очередь называют структурой типа FIFO (First In – First Out) – первым пришел, первым ушел. На рисунке изображена очередь из 3-ех элементов. Добавление элемента -> в б а ->удаление элемента конец начало Если максимальный размер очереди заранее известен, его можно реализовать в программе в виде массива. Если максимальный размер заранее неизвестен или требуется сделать его динамическим, для реализации используют список.
Дерево – иерархическая структура данных, хранящая набор элементов. Каждый элемент имеет значение и может указывать на ноль или более других элементов. На каждый элемент указывает только один другой элемент. Единственным исключением является корень дерева, на который не указывает ни один элемент. Входящие в дерево элементы называются его вершинами. Существует два основных типа деревьев. В рекурсивном дереве или неупорядоченном дереве имеет значение лишь структура самого дерева без учета порядка потомков для каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку, присвоены различные натуральные числа) называется деревом с именованными ребрами или упорядоченным деревом. Упорядоченные деревья являются наиболее распространенными среди древовидных структур. Двоичное дерево поиска – одно из разновидностей упорядоченного дерева. Существует множество различных способов представления деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определенными их позициями в массиве. Операции:
Применение: -управление иерархией данных; - упрощение поиска информации; - оптимизация программ; -в качестве технологии компоновки цифровых картинок для получения различных визуальных эффектов и др. Дерево – структура данных, состоящая из узлов и соединяющих их направленных ребер (дуг), причем в каждый узел (кроме корневого) ведет ровно одна дуга. Корень – это начальный узел дерева. Лист – это узел, из которого не выходит ни одной дуги. С помощью деревьев изображаются отношения подчиненности (иерархия, старший-младший, родитель – ребенок). Предок узла х – это узел, из которого существует путь по стрелкам в узел х. Потомок узле х – это узел, в который существует путь по стрелкам из узла х. Высота дерева – это наибольшее расстояние от корня до листа. Двоичное (бинарное) дерево – это дерево, в котором каждый узел имеет не более двух сыновей. Применение двоичных деревьев: -поиск данных в специально построенных деревьях (БД) -сортировка данных -вычисление арифметических выражений -кодирование Ключ – это характеристика узла, по которой выполняется поиск. Обход дерева – это перечисление всех узлов в определенном порядке. |
Похожие:
 |
Техническое задание на выполнение работ по устройству ограждения... Акционерное общество «Научно-производственное объединение «Поиск» (ао «нпо «Поиск») |
 |
Конспект лекций по дисциплине «Информационные системы и технологии в науке и образовании» Введение. Содержание дисциплины и порядок ее изучения. Фактографический поиск. Математические модели фактографического поиска. Информационная... |
|
Инструкция по поиску и спасанию в Приволжской зоне авиационно-космического... Приложениями №11 и №12 к Конвенции о международной гражданской авиации «Поиск и спасание» |
|
Руководство по эксплуатации системы Регистр онмк и окс «Система Витакарта» Для поиска карты пациента в базе данных на панели инструментов выбираем поиск карты |
|
Инструкция по поиску и спасанию в Приволжской зоне авиационно-космического... Приложениями №11 и №12 к Конвенции о международной гражданской авиации «Поиск и спасание» |
|
Сборник по итогам декады молодого специалиста «Молодой учитель: поиск, открытие, перспектива» Молодой педагог: поиск, открытие, перспектива. Сборник по итогам декады молодого специалиста «Молодой учитель: поиск, открытие, перспектива»... |
|
Доклад мбоу до «Станция юных техников «Поиск» Мбоу до «Станция юных техников «Поиск» была образована в 1972 году в здании бывшей школы №35 производственным объединением «Прогресс»... |
|
Российской федерации (минэкономразвития россии) Для указания области на карте, внутри которой требуется провести поиск ресурсов и осуществления поиска только среди ресурсов, экстент... |
|
Инструкция по организации массовых мероприятий с детьми Настоящая Инструкция определяет порядок организации массовых мероприятий в государственном автономном образовательном учреждении... |
|
1. Справки и сводки по заказам Поиск в базе данных ранее созданного pnr производится запросом сз, если требуется просматривать pnr, или запросом кз, если его необходимо... |
|
Инструкция Поиск в спс «Кодекс web» Вы можете воспользоваться поиском. В поисковую строку вводите, интересующую Вас информацию. После ввода нажмите расположенную рядом... |
|
Поиск на Google Картах |
|
Занятие 1-2 Поиск информации в сети Интернет Российские и зарубежные поисковые системы |
|
Роль цитомегаловирусной инфекции в патологии плода и новорожденного.... Роль цитомегаловирусной инфекции в патологии плода и новорожденного. Поиск новых противовирусных средств |
|
Обнаружитель скрытых видеокамер Поиск объектива видеокамеры и его локализация осуществляется методом световой локации |
|
Обнаружитель скрытых видеокамер Поиск объектива видеокамеры и его локализация осуществляется методом световой локации |