1632
правки
Изменения
м
'''int''' i = 0
'''while''' i < s.n '''&&''' s.elements[i] < elem <font color=green>// Ищем индекс первого элемента, большего elem.</font color=green>
i++
Array.Resize(s.elements, s.n) <font color=green>// увеличиваем размер массива с элементами множества на единицу.</font color=green> '''if''' i != s.elements[s.n - 1 ] = elem <font color=green>// Если Вставляем ''elem не максимальный,'' в конец массива</font color=green> '''int''' j '''for''' j i = s.n - 2 1 '''downtowhile''' i <font color=green>// то сдвигаем все элементы массива, большие elem,</font color=green> s.elements[j + 1i] = < s.elements[ji - 1] <font color=green>// на одну позицию вправо.Сортируем массив,</font color=green> swap(s.elements[i], s.elements[i- 1] = elem ) <font color=green>// Вставляем пока ''elem '' не окажется в нужное местонужном месте.</font color=green>
Array.Resize(s.elements, s.n) <font color=green>// Удаляем дубликат последнего элемента.</font color=green>
=== '''successor''' ===
rollbackEdits.php mass rollback
* <tex>\mathrm {insert(set, elem)}</tex> {{---}} добавляет заданный элемент <tex>elem</tex> в подходящее место множества <tex>set</tex> (сохраняя свойство упорядоченности),
* <tex>\mathrm {delete(set, elem)}</tex> {{---}} удаляет элемент <tex>elem</tex> (сохраняя свойство упорядоченности),
* <tex>\mathrm {search(set, elem)}</tex> {{---}} получает на вход искомое значение элемента <tex>elem</tex> и возвращает найденный элемент множества <tex>settrue</tex> при наличии элемента в множестве или специальное значение <tex>nullfalse</tex>, если такого элемента нетв противном случае,
* <tex>\mathrm {minimum(set)}</tex> {{---}} возвращает минимальный элемент множества <tex>set</tex>,
* <tex>\mathrm {maximum(set)}</tex> {{---}} возвращает максимальный элемент множества <tex>set</tex>,
== Наивная реализация на массиве ==
Упорядоченное множество <tex>sets</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью [[Сортировки | отсортированного]] массива <tex>elements[0..n-1]</tex>.
Рассмотрим реализацию на примере отсортированного по возрастанию целочисленного массива.
'''struct''' Set<T>:
'''int''' n <font color=green>// количество элементов множества</font color=green>
'''T'''[n] elements <font color=green>// массив элементов множества типа ''T''</font color=green>
</code>
<code>
'''func''' insert(Set<T> s, T elem):
s.n = s.n + 1 <font color=green>// Увеличиваем количество элементов множества на единицу,</font color=green>
</code>
Время выполнения {{---}} <tex>O(n)</tex>.
'''func''' delete(Set<T> s, T 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''' i != s.n <font color=green>// Если элемент найден, то</font color=green>
'''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>
s.n = s.n - 1 <font color=green>// Уменьшаем число элементов массива на единицу.</font color=green>
</code>
Время выполнения {{---}} <tex>O(n)</tex>.
=== '''search''' ===
Для нахождения результата используем [[Целочисленный двоичный поиск|бинарный поиск]].
<code>
'''Tbool''' search(Set<T> s, T elem): '''if''' s.elements[0] <= elem '''&&''' s.elements[s.n] >= elem <font color=green>// Если элемент elem существует, то</font color=green> '''int''' i = binSearch(s.elements, elem) <font color=green>// ищем индекс элемента elem</font color=green> '''return''' s.elements[i] == elem <font color=green>// и выводим его Сравниваем найденное значениес искомым..</font color=green> '''else''' <font color=green>// В противном случае</font color=green> '''return''' ''null'' <font color=green>// возвращаем ''null''.</font color=green>
</code>
Время выполнения {{---}} <tex>O(\log n)</tex>.
=== '''minimum''' ===
Первый элемент множества минимальный, так как массив отсортирован по неубываниювозрастанию.
<code>
<code>
'''T''' maximum(Set<T> s):
'''T''' max = s.elements[0s.n - 1]
'''return''' max
</code>
Время выполнения {{---}} <tex>O(1)</tex>.
=== '''predecessorsuccessor''' ===<code> '''T''' predecessor(Set<T> s, T elem): '''if''' s.elementsВ операции используется [[0Целочисленный двоичный поиск|правосторонний бинарный поиск] < elem '''&&''' s.elements[s.n] >= elem , который вернет такое <font color=greentex>// Если элемент elem существует и не равен минимальному,i</font color=greentex> '''int''' i = binSearch(s.elements, elem) что <font color=greentex>// то ищем индекс элемента elem</font color=green> '''return''' s.elements[i - 1] \leqslant elem <font color=green>// и выводим предшествующий ему элементs.</font color=green> '''else''' <font color=green>// В противном случае</font color=green> '''return''' ''null'' <font color=green>// возвращаем ''null''.</font color=green></code>Время выполнения {{---}} <tex>O(log n)elements[i] </tex>.
<code>
'''T''' successor(Set<T> s, T elem):
'''if''' s.elements[0] <= elem '''&&''' > s.elements[s.n- 1] > elem <font color=green>// Если элемент elem существует и не равен максимальномубольше максимального,</font color=green> '''intreturn''' ''null'' i = binSearch(s.elements, elem) <font color=green>// то ищем индекс элемента elemвозвращаем ''null''.</font color=green> '''returnelse if''' elem < s.elements[i + 10] '''return''' min(s) <font color=green>// и выводим следующий за ним Если элемент меньше минимального, возвращаем минимальный элемент.</font color=green> '''elseint''' i = binSearch(s.elements, elem) <font color=green>// В противном случаеИначе ищем элемент, больший ''elem''.</font color=green> '''return''' ''null'' <font color=green>// возвращаем ''null''s.</font color=green>elements[i]
</code>
Время выполнения {{---}} <tex>O(\log n)</tex>.Операция <tex>\mathrm{predecessor}</tex> выполняется аналогичным образом.
== Замечания ==* В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']].
== Примеры ==
* множество натуральных чисел <tex> \mathbb N </tex>,
* множество целых чисел <tex> \mathbb Z </tex>,
* строки, отсортированные в [[лексикографический порядок|лексикографическом порядке]].
== Источники информации ==
