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

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

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

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

Есть задачка. Смысл её в том что есть куча классов геом. фигур. У всех есть 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++

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++

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() ? Но что-то оно не правдоподобная идея по-моему у меня возникла. Может есть получше?

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

Следующий ответ

Другие темы раздела
C++ Написать программу на с++, которая считывает текст из файла.. https://www.cyberforum.ru/ cpp-beginners/ thread563145.html Написать программу, которая считывает текст из файла и выводит на экран только строки, не содержащие двузначных чисел. Что-то вот получилось,но не правильно работает) помогите пожалуйста #include <iostream.h> #include <stdio.h> #include <fstream.h> #include <stdio.h> #include <ctype.h> #include <conio.h> #include <string.h>	C++ Массив и наследование, создать базовый класс Array, в котором определить поле-массив подходящего типа и поле для хранения количества элементов у текущего объекта-массива. Реализовать конструктор инизиализации, задающий количество элементов и начальное значение(по умолчанию 0). Реализовать методы доступа к отдельному элементу, перегрузив операцию индексирования.При этом должна выполняться проверка индекса на...
C++ Двусвязный список "Факультет" https://www.cyberforum.ru/ cpp-beginners/ thread563121.html Разработать программу, реализующую алгоритм двусвязного списка (20 элементов). В качестве элемента списка выбрать структуру: Код (ключ) Название Фамилия И.О. декана К-во кафедр К-во преподавателей Предусмотреть заполнение списка из файла (подготовить файл на 20 элементов). Заполнение списка с начала: a) с консоли (циклически) b) из файла (выбор файла, тек....	C++ Файлы Из текстового файла выбросить все пробельные символы. Новый файл не создавать. Помогите пожалуйста решить эту задачу, в файлах не разбираюсь, так как когда прослушала лекцию. Очень сильно нуждаюсь в вашей помощи)..Буду благодарна. https://www.cyberforum.ru/ cpp-beginners/ thread563118.html
Объявление дружественного класса внутри класса C++ class A{ friend class B{ B(A &a); } } Подскажите пожалуйста, такое возможно или нет, я хотел чтобы конструктор класса В имел доступ к закрытым полям класса А, но компилятор пишет: E2111 Type 'А::В' may not be defined here	C++ Дана последовательность чисел. Выяснить, сколько раз в ней встречается максимальное число https://www.cyberforum.ru/ cpp-beginners/ thread563115.html #include <iostream.h> #include <stdlib.h> #include <time.h> #include <stddef.h> // ------------ size_t index_of_max(int* a, size_t n) { int max_idx = 0;
C++ Решение системы линейных алгебраических уравнений методом ГРАДИЕНТОВ... Нужно решить СЛАУ методом градиентов, пожалуйста, скиньте алгоритм, если есть м-файл в матлабе, то вообще отлично))), но на си++ тоже пойдет https://www.cyberforum.ru/ cpp-beginners/ thread563112.html	Вывести номера элементов списка, которые равны значению Х C++ Помогите программку написать. Создать односвязный линейный список, елементами которого являють действительные значений. Вывести номера елементов списка, которые равны значению Х. Значение Х ввести с клавиатуры.
C++ Для чего нужны указатели на члены-функции класса и как их делать? Собственно сабж https://www.cyberforum.ru/ cpp-beginners/ thread563100.html	C++ Написать функцию replace для массива char'ов Нужно написать функцию замены подстроки f на подстроку t в строке а: int replace(char a, const char f, const char t)f может быть равна или больше t, но не меньше. Нельзя использовать stl. https://www.cyberforum.ru/ cpp-beginners/ thread563096.html
Точка входа не найдена C++ написал dll и создал приложение. Как проге показать эту самую точку входа?	C++ Поиск слов по категориям помогите пожалуйста написать их на с++))сам я в с++ не очень шарю..и если можно пожалуйста с комментами)) Программа говорит о смысле предложения.То есть вбиваем несколько категорий.Например: Семья: мама папа я;Спорт:футбол хоккей итд итп А потом если мы вводим в программу предложение любое,например я люблю папу,и он ищет эти все слова по котегориям и выдает котегорию) вроде понятно написал)) https://www.cyberforum.ru/ cpp-beginners/ thread563090.html

	01.05.2012, 22:30