Есть ли веская причина не включать несколько указателей узла в узел для использования в более чем одной структуре данных?

Question

Возьмите, к примеру, задание, над которым я работаю.Мы должны использовать бинарное дерево поиска для одной части набора данных и затем связанный список для другой части в наборе.Профессор предложил метод:

struct treeNode
{
    data * item;
    treeNode *left, *right;
};

struct listNode
{
    data * item;
    listNode *next, *prev;
};

class collection
{
public:
         ........
}

Где данные - это класс, содержащий данные каждой записи.Очевидно, что при настройке treeNode не может существовать в связанном списке.

Не будет ли намного проще:

struct node
{
    data * item;
    node *listNext, *listPrev, *treeLeft, *treeRight;
};

, тогда мы можем объявить:

node * listHead;
node * treeRoot;

и включить оба алгоритма вставки в класс.

Есть что-то, что я пропускаю?

Answer 1

На самом деле, элементы данных должны быть вставлены в оба списка. (Мирская) цель назначения состоит в том, чтобы отсортировать наборы данных по двум различным элементам в наборе.

Так что с этим сказал, я бы не стал экономить память? Объединяя 2 узла, я получаю 5 указателей, и если я оставлю их отдельно, я буду использовать 6. Кроме того, у меня действительно только одна группа данных таким образом. если бы у меня было 250 элементов данных для отслеживания, у меня была бы одна группа из 1250 указателей вместо 2 списков из 750. Возможно, я неправильно понимаю, что на самом деле распределяется при вызовах указателей.

Answer 2

Какой был ответ?

Если ваши данные меньше (хммм) мегабайт, не беспокойтесь о потреблении памяти. 1 или 2 гигабайта типичны для обычных компьютеров сегодня.

Насколько велики предметы? 32 символа? 64 К сжатых мультимедиа? Что-то большое?

Насколько разумно организовать один предмет, используя обе техники? Если данные действительно одинаковы, то интересна структура из 5 указателей: кто-то может найти узел в одном порядке, а затем просмотреть связанные узлы в другом порядке.

Предметы не связаны, мел, сыр? Они многомерны? кадровые записи? Описание аудиофайлов? Рецепты?

В школе хороший учитель пытается поделиться с вами общими навыками и дисциплинами. Так же, как художественный класс или композиция. Карандаш, пастель, эссе 5 абзац. Поэтому учитель может захотеть, чтобы вы написали два разных класса и конструкторы. Используйте одну структуру для одной части данных, другую для других данных. Или то же самое. Просто так.

За пределами школы данные поступают в формате, и с ним / с ним желательны операции. «Варианты использования» - это истории о том, как используются данные, что нужно хранить, какие алгоритмы используются.

Смысл в этом может быть бимодальный поиск, 2 пары ортогональных указателей. Это могут быть Союзы, где каждый элемент связан со списком или деревом, но не оба одновременно. Это может быть поток легковесных подмножеств, деревьев и списков, которые сравниваются и сопоставляются ...

В случае сомнений "структуры данных + алгоритмы = программы". Но стоит знать, какую мысль пытается сделать учитель, и хотите ли вы следовать их примеру. (Обычно в школе, вы делаете.)

Answer 3

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

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