Изменения

* <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>Setset</tex> или специальное значение <tex>null</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>Setset</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью массива <tex>elements[0..n-1]</tex>. Оно будет обладать следующими полямиРассмотрим реализацию на примере следующего множества:* <tex>elem</tex> {{---}} элемент множества0, 2, 4, ..., 5, 3,* <tex>key</tex> {{---}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, key): Sets.n = Sets.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> Set'''else''' <font color=green>// Если элемент elem нечетный, то,</font color=green> '''int''' i = s.even <font color=green>// устанавливаем счетчик на первый нечетный элемент,</font color=green> '''while''' elem < s.elements[keyi] <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>// вставляем элемент с ключом keyelem в ту ячейку массива, на которую указывает счетчик,</font color=green> s.odd = s.odd + 1 <font color=green>// увеличиваем количество нечетных элементов на единицу.</font color=green>

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

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

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

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

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

'''T''' successor(Setset<T> s, T elem): '''int''' i '''for''' i = 0 1 '''to''' Sets.n - 21 '''if''' elem == Sets.elements[i] <font color=green>// Если в массиве находим елемент elem,</font color=green> '''return''' *(Sets.elements + [i + 1)] <font color=green>// то выводим следующий за ним элемент.</font color=green> '''return''' ''null'' <font color=green>// Иначе выводим ''null''.</font color=green>