Программа сортировки и поиска баз данных

for (int i = first; i<=last; ++i) {int ti = i — first; // Временный массив всегда начинается с нуля, а наш исходный — с first. Так что вычисляем индекс временного массива поправкой на first. v[i] = tmp[ti]; }}/*** Функция сортировки базы данных.* Функция возращает массив с индексами записей БД, отсортированными по дню рождения и имени.*/std:vector<int> sortDB (){std:vector<int> v (db.size ()); // Создаем массив, который будем формироватьfor (int i = 0; i<v.size (); ++i) { // Заполняем его всеми индексами БД по порядку (от 0 до 3999) v[i] = i;}mergeSort (v, 0, v. size ()-1); // Сортируем массив слиянием (см. функцию выше) return v;}/*** Функция поиска записей БД со конкретным днем рождения.* Функция возвращает очередь с индексами записей БД, отсортированными по дню рождения и имени И имеющих конкретный день рождения day.* Для формирования очереди используется бинарный поиск.** day — искомый день рождения* sorted — массив с индексами записей БД, отсортированными по дню рождения и имени, по которому будет происходить поиск. Формируетсяфункцией sortDB (см. функциювыше).*/ std: deque<int> searchByDay (int day, const std: vector<int> &sorted){std:deque<int> res; // Создаем очередь, которую будем формироватьint first = 0; // Левая граница бинарного поискаint last = sorted. size ()-1; // Правая граница бинарного поискаint mid = (first+last)/2; // Текущий (серединный) индекс бинарного поискаwhile (first <= last) { // Пока диапазон ненулевой, проводим бинарный поискint middleDay = db[ sorted[mid] ].

date.day; // По серединному индексу находим день рождения записи БД, соответствующий данному индексу. if (middleDay < day) { // Если день меньше искомого, начинаем искать в правой половине диапазонаfirst = mid+1; // Начало перемещается за бывшую серединуmid = (first+last)/2; // Середина обновляется с новыми first и last} elseif (middleDay > day) { // Если день больше искомого, начинаем искать в левой половине диапазонаlast = mid-1; // Конец перемещается за бывшую серединуmid = (first+last)/2; // Середина обновляется с новыми first и last} else{ // Если мы нашли искомый день:/* * Когда найден искомый день, мы должны идти влево по массиву, пока его элементы все еще содержат искомый день. * После того, как мы найдем самый левый искомый день, идет по массиву вправо, пока не дойдем до следующего дня или конца массива, * попутно занося записи с искомым днем рождения в очередь. */ int i = mid; // Запоминаем середину// И идем от нее влево до упора либо до записи с другим днемwhile (i >= 0 && db[ sorted[i] ]. date. day == day) {—i;}++i; // После цикла i равен либо -1 либо индексу записи с предыдущим днем, нужно увеличить индекс на 1, чтобы встать на первую запись с нужным днем.// Идем по массиву вправо до упора либо до записи с другим днемwhile (i<sorted.size () && db[ sorted[i] ]. date. day == middleDay) {res.push_back (sorted[i++]); // заносим каждый индекс правильной записи в очередь}return res; // Возвращаем заполненную очередь}}return res; // Здесь мы возвращаем пустую очередь, в случае, если нет искомого дня}int main (){if (!loadDB ()) { // Загрузка.

БДstd:cout << «FAIL!» << std: endl;return -1; // Выходим, если не загрузилась}printDB (); // Распечатываем.

БДstd:cout << «Press ENTER to sort by day «; // Предложениепродолжитьstd: cin. get ();std:vector<int> dayIndexes = sortDB (); // Получение массива с индексами БД, отсортированными по дню рожденияprintSortedDB (dayIndexes); // Распечатка записей БД по индексному массивуint day; // Предложениеввестиденьstd: cout << «Enter day: «<< std: endl;std:cin >> day;std:deque<int> searchResult = searchByDay (day, dayIndexes); // Получениеочередисиндексами.

БДпоконкретномуднюрожденияprintSortedDB (searchResult); // Распечатка записей БД по индекной очередиif (searchResult.empty ()) { // Если ничего не нашлось, выходим из программыreturn 0;}std:cout << «Press ENTER to build AVL tree «; // Предложение продолжить и перейти к построению АВЛ-дереваstd:cin.get (); // Это съедает предыдущий перевод строки от ввода дняstd: cin. get (); // Это съедает новый перевод строкиconst Record &first = db[ searchResult. front () ]; // Извлекаем первую запись из очередиsearchResult. pop_front ();Node<int, int> *avl = Node<int, int>:createNode (first.date.year, searchResult[0]); // Наееосновестроимкореньдерева// Вынимаем и заносим в АВЛ-дерево остальные записи из очередиwhile (!searchResult.empty ()) {int idx = searchResult. front (); // Вынимаем индекс очередного элементаsearchResult. pop_front ();const Record &record = db[ idx ]; // Поиндексунаходимзаписьв.

БДavl = avl->insert (record.date.year, idx); // Вставляемвдерево}std:cout << «AVL tree built» << std: endl << std: endl;int year; // Предложениеввестигодstd: cout << «Enter year: «<< std: endl;std:cin >> year;std:vector<int> yearIndexes = avl->seek (year); // ИщемвсевхожденияузловдеревасзаданнымгодомprintSortedDB (yearIndexes); // Распечатка записей БД по индексному массивуdelete avl; // Освобождаем память, выделенную под АВЛ-деревоreturn 0;}Приложение.

Б. Кодтестовалгоритмовсортировки/*** Узел АВЛ-дерева.* Шаблонный параметр — данные, которые несет узел помимо ключа.* В нашем случае этими данными будет индекс записей БД типа int.** Данный класс представляет собой, как отдельный узел, так и целое дерево,* поскольку каждый узел дерева — сам по себе дерево .*/template <class Key, class Data>class Node{private:// Данные, которые содержит узелKey key; // ключ поискаData data; // пользовательские данные (в нашем случае — индекс, представляющий запись из БД) inth; // высота узлаNode* left; // левое поддеревоNode* right; // правое поддеревоpublic:/*** Конструктор. Чтобы создать узел, нужен ключ и данные.*/Node (Key k, Data d){key = k;data = d;left = right = NULL; // Левого и правого поддеревьев нетh = 1; // Высота дерева — 1}/*** Деструктор. Освобождаем память, выделенную под узел и его поддеревья.*/~Node (){if (left) { // Если есть левое поддерево, удалить егоdelete left;}if (right) { // Если есть правое поддерево, удалить егоdelete right;}}/*** Статическая функция (не вызывается из-под объекта, вызывается сама по себе)* создания принципиально нового узла или дерева.*/static Node* createNode (Key k, Data d){returnnew Node (k, d);}/*** Функция вставки новых данных в дерево.* Функция сама найдет место куда вставить новый узел, сама его создаст и сама перебалансирует дерево.*/Node* insert (Key k, Data d) // вставка ключа k в дерево с корнем p{if (k < key) { // Если ключ меньше ключа этого узла, то если у нас нет левого поддерева, создаем там новый узел, иначе просим левое поддерево самому вставить новые данныеleft = left? left->insert (k, d): createNode (k, d);} else{ // Если ключ больше или равен ключа этого узла, то если у нас нет правого поддерева, создаем там новый узел, иначе просим правое поддерево самому вставить новые данныеright = right? right->insert (k, d): createNode (k, d);}returnbalance (); // Выполняем балансировку дерева}/*** Функция поиска данных в по ключу.* Функция вернет массив с данными, узлы которых равны искомому ключу.* */std:vector<Data> seek (Key k){std:vector<Data> res; // Создаем пустой массивNode* n = this; // Начинаем с этого узлаwhile (n) { // Пока по дереву есть куда идти, начинаем идти по нему и искать ключif (n->key > k) { // Если искомый ключ меньше текущего ключа, n = n->left; // идем в левое поддерево} elseif (n->key < k) { // Если искомый ключ больше текущего ключа, n = n->right; // идем в правое поддерево} else {pushSame (n, k, res); // Если мы нашли искомый ключ, идем вблубь этого узла и копируем в массив все данные с таким же ключом (см. pushSame) returnres; // Возвращаем заполненный массив}}returnres; // Мы здесь, если не нашли искомый ключ, возвращаем пустой массив.}private:/*** Статическая функция (не вызывается из-под объекта, вызывается сама по себе)* возвращающая высоту поддерева.* Если узла не существует, возвращает ноль.*/staticint height (Node* n){return n? n->h: 0;}/*** Би-факторузла.* Разница между высотой правого и левого поддеревьев.* Если би-фактор равен 0, -1 или 1 — дерево сбалансировано* Если би-фактор равен 2, или -2 — дерево разсбалансировано*/int bfactor () const{return height (right) — height (left);}/*** Функция обновления высоты дерева на актуальную.* При этом считаем, что левое и правое поддеревья имеют актуальную высоту.*/void fixheight (){int hl = height (left);int hr = height (right);h = (hl > hr? hl: hr) + 1;}/*** Правый поворот узла.*/Node* rotateRight (){Node* l = left; // Запоминаем левое поддеревоleft = l->right; // Присваиваем левому поддереву его правое поддеревоl->right = this; // Присваиваем правому поддереву бывшего левого поддерева этот узелfixheight (); // Обновляем высоты этого узла и повернутого узлаl->fixheight ();returnl; // Возвращаем повернутый узел, который сейчас в дереве занимает положение, которое раньше занимал текущий узел}/*** Левый поворот узла.*/Node* rotateLeft (){Node* r = right; // Запоминаем правое поддеревоright = r->left; // Присваиваем правому поддереву его левое поддеревоr->left = this; // Присваиваем левому поддереву бывшего правого поддерева этот узелfixheight (); // Обновляем высоты этого узла и повернутого узлаr->fixheight ();returnr; // Возвращаем повернутый узел, который сейчас в дереве занимает положение, которое раньше занимал текущий узел}/*** Функция балансировки узла.* Балансировка выполняется функциями rotateRight, rotateLeft (см.

выше).*/N ode* balance (){fixheight (); // На всякий случай обновляем выосту дереваif (bfactor () == 2) { // Если правое поддерево сильно выше левогоif (right->bfactor () < 0) { // То если правое поддерево правого поддерева ниже левого поддерева правого поддерева, right = right->rotateRight (); // То сначала сделаем оборот правого поддерева вправо}returnrotateLeft (); // Сделаем оборот этого узла влево}if (bfactor () == -2) { // Если левое поддерево сильно выше правогоif (left->bfactor () > 0) { // То если левое поддерево левого поддерева ниже правого поддерева левого поддерева, left = left->rotateLeft (); // То сначала сделаем оборот левого поддерева влево}returnrotateRight (); // Сделаем оборот этого узла вправо}returnthis; // балансировка не нужна}/*** Статическая функция (не вызывается из-под объекта, вызывается сама по себе)* вставки в массив res всех данных, лежащих в узлах, у которых ключ равен k.* Функция является вспомогательной для функции seek (см. выше).*/staticvoid pushSame (Node* n, Key k, std: vector<Data> &res){if (!n) { // Если узла не существует, ничего не делаем, выходимreturn;}if (n->key == k) { // Если текущий узел с нужным ключом, добавляем в массив его данныеres. push_back (n->data);}pushSame (n->left, k, res); // Рекусивно вызываем эту функцию для левого поддерева узла npushSame (n->right, k, res); // Рекусивно вызываем эту функцию для правого поддерева узла n}};