Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
#1

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

01.05.2012, 22:30. Просмотров 794. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.05.2012, 22:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Необходимо выбрать структуру (список, К-Ч дерево и т.д) для хранения данных (C++):

Реализовать односвязный список для хранения данных вида: ФИО, группа, средний балл. - C++
Интересует именно структура(синтаксис) как это описать.Как в памяти оно выглядит я представляю и со структурами более-менее уже знаком.Если...

Описать структуру для хранения следующей информации - C++
Нужно срочно написать, а не выходит(((( Описать структуру для хранения следующей информации (при необходимости используйте перечисления):...

Сформировать список из 10 работников, используя динамическую структуру данных двусвязный список - C++
спасайте Сформировать список из 10 работников, используя динамическую структуру данных двусвязный список. Информация о работнике...

Сформировать список из 10 книг, используя динамическую структуру данных односвязный список - C++
друзья спасайте Сформировать список из 10 книг, используя динамическую структуру данных односвязный список С++

Определите структуру Complex для хранения комплексных чисел - C++
Не могу осилить задание, помогите! Определите структуру Complex для хранения комплексных чисел: struct Complex { ...

Определите структуру Complex для хранения комплексных чисел - C++
Условия задачи: Определите структуру Complex для хранения комплексных чисел: struct Complex { double re; //вещественная...

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

Добавлено через 2 минуты
Я за праздники ещё было облюбовал В+ дерево, оно вроде тоже должно подойти бы, но я его не писал да и не использовал так что уверенности особой нету что оно лучше сегментного дерева ... помогите решиться Выбирать можно из вообще любых существующих структур данных, не только из тех что я облюбовал.
0
dsa73
2 / 2 / 0
Регистрация: 08.05.2012
Сообщений: 6
08.05.2012, 11:26 #3
Привет!
У меня подобная задача. Куча элементов с координатами. Нужно по очереди опрашивать состояние каждого элемента, иметь возможность найти элемент с заданной координатой, а так же элементы попадающие в определенную область... Давай кубатурить вместе
Список с этим справляется отвратительно, но для общей обработки полезен. Может скрестить его с деревом для поиска? Но вот с каким деревом его скрещивать ...
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
08.05.2012, 23:07  [ТС] #4
Цитата Сообщение от dsa73 Посмотреть сообщение
Список с этим справляется отвратительно, но для общей обработки полезен.
Ну это логично, последовательный перебор будет слишком долго работать. Ну а вот какую стрктуру взять я так и не решился, был занят экзаменами. Завтра думаю написать тестовую версию с multimap да глянуть как работать будет.
0
dsa73
2 / 2 / 0
Регистрация: 08.05.2012
Сообщений: 6
09.05.2012, 00:08 #5
Какую структуру решил взять за основу и что такое multimap? А то у меня вообще какие то больные идеи в голову лезут ...
0
09.05.2012, 00:08
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.05.2012, 00:08
Привет! Вот еще темы с ответами:

Определите структуру Complex для хранения комплексных чисел - C++
Помоги пожалуйста не могу разобраться. Нужно определить типы и функции и в функции main() реализовать демонстрацию работы созданных...

Определите структуру Complex для хранения комплексных чисел - C++
Я чего-то совсем запутался, может кто поможет. =определить типы и функции в соответствии с вариантом задания; =в функции main()...

Реализовать структуру данных «сбалансированное дерево поиска» - C++
Добрый вечер. Дали задание, не до конца ясна реализация, не могли бы подбросить пару шаблонов, или готовых решений, чтобы посмотреть на...

Разработать объектную структуру для хранения информации о зачетной книжке - C++
Разработать объектную структуру для хранения информации в зачетнойкнижке,а конкретно титульный лист зачетки.


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru