Алгоритмы упорядоченных интервалов. Слияние смежных упорядоченных интервалов

   
На этом шаге мы рассмотрим алгоритмы, используемые для слияния смежных упорядоченных интервалов.

   
Для выполнения этой операции можно использовать следующие алгоритмы:

  void
  inplace_merge (BidirectionalIterator beg1,
                 BidirectionalIterator end1beg2,
                 Bidirectional Iterator end2)

  void
  inplace_merge (BidirectionalIterator beg1,
                 BidirectionalIterator end1beg2,
                 BidirectionalIterator end2, BinaryPredicate op)

   
Обе формы выполняют слияние смежных упорядоченных интервалов [beg1, end1beg2) и [end1beg2,end2) так,
чтобы интервал [beg1,end2) содержал упорядоченную совокупность элементов обоих интервалов.

   
Сложность линейная при наличии дополнительной памяти (numberOfElements-1 сравнений), n*log(n) в противном
случае (numberOfElements*log(numberOfElements) сравнений).

   
Пример использования алгоритма inplace_merge():

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iterator>
#include "algostuff.hpp"

#include <conio.h> //необходимо для getch()

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;

std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

int main()
{
  list<int> coll;

  // Вставка двух упорядоченных интервалов
  INSERT_ELEMENTS(coll,1,7);
  INSERT_ELEMENTS(coll,1,8);
  PRINT_ELEMENTS(coll,"Исходная коллекция:\n");

  // Определение начала второго интервала (элемент после 7)
  list<int>::iterator pos;
  pos = find (coll.begin(), coll.end(),    // Интервал
              7);                          // Значение
  ++pos;

  // Слияние в один упорядоченный интервал
  inplace_merge (coll.begin(), pos, coll.end());

  PRINT_ELEMENTS(coll,"Коллекция после слияния:\n");


  getch();
  return 0;
}

//---------------------------------------------------------------------------

Текст этого примера можно взять здесь.

   
Результат выполнения программы выглядит так:


Рис.1. Результат работы приложения

   
Со следующего шага мы начнем рассматривать численные алгоритмы.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий