Официальный сайт студ.городка НГТУ
Программирование и БД » [C++] двухуровневые структуры данных 

#1  30.01.11 17:05

[C++] двухуровневые структуры данных

товарищи, помогите разобраться в задании (делать ничего не надо, напишу сам, не могу понять задание):

Для заданной двухуровневой структуры данных, содержащей указатели на объекты (или сами объекты) - параметры шаблона, разработать полный набор операций (добавление, включение и извлечение по логическому номеру, сортировка, включение с сохранением порядка, загрузка и сохранение строк в бинарном файле, балансировка – выравнивание размерностей структур данных нижнего уровня). Предполагается, что операции сравнения хранимых объектов переопределены стандартным образом (в виде операций <,>  и т.д.). Программа должна использовать шаблонный класс с объектами- строками и реализовывать указанные выше действия над текстом любого объема, загружаемого из файла.
Программа должна реализовывать указанные выше действия. Протестировать структуру данных. Программа тестирования должна содержать меню, обеспечивающее выбор операций.
1.    Шаблон структуры данных – дерево. Конечная вершина  дерева содержит  статический массив указателей на объекты (ограниченный NULL-указателем), промежуточная вершина содержит счетчик вершин дерева  и  два указателя на правое  и  левое  поддерево. Значения в дереве не упорядочены. Естественная нумерация значений производится путем обхода дерева по принципу “левое поддерево – вершина – правое поддерево”. Если при включении указателя в найденный массив последний переполняется, он становится промежуточной вершиной.

собственно, как я его понимаю:
нужно написать шаблон-дерево, в каждом поддереве есть указатель на левое правое поддеревья и массив указателей на элементы (параметры шаблона). То есть например по четыре указателя на объекты и два указателя на поддеревья. НО, кок могут быть "Значения в дереве не упорядочены"? То есть при включении нового элемента в дерево, просто кидаем его на первую попавшуюся пустую позицию и все? а в чем тогда сам смысл дерева, на сколько я знаю бинарные деревья для быстрого поиска элементов нужны (упорядоченных причем!), а тут получается надо мотаться непонятно куда по всему дереву и искать какой-то элемент.

Offline

#2  31.01.11 11:13

Re: [C++] двухуровневые структуры данных

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

Offline

Программирование и БД » [C++] двухуровневые структуры данных 

ФутЕр:)

© Hostel Web Group, 2002-2025.   Сообщить об ошибке

Сгенерировано за 0.067 сек.
Выполнено 14 запросов.