Вставка элемента в отсортированный контейнер

Вставка элемента в отсортированный контейнер

Если необходимо создать отсортированный массив или связный список, у нас существует выбор того или иного метода поддержания порядка элементов. Можно сначала вставлять элементы в контейнер, а затем их сортировать и сортировать содержимое контейнера при вставке каждого нового элемента, или же при выполнении вставки находить позицию, вставив новый элемент в которую контейнер останется отсортированным. Если предполагается, что контейнер будет часто использоваться в отсортированном виде, тогда имеет смысл при вставке сохранять правильный порядок элементов.

В таком случае наша задача сводится к вычислению положения нового элемента в отсортированном списке. После определения позиции мы просто вставляем в нее новый элемент. Ранее говорилось, что последовательный поиск может помочь определить точку вставки, но, к сожалению, быстродействие последовательного поиска достаточно низкое. Можно ли для определения точки вставки воспользоваться бинарным поиском?

Оказывается, можно. Посмотрите внимательно на реализацию бинарного поиска для массива, приведенную в листинге 4.9. Когда выполнение цикла завершается, и искомый элемент не найден, что можно определить на основании значений переменных L, R и M? Во-первых, очевидно, что L>R. Рассмотрим, что происходит при выполнении цикла в последний раз. В начале цикла мы должны были иметь L=R или L=R-1. При этом вычисление даст, что M=L. Если бы разница между L и R была больше, скажем, L=R-2, тогда значение M попало бы в диапазон между L и R, и цикл был бы выполнен, по крайней мере, еще один раз.

Если при выполнении цикла в последний раз искомый элемент был меньше, чем элемент в позиции M, то переменная R получила бы значение M-1, и цикл завершился бы. Мы уже знаем, что искомого значения не было до элемента M, поэтому можно сделать вывод, что новый элемент должен быть вставлен между элементами M-1 и M. Другими словами, мы вставляем элемент в позицию M.

С другой стороны, если бы искомый элемент был больше элемента в позиции M, то переменная L получила бы значение M+1. В этом случае можно принять, что в начале цикла L=R. В противном случае цикл был бы выполнен еще один раз. Мы уже знаем, что искомого значения не было после элемента M, поэтому можно сделать вывод, что новый элемент должен быть вставлен между элементами M и M+1. Другими словами, мы вставляем элемент в позицию M+1.

Таким образом, новый элемент должен вставляться в позицию M или M+1 в зависимости от того, что произошло при последнем выполнении цикла. Но давайте подумаем еще раз. Разве между описанными двумя случаями нет ничего общего? Оказывается, что на место вставки в обоих случаях указывает значение переменной L. Таким образом, вставка выполняется в позицию L.

В приведенном ниже листинге показано, каким образом можно вставить новый элемент в массив TList. В коде предполагается, что если вновь вставляемый элемент уже присутствует в массиве, вставка будет игнорироваться (другими словами, повторение элементов не допускается). Функция возвращает индекс вставленного элемента. Легко проверить, что приведенная функция будет работать даже в случае, когда список перед вставкой пуст.

Листинг 4.11. Вставка элемента в отсортированный массив TList с помощью алгоритма бинарного поиска

function TDTListSortedInsert(aList : TList; aItem : pointer;

aCompare : TtdCompareFunc) : integer;

var

L, R, M : integer;

CompareResult : integer;

begin

{задать значения левого и правого индексов}

L := 0;

R := pred(aList.Count);

while (L <= R) do begin

{вычислить индекс среднего элемента}

M := (L + R) div 2;

{сравнить значение среднего элемента с заданным значением}

CompareResult := aCompare(aList.List^[M], aItem);

{если значение среднего элемента меньше заданного значения, переместить левый индекс на позицию после среднего элемента}

if (CompareResult < 0) then

L := succ(M)

{если значение среднего элемента больше заданного значения, переместить правый индекс на позицию перед средним элементом}

else if (CompareResult > 0) then

R := pred(M)

{в противном случае элемент найден, выйти из функции}

else begin

Result := M;

Exit;

end;

end;

Result := L;

aList.Insert(L, aItem);

end;

Для связного списка функция будет еще проще, поскольку нам не нужно решать, каким образом вычислять индекс для вставки нового элемента. Поиск сам указывает на точку вставки элемента.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Атрибуты элемента OBJECT

Из книги автора

Атрибуты элемента OBJECT Этот элемент позволяет встроить на сайт любой мультимедиа-объект вместе с программой обработки данного объекта. В этом разделе мы рассмотрим вопросы встраивания музыки, видео и Flash-анимации. Однако возможности элемента OBJECT намного шире: в принципе,


Структура элемента списка

Из книги автора

Структура элемента списка Раньше в ядре было несколько реализаций связанных списков. Тем не менее в таких случаях необходима единая реализация с целью убрать разный код, который выполняет одинаковые действия. Во время разработки серии ядер 2.1 была предложена единая


Выбор потомков элемента

Из книги автора

Выбор потомков элемента В предыдущем разделе при помощи выражения "PLANET/NAME" я выбирал все элементы <NAME>, являющиеся прямыми потомками элементов <PLANET>, а при помощи выражения "PLANET/*/NAME" — все элементы <NAME>, являющиеся внуками элементов <PLANET>. Есть, однако, более


Регистрация элемента управления

Из книги автора

Регистрация элемента управления Чтобы зарегистрировать новый элемент управления, выясните имя файла, содержащего элемент управления, и место, где размещается этот файл на диске. После этого выполните следующее.1. Выберите Tools=References, чтобы открыть диалоговое окно со


76. По умолчанию используйте vector . В противном случае выбирайте контейнер, соответствующий задаче

Из книги автора

76. По умолчанию используйте vector. В противном случае выбирайте контейнер, соответствующий задаче РезюмеОчень важно использовать "правильный контейнер". Если у вас есть весомые причины выбрать определенный тип контейнера, используйте тот контейнер, который наиболее


Удаление элемента из указателя

Из книги автора

Удаление элемента из указателя Для удаления элемента из указателя нужно удалить весь текст, помещенный в фигурные скобки. Чтобы текст указателя был виден, нужно включить режим отображения непечатаемых символов при помощи кнопки Отобразить все знаки в группе Абзац


Трансформации элемента

Из книги автора

Трансформации элемента Как правило, вставляемый при помощи копирования элемент получается гораздо больше или, наоборот, меньше ожидаемого размера; иногда его надо как-то повернуть, растянуть или вытянуть. В таких случаях мы применяем специальные операции трансформации.


8.4. Автоматическое добавление новых экземпляров класса в контейнер

Из книги автора

8.4. Автоматическое добавление новых экземпляров класса в контейнер ПроблемаТребуется хранить все экземпляры класса в едином контейнере, не требуя от пользователей класса выполнения каких-либо специальных операций.РешениеВключите в класс статический член, являющийся


Выбор элемента

Из книги автора

Выбор элемента Синтаксис:<выражение>.<идентификатор><выражение> -> <идентификатор>Выражение выбора элемента позволяет получить доступ к элементу структуры или объединения. Выражение имеет значение и тип выбранного элемента.В первой синтаксической форме


6.4. Как определить последовательный контейнер?

Из книги автора

6.4. Как определить последовательный контейнер? Для того чтобы определить объект контейнерного типа, необходимо сначала включить соответствующий заголовочный файл:#include vector#inclnde list#include deque#include map#include setОпределение контейнера начинается именем его типа, за которым в


6.13.2. Поиск элемента

Из книги автора

6.13.2. Поиск элемента Две операции, позволяющие отыскать в наборе определенное значение, – это find() и count(). find() возвращает итератор, указывающий на найденный элемент, или значение, равное end(), если он отсутствует. count() возвращает 1 при наличии элемента и 0 в противном случае.


Использование элемента DateTimePicker

Из книги автора

Использование элемента DateTimePicker Элемент управления DateTimePicker появился только в последней версии .NET Compact Framework 2.0. В документации MSDN есть ряд замечательных статей о том, как создать собственный элемент DateTimePicker для программ, работающих на платформе .NET Compact Framework 1.0. Стоит


3.2.3. Добавление элемента

Из книги автора

3.2.3. Добавление элемента Наиболее простой способ добавить элемент в список — это вставить его в самое начало так, чтобы он стал его новой головой. Если X — это новый элемент, а список, в который X добавляется — L, тогда результирующий список — это просто[X | L]Таким


3.2.4. Удаление элемента

Из книги автора

3.2.4. Удаление элемента Удаление элемента X из списка L можно запрограммировать в виде отношенияудалить( X, L, L1)где L1 совпадает со списком L, у которого удален элемент X. Отношение удалить можно определить аналогично отношению принадлежности. Имеем снова два случая:(1) Если X


Уничтожение одного элемента.

Из книги автора

Уничтожение одного элемента. 1. Кликните дважды на элемент (заголовок, параграф, стихи и т. д.).2. Нажмите иконку BookCorrector "delete" или кликните правой кнопкой мышки внутри основного окна BookDesigner и затем нажмите "delete" в появившемся