21
правка
Изменения
Нет описания правки
=== Successor ===
Функция <tex>\mathrm {successor(Set, elem)}</tex> возвращает указатель на элемент, стоящий после элемента <tex>elem</tex> множества <tex>Set</tex>.
==Наивная реализация на массиве==
Пусть Set -- упорядоченное множество (массив), состоящее из n элементов. В
Set[1, i] хранятся элементы множества, в Set[2, i] -- их ключи.
int Set[2, n]
func initialize():
for i = 0 to n - 1
Set[1, i] = i
Set[2, i] = i + 1
Функция insert добавляет заданный элемент elem, имеющий ключ elemKey, в
подходящее место множества Set (сохраняя свойство упорядоченности).
func insert(Set, elem, elemKey):
n = n + 1
A rray.Resize(Set[2], n)
i = n - 1
Set[1, i] = Set[1, i - 1]
Set[2, i] = Set[2, i - 1]
while elemKey < Set[2, i - 1]
Set[1, i - 1] = Set[1, i - 2]
Set[2, i - 1] = Set[2, i - 2]
i = i - 1
Set[1, i] = elem
Set[2, i] = elemKey
Функция delete удаляет элемент, имеющий ключ key (сохраняя свойство
упорядоченности).
func delete(Set, key):
i = 0
while i < n
if key == Set[2, i]
for j = i to n - 2
Set[1, j] = Set[1, j + 1]
Set[2, j] = Set[2, j + 1]
n = n - 1
Array.Resize(Set[2], n)
Функция search, которая получает на вход искомый ключ key, и возвращает
указатель на элемент множества Set или специальное значение null, если такого
элемента нет.
int search(Set, key):
for i = 0 to n - 1
if Set[2, i] == key
return Set[1, i]
else return null
Функция minimum возвращает указатель на минимальный элемент множества Set.
int Minimum(Set):
return Set[1, 0]
Функция maximum возвращает указатель на максимальный элемент множества Set.
int maximum(Set):
return Set[1, n - 1]
Функция predecessor возвращает указатель на элемент, стоящий перед элементом
elem множества Set.
int predecessor(Set, elem):
for i = 1 to n - 1
if elem == Set[1, i]
return Set[1, i - 1]
else return null
Функция successor(Set, elem) возвращает указатель на элемент, стоящий после
элемента elem множества Set.
int successor(Set, elem):
for i = 0 to n - 2
if elem == Set[1, i]
return Set[1, i + 1]
else return null
==Примеры==
