Изменения

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

'''Вполне упорядоченным множеством''', которое явяется важнейшим частным случаем, называется упорядоченное множество, каждое непустое подмножество которого содержит минимальный элемент. ==Операции над упорядоченным множеством==

=== Insert ===Функция * <tex>\mathrm {insert(Set, elem, elemKey)}</tex> {{---}} добавляет заданный элемент <tex>elem</tex>, имеющий ключ <tex>elemKey</tex>, в подходящее место множества <tex>Set</tex> (сохраняя свойство упорядоченности),* <tex>\mathrm {delete(Set, key)}</tex> {{---}} удаляет элемент, имеющий ключ <tex>key</tex> (сохраняя свойство упорядоченности),* <tex>\mathrm {search(Set, key)}</tex> {{---}} получает на вход искомый ключ <tex>key</tex> и возвращает указатель на элемент множества <tex>Set</tex> или специальное значение <tex>null</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>.

=== Delete =Наивная реализация на массиве ==Функция Упорядоченное множество, содержащее <tex>n</tex>\mathrm {delete(Setэлементов, key)}можно реализовать с помощью массива <tex>elements[0..n-1]</tex>. Оно будет обладать следующими полями:* <tex>elem</tex> удаляет {{---}} элементмножества, имеющий ключ * <tex>key</tex> (сохраняя свойство упорядоченности){{---}} ключ элемента.

=== Search ===Функция <texcode>\mathrm {search(Set, key)}</tex>, которая получает на вход искомый ключ <tex>key</tex>, и возвращает указатель на элемент множества <tex>Set</tex> или специальное значение <tex>null</tex>, если такого элемента нет. === Minimum ===Функция <tex>\mathrm {minimum( '''struct''' Set)}</tex> возвращает указатель на минимальный элемент множества <tex>Set</texT>.: === Maximum ===Функция <tex>\mathrm {maximum(Set)}</tex> возвращает указатель на максимальный элемент множества <tex>Set '''int''' n </tex>. font color=== Predecessor ===Функция <texgreen>\mathrm {predecessor(Set, elem)}</tex> возвращает указатель на элемент, стоящий перед элементом <tex>elem</tex> количество элементов множества <tex>Set</texfont color=green>.  '''T'''[] elements <font color=== Successor ===Функция <texgreen>\mathrm {successor(Set, elem)}</tex> возвращает указатель на элемент, стоящий после элемента <tex>elem</tex> массив элементов множества <tex>Setтипа T</tex>. font color==Наивная реализация на массиве==Пусть <tex>Set</tex> — упорядоченное множество (массив), состоящее из <tex>n</texgreen> элементов. В<tex>Set[1, i]</tex> хранятся элементы множества, в <tex>Set[2, i]</texcode> — их ключи.

Функция <tex>\mathrm {=== '''insert(Set, elem, elemKey)}</tex>:''' ===

'''func''' insert(Set, elem, elemKeykey): Set.n = Set.n + 1 Array.Resize(Set[2], n) i <font color= n - 1 Set[1, i] green>//Увеличиваем размер массива на единицу</font color= Set[1, i - 1]green> Set.elements[2, ikey] = Set[2, i - 1] '''while''' elemKey elem < Set[2, i - 1] Set[1, i - 1] 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>//и добавляем элемент с ключом key.</font color= elemKeygreen>

Функция <tex>\mathrm {=== '''delete(Set, key)}</tex>:''' ===

i = 0 '''whileif''' key < Set[2,i] .n - 1 < font color=green>//Если key && i {{---}} не последний элемент,< n/font color=green> i = i + 1 '''iffor''' i < n = key '''ifto''' i < Set.n - 1 Set[12 <font color=green>//то сдвигаем все элементы множества, начиная с key, j] влево.</font color= Set[1, j + 1]green> Set.elements[2, ji] = Set.elements[2, j i + 1] Set.n = Set.n - 1 Array.Resize <font color=green>//Затем удаляем последний элемент (Set[2], nуменьшаем количество элементов множества на единицу).</font color=green>

Функция <tex>\mathrm {=== '''search(Set, key)}</tex>:''' ===

'''intT''' search(Set, key): '''for''' i = 0 '''to''' Set.n - 1 '''if''' Set[2, i] == key <font color=green>//Если элемент с ключом key существует, возвращаем указатель на него,</font color=green> '''return''' *(Set[1, i].elements + key) '''return''' ''null'' <font color=green>//в противном случае возвращаем '' null''.</font color=green>

Функция <tex>\mathrm {=== '''minimum(Set)}</tex>:''' ===

'''intT''' minimum(Set): '''returnT''' min = Set.elements[0] <font color=green>//Принимаем первый элемент множества за минимальный.</font color=green> '''int''' res = 0 '''for''' i = 1'''to''' Set.n - 1 '''if''' min > Set.elements[i] <font color=green>//Если есть элементы меньше min, 0</font color=green> min = Set.elements[i] <font color=green>//то записывает элемент в min</font color=green> res = i <font color=green>//и его ключ в res.</font color=green> '''return''' *(Set.elements + key)

Функция <tex>\mathrm {=== '''maximum(Set)}</tex>:''' ===

'''intT''' maximum(Set): '''returnT''' max = Set.elements[0] <font color=green>//Принимаем первый элемент множества за максимальный.</font color=green> '''int''' res = 0 '''for''' i = 1, '''to''' Set.n - 1 '''if''' max < Set.elements[i] <font color=green>//Если есть элементы больше max,</font color=green> max = Set.elements[i] <font color=green>//то записывает элемент в max</font color=green> res = i <font color=green>//и его ключ в res.</font color=green> '''return''' *(Set.elements + key)

Функция <tex>\mathrm {=== '''predecessor(Set, elem)}</tex>:''' ===

'''intT''' predecessor(Set, elem): '''for''' i = 1 '''to''' Set.n - 1 '''if''' elem == Set.elements[1, i] '''return''' *(Set[1, .elements + i - 1]) '''return''''' null''

Функция <tex>\mathrm {=== '''successor(Set, elem)}</tex>:''' ===

'''intT''' successor(Set, elem): '''for''' i = 0 '''to''' Set.n - 2 '''if''' elem == Set.elements[1, i] '''return''' *(Set[1, .elements + i + 1]) '''return''''' null''

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

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