Изменения

Над упорядоченным множеством <tex>Setset</tex> заданы следующие операции:

* <tex>\mathrm {search(set, elem)}</tex> {{---}} получает на вход искомое значение элемента <tex>elem</tex> и возвращает найденный элемент множества <tex>settrue</tex> при наличии элемента в множестве или специальное значение <tex>nullfalse</tex>, если такого элемента нетв противном случае,

Упорядоченное множество <tex>sets</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью [[Сортировки | отсортированного]] массива <tex>elements[0..n-1]</tex>.

Рассмотрим реализацию на примере следующего множества: {0, 2, 4, ..., 5, 3, 1}отсортированного по возрастанию целочисленного массива.

'''struct''' setSet<T>: '''int''' even <font color=green>// количество четных элементов множества</font color=green> '''int''' odd <font color=green>// количество нечетных элементов множества</font color=green> '''int''' n = even + odd <font color=green>// общее количество элементов множества</font color=green> '''T'''[n] elements <font color=green>// массив элементов множества типа ''T''</font color=green>

'''func''' insert(setSet<T> s, T elem): s.n = s.n + 1 <font color=green>// Увеличиваем количество элементов множества на единицу,</font color=green> Array.Resize(s.elements, s.n) <font color=green>// увеличиваем размер массива с элементами множества на единицу.</font color=green> '''if''' elem % 2 == 0 <font color=green>// Если элемент elem четный, то,</font color=green> '''int''' i = 0 <font color=green>// ставим счетчик элементов массива на первый элемент,</font color=green> '''while''' elem > s.elements[i] <font color=green>// увеличиваем счетчик до тех пор, пока не найдем первый элемент, больший elem,</font color=green> i = i + 1 '''for''' j = s.n - 1 '''downto''' i+1 <font color=green>// сдвигаем все элементы, большие elem, на единицу вправо,</font color=green> s.elements[j] = s.elements[j - 1] s.elements[i] = elem <font color=green>// вставляем элемент elem в ту ячейку массива, на которую указывает счетчик,</font color=green> s.even = s.even + 1 <font color=green>// увеличиваем количество четных элементов на единицу.</font color=green> Вставляем ''elem'else''' <font color=green>// Если элемент elem нечетный, то,в конец массива</font color=green> '''int''' i = s.even <font color=green>// устанавливаем счетчик на первый нечетный элемент,</font color=green>n - 1 '''while''' elem < s.elements[i] <font color=green>// увеличиваем счетчик до тех пор, пока не найдем первый элемент, меньший elem,</font color=green> i = i + 1 '''for''' j = s.n elements[i - 1 '''downto''' i+1 ] <font color=green>// сдвигаем все элементы, большие elem, на единицу вправоСортируем массив,</font color=green> swap(s.elements[ji] = , s.elements[j i - 1] s.elements[i] = elem ) <font color=green>// вставляем элемент пока ''elem '' не окажется в ту ячейку массива, на которую указывает счетчик,</font color=green> s.odd = s.odd + 1 <font color=green>// увеличиваем количество нечетных элементов на единицунужном месте.</font color=green>

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

'''func''' delete(setSet<T> s, T elem):

'''while''' elem != i < s.n '''and''' s.elements[i] && i < s.n != elem <font color=green>// Ищем элемент индекс элемента ''elem''.</font color=green> i = i + 1+

'''for''' j = i '''to''' s.n - 2 <font color=green>// сдвигаем все элементы массива, следующие за текущимбольшие ''elem'', на единицу влево</font color=green> s.elements[j] = s.elements[j + 1] <font color=green>// на одну позицию влево (тем самым удаляем элемент elem; последний элемент массива дублируетсяудаляется).</font color=green> '''if''' elem % 2 == 0 <font color=green>// Если удаленный элемент был четным, то</font color=green> s.even = s.even - 1 <font color=green>// уменьшаем количество четных элементов на единицу,</font color=green> '''else''' <font color=green>// в противном случае</font color=green> s.odd = s.odd - 1 <font color=green>// уменьшаем количество нечетных элементов.</font color=green> s.n = s.n - 1 <font color=green>// Уменьшаем общее число элементов массива на единицу.</font color=green> Array.Resize(s.elements, s.n) <font color=green>// Удаляем дубликат последнего элемента.</font color=green>

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

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

'''T''' minimum(setSet<T> s): '''T''' min = s.elements[0] <font color=green>// Принимаем первый элемент множества за минимальный.</font color=green> '''int''' i '''for''' i = 1 '''to''' s.n - 1 '''if''' min > s.elements[i] <font color=green>// Ищем минимальный элемент множества</font color=green> min = s.elements[i] '''return''' min <font color=green>// и выводим его.</font color=green>

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

Выполняется аналогично операции <codetex> '''T''' maximum\mathrm {minimum(set<T> s): '''T''' max = s.elements[0] <font color=green>// Принимаем первый элемент множества за максимальный.</font color=green> '''int''' i '''for''' i = 1 '''to''' s.n - 1 '''if''' max < s.elements[i] <font color=green>// Ищем максимальный элемент множества</font color=green> max = s.elements[i] '''return''' max <font color=green>// и выводим его.</font color=green></code>Время выполнения {{---}} <tex>O(n)</tex>.

'''T''' predecessormaximum(setSet<T> s, T elem): '''int''' i '''for''' i = 1 '''to''' s.n - 1 'T''if''' elem =max = s.elements[i] <font color=green>// Если в массиве находим елемент elem,</font color=green> '''return''' s.elements[i n - 1] <font color=green>// то выводим предшествующий ему элемент.</font color=green> '''return''' ''null'' <font color=green>// Иначе выводим ''null''.</font color=green>max

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

'''T''' successor(setSet<T> s, T elem): '''int''' i '''for''' i = 1 '''toif''' elem > s.elements[s.n - 1] <font color=green>// Если элемент больше максимального,</font color=green> '''ifreturn''' ''null'' elem == s.elements[i] <font color=green>// Если в массиве находим елемент elem,возвращаем ''null''.</font color=green> '''returnelse if''' elem < s.elements[i + 10] '''return''' min(s) <font color=green>// то выводим следующий за ним Если элемент меньше минимального, возвращаем минимальный элемент.</font color=green> '''returnint''' ''null'' i = binSearch(s.elements, elem) <font color=green>// Иначе выводим ищем элемент, больший ''nullelem''.</font color=green> '''return''' s.elements[i]

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

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

* строки, отсортированные в [[лексикографический порядок|лексикографическом порядке порядке]].

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