Абстрактные типы данных. Методы представления множеств

Begin

Type

End

Begin

Begin

Алгоритмы поиска элементов во множестве.

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

Пусть, -некоторое универсальное множество с заданным на нем линейным порядком т.е. отношением «<», которое:

1. Антисимметрично: из и

2. Транзитивно: из и

3. Связано: или или.

1. Последовательный поиск

Линейный, последовательный поиск — алгоритм нахождения заданного элемента z поочередным сравнением с элементами таблицы в том порядке, в котором они расположены.

Данный алгоритм является простейшим алгоритмом поиска, не накладывает никаких ограничений на таблицу и имеет простейшую реализацию.

В худшем случае потребуется просмотр всей таблицы для отыскания элемента z или установления, что z в таблице отсутствует. Таким образом, эффективность линейного поиска равна O(n), где n=|T|. Это является основным недостатком алгоритма. В связи с малой эффективностью по сравнению с другими алгоритмами поиска линейный поиск обычно используют только если таблица содержит мало элементов. Тем не менее, преимуществом линейного поиска является то, что он не требует дополнительной памяти или обработки/анализа таблицы, так что может работать в потоковом режиме при непосредственном получении данных из любого источника.

Далее приведена процедура, реализующая линейный поиск элемента z в таблице (одномерном массиве) Т. Переменные L и R содержат, соответственно, левую и правую границы отрезка массива, где ищется нужный элемент. Исследования начинаются с первого элемента отрезка. Если этот элемент не совпадает с искомым z, осуществляется переход к следующему элементу. Таким образом, в результате каждой проверки область поиска уменьшается на один элемент.

(1) T[R+1]:=z;

(2) x:= L;

(3) while T[x] <> z do x:= x + 1;

(4) if x < R+1 then return x; // элемент найден в позиции x

(5) else return -1; // элемент не найден

end;

Использован цикл while, т.к. в цикле со счетчиком по x при каждом прохождении тела цикла требуется проверка условия окончания цикла x=R.

Для гарантированного выхода из цикла на R+1 – ом шаге в таблицу добавлен элемент T[R+1]:=z.

2. Бинарный поиск

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

Поиск элемента в отрезке:

- Новый индекс для «средней точки» устанавливается в середине отрезка (это дает самый эффективный алгоритм).

- Если, то поиск продолжается на отрезке [b, c-1];

- Если, то далее ищем в отрезке [c+1, e];

- Если, то искомый элемент найден и поиск завершен.

(1) b:=1;

(2) e:=n;

(3) while b<=e do begin

(4) c:=(b+e) div 2;

(5) if T[c]>z then e:=c-1;

(6) else if T[c]<z then b:=c+1;

(7) else return c;

end;

(8) return «не найдено»;

Рассмотрим сложность алгоритма бинарного поиска.

Тело цикла (4)-(7) требует времени О(1).

Оценим количество итераций цикла (3)-(7), предполагая, что длина отрезка является степенью двойки:. (В остальных случаях сложность алгоритма можно оценить исходя из Замечания 1 § 6)

-После первой итерации длина рассматриваемого отрезка равна.

-После второй итерации -.

……………………………………

-После k-й итерации -. Это означает, что b=e. Далее, в строке (4) получим с=b=e, и если искомый элемент всё же не будет найден (строка (7)), то операции в строке (5) или (6) приведут к условию b>e, и цикл закончит работу.

Таким образом, количество итераций цикла (3)-(7) равно.

Время выполнения цикла (3)-(7) равно

Таким образом сложность алгоритма равна.

3. Деревья бинарного поиска

На практике в большинстве таблиц встречаются элементы, к которым обращаются чаще, чем к другим. Такие элементы будут быстрее обнаружены, если находятся в «средних точках» на ранних этапах работы бинарного поиска. Обеспечить такое их расположение невозможно для последовательно распределенных таблиц, элементы которых упорядочены. Для этого введем особую структуру данных.

Дерево бинарного поиска над множеством T={x₁, …, x_n} – бинарное дерево, узлы которого содержат элементы множества Т так, что при симметричном обходе дерева порядок узлов совпадает с порядком их во множестве Т.

Пример 1: Два дерева двоичного поиска над таблицей Т= {5, 7, 10, 12, 14, 15, 18}

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

Для поиска элемента х в дереве бинарного поиска, х сравнивается с элементом, стоящим в корне.

1. Если корня нет(дерево пусто), то х не найден.

2. Если х совпадает с элементом в корне, то х найден.

3. Если х меньше элемента в корне, то продолжить поиск в левом поддереве.

4. Если х больше элемента в корне, продолжить поиск в правом поддереве.

Рассмотрим далее функцию MEMBER(x, A), которая осуществляет поиск элемента х в бинарном дереве А. Здесь все элементы множества имеют тип elementtype(это может быть встроенный в язык программирования или определенный пользователем).

Узлы дерева имеют тип nodetype, т.е. запись, содержащее поле element для элементов множества и два поля leftchild и rigthchild для указателей на левого и правого сына.

nodetype= record

element:elementtype;

leftchild, rigthchild:^nodetype;

end;

Для дерева определим тип SET-указатель на корень дерева двоичного поиска:

type SET:^nodetype;

function MEMBER (х: elementtype; A: SET): boolean;

{ возвращает true, если элемент х принадлежит множеству А, false — в противном случае }

if A = nil then

return (false) { x не может принадлежать Ø }

else if x = A^.element then

return (true)

else if x < A^.element then

return (MEMBER(x, A^.leftchild))

else { x > A^.element }

return (MEMBER(x, A^.rightchild))

end; { MEMBER }

Для работы с бинарными деревьями поиска также требуются процедуры INSERT(x, A) и DELETE(x, A), которые добавляют и удаляют элемент из бинарного дерева соответственно.

Абстрактный тип данных (АТД) можно определить как математическую модель объекта с совокупностью операторов, определенных над объектом в рамках этой модели.

Простым примером абстрактного типа данных могут служить множества целых чисел с операторами объединения, пересечения и разности множеств.

Реализация АТД подразумевает 1) определение с помощью выбранного языка программирования переменных, представляющих объекты этого АТД; 2) написание процедуры для каждого оператора, выполняемого над объектами АТД.

Реализация АТД зависит от структуры данных, представляющих АТД. Каждая структура данных строится на основе базовых типов данных применяемого языка программирования, используя доступные в этом языке средства структурирования данных. Например, структуры массивов и записей — два важных средства структурирования данных, возможных в языке Pascal.

Часто в рамках одной математической модели определяются и реализуются различные АТД. Причина в том, что над объектами этих АТД необходимо выполнять различные действия, т.е. определять операторы разных видов.

Особенности реализации АТД «Множество».

Рассмотрим операторы, выполняемые над множествами, которые часто включаются в реализацию различных абстрактных типов данных. Некоторые из этих операторов имеют общепринятые (на сегодняшний день) названия и эффективные методы их реализации.

1. — оператор объединения. Имеет "входными" аргументами множества и, а в качестве результата — "выходное" множество, равное.

2. ‑ оператор пересечения. Имеет "входными" аргументами множества и, а в качестве результата — "выходное" множество, равное.

3. ‑ оператор вычитания. Имеет "входными" аргументами множества и, а в качестве результата — "выходное" множество, равное.

4. ‑ оператор слияния. Используется очень редко. Имеет "входными" аргументами множества и, а в качестве результата — "выходное" множество, равное, но результат будет не определен, если. Это единственное отличие оператора от оператора. Функциональности оператора, при написании программы вполне достаточно.

5. – оператор проверки принадлежности элемента множеству. Имеет входящие аргументы множество и объект того же типа, что и элементы множества, и возвращает булево значение (истина), если, и значение (ложь), если.

6. ‑ оператор присваивает множеству значение пустого множества.

7. – оператор вставки элемента в множество. Имеет аргументами объект, который имеет тот же тип данных, что и элементы множества. Данный оператор делает элементом множества. Другими словами, новым значением множества будет множество. В случае, когда элемент уже присутствует в множестве, это множество не изменяется в результате выполнения данной процедуры.

8. ‑ оператор удаления. Удаляет элемент из множества, т.е. заменяет множество множеством. Если элемента нет в множестве, то это множество не изменяется.

9. ‑ оператор присваивания. Присваивает множеству в качестве значения множество. На практике, обычно, происходит копирование множества во множество. Такой алгоритм связан с особенностями реализации языков программирования.

10. ‑ оператор поиска минимального элемента. Возвращает наименьший элемент множества. Для применения этой функции необходимо, чтобы элементы множества А были линейно упорядочены.

11. ‑ оператор поиска максимального элемента. Возвращает наибольший элемент множества. Реализация аналогично оператору.

12. ‑ оператор равенства множеств. Возвращает значение тогда и только тогда, когда множества и состоят из одних и тех же элементов, в противном случае возвращает значение.

Далее будет предполагаться, что все рассматриваемые множества упорядочены по возрастанию. На данном условии будут строиться все алгоритмы работы операторов.

1. Реализация АТД «множество» посредством двоичных векторов

Наилучшая конкретная реализация абстрактного типа данных (Множество) выбирается исходя из набора выполняемых операторов и размера множества. Если все рассматриваемые множества будут подмножествами небольшого универсального множества целых чисел для некоторого фиксированного, тогда можно применить реализацию посредством двоичного (булева) вектора.

В этой реализации множество представляется двоичным вектором, в котором -й бит равен единице или, если является элементом множества. Главное преимущество этой реализации состоит в том, что здесь операторы, и можно выполнить за фиксированное время (независимо от размера множества) путем прямой адресации к соответствующему биту. Но операторы, и выполняются за время, пропорциональное размеру универсального множества.

Если универсальное множество так мало, что двоичный вектор занимает не более одного машинного слова, то операторы, и можно выполнить с помощью простых логических операций (конъюнкции и дизъюнкции), выполняемых над двоичными векторами.

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

2. Реализация АТД «множество» с помощью массивов

Главным достоинством массива по сравнению с бинарным вектором является отсутствие ограничения на тип элементов, хранимых массивом. Это свойство позволяет хранить в массиве как простые типы данных, строки и вещественные числа, так и структуры данных, которые представляют более сложную реализацию. Так же стоит отметить скорость доступа к -му элементу, где - индекс элемента в массиве.

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

3. Реализация АТД «множество» посредством связанных списков

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

Представление множества связанным списком ячеек определяется следующим образом:

type TElementType = integer;

Дата добавления: 2014-01-04