- •Лабораторная работа по теме: методы поиска
- •Краткие сведения из теории
- •1. Линейный (последовательный) поиск
- •2. Быстрый последовательный список
- •3. Дихотомический (бинарный) поиск
- •4. Интерполяционный поиск
- •5. Сравнение рассмотренных методов
- •Контрольные вопросы
- •Методические указания
- •Содержание отчета
- •Варианты индивидуальных заданий
федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Тобольская государственная социально-педагогическая академия
им. Д.И. Менделеева»
Кафедра информатики, ТиМОИ
Лабораторная работа по теме: методы поиска
по дисциплине «Основы компьютерных наук»
для студентов физико-математического факультета
Составила: ст. преподаватель Оленькова М.Н.
Тобольск, 2012
Цель данной работы:
изучить различные методы поиска.
программно реализовать хранение множества однотипных элементов и операции, перечисленные в индивидуальном задании так, чтобы они удовлетворяли требованиям, предъявляемым к сложности операций.
Краткие сведения из теории
В этой лабораторной работе будут рассматриваться способы хранения множества однотипных элементов. Основными критериями сравнения этих способов будут временные сложности алгоритмов поиска/добавления/удаления элементов множества.
Главная задача лабораторной работы:
показать различные способы организации хранения множества однотипных элементов.
показать взаимную зависимость способов хранения данных и сложности алгоритмов их обработки,
понять важность изначального выбора структуры данных и алгоритмов их обработки, удовлетворяющей всем необходимым требованиям, следующим из особенностей эксплуатации программного продукта.
Кроме того, интерес представляют операции добавления и удаления элементов, так как в реальных задачах редко встречается статическое множество, то есть множество, которое не меняется. Далее будет видно, как сильно зависят друг от друга способ хранения множества элементов и сложности перечисленных операций.
Начнем рассмотрение способов хранения множества однотипных элементов с точки зрения алгоритмов поиска/добавления/удаления с алгоритма линейного поиска.
1. Линейный (последовательный) поиск
Линейный поиск – самый простой из известных. Суть его заключается в следующем. Множество элементов просматривается последовательно в некотором порядке, гарантирующем, что будут просмотрены все элементы множества (например, слева направо). Если в ходе просмотра множества будет найден искомый элемент, просмотр прекращается с положительным результатом; если же будет просмотрено все множество, а элемент не будет найден, алгоритм должен выдать отрицательный результат. Именно так поступает человек, когда ищет что-то в неупорядоченном множестве. Например, при поиске нужной визитки в некотором неупорядоченном множестве визиток человек просто перебирает все визитки в поисках нужной.
Оформим описанный алгоритм в виде фрагмента программы на Паскале. Пусть множество хранится в первых n элементах массива A. При этом не важен тип элементов множества, важна лишь возможность проверки эквивалентности элемента множества искомому элементу Key.
i := 1;
while (i<=n) and (A[i]<>Key) do inc(i);
if A[i]=Key then <элемент найден> else <элемент не найден>;
В среднем этот алгоритм требует n/2 итераций цикла. Это означает сложность алгоритма поиска T(n). Единственное требование к способу хранения множества – существование некоторого порядка на множестве: чтобы можно было указать, что один элемент предшествует другому. Здесь можно хранить множество как в массиве (рассмотренный выше фрагмент программы), так и в обычном однонаправленном списке:
Type
PListItem = ^TListItem;
TListItem = record
Item: TItem;
Next: PListItem;
end;
Рассмотрим добавление элемента Key во множество, хранимое в виде массива. Здесь достаточно просто дописать новый элемент в «конец» множества:
inc(n); A[n] := Key;
Удалению элемента всегда предшествует успешный поиск. Это значит, что сложность операции удаления не может быть меньше сложности операции поиска. В данном случае при удалении нам придется сначала найти положение удаляемого элемента, затем все элементы, следующие за ним, сдвинуть на одну позицию к началу массива и уменьшить n. То есть в любом случае надо пробежать весь массив от начала до конца (это означает сложность T(n)):
i := 1;
while (i<=n) and (A[i]<>Key) do inc(i); {поиск}
if A[i]=Key then
begin
while i<n do
begin
A[i] := A[i+1]; {сдвигаем}
inc(i);
end;
dec(n);
end;
Теперь положим, что множество хранится в виде списка. Добавление элемента сведется к добавлению элемента в начало списка (при добавлении в конец списка пришлось бы сначала искать конец, либо специально хранить указатель на последний элемент списка). Удаление элемента будет состоять из поиска и собственно удаления (никаких сдвигов последующих элементов производить не придется).