Лекции - Структуры и алгоритмы компьютерной обработки данных / 8.Динамические множества. Поиск в неупорядоченном массиве. Двоичный поиск в упорядоченном массиве
..docДинамические множества
В практических приложениях часто возникает задача сохранения больших массивов данных с возможностью быстрого поиска в них. Совокупность данных, изменяющихся во время работы алгоритма, будем называть динамическим множеством.
Для представления динамического множества могут использоваться различные структуры данных в зависимости от необходимого набора операций.
Элемент множества
Обычно элемент динамического множества представляет собой запись, содержащую различные поля. Одно из полей с именем key рассматривается как ключ, предназначенный для идентификации элементов, а остальные – как дополнительные данные. Поиск элемента производится по известному ключу. Удобно в динамическом множестве хранить не сами записи, а указатели на них -- это могут быть, например, индексы записей в массиве.
Type Data = record
key: <тип ключевого поля>;
other: <тип данных>
end;
Типичные операции
Часто требуется лишь добавлять элементы во множество, удалять их, а также проверять, принадлежит ли множеству элемент с данным ключом. Структура, поддерживающая эти три операции, называется словарем. Иногда необходимо выполнять и другие операции: например, искать элемент с наименьшим или наибольшим ключом.
Операции над множествами делятся на запросы (не изменяющие множество) и операции, изменяющие множество.
Функция Search(S,k) возвращает элемент (или указатель на элемент) множества S с ключом k. Если такого элемента нет, то возвращается nil или некоторое пустое значение.
Процедура Insert(S,x) добавляет в S элемент, на который указывает
указатель x.
Процедура Delete(S,x) удаляет из S элемент, на который указывает указатель x.
Функция Minimum(S) возвращает указатель на элемент множества S c минимальным ключом
Функция Maximum(S) возвращает указатель на элемент множества S c максимальным ключом.
Неупорядоченный массив
Неупорядоченный массив или линейный список - наиболее простой способ организации динамического множества. Пусть n - количество элементов в массиве.
При добавлении элемент помещается в конец массива, эта операция имеет сложность Ө(1).
Для поиска элемента с заданным ключом в худшем случае (если такой элемент
отсутствует) необходимо полностью просмотреть весь массив от первого элемента до последнего. Такой последовательный просмотр носит название линейный поиск. Cложность линейного поиска Ө(n). Отметим, что линейный поиск позволяет найти не только один, но и все элементы с заданным ключом.
При удалении элемента необходимо сдвинуть следующий элемент на место удаляемого, далее следующий на место предыдущего сдвинутого и так далее до конца массива. В худшем случае, при удалении первого элемента, сдвигу подвергнутся все оставшиеся, что обеспечивает сложность Ө(n).
Поиск минимального или максимального элемента также имеет сложность Ө(n).
Упорядоченный массив
Значительно ускоряет операцию поиска использование в качестве динамического множества массива, упорядоченного по ключевому полю.
Для поиска в упорядоченном массиве можно использовать алгоритм двоичного поиска. Сначала сравним искомый ключ с ключом
среднего элемента массива. Если они не совпадают, то возможны два случая:
-
Искомый ключ меньше ключа среднего элемента. Тогда искомый элемент следует искать в первой половине массива.
-
Искомый ключ больше ключа среднего элемента. Тогда искомый элемент следует искать во второй половине массива.
В любом случае диапазон поиска сокращается вдвое. На следующем шаге процедура повторяется. Поиск продолжается, пока элемент не будет найден, либо пока диапазон поиска не уменьшится до нуля, что означает отсутствие элемента. Очевидно, что алгоритм является рекурсивным и может быть записан в виде рекурсивной функции.
Функция двоичного поиска
Функция, кроме множества и ключа, будет иметь параметры l и r - номера элементов массива, ограничивающие диапазон поиска. Возвращаемое значение - номер найденного элемента, либо 0, если элементы с заданным ключом не найдены. Вычислительная сложность поиска будет Ө(log n). Отметим, что двоичный поиск позволяет найти один элемент с заданным ключом, но не все.
function search(const x:DataSet;l,r:longint;k:KeyType):longint;
var m:longint;
begin
if l>r then search:=0
else
begin
m:=(l+r) div 2;
if x[m].key>k then search:=search(x,l,m-1,k)
else if x[m].key<k then search:=search(x,m+1,r,k)
else search:=m
end;
end;
Добавление и удаление в упорядоченном массиве
При вставке и удалении записи необходимо сохранять массив в упорядоченном состоянии. Для этого вставка производится не в конец, а в нужное место по порядку. Поиск места вставки может быть выполнен за Ө(log n), однако при вставке все элементы после вставляемого сдвигаются, что требует Ө(n) операций в худшем случае.
Аналогично сложность удаления будет Ө(n).
Минимальный и максимальный элемент в отсортированном массиве легко получить на первом и последнем месте соответственно - сложность Ө(1).
Таким образом, использование отсортированного массива позволяет ускорить операцию поиска за счет замедления операции добавления. Поэтому если операции поиска встречаются чаще, чем операции добавления, то выгодно использовать отсортированный массив; если чаще приходится добавлять, чем искать, то проще использовать обычный массив.