Изменения

{{Определение|definition ='''Упорядоченное множество''' <tex>Set</tex> (англ. ''ordered set'') представляет собой коллекцию элементов <tex>elem</tex>, каждому из которых присваивается определенный ключ <tex>key</tex>, отвечающий за порядок этого элемента в множестве. Бинарное отношение <tex>R</tex> на упорядоченном множестве <tex>Set</tex> является [[отношение порядка|отношением порядка]].}}''Вполне упорядоченным множеством'', которое явяется важнейшим частным случаем, называется упорядоченное множество, каждое непустое подмножество которого содержит минимальный элемент.

==Операции над '''Вполне упорядоченным множеством==Над упорядоченным множеством <tex>Set</tex> заданы следующие операции:=== Insert ===Функция <tex>\mathrm {insert(Set''', которое явяется важнейшим частным случаем, elemназывается упорядоченное множество, elemKey)}</tex> добавляет заданный каждое непустое подмножество которого содержит минимальный элемент <tex>elem</tex>, имеющий ключ <tex>elemKey</tex>, в подходящее место множества <tex>Set</tex> (сохраняя свойство упорядоченности).

=== Delete =Операции над упорядоченным множеством ==Функция Над упорядоченным множеством <tex>set</tex> заданы следующие операции:* <tex>\mathrm {insert(set, elem)}</tex> {{---}} добавляет заданный элемент <tex>elem</tex> в подходящее место множества <tex>set</tex> (сохраняя свойство упорядоченности),* <tex>\mathrm {delete(Setset, keyelem)}</tex> {{---}} удаляет элемент, имеющий ключ <tex>keyelem</tex> (сохраняя свойство упорядоченности),* <tex>\mathrm {search(set, elem)}</tex> {{---}} получает на вход искомое значение элемента <tex>elem</tex> и возвращает <tex>true</tex> при наличии элемента в множестве или <tex>false</tex> в противном случае,* <tex>\mathrm {minimum(set)}</tex> {{---}} возвращает минимальный элемент множества <tex>set</tex>,* <tex>\mathrm {maximum(set)}</tex> {{---}} возвращает максимальный элемент множества <tex>set</tex>,* <tex>\mathrm {predecessor(set, elem)}</tex> {{---}} возвращает элемент, стоящий перед элементом <tex>elem</tex> множества <tex>set</tex>.* <tex>\mathrm {successor(set, elem)}</tex> {{---}} возвращает элемент, стоящий после элемента <tex>elem</tex> множества <tex>set</tex>.

=== Search =Наивная реализация на массиве ==Функция Упорядоченное множество <tex>\mathrm {search(Set, key)}s</tex>, которая получает на вход искомый ключ содержащее <tex>keyn</tex>элементов, и возвращает указатель на элемент множества <tex>Setможно реализовать с помощью [[Сортировки | отсортированного]] массива </tex> или специальное значение <tex>nullelements[0..n-1]</tex>, если такого элемента нет.

=== Minimum ===Функция <tex>\mathrm {minimum(Set)}</tex> возвращает указатель Рассмотрим реализацию на минимальный элемент множества <tex>Set</tex>примере отсортированного по возрастанию целочисленного массива.

'''funcstruct''' insert(Set, elem, elemKey)<T>: '''int''' n <font color= n + 1 Array.Resize(Set[2], n) i = n - 1 Set[1, i] green>// количество элементов множества</font color= Set[1, i - 1]green> Set[2, i] = Set[2, i - 1] '''whileT''' elemKey < Set[2, i - 1] Set[1, i - 1n] elements <font color= Set[1, i - 2] Set[2, i - 1] = Set[2, i - 2] i = i - 1 Set[1, i] = elem Set[2, i] green>// массив элементов множества типа ''T''</font color= elemKeygreen>

'''func''' deleteinsert(Set<T> s, keyT elem): i s.n = s.n + 1 <font color=green>// Увеличиваем количество элементов множества на единицу,</font color=green> <font color=green>// увеличиваем размер массива с элементами множества на единицу.</font color= 0green> s.elements[s.n - 1] = elem <font color=green>// Вставляем '''whileelem''' i в конец массива< n i /font color= 0green> '''forint''' j i = i s.n - 1 '''towhile''' n -1 Sets.elements[1, ji] = Set< s.elements[1, j + i - 1] Set[2, j] <font color= Set[2green>// Сортируем массив, j + 1] n </font color= n - 1green> Array swap(s.Resize(Setelements[2i], ns.elements[i - 1]) <font color=green>// пока ''elem'' не окажется в нужном месте.</font color=green>

'''intfunc''' searchdelete(Set<T> s, keyT elem): '''forint''' i = 0 <font color=green>// Устанавливаем счетчик на первый элемент.</font color=green> '''towhile''' i < s.n - 1 '''ifand''' Sets.elements[2, i] != elem <font color=green>// Ищем индекс элемента ''elem''.</font color= keygreen> i++ '''returnif''' Set[1i != s.n <font color=green>// Если элемент найден, i]то</font color=green> '''elsefor''' j = i '''returnto''' nulls.n - 2 <font color=green>// сдвигаем все элементы массива, большие ''elem'',</font color=green> s.elements[j] = s.elements[j + 1] <font color=green>// на одну позицию влево (elem удаляется).</font color=green> s.n = s.n - 1 <font color=green>// Уменьшаем число элементов массива на единицу.</font color=green>

'''intbool''' minimumsearch(Set<T> s, T elem): '''int''' i = binSearch(s.elements, elem) '''return''' Sets.elements[1, 0i]== elem <font color=green>// Сравниваем найденное значение с искомым...</font color=green>

'''intT''' maximumminimum(Set<T> s): '''returnT''' Setmin = s.elements[1, n - 10] '''return''' min

'''intT''' predecessormaximum(Set, elem<T> s): '''forT''' i max = 1 '''to''' s.elements[s.n - 1 '''if''' elem == Set[1, i] '''return''' Set[1, i - 1] '''else''' '''return''' nullmax

'''intT''' successor(Set<T> s, T elem): '''forif''' i elem > s.elements[s.n - 1] <font color=green>// Если элемент больше максимального,</font color= 0 green> '''return'''''tonull'' <font color=green>// возвращаем ' n - 2'null''.</font color=green> '''else if''' elem == Set< s.elements[1, i0] '''return''' Set[1min(s) <font color=green>// Если элемент меньше минимального, i + 1]возвращаем минимальный элемент.</font color=green> '''int'''i = binSearch(s.elements, elem) <font color=green>// Иначе ищем элемент, больший 'else'elem''.</font color=green> '''return''' nulls.elements[i]

В случае== Примеры == * Пустое множество <tex> \varnothing </tex>, когда упорядоченность элементов коллекции не важна* множество натуральных чисел <tex> \mathbb N </tex>, возможно использование * множество целых чисел <tex> \mathbb Z </tex>,* строки, отсортированные в [[Хеш-таблицалексикографический порядок|''хешей''лексикографическом порядке]].

==ПримерыИсточники информации == * Графы;Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5* Пустое множество <tex> \varnothing <Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 1977. — 368 с.* Н. К. Верещагин, А. Шень. Часть 1. Начала теории множеств //tex>;Лекции по математической логике и теории алгоритмов. — 2-е изд., испр. — М.: МЦНМО, 2002. — 128 с.* Множество натуральных чисел <tex> \mathbb N <[http:/tex>/ru.wikipedia.org/wiki/Упорядоченное_множество Википедия — Упорядоченное множество]

== Литература ==# Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы[[Категория: построение Дискретная математика и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5алгоритмы]]# Александров П. С. Введение в теорию множеств и общую топологию. — М.[[Категория: Наука, 1977. — 368 с.Деревья поиска]]# Н. К. Верещагин, А. Шень. Часть 1. Начала теории множеств // Лекции по математической логике и теории алгоритмов. — 2-е изд., испр. — М.[[Категория: МЦНМО, 2002. — 128 с.Структуры данных]]