Изменения

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

Упорядоченное множество<tex>s</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью [[Сортировки | отсортированного]] массива <tex>elements[0..n-1]</tex>. Оно будет обладать следующими полями:* <tex>elem</tex> {{---}} элемент множества,* <tex>key</tex> {{---}} ключ элементаРассмотрим реализацию на примере отсортированного по возрастанию целочисленного массива.

'''int''' n <font color=green>//количество элементов множества</font color=green> '''T'''[n] elements <font color=green>//массив элементов множества типа ''T''</font color=green>

'''func''' insert(Set<T> s, T elem, key): Sets.n = Sets.n + 1 <font color=green>//Увеличиваем количество элементов множества на единицу,</font color=green> <font color=green>// увеличиваем размер массива с элементами множества на единицу.</font color=green> Sets.elements[keys.n - 1] = elem <font color=green>// Вставляем ''elem'' в конец массива</font color=green> '''int''' i = s.n - 1 '''while''' s.elements[i] < s.elements[i - 1] <font color=green>// Сортируем массив,</font color=green> swap(s.elements[i], s.elements[i - 1]) <font color=green>//и добавляем элемент с ключом keyпока ''elem'' не окажется в нужном месте.</font color=green>

Время выполнения {{---}} <tex>O(1n)</tex>.

'''func''' delete(Set<T> s, keyT elem): '''int''' i = 0 <font color=green>// Устанавливаем счетчик на первый элемент.</font color=green> '''while''' i < s.n '''and''' s.elements[i] != elem <font color=green>// Ищем индекс элемента ''elem''.</font color=green> i++ '''if''' key < Seti != s.n - 1 <font color=green>//Если key {{---}} не последний элементнайден,то</font color=green> '''for''' j = i = key '''to''' Sets.n - 2 <font color=green>//то сдвигаем все элементы множествамассива, начиная с keyбольшие ''elem'', влево.</font color=green> Sets.elements[ij] = Sets.elements[i j + 1] <font color=green>// на одну позицию влево (elem удаляется).</font color=green> Sets.n = Sets.n - 1 <font color=green>//Затем удаляем последний элемент (уменьшаем количество Уменьшаем число элементов множества массива на единицу).</font color=green>

'''Tbool''' search(Set<T> s, keyT elem): '''forint''' i = 0 '''to''' SetbinSearch(s.n - 1elements, elem) '''ifreturn''' s.elements[i ] == key elem <font color=green>//Если элемент Сравниваем найденное значение с ключом key существует, возвращаем указатель на него,</font color=green> '''return''' *(Setискомым..elements + key) '''return''' ''null'' <font color=green>//в противном случае возвращаем ''null''.</font color=green>

Время выполнения {{---}} <tex>O(\log n)</tex>.

'''T''' minimum(Set<T> s): '''T''' min = Sets.elements[0] <font color=green>//Принимаем первый элемент множества за минимальный.</font color=green> '''int''' res = 0 '''for''' i = 1 '''to''' Set.n - 1 '''ifreturn''' min > Set.elements[i] <font color=green>//Если есть элементы меньше min,</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>O(n1)</tex>. 

Выполняется аналогично операции <codetex> '''T''' maximum\mathrm {minimum(Setset): '''T''' 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)</code>Время выполнения {{---}} <tex>O(n)</tex>. 

'''T''' predecessormaximum(Set, elem<T> s): '''forT''' i max = 1 '''to''' Set.n - 1 '''if''' elem == Sets.elements[i] '''return''' *(Sets.elements + i n - 1)] '''return''' ''null''max

Время выполнения {{---}} <tex>O(n1)</tex>.

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

Время выполнения {{---}} <tex>O(\log n)</tex>. Операция <tex>\mathrm{predecessor}</tex> выполняется аналогичным образом.

== Замечания ==* В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']].

* Простые приверы множеств:** {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 Z </tex>,* строки, отсортированные в алфавитном [[лексикографический порядок|лексикографическом порядке]].

 == Ссылки ==* [http://ru.wikipedia.org/wiki/Упорядоченное_множество Википедия — Упорядоченное множество — Википедия]