федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Тобольская государственная социально-педагогическая академия

им. Д.И. Менделеева»

Кафедра информатики, ТиМОИ

Лабораторная работа по теме: методы поиска

по дисциплине «Основы компьютерных наук»

для студентов физико-математического факультета

Составила: ст. преподаватель Оленькова М.Н.

Тобольск, 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;

Теперь положим, что множество хранится в виде списка. Добавление элемента сведется к добавлению элемента в начало списка (при добавлении в конец списка пришлось бы сначала искать конец, либо специально хранить указатель на последний элемент списка). Удаление элемента будет состоять из поиска и собственно удаления (никаких сдвигов последующих элементов производить не придется).