Родились сегодня:
goldssky@yandex.ru


Лидеры рейтинга

ID: 226425

Konstantin Shvetski

Модератор

768

Россия, Северодвинск


ID: 259041

Алексеев Владимир Николаевич

Мастер-Эксперт

342

Россия, пос. Теплоозёрск, ЕАО


ID: 401284

Михаил Александров

Академик

278

Россия, Санкт-Петербург


ID: 325460

CradleA

Мастер-Эксперт

211

Беларусь, Минск


ID: 137394

Megaloman

Мастер-Эксперт

148

Беларусь, Гомель


ID: 400815

alexleonsm

6-й класс

130


ID: 400669

epimkin

Профессионал

120


8.8.15

09.05.2021

JS: 2.8.21
CSS: 4.5.5
jQuery: 3.6.0
DataForLocalStorage: 2021-05-14 03:16:12-standard


Создание программ на языках C и C++.

Администратор раздела: CradleA (Мастер-Эксперт)

Консультация онлайн # 200702

Раздел: С / С++
Автор вопроса: Артур (Посетитель)
Дата: 22.04.2021, 19:11 Консультация закрыта
Поступило ответов: 0

Уважаемые эксперты! Пожалуйста, ответьте на вопрос:

Написать программу для работы по запросам оператора с упорядоченной таблицей в двух ключевом ограниченном пространстве, реализованной в виде kd-дерева поиска. Количество элементов на одном уровне ограничено числом N.
Узел дерева содержит граничное значение, указатели на правое и левое поддеревья, массив указателей на элементы таблицы (ключи + информация) в порядке возрастания основных ключей на текущем уровне. Данные могут храниться в любых узлах дерева.
В таблице не могут храниться записи с одинаковыми ключами.
Предусмотреть следующие операции:
Включение нового элемента в таблицу без нарушения свойств упорядоченности; если информация с заданным ключом уже есть, но дублирование ключей не допускается, то изменяется значение информационного поля, а старое возвращается в качестве результата.
Удаление из таблицы элемента, заданного своим ключом, без нарушения свойств упорядоченности таблицы (если элементов несколько, то указывается номер удаляемого элемента).
Поиск информации по заданному ключу; если элементов с одинаковым ключем может быть несколько, в качестве результата возвращаются все элементы с заданным ключем или вектор их адресов; возврат копий элементов не допускается.
Вывод всех элементов таблицы, ключи которых:
- для числовых ключей - имеют заданное число десятичных разрядов;
- для строковых ключей - начинаются с заданной подстроки.
Вывод осуществлять в обратном порядке следования ключей.
Поиск элемента, соответствующего значению наибольшего ключа, не превышающего заданное значение. (если таких элементов несколько – действовать по аналогии с операцией поиска по ключу).
Для Q и kd-деревьев – поиск элемента, расположенного наиболее близко к заданным ключам согласно евклидовому расстоянию, и значения всех ключей которого не превышают значения заданных ключей.
Примечания:
1. Программа должна содержать несколько функций; функция main() должна выполнять: вывод меню, ввод и анализ ответа, вызов на исполнение требуемой функции.
2. В программе нужно предусмотреть проверку правильности ввода данных.
3. Оценить сложность реализованных алгоритмов.
4. Для целей отладки реализовать форматированный вывод таблицы в виде дерева.
5. Для целей отладки реализовать загрузку таблицы из файла в формате
• Ключ1
• Инофрмация1
• Ключ2
• …
6. Провести таймирование (или профилирование) программы.
7. Реализовать графический вывод таблицы (дерева) при помощи внешней библиотеки или внешнего инструмента (например, graphviz).

Ключи типа int, информация из двух строк разной длины (завершающиеся NULL)

Ответов пока не поступило

Мини-форум консультации # 200702

Нет сообщений в мини-форуме

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

Лучшие эксперты раздела

CradleA

Мастер-Эксперт

Рейтинг: 211

Коцюрбенко Алексей Владимирович

Старший модератор

Рейтинг: 74

Зенченко Константин Николаевич

Старший модератор

Рейтинг: 74

Хватов Сергей

Академик

Рейтинг: 26

Степанов Иван /REDDS

4-й класс

Рейтинг: 1

Лысков Игорь Витальевич

Мастер-Эксперт

Рейтинг: 0