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

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

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

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

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

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

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

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

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

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

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

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

Программирование и основы алгоритмизации
Тема 08. Алгоритмы и структуры данных. Поиск.
Шевченко А. В.
Прямой поиск в строке
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. Алгоритмы и структуры данных. Поиск.
Шевченко А. В.
Прямой поиск в строке (вариант с указателями)
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. Алгоритмы и структуры данных. Поиск.
Шевченко А. В.
Алгоритм Кнута, Морриса и Пратта
У
Ч
Е
Н
Ы
Й
У
Ч
И
Л
У
Ч
Е
Н
У
Ч
Е
Н
И
К
У
Ч
Е
Н
К
И
Ю
У
Ч
Е
Н
И
К
О
В
У
И
К
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
Сравнение строк слева направо и сдвиг на вычисляемое число позиций.
У
Ч
Е
Н
И
К
…
…
У
Ч
Е
Н
И
К

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. Алгоритмы и структуры данных. Поиск.
Шевченко А. В.
Алгоритм Кнута, Морриса и Пратта
Вычисление префиксной функции
Поиск

Программирование и основы алгоритмизации
Тема 08. Алгоритмы и структуры данных. Поиск.
Шевченко А. В.
Алгоритм Кнута, Морриса и Пратта. Префиксная функция
У
Ч
Е
Н
И
К
К
// Вычисление префиксной функции
tab[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;
}
0
0
0
0
0
К
0
A
B
C
A
B
К
C
0
0
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
Примеры

Программирование и основы алгоритмизации
Тема 08. Алгоритмы и структуры данных. Поиск.
Шевченко А. В.
Алгоритм Кнута, Морриса и Пратта. Поиск
// Поиск
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. Алгоритмы и структуры данных. Поиск.
Шевченко А. В.
Алгоритм Боуера – Мура - Хорспула
У
Ч
Е
Н
Ы
Й
У
Ч
И
Л
У
Ч
Е
Н
У
Ч
Е
Н
И
К
У
Ч
Е
Н
К
И
Ю
У
Ч
Е
Н
И
К
О
В
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
У
Ч
Е
Н
И
К
Сравнение строк справа налево и сдвиг на вычисляемое число позиций.

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

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

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. Алгоритмы и структуры данных. Поиск.
Шевченко А. В.
Алгоритм Боуера – Мура – Хорспула. Поиск

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

да
Блок 1
Программирование и основы алгоритмизации
Тема 08. Алгоритмы и структуры данных. Поиск.
Шевченко А. В.
Индексно-последовательный метод доступа (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 - число блоков