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

1.

Программирование и основы алгоритмизации
Тема 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. Алгоритмы и структуры данных. Поиск.
У Ч Е Н И К
13

14.

Программирование и основы алгоритмизации
Прямой поиск в строке
int StringSearch(char text[], char val[])
{
int n = strlen(text);
// Длина строки
int m = strlen(val);
// Длина образца
for(int i = 0; i <= n-m; i++)
{
bool found = true;
for(int j = 0; j < m; j++)
if(text[i+j] != val[j])
{
found = false; break;
}
}
if(found) return(i);
return(-1);
}
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
14

15.

Программирование и основы алгоритмизации
Прямой поиск в строке (вариант с указателями)
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(*v != *s || !*s)
{
found = false;
break;
}
if(found) return(p);
}
return(NULL);
}
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
15

16.

Программирование и основы алгоритмизации
Алгоритм Кнута, Морриса и Пратта
У Ч Е Н И К
У Ч Е Н Ы Й
У Ч И Л
У Ч Е Н И Ю
У Ч Е Н И К О В
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. Алгоритмы и структуры данных. Поиск.
У Ч Е Н И К
У Ч Е Н И К
16

17.

Программирование и основы алгоритмизации
Алгоритм Кнута, Морриса и Пратта
char* KMP(char* text, char* val)
{
char* sea = NULL;
int n = strlen(text);
// Длина строки
int m = strlen(val);
// Длина образца
int* tab = new int[m];
// Массив префиксов
Вычисление префиксной функции
Поиск
delete [] tab;
return(sea);
}
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
17

18.

Программирование и основы алгоритмизации
Алгоритм Кнута, Морриса и Пратта. Префиксная функция
Примеры
// Вычисление префиксной функции
A B C A B К
C
tab[0] = 0;
0
for(int i = 1, j = 0; i < m; i++)
{
while(j > 0 && val[j] != val[i])
j = tab[j-1];
if(val[j] == val[i])
j++;
tab[i] = j;
}
Тема 08. Алгоритмы и структуры данных. Поиск.
0
1
2 К
3
A A C A A К
C
0
1
0
1
2 К
3
A A A A A К
A
0
1
2
3
4 К
5
У Ч Е Н И К
0
Шевченко А. В.
0
0
0
0
0 К
0
18

19.

Программирование и основы алгоритмизации
Алгоритм Кнута, Морриса и Пратта. Поиск
Примеры
// Поиск
for(int i = 0, j = 0; i < n; i++)
{
while(j > 0 && val[j] != text[i])
j = tab[j-1];
if(val[j] == text[i])
j++;
if(j == m)
{
sea = text+i-j+1;
break;
У Ч Е Н И К
0
0
0
0
0 К
0
У Ч Е Н Ы Й
У Ч Е Н И К
У Ч Е
d = 4-0
У Ч И Л
У
У Ч Е Н И К
}
У Ч Е Н
}
d = 2-0
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
19

20.

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

21.

Программирование и основы алгоритмизации
Алгоритм Боуера – Мура - Хорспула
char* BMH(char* text, char* val)
{
int n = strlen(text);
// Длина строки
int m = strlen(val);
// Длина образца
int tab[256];
// Массив сдвигов
Заполнение массива сдвигов
Поиск
return(NULL);
}
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
21

22.

Программирование и основы алгоритмизации
Алгоритм Боуера – Мура – Хорспула. Заполнение массива
Примеры
A B C A B К
C
// Заполнение массива сдвигов
…
A=2
for(int i = 1; i < 256; i++)
B=1
С=3
…
tab[i] = m;
for(int j = 0; j < m-1; j++)
tab[val[j]] = m-j-1;
У Ч Е Н И К
5
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
4
3
2
1 К
6
22

23.

Программирование и основы алгоритмизации
Алгоритм Боуера – Мура – Хорспула. Поиск
for(int i = 0; i <= n-m;)
{
bool found = true;
for(int j = m-1; j >= 0; j--)
if(text[i+j] != val[j])
{
i += tab[text[i+m-1]];
found = false;
break;
}
if(found) return(text+i);
}
Шевченко А. В.
Тема 08. Алгоритмы и структуры данных. Поиск.
23

24.

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

25.

Программирование и основы алгоритмизации
Индексно-последовательный метод доступа (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
25

26.

Программирование и основы алгоритмизации
Доступ по вычисляемому ключу (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. Алгоритмы и структуры данных. Поиск.
26