Программная инженерия Нижний Новгород 017 Лабораторный

2.2. Алгоритмы 
2.2.1. Просматриваемые таблицы 
Простейшим способом отыскания нужного элемента является метод полного просмотра 
(сканирования), когда искомый ключ сравнивается по очереди со всеми ключами таблицы, 
начиная с первого, вплоть до отыскания совпадающего элемента или до исчерпания записей. 
Если ключи в таблице расположены в произвольном порядке (неупорядоченная таблица), этот 
способ является единственно возможным. 
Операция вставки в неупорядоченную таблицу может быть выполнена путём добавления 
новой записи в конец таблицы с корректировкой номера последней занятой строки. Операция 
удаления строки может быть реализована при помощи переписывания последней записи 
таблицы на место удаляемой и соответствующей корректировки номера последней строки. 
Среднее количество просматриваемых записей таблицы при поиске записи по ключу при 
предположении равной вероятности использования ключей определяется следующим 
соотношением
N
p
N
p
T
ср
)
1
(
2



,
где
p – вероятность того, что искомая запись имеется в таблице; 
N – количество записей в таблице. 
2.2.2. Упорядоченные таблицы 
При большом количестве записей в таблице (N>>1) затраты на выполнение полного 
просмотра становятся значительными. Эффективность процедуры поиска можно повысить 
при размещении записей в таблице в порядке возрастания (или убывания) ключей 
(упорядоченная, или сортированная таблица). Упорядоченность таблиц может быть 
организована только при возможности сравнения ключей (на множестве ключей задано 
отношение линейного порядка). Для поиска нужной записи в таких таблицах может быть 

---

 
94 
использован быстрый метод бинарного (двоичного) поиска. Вместе с тем, в упорядоченных 
таблицах усложняется реализация операций вставки и удаления записей, при выполнении 
которых для сохранения упорядоченности становится необходимой перепаковка записей 
таблицы. 
Среднее количество просматриваемых записей таблицы при использовании бинарного 
поиска определяется как 
N
T
ср
2
log

.