NetNado
  Найти на сайте:

Учащимся

Учителям



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



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

  • Поиск - нахождение какой-либо конкретной информации в большом объеме ранее собранных данных.

  • Данные делятся на записи, и каждая запись имеет хотя бы один ключ. Ключ используется для того, чтобы отличить одну запись от другой.

  • Целью поиска является нахождение всех записей подходящих к заданному ключу поиска.


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

  • Кроме поиска совпадению аргумента поиска с ключом записи, существует поиск по близости аргумента и ключа и поиск по интервалу, означающий попадание ключа в заданный двумя аргументами (границами) интервал.

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



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



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

  • Var a: array[0..N -1] of Item;

  • Item описывает запись с некоторым полем, играющим роль ключа.

  • Задача заключается в поиске элемента, ключ которого равен заданному аргументу поиска x



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

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

  • Так как мы рассматриваем, прежде всего, сам процесс поиска, то мы будем считать, что тип Item включает только ключ key



Линейный поиск

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

  • Такой метод называется линейным поиском



Линейный поиск

  • Алгоритм 1.

  • i:=0;

  • while (iand (а[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 упорядочен, т. е. удовлетворяет условию

  • ak-1 ak, 1 k< N



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



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

  • L:=0; R:=N-1; Found:=false;

  • while(L<=R) and not Found do

  • begin

  •          m:=(L+R) div 2;

  •          if a[m]=x then Found:= true

  •                          else

  •                             if a[m]then L:=m+1

  • else R:=m-1

  •                     

  • end;



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

  • Максимальное число сравнений для этого алгоритма равно log2n

  • Линейный поиск - N/2



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

  • Быстрый алгоритм

  • L:=0; R:=N;

  • while Ldo

  • begin

  •            m:=(L+R) div 2;

  •            if а[m]

  • then L:=m+1

  • else R:=m

  • end;

  • If a[R] = x then …. {элемент найден}



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

  • Поиск в массиве иногда называют поиском в таблице, особенно если ключ сам является составным объектом, таким, как массив чисел или символов

  • 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 Ldo

  • begin

  •              m:=(L+R) div 2; i:=0;

  •            while (T[m,i]=x[i]) and (x[i]<>*) do i:=i+1;

  •               if T[m,i]then L:=m+1 else R:=m

  • end;



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

  • if Rthen

  • begin

  •            i:=0;

  •            while (T[R,i]=х[i]) and (х[i]<>*) do

  • i:=i+1

  • end

  • {(Rand (T[R,i]=x[i]) фиксирует совпадение}



Прямой поиск строки

  • Пусть задан массив 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 (jand (s[i+j]=p[j]) do

  • j:=j+1;

  • until (j=M) or (i=N-M)



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



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



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

  • Общая схема КМП-алгоритма

  • i:= 0; j:=0;

  • While (jand (ido

  • begin

  • While (j>=0) and (s[i] <>p[j]) do

  • j:=d;

  • i:= i+1; j := j+1

  • end

  • shift



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

  • 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<(M-1) do

  • begin

  •             while(k>=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 (jand (ido

  • begin

  •          while (j>=0) and (s[i]<>p[j]) do

  • j:=d[j]; {Сдвиг слова}

  •           i:=i+1; j:=j+1;

  • end;



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

  • {Вывод результата поиска}

  • if j=M then Writeln('Yes') {найден }

  • else Writeln('No'); {не найден}

  • Readln;

  • end.

  • Число сравнений – m+n



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



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



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



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

  • 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<0) or (p[j]<>s[k]); {Выход, если сравнили все}

  •           {слово или несовпадение. }

  •           i:=i+d[s[i-1]]; {Сдвиг слова вправо }

  • until (j<0) or (i>N);



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

  • {Вывод результата поиска}

  • if j<0 then Writeln('Yes') {найден }

  • else Writeln('No'); {не найден}

  • Readln;

  • end.



страница 1


скачать

Другие похожие работы: