Необходимо выбрать структуру (список, К-Ч дерево и т.д) для хранения данных

@Gepar · Регистрация: 01.07.2009

Студворк — интернет-сервис помощи студентам

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

Есть задачка. Смысл её в том что есть куча классов геом. фигур. У всех есть ID и координаты. Я планирую сделать их всех наследником от некого CObject, что позволит мне потом удобно держать список этих классов (ну чтобы узлы были CObject* something), я думаю вы меня поняли. Вот список тех классов геом. фигур:
CRectangle ( int ID, int x1, int y1, int x2, int y2 ) - , координаты противоположных углов
CCircle ( int ID, int x, int y, int r) - середина и радиус
CTriangle ( int ID, CCoord a, CCoord b, CCoord c) - треугольник, 3 вершины (декларация CCoord ниже)
CPolygon ( int ID, int n, const CCoord * v ) , многоугольник, n вершин, координаты вершин переданы в массиве v (значения должны будем скопировать в созданный объект.

CCoord очень простая:

C++
1
2
3
4
5
6
struct CCoord
 {
   CCoord   ( int x = 0, int y = 0 ) { m_X = x; m_Y = y; }
   int   m_X;
   int   m_Y;
 };

Задание: хранить эти объекты в классе CScreen. Класс CScreen принимает методом Add вот эти наши наследники от CObject и сохраняет в себе их копии. Потом есть метод Test который указывает координату x,y (20,30 например) и в ответ получает количество объектов что хранятся с этими координатами в списке, а также их список их ID. Чтобы всё не казалось так легко, прямолинейно и просто у нас есть ещё метод Optimize(), который вызывается после всех добавлений объектов в класс CScreen.

main

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int   * res, resLen;
CScreen  S0;
S0 . Add ( CRectangle ( 1, 10, 20, 30, 40 ) );
S0 . Add ( CRectangle ( 2, 20, 10, 40, 30 ) );
S0 . Add ( CTriangle ( 3, CCoord ( 10, 20 ), CCoord ( 20, 10 ), CCoord ( 30, 30 ) ) );
S0 . Optimize();
S0 . Test ( 0, 0, resLen, res );
 // resLen = 0, res = [ ]
delete [] res;
S0 . Test ( 21, 21, resLen, res );
 // resLen = 3, res = [ 1 2 3 ]
delete [] res;
S0 . Test ( 16, 17, resLen, res );
 // resLen = 1, res = [ 3 ]
delete [] res;
S0 . Test ( 30, 22, resLen, res );
 // resLen = 2, res = [ 1 2 ]
delete [] res;

Вопросы которые меня мучат по заданию:
1) Какую структуру выбрать для хранения наследников от CObject? Элементов, предположу, может быть под 1000 в одном CScreen. Ограничения на оп: 50 мб. Обычный список наверное не пойдёт, в задании советуют деревья использовать, но какое именно хорошо подойдёт чтобы эффективно представлять в нём интервалы и быстро-быстро потом искать? Красно-чёрное дерево? B+ дерево? Из того что выгуглил интересного, но мне не известного: http://en.wikipedia.org/wiki/Segment_tree , только пока не понял чего и как с ним работать то.
2) Как же использовать метод Optimize() в свою пользу? Как видно из мейна: сначала вызывают Add несколько раз, а потом перед тем как искать вызывают Optimize. Это что намекают что я буду держать буфер при каждом вызове Add, а потом быстро хитро засуну всё в свой список (ну или дерево) при вызове Optimize() ? Но что-то оно не правдоподобная идея по-моему у меня возникла. Может есть получше?

@Gepar · 02.05.2012, 23:01 **[ТС]**

Any idea ?
Ато я сам не знаю какую структуру подобрать и что придумать с методом оптимизации, высказывайте даже самые безумные идеи какие есть

Добавлено через 2 минуты
Я за праздники ещё было облюбовал В+ дерево, оно вроде тоже должно подойти бы, но я его не писал да и не использовал так что уверенности особой нету что оно лучше сегментного дерева ... помогите решиться

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

@dsa73 · 08.05.2012, 11:26

Привет!
У меня подобная задача. Куча элементов с координатами. Нужно по очереди опрашивать состояние каждого элемента, иметь возможность найти элемент с заданной координатой, а так же элементы попадающие в определенную область... Давай кубатурить вместе

Список с этим справляется отвратительно, но для общей обработки полезен. Может скрестить его с деревом для поиска? Но вот с каким деревом его скрещивать ...

@Gepar · 08.05.2012, 23:07 **[ТС]**

Сообщение от dsa73

Список с этим справляется отвратительно, но для общей обработки полезен.

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

@dsa73 · 09.05.2012, 00:08

Какую структуру решил взять за основу и что такое multimap? А то у меня вообще какие то больные идеи в голову лезут ...

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Gepar 1186 / 543 / 78 Регистрация: 01.07.2009 Сообщений: 3,517
	02.05.2012, 23:01 [ТС]
	Any idea ? Ато я сам не знаю какую структуру подобрать и что придумать с методом оптимизации, высказывайте даже самые безумные идеи какие есть Добавлено через 2 минуты Я за праздники ещё было облюбовал В+ дерево, оно вроде тоже должно подойти бы, но я его не писал да и не использовал так что уверенности особой нету что оно лучше сегментного дерева ... помогите решиться Выбирать можно из вообще любых существующих структур данных, не только из тех что я облюбовал. 0

@dsa73 2 / 2 / 0 Регистрация: 08.05.2012 Сообщений: 6
	08.05.2012, 11:26
	Привет! У меня подобная задача. Куча элементов с координатами. Нужно по очереди опрашивать состояние каждого элемента, иметь возможность найти элемент с заданной координатой, а так же элементы попадающие в определенную область... Давай кубатурить вместе Список с этим справляется отвратительно, но для общей обработки полезен. Может скрестить его с деревом для поиска? Но вот с каким деревом его скрещивать ... 0

@dsa73 2 / 2 / 0 Регистрация: 08.05.2012 Сообщений: 6
	09.05.2012, 00:08
	Какую структуру решил взять за основу и что такое multimap? А то у меня вообще какие то больные идеи в голову лезут ... 0