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

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

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

2. Алгоритмы поиска

Программирование и основы алгоритмизации
Алгоритмы поиска
Поиск
Поиск в строках
Поиск в массивах
Поиск в файлах
А. С. Пушкин
"ЕВГЕНИЙ ОНЕГИН"
ГЛАВА ПЕРВАЯ
Код
Наименование
Цена
44
Яблоки
35.50
55
Апельсины
29.90
12
Бананы
22.00
...
Шевченко А. В.
...
...
«Мой дядя самых честных правил,
Когда не в шутку занемог,
Он уважать себя заставил
И лучше выдумать не мог.
Его пример другим наука;
Но, боже мой, какая скука
С больным сидеть и день и ночь,
Не отходя ни шагу прочь!
Какое низкое коварство
Полуживого забавлять,
Ему подушки поправлять,
Печально подносить лекарство,
Вздыхать и думать про себя:
Когда же черт возьмет тебя!»
Тема 08. Алгоритмы и структуры данных. Поиск.
2

3. Поиск в массивах

Программирование и основы алгоритмизации
Поиск в массивах
Цена товара
с кодом 55?
Код
Наименование
Цена
44
Яблоки
35.50
55
Апельсины
29.90
12
Бананы
22.00
...
...
...
Ключ
Поиск в массивах
Линейный
поиск
Шевченко А. В.
Двоичный
поиск
Уникальный
Интерполяционный поиск
Тема 08. Алгоритмы и структуры данных. Поиск.
Неуникальный
Поиск - получение записи
по значенияю ключа
3

4. Линейный поиск в массиве

Программирование и основы алгоритмизации
Линейный поиск в массиве
01
99
44
55
12
42
94
18
06
67
98
03
95
18
Линейный поиск - единственно
возможный способ поиска в
неупорядоченном массиве
Эффективность n/2
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
4

5. Пример линейного поиска в массиве

Программирование и основы алгоритмизации
Пример линейного поиска в массиве
int LinearSearch(PROD* p, int n, short Val)
{
for(int i = 0; i < n; i++)
if(p[i].code == Val)
return(i);
return(-1);
}
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
5

6. Двоичный поиск в массиве

Программирование и основы алгоритмизации
Двоичный поиск в массиве
Как поймать льва в пустыне?
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
6

7. Двоичный поиск в массиве

Программирование и основы алгоритмизации
Двоичный поиск в массиве
01
03
06
12
18
42
44
55
67
94
95
98
99
18
06
44
18
Шевченко А. В.
Эффективность log2n
Тема 08. Алгоритмы и структуры данных. Поиск.
7

8. Пример двоичного поиска в массиве

Программирование и основы алгоритмизации
Пример двоичного поиска в массиве
int BinarySearch(PROD* p, int n, short Val)
{
int L = 0;
01
03
06
12
18
42
44
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);
L=3
55
67
94
95
98
99
18
m=4
06
R=5
m=2
44
m=6
L=0
18
R = 12
return(-1);
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
8

9. Интерполяционный поиск в массиве

Программирование и основы алгоритмизации
Интерполяционный поиск в массиве
01
03
06
12
18
42
44
55
67
94
95
98
99
120
100
80
12
60
40
20
06
0
1
2
3
4
5
6
7
8
9
10
11
12
13
int ind = L+((V-a[L])*(R-L))/(a[R]-a[L]);
18
Шевченко А. В.
Эффективность log2n
Тема 08. Алгоритмы и структуры данных. Поиск.
9

10. Пример интерполяционного поиска в массиве

Программирование и основы алгоритмизации
Пример интерполяционного поиска в массиве
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);
01
03
06
12
18
42
44
55
67
94
95
98
99
m = 4+((18-18)*(12-4))/(99-18) = 4
L=4
12
m = 3+((18-12)*(12-3))/(99-12) = 3
06
L=3
m = 0+((18-1)*(12-0))/(99-1) = 2
}
18
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
10

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

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

12. Задача поиска в строках

Программирование и основы алгоритмизации
Задача поиска в строках
N
« М о й
д я д я
с
а м ы х
ч е
с
т н ы х
п р
...
M
н а
у к а
M < N
Алфавит
А
а
Б
б
В
в
...
«
»
.
,
!
?
...
Строка (текст) - неупорядоченный
массив символов, принадлежащих к
некоторому алфавиту
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
Код символа = целое число
12

13. Прямой поиск в строке

Программирование и основы алгоритмизации
Прямой поиск в строке
У Ч Е Н И К
У Ч Е Н Ы Й
У Ч И Л
У Ч Е Н И Ю
У Ч Е Н И К О В
У Ч Е Н И
У
У
У
…
У Ч Е
У
…
У Ч Е Н И К
У
Шевченко А. В.
…
Тема 08. Алгоритмы и структуры данных. Поиск.
У Ч Е Н И К
3

14. Прямой поиск в строке

Программирование и основы алгоритмизации
Прямой поиск в строке
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);
}
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
14

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

Программирование и основы алгоритмизации
Алгоритм Кнута, Морриса и Пратта
У Ч Е Н И К
У Ч Е Н Ы Й
У Ч И Л
У Ч Е Н И Ю
У Ч Е Н И К О В
A B C A B C A B D
У Ч Е Н И К
A B C A B D
У Ч Е Н И К
d = 5-2
A B C A B D
У Ч Е Н И К
A B C D E A B C D E F
У Ч Е Н И К
У Ч Е Н И К
…
A B C D E F
d = 5-0
A B C D E F
У Ч Е Н И К
У Ч Е Н И К
Сравнение строк слева направо и
сдвиг на вычисляемое число позиций.
У Ч Е Н И К
У Ч Е Н И К
У Ч Е Н И К
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
15

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

Программирование и основы алгоритмизации
Алгоритм Боуера и Мура
У Ч Е Н И К
У Ч Е Н Ы Й
У Ч И Л
У Ч Е Н И Ю
У Ч Е Н И К О В
У Ч Е Н И К
У Ч Е Н И К
У
d=5
Ч
d=4
Е
d=3
Н
d=2
И
d=1
К
d=0
...
d=6
Шевченко А. В.
У Ч Е Н И К
У Ч Е Н И К
У Ч Е Н И К
Сравнение строк справа налево и
сдвиг на вычисляемое число позиций.
Тема 08. Алгоритмы и структуры данных. Поиск.
16

17. Поиск в файлах базы данных

Программирование и основы алгоритмизации
Поиск в файлах базы данных
Цена товара
с кодом 55?
Код
Наименование
Цена
44
Яблоки
35.50
55
Апельсины
29.90
12
Бананы
22.00
...
...
...
Блок 1
Блок 2
Блок 3
...
Файлы базы данных размещаются на
блочных устройствах (чтение и запись
производится
блоками
фиксированной
длины). Чтение блока - медленная операция.
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
17

18. Индексно-последовательный метод доступа (ISAM)

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

19. Доступ по вычисляемому ключу (HASH)

Программирование и основы алгоритмизации
Доступ по вычисляемому ключу (HASH)
Блок 0
44
64
Блок 4
Яблоки
Черешня
55
75
Блок 5
Апельсины
Мандарины
56
Блок 6
Груши
67
Блок 7
Персики
55
01
Блок 1
Ананасы
12
62
Блок 2
Бананы
Вишня
03
83
Блок 3
Абрикосы
Нектарины
MOD(x, 10)
HASH-функция
18
68
78
98
99
Блок 8
Сливы
Манго
Малина
Гранаты
Блок 9
Айва
Хэш-функция непосредственно преобразует значение
ключа поиска в номер блока.
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
19