Методы программирования. Громов Ю.Ю - 107 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

107
Этот алгоритм выполняет поиск за (4C – 4R + 10) единиц времени.
Следовательно, выигрыш по сравнению с предыдущим алгоритмом по-
лучается в случае C ≥ 6 для успешного поиска и N ≥ 8 – для неудачного.
При переходе от алгоритма S к алгоритму Q использован важный
ускоряющий принцип – несколько проверок во внутреннем цикле свести
к одной проверке по его окончании.
Другим улучшенным алгоритмом поиска можно воспользоваться,
если ключи в таблице расположены в порядке возрастания.
Алгоритм T. (Последовательный поиск в упорядоченной таблице.)
В заданной таблице записей R
1
, R
2
, …, R
N
ключи расположены в по-
рядке возрастания: K
1
< K
2
< … < K
N
. Алгоритм предназначен для поиска
записи с заданным ключом K. Для удобства и ускорения работы алгоритма
предполагается наличие фиктивной записи R
N+1
с ключом K
N+1
= ∞ > K.
T1. [Инициализация.] Присвоить i ← 1.
T2. [Сравнение.] Если K ≤ K
i
, то перейти к шагу T4.
T3. [Продвижение.] Увеличить i на 1 и вернуться к шагу T2.
T4. [Равенство?] Если K = K
i
, то алгоритм заканчивается успешно.
В противном случае – неудачное завершение алгоритма. ■
В предположении, что все входные аргументы-ключи равновероят-
ны, алгоритм по скорости работы в случае успешного поиска аналогичен
алгоритму Q. При неудачном поиске отсутствие нужного ключа опреде-
ляется примерно вдвое быстрее.
Во всех приведённых здесь алгоритмах использовалась запись с ин-
дексами для элементов таблиц (она более удобна для описания алгорит-
мов). Однако все описанные алгоритмы применимы и к другим типам
данных, например, к таблицам со связанным представлением данных,
поскольку в них данные также расположены последовательно. Например,
алгоритм S последовательного поиска преобразуется к следующему виду.
Алгоритм S’. (Последовательный поиск в связанном списке.)
Дана таблица записей R
1
, R
2
, …, R
N
. Если P указывает на некоторую
запись, то KEY(P) – ключ, INFO(P) – соответствующая ключу информа-
ция и LINK(P) – указатель на следующую запись. Переменная FIRST ука-
зывает на первую запись, а в поле LINK последней записи содержится
пустая связь Λ. Алгоритм предназначен для поиска записи с заданным
ключом K. Предполагается, что N ≥ 1.
S’1. [Инициализация.] Присвоить P ← FIRST.
S’2. [Сравнение.] Если K = KEY(P), то успешное завершение алго-
ритма.
S’3. [Продвижение.] Присвоить P ← LINK(P).
S’4. [Конец файла?] Если P ≠ Λ, то вернуться к шагу S’2. В против-
ном случае алгоритм заканчивается неудачно. ■

Страницы