Лабораторная работа на языке С

Написать программу для работы по запросам оператора с упорядоченной таблицей в двух ключевом ограниченном пространстве, реализованной в виде Q-дерева поиска. Количество элементов в одном квадрате ограничено числом N. Узел дерева содержит границы ключей в каждом пространстве, массив указателей на поддеревья и указатель на начало списка элементов (ключи + информация) в порядке возрастания ключей (приоритет по первому ключу).

Данные хранятся только в листьях дерева.

В таблице не могут храниться записи с одинаковыми ключами.

Предусмотреть следующие операции:

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

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

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

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

Поиск элемента, наиболее отличающегося по значению ключа от заданного ключа (если таких элементов несколько – действовать по аналогии с операцией поиска по ключу; для Q и kd-деревьев, использовать евклюдову метрику).

Примечания:

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

2. В программе нужно предусмотреть проверку правильности ввода данных.

3. Оценить сложность реализованных алгоритмов.

4. Для целей отладки реализовать форматированный вывод таблицы в виде дерева.

5. Для целей отладки реализовать загрузку таблицы из файла в формате

• Ключ1

• Инофрмация1

• Ключ2

• …

6. Провести таймирование (или профилирование) программы.