C++ : Алгоритмы - Бинарное дерево поиска. Часть II

Итак, продолжим..

Вторая статья про Бинарные деревья поиска. Будем реализовывать метод для вставки элементов в дерево, то есть, создание самого дерева.

Чуть-чуть за саму вставку. Деревья - это не списки, хотя чуть похожи. Поэтому и вставка будет кардинально отличатся от добавления элемента в простой список.

Добавление первого элемента в дерево простое. При добавлении же второго элемента мы должны посмотреть на значение корня: если же добавляемое значение меньше, чем значение корня, то добавляем вставляемый элемент в левое поддерево(то есть присваиваем левому указателю корня новый обьект структуры). Если же второй вставляемый элемент больше, чем значение корня, то добавляем узел в правое поддерево.

C++ : Алгоритмы - Бинарное дерево поиска. Часть I

Наконец-то у меня появилось время, чтобы продолжить заниматься своим блогом. На сей раз я представлю вам цикл статей, в котором буде повествоваться про одну из самых известных, ну и, я так думаю, самую простую структуру "из самых сложных" - Бинарное дерево поиска.

Деревья - это вообще интересная вещь. Если рассмотреть уже построеное дерево, то оно реально оправдывает свое название - оно реально похоже на дерево...только перевёрнутое=). Но это не мешает ему иметь корень - самую верхнюю вершину, с которой и начинается все дерево, листья - это самые  нижние вершины. Так же можно увидеть сходство и генеалогическим деревом - в нем есть родители, дети, братья etc..

С++: Внешняя сортировка на 3х лентах

Приступим. Закончив с рассмотрением основных внутренних алгоритмов сортировки, приступим к рассмотрению внешних алгоритмов. Одним из таких есть внешняя сортировка на 3 лентах или простое слияние

Прямое слияние

Слияние означает объединение двух (или более) последовательностей в одну-единственную упорядоченную последовательность с помощью повторяющегося выбора из доступных в данный момент элементов. Слияние намного проще сортировки, и его используют как вспомогательную операцию в более сложных процессах сортировки последовательностей. Одна из сортировок на основе слияния называется простым слиянием. Она выполняется следующим образом:

C++ : Алгоритмы сортировок[2]

Продолжение предыдущей статьи...

Рекурсивные алгоритмы и улучшение известных нам из предыдущей статьи.

 Быстрая сортировка

Теперь коснемся третьего улучшения метода, основанного на обмене. Если учесть, что пузырьковая сортировка в среднем была самой неэффективной из всех трех алгоритмов прямой сортировки, то следует ожидать относительно существенного улучшения. Оно, оказывается, приводит к самому лучшему из известных в данный момент методу сортировки для массивов. Его изобретатель Ч. Хоар назвал метод быстрой сортировкой (QuickSort).

Алгоритм. Выберем наугад какой-либо элемент (назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент  , затем будем просматривать массив справа, пока не встретим  . Теперь Поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена , пока оба просмотра не встретятся где-то в середине массива. В результате массив окажется разбитым на левую часть, с ключами меньше (или равными) x, и правую – с ключами больше (или равными) x.

C++ : Алгоритмы сортировок

Для начала немного теории:

Сортировка – это упорядочение данных по некоторому признаку.

Все методы сортировки разбиты на два класса – сортировку массивов и сортировку файлов (последовательностей). Их называют соответственно внутренней и внешней сортировкой, поскольку массивы хранятся в быстрой оперативной внутренней памяти машины со случайным доступом, а файлы обычно размещаются в более медленной, но более емкой внешней памяти (на носителях). При рассмотрении элементов значение каждого будем называть ключом (key) элемента.

Сейчас мы будем говорить про сортировку массивов, то есть про Внутреннюю сортировку данных.

Сортировка массивов

Пусть задан массив с элементами a1, a2, .......an, которые нужно расположить в возрастающем порядке.

С++ : Работа с файлами

Итак... Мы подошли с вами к очень интересной теме - работе с файлами. Она не очень тяжелая, просто надо разобраться , что такое файловый поток и с чем его едят. Лабораторная, даная мне для закрепления материала, оказалась простой. Вот задание и код:

/*

Лабораторная работа № 3

   Разработать алгоритм решения задачи обработки данных, хранящихся в бинарном

файле чисел или символов.

   Реализовать алгоритм на языке С++ с помощью функций с параметрами. Описать следующие функции:

1) функцию формирования файла (параметрами должны быть файловый поток и его имя);

2) функцию чтения файла (параметрами должны быть файловый поток и его имя);

3) функцию обработки файла (параметрами должны быть файловый поток и его имя).

   В главной функции должны быть реализованы объявления файловых потоков и вызов функций

работы с файлами.

Юмор : Пpоект Genezis

Пpоект genezis

(из коpпоpативной пеpеписки)Генеpальномy диpектоpy Иегове
от начальника маpкетингового отдела Гавpиила

Исследования, пpоведенные нашим отделом в pамках пpоекта Genesis, показали, что наилyчшие пеpспективы на pынке имеют системы следyющей конфигypации:

o Планета: 1 шт.
o Радиyс: 3 000 км
o Сила тяжести: 0.5g
o Соотношение сyша/вода: 1:1
o Темпеpатypа: +24
o Атмосфеpа: кислоpод
o Моpя: пpесная вода
o Реки: молоко, мед
o Фаyна: тpавоядная