Структуры и алгоритмы обработки данных_Лекция_1_7_( Алгоритмы поиска в массивах (таблицах) (1)

1.

Алгоритмы поиска в
массивах и таблицах

2.

Классификация методов поиска
• Последовательный поиск
• Поиск посредством сравнения ключей
• Поиск со вставкой
Некоторые алгоритмы при неудачном поиске предусматривают вставку новой
записи, содержащей ключ К в таблицу, такие алгоритмы называют алгоритмами
«поиск со вставкой».
• Цифровой поиск
• Оптимизированный поиск с применением структур данных

3.

Задача алгоритмов поиска
Дано множество из N элементов.
Элементы представлены записями R1 R2 R3……… RN , которые содержат специальное
поле – ключ (К).
Задача сводится к отысканию записи, имеющей К своим ключом.
Ключи в записях уникальны, т.е. ключ однозначно определяет запись.
Совокупность всех записей называют таблицей или файлом.

4.

Пример таблицы
struct student{
char num[8]; //номер зачетки
char fio[50];
char data[10];
char group[10];
};
student group[30];
// таблица
num
fio
date
group
num
fio
date
group
num
fio
date
123
АА
1.12
IKBO1
100
BB 1.03
IKBO2
…… 124
CC
5.05 IKBO1
Запись 1
Запись 2
Запись 3
group

5.

Два случая завершения поиска
• удачный/успешный – запись с ключом К найдена (позволяет определить
положение записи, содержащей аргумент К);
• неудачный/безуспешный – показывает, что элемент с аргументом К не может быть
найден ни в одной из записей.

6.

Алгоритм последовательного поиска
Поиск записи с ключом К в таблице (массиве или файле) записей.
Особенности
При последовательном поиске допустим один из двух исходов:
K= Ki Запись с ключом К найдена в позиции i
K≠Ki Нет записи с ключом К
Результат:
при K= Ki –запись с ключом К найдена (успешно), вернуть запись или ее
индекс(номер в файле(
при K≠Ki значение, сообщающее о неуспешном поиске, например -1.

7.

Алгоритм последовательного поиска
Задача. Имеется таблица записей R1 R2 R3……… RN , имеющими соответственно ключи К1
К2 К3……… КN . Требуется найти запись с ключом К. Предполагается, что N≥1.
Шаг 1. Начальная установка: K и i 1.
Шаг 2. Сравнение ключей: K= Кi вернуть i // удачное завершение алгоритма
Шаг 3. Продвижение: i=i+1
Шаг 4. Если i≤ N перейти к шаг 2
Иначе алгоритм завершается неудачно
Эффективность алгоритма оценивается количеством выполненных операций
сравнения

8.

Критическая операция алгоритмов поиска
Критерием оценки сложности алгоритмов поиска является количество
операций сравнения

9.

Анализ алгоритма
Время работы алгоритма зависит от С – количество сравнений и S – исхода поиска: S=1 запись
найдена; S=0 запись не найдена;
Начальная установка: K
i=1.
2
While(i<=N)do
C
if (К = Кi )
return i;
C
C-S
else i=i+1;
endif
C-S
return -1;
od
1
Алгоритм требует 4С – 2S + 3 единиц времени.
При удачном исходе, т.е. нашли К = Кi , то C=i, а S=1, значит полное время равно (4i+2) t
При неудачном исходе C=N, а S=0, значит полное время равно (4N+3) t.
Если все ключи поступают на вход с равной вероятностью, то среднее значение С при удачном поиске
1+2+3+⋯…..+