Тема 8. Алгоритмы и структуры данных. Поиск

8. Алгоритмы и структуры данных. Поиск.
Шевченко А. В.

А. В.
Алгоритмы поиска
Поиск в массивах
Поиск
Поиск в строках
Поиск в файлах
А. С.

Пушкин
"ЕВГЕНИЙ ОНЕГИН"
ГЛАВА ПЕРВАЯ
«Мой дядя самых честных правил, Когда не в шутку занемог, Он уважать себя заставил И лучше выдумать не мог. Его пример другим наука; Но, боже мой, какая скука С больным сидеть и день и ночь, Не отходя ни шагу прочь! Какое низкое коварство Полуживого забавлять, Ему подушки поправлять, Печально подносить лекарство, Вздыхать и думать про себя: Когда же черт возьмет тебя!»

А. В.
Поиск в массивах
Поиск в массивах
Линейный поиск
Двоичный поиск
Интерполяци-онный поиск
Код
Наименование

Цена

44
Яблоки
35.50

55
Апельсины
29.90

12
Бананы
22.00

...
...
...

Ключ
Уникальный
Неуникальный
Поиск -

получение записи по значенияю ключа

Цена товара
с кодом 55?

А. В.
Линейный поиск в массиве
18
Эффективность n/2
Линейный поиск - единственно возможный

способ поиска в неупорядоченном массиве

01

99

44

55

12

42

94

18

06

67

98

03

95

А. В.
Пример линейного поиска в массиве
int LinearSearch(PROD* p, int n,

short Val)
{
for(int i = 0; i < n; i++)
if(p[i].code == Val)
return(i);

return(-1);
}

и структуры данных. Поиск.
6
Шевченко А. В.
Двоичный поиск в массиве

А. В.
Двоичный поиск в массиве
18
Эффективность log2n
01
03
06
12
18
42
44
55
67
94
95
98
99
44
06
18

А. В.
Пример двоичного поиска в массиве
int BinarySearch(PROD* p, int n,

short Val)
{
int L = 0;
int R = n-1;

while(L <= R)
{
int m = (L+R)/2;

if(p[m].code < Val)
L = m+1;
else
if(p[m].code > Val)
R = m-1;
else
return(m);
}

return(-1);
}

А. В.
Интерполяционный поиск в массиве
18
Эффективность log2n
01
03
06
12
18
42
44
55
67
94
95
98
99
06
12
int ind = L+((V-a[L])*(R-L))/(a[R]-a[L]);

А. В.
Пример интерполяционного поиска в массиве
int InterpolationSearch(PROD* p, int n,

short Val)
{
int L = 0;
int R = n-1;

while(L <= R)
{
int m = L+((Val-p[L].code)*(R-L))/(p[R].code-p[L].code);

if(p[m].code < Val)
L = m+1;
else
if(p[m].code > Val)
R = m-1;
else
return(m);
}

return(-1);
}

m = 0+((18-1)*(12-0))/(99-1) = 2

L = 3

m = 3+((18-12)*(12-3))/(99-12) = 3

L = 4

m = 4+((18-18)*(12-4))/(99-18) = 4

А. В.
Поиск в строках
А. С. Пушкин
"ЕВГЕНИЙ ОНЕГИН"
ГЛАВА ПЕРВАЯ
«Мой дядя самых

честных правил, Когда не в шутку занемог, Он уважать себя заставил И лучше выдумать не мог. Его пример другим наука; Но, боже мой, какая скука С больным сидеть и день и ночь, Не отходя ни шагу прочь! Какое низкое коварство Полуживого забавлять, Ему подушки поправлять, Печально подносить лекарство, Вздыхать и думать про себя: Когда же черт возьмет тебя!»

наука

Поиск в строках

Прямой поиск

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

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

А. В.
Задача поиска в строках
Алфавит
«
М
о
й

д
я
д
я

с
а
м
ы
х

ч
е
с
т
н
ы
х
п
р
...
N
«
А
а
Б
б
В
в
...
»
.
,
!
?
...
Строка (текст) -

неупорядоченный массив символов, принадлежащих к некоторому алфавиту

Код символа = целое число

н

а

у

к

а

M

M < N

А. В.
Прямой поиск в строке
У
Ч
Е
Н
Ы
Й

У
Ч
И
Л

У
Ч
Е
Н
У
Ч
Е
Н
И
К
У
Ч
Е
Н
К
И
Ю

У
Ч
Е
Н
И
К
О
В
У
У
У
У
Ч
У
Ч
Е
Н
И
К
…
У
…
У
Ч
Е
Н
И
У
…
И
Е
К

А. В.
Прямой поиск в строке
char* StringSearch(char* Text, char* Val)
{

for(char* p = Text; *p; p++)
{
bool found = true;

for(char* v = Val, *s = p; *v; v++, s++)
if(!*s || *v != *s)
{
found = false;
break;
}

if(found) return(p);
}

return(NULL);
}

А. В.
Алгоритм Кнута, Морриса и Пратта
У
Ч
Е
Н
Ы
Й

У
Ч
И
Л

У
Ч
Е
Н
У
Ч
Е
Н
И
К
У
Ч
Е
Н
К
И
Ю

У
Ч
Е
Н
И
К
О
В
У
И
К
…
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
Сравнение строк

слева направо и сдвиг на вычисляемое число позиций.

А. В.
Алгоритм Боуера и Мура
У
Ч
Е
Н
Ы
Й

У
Ч
И
Л

У
Ч
Е
Н
У
Ч
Е
Н
И
К
У
Ч
Е
Н
К
И
Ю

У
Ч
Е
Н
И
К
О
В
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
Сравнение строк справа

налево и сдвиг на вычисляемое число позиций.

А. В.
Поиск в файлах базы данных
Файлы базы данных размещаются на

блочных устройствах (чтение и запись производится блоками фиксированной длины). Чтение блока - медленная операция.

Код

Наименование

Цена

44

Яблоки

35.50

55

Апельсины

29.90

12

Бананы

22.00

...

...

...

Цена товара
с кодом 55?

Блок 1

Блок 2

Блок 3

...

Поиск.
18
Шевченко А. В.
Индексно-последовательный метод доступа (ISAM)
01
Ананасы
89.00
03
Абрикосы
50.00
12
Бананы
22.00
18
Сливы
34.50
Блок 2
44
Яблоки
35.50
55
Апельсины
29.90
56
Груши
65.50
62
Вишня
99.90
Блок 3
64
Черешня
95.00
67
Персики
50.00
68
Манго
67.00
75
Мандарины
39.50
Блок 4
78
Малина
75.00
83
Нектарины
42.00
98
Гранаты
44.00
99
Айва
38.50
>= 64
>=

44

>= 78

да

нет

нет

да

нет

55

Число ступеней индекса = log2n,
где n - число блоков

Поиск.
19
Шевченко А. В.
Доступ по вычисляемому ключу (HASH)
Блок 1
55
Блок 4
01
Ананасы
Блок 8
18
Сливы
Блок

2

12

Бананы

62

Вишня

Блок 3

03

Абрикосы

83

Нектарины

44

Яблоки

64

Черешня

Блок 5

55

Апельсины

75

Мандарины

Блок 6

56

Груши

Блок 7

67

Персики

68

Манго

78

Малина

98

Гранаты

Блок 9

99

Айва

HASH-функция

MOD(x, 10)

Хэш-функция непосредственно преобразует значение ключа поиска в номер блока.