Поиск. 1. Линейный поиск. 2. Двоичный поиск. 3. Индексно-последовательный поиск. 4. Поиск в таблице. 5. Алгоритм Кнута, Мориса и Пратта. 6. Алгоритм Боуэра и Мура. 7. Поиск прямой строки. Эффективность поиска.

Поиск

1. Линейный поиск

2. Двоичный поиск

3. Индексно-последовательный поиск

4. Поиск в таблице

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

6. Алгоритм Боуэра и Мура

7. Поиск прямой строки

1. Признак, по которому элемент структуры отличается от других данных, называется ключом. Если в таблице данных существует только одно данное с ключом, такой ключ является уникальным и называется первичным. Вторичный ключ может повторяться.

Внешний ключ – ключ, который выделен из таблицы данных и организован в свой файл.

Внутренний ключ – ключ, который находится в записи.

Поиск – основная операция при обработке данных. Ее цель: по заданному аргументу среди данных массива найти те данные, которые соответствуют данному аргументу. Результат: нахождение элемента или его отсутствие в таблице. Если элемент отсутствует:

· Идентификация того, что данного нет

· Вставка данного в таблицу

Обозначения: k-массив ключей, i-информационное поле, r-массив данных.

Линейный поиск – применяется в том случае, если неизвестна организация данных или данные неупорядочены. Производится просмотр по всей таблице данных, начиная с младшего адреса в оперативной памяти к старшим. Поиск производится по ключу. Существует 2 вида поиска:

· В неупорядоченном массиве

· В упорядоченном массиве

Пример (С++):

Int sequential_search(char *items, int count, char key)

{

Register int t;

For(t=0; t< count; ++t)

If(key == items[t]) return t;

Return -1; /*ключ не найден*/

}

Items – указатель на массив, содержащий информацию.

Эффективность поиска.

M_min=1, M_max=n

M_ср=(n+1)/2

n=n+1

Цель поиска:

· Найденную запись считать

· При отсутствии записи произвести

· Найденную запись удалить

2. При отсортированных данных. Применяется метод «разделяй и властвуй». Если его ключ больше ключа требуемого элемента, то делается проверка для среднего элемента из первой половины.

Пример: 123456789. Необходимо найти элемент с ключом 4.

12345. 45.

Количество сравнений: log₂n

В лучшем случае количество сравнений: 1.

Пример:

int dub_search(char a[], int count, char key)

{

Int low, high, mid;

Low=0;

High=count-1;

If(key< a[mid]) high =mid-1;

Else if(key> a[mid])low=mid+1;

Else return mid;

Break;

} While(low< =high)/2;

Return -1;

}

3. Организуется 2 таблицы:

· Со своими ключами

· Состоит из ключей

Индексный файл и файл данных организованны последовательно. Индексный файл содержит только максимальное значение первичных ключей.

В зависимости от значений добавляемых записей может потребоваться изменение элементов индекса.

Если нет места в блоке:

· Запись запоминается в отдельной области, области переполнения, и блок в этой области связывается в цепочку с блоком, которому логически принадлежит запись.

· При невозможности введения записи в блок он делится пополам.