Задачи поиска в структурах данных Поиск - нахождение какой-либо конкретной информации в большом объеме ранее собранных данных. Данные делятся на записи, и каждая запись имеет хотя бы один ключ. Ключ используется для того, чтобы отличить одну запись от другой. Целью поиска является нахождение всех записей подходящих к заданному ключу поиска.

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

Задачи поиска в структурах данных d

Var a: array[0..N -1] of Item; Item описывает запись с некоторым полем, играющим роль ключа. Задача заключается в поиске элемента, ключ которого равен заданному аргументу поиска x

Задачи поиска в структурах данных Полученный в результате индекс i, удовлетворяющий условию а[i].key = x, обеспечивает доступ к другим полям обнаруженного элемента. Так как мы рассматриваем, прежде всего, сам процесс поиска, то мы будем считать, что тип Item включает только ключ key

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

Линейный поиск Алгоритм 1. i:=0; while (i х) do i:=i+1;

Линейный поиск Алгоритм 2.( алгоритм линейного поиска с барьером ) а: array[0..N] of integer a[N]:=x; i:=0; while a[i]x do i:=i+1;

Поиск делением пополам (двоичный поиск) массив A упорядочен, т. е. удовлетворяет условию a k-1 a k, 1 k< N

Поиск делением пополам (двоичный поиск)

L:=0; R:=N-1; Found:=false; while(L

Поиск делением пополам (двоичный поиск) Максимальное число сравнений для этого алгоритма равно log 2 n Линейный поиск - N/2

Поиск делением пополам (двоичный поиск) Быстрый алгоритм L:=0; R:=N; while L

Поиск в таблице Поиск в массиве иногда называют поиском в таблице, особенно если ключ сам является составным объектом, таким, как массив чисел или символов Type String = array[0..М-1] of char; отношение порядка для строк x и y: x = y, если xj = yj для 0=< j < M x < y, если xi < yi для 0=< i < M и xj = yj для 0 =< j < i

Поиск в таблице Схема поиска с концевым символом i:=0; while (x[i]=y[i]) and (x[i]*) do i:=i+1 Концевой символ работает здесь как барьер

Поиск в таблице Пусть таблица T и аргумент поиска x определяются следующим образом: T: array[0..N-1] of String; x: String; Пусть N достаточно велико и таблица упорядочена в алфавитном порядке

Поиск в таблице L:=0; R:=N; while L

Поиск в таблице if R

Прямой поиск строки Пусть задан массив s из N элементов и массив p из M элементов, причем 0 < M =< N. Описаны они так: s: array[0..N-1] of Item р: array[0..M-1] of Item Поиск строки обнаруживает первое вхождение p в s.

Прямой поиск строки Алгоритм прямого поиска i:=-1; repeat i:=i+1; j:=0; while (j

Алгоритм Кнута, Мориса и Пратта R F

Общая схема КМП-алгоритма i:= 0; j:=0; While (j

Алгоритм Кнута, Мориса и Пратта Program KMP; const Mmax = 100; Nmax = 10000; var i, j, k, M, N: integer; p: array[0..Mmax-1] of char; {слово} s: array[0..Nmax-1] of char; {текст} d: array[0..Mmax-1] of integer;

Алгоритм Кнута, Мориса и Пратта begin {Ввод текста s и слова p} Write('N:'); Readln(N); Write('s:'); Readln(s); Write('M:'); Readln(M); Write('p:'); Readln(p); {Заполнение массива d} j:=0; k:=-1; d[0]:=-1;

Алгоритм Кнута, Мориса и Пратта while j=0) and (p[j]p[k]) do k:=d[k]; j:=j+1; k:=k+1; if p[j]=p[k] then d[j]:=d[k] else d[j]:=k; end;

Алгоритм Кнута, Мориса и Пратта {Поиск слова p в тексте s} i:=0; j:=0; while (j

Алгоритм Кнута, Мориса и Пратта {Вывод результата поиска} if j=M then Writeln('Yes') {найден } else Writeln('No'); {не найден} Readln; end. Число сравнений – m+n

Алгоритм Боуера и Мура

Program BM; const Mmax = 100; Nmax = 10000; var i, j, k, M, N: integer; ch: char; p: array[0..Mmax-1] of char; {слово} s: array[0..Nmax-1] of char; {текст} d: array[' '..'z'] of integer;

Алгоритм Боуера и Мура begin {Ввод текста s и слова p} Write('N:'); Readln(N); Write('s:'); Readln(s); Write('M:'); Readln(M); Write('p:'); Readln(p); {Заполнение массива d} for ch:=' ' to 'z' do d[ch]:=M;

Алгоритм Боуера и Мура for j:=0 to M-2 do d[p[j]]:=M-j-1; i:=M; repeat j:=M; k:=i; repeat {Цикл сравнения символов } k:=k-1; j:=j-1; {слова, начиная с правого.} until (j s[k]); {Выход, если сравнили все} {слово или несовпадение. } i:=i+d[s[i-1]]; {Сдвиг слова вправо } until (j N);

Алгоритм Боуера и Мура {Вывод результата поиска} if j