Аватар для Gepar
1186 / 543 / 78
Регистрация: 01.07.2009
Сообщений: 3,517

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

01.05.2012, 22:30. Показов 1663. Ответов 4
Метки нет (Все метки)

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

Есть задачка. Смысл её в том что есть куча классов геом. фигур. У всех есть 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() ? Но что-то оно не правдоподобная идея по-моему у меня возникла. Может есть получше?
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
01.05.2012, 22:30
Ответы с готовыми решениями:

Необходимо реализовать структуру для хранения данных в виде бинарного дерева
Ассоциативный массив должен храниться в виде бинарного дерева

Какую структуру хранения данных выбрать?
Подскажите как правильно организовать хранение данных для следующего случая. Предположим есть таблица объявлений(ид, текст объявления,...

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

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

Добавлено через 2 минуты
Я за праздники ещё было облюбовал В+ дерево, оно вроде тоже должно подойти бы, но я его не писал да и не использовал так что уверенности особой нету что оно лучше сегментного дерева ... помогите решиться Выбирать можно из вообще любых существующих структур данных, не только из тех что я облюбовал.
0
2 / 2 / 0
Регистрация: 08.05.2012
Сообщений: 6
08.05.2012, 11:26
Привет!
У меня подобная задача. Куча элементов с координатами. Нужно по очереди опрашивать состояние каждого элемента, иметь возможность найти элемент с заданной координатой, а так же элементы попадающие в определенную область... Давай кубатурить вместе
Список с этим справляется отвратительно, но для общей обработки полезен. Может скрестить его с деревом для поиска? Но вот с каким деревом его скрещивать ...
0
 Аватар для Gepar
1186 / 543 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
08.05.2012, 23:07  [ТС]
Цитата Сообщение от dsa73 Посмотреть сообщение
Список с этим справляется отвратительно, но для общей обработки полезен.
Ну это логично, последовательный перебор будет слишком долго работать. Ну а вот какую стрктуру взять я так и не решился, был занят экзаменами. Завтра думаю написать тестовую версию с multimap да глянуть как работать будет.
0
2 / 2 / 0
Регистрация: 08.05.2012
Сообщений: 6
09.05.2012, 00:08
Какую структуру решил взять за основу и что такое multimap? А то у меня вообще какие то больные идеи в голову лезут ...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
09.05.2012, 00:08
Помогаю со студенческими работами здесь

Для хранения данных о ноутбуках описать структуру NOTEBOOK
Для хранения данных о ноутбуках описать структуру вида (при необходимости дополнив ее): struct NOTEBOOK{ char model; //...

Организовать структуру данных Heap для хранения целых чисел
Помогите пожалуйста решить задачую Заранее спасибо! В этой задаче вам необходимо организовать структуру данных Heap для хранения целых...

Построить структуру данных для хранения слов в виде двумерного массива
Помогите пожалуйста сделать лабораторную. Очень надеюсь на вашу помощь. я в этом нуб. 1.Построить структуру данных для хранения слов в...

Какой вариант для хранения данных выбрать?
Есть прога. Работает с БД (не суть важно для вопроса с какой). Программа принимает различные данные от пользователя. Номер контракта, дом...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

Новые блоги и статьи
Непрерывная интеграция для пакета Python
Mr. Docker 22.06.2025
Было 4 часа утра пятницы, когда я выпустил новую версию нашей внутренней библиотеки для обработки данных. Релиз 0. 5. 2 содержал небольшой фикс для обработки дат в ISO формате, что может пойти не так?. . .
Продвинутый ETL на C# из OLTP БД в хранилище
stackOverflow 22.06.2025
Работая в сфере корпоративной аналитики, я постоянно сталкиваюсь с одним и тем же - нужны чистые, структурированные и, главное, свежие данные. Без них современные аналитические системы, машинное. . .
Мастер-класс по микросервисам на Node.js
Reangularity 21.06.2025
Node. js стал одной из самых популярных платформ для микросервисной архитектуры не случайно. Его неблокирующая однопоточная модель и событийно-ориентированный подход делают его идеальным для. . .
Управление Arduino из WPF приложения
Wired 21.06.2025
Зачем вообще связывать Arduino с WPF-приложением? Казалось бы, у Arduino есть собственная среда разработки, своя экосистема, свои способы управления. Однако при создании серьезных проектов. . .
Звёздная пыль
kumehtar 20.06.2025
Я просто это себе представляю: как создавался этот мир. Как энергия слипалась в маленькие частички. Как они собирались в первые звёзды, как во вселенной впервые появился Свет. Как эти звёзды. . .
Создание нейросети с PyTorch
AI_Generated 19.06.2025
Ключевое преимущество PyTorch — его питоновская натура. В отличие от TensorFlow, который изначально был построен как статический вычислительный граф, PyTorch предлагает динамический подход. Это. . .
JWT аутентификация в ASP.NET Core
UnmanagedCoder 18.06.2025
Разрабатывая веб-приложения, я постоянно сталкиваюсь с дилеммой: как обеспечить надежную аутентификацию пользователей без ущерба для производительности и масштабируемости? Классические подходы на. . .
Краткий курс по С#
aaLeXAA 18.06.2025
Здесь вы найдете все необходимые функции чтоб написать програму на C# Задание 1: КЛАСС FORM 1 public partial class Form1 : Form { Spisok listin = new Spisok(); . . .
50 самых полезных примеров кода Python для частых задач
py-thonny 17.06.2025
Эффективность работы разработчика часто измеряется не количеством написаных строк, а скоростью решения задач. Готовые сниппеты значительно ускоряют разработку, помогают избежать типичных ошибок и. . .
C# и продвинутые приемы работы с БД
stackOverflow 17.06.2025
Каждый . NET разработчик рано или поздно сталкивается с ситуацией, когда привычные методы работы с базами данных превращаются в источник бессонных ночей. Я сам неоднократно попадал в такие ситуации,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru