LINUX.ORG.RU

Дерево, список и соседи

 ,


0

2

По мотивам: Прикрутить список к элементам уже содержащим ссылки на соседей?

У меня предполагается структура данных, которую можно визуально представить так:

root
|
-> a
   |
   -> b -> c -> d
   |       |
   |       -> h -> i -> j -> k
   |
   -> e -> f -> g

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

Мыслю так, на примере «a»:

Добавить в список только потомков «b» и «e», а так же указать этим «b» и «e» что их родитель это «a».

Затем, «скрепить» соседей «b» и «c» и соседей «c» и «d», указав для «c» и «d», что их родитель тоже «a».

Повторить процедуру скрепления соседей для «e» как для «b».

Повторить процедуру для «c» как для «a».

Таким образом, смотря на любой узел, если левый сосед NULL, значит этот узел в списке родителя, если правый сосед NULL, значит узел в конце «отростка», если список потомков не пуст, то можно провалиться глубже, ну и у каждого узла есть указатель на родителя для подъёма вверх.

Всё ли я предусмотрел? Насколько сложно будет этим разруливать при добавлении, удалении, перемещении узлов? Есть ли более подходящие варианты взаимосвязей для такой структуры данных?

Мне кажется, будет проще сделать просто дерево:

struct Node
  {
	list<Node> children;
	T data;
  }

И тут два варианта минимум: держи в каждом элементе ссылку на корень, от которого можно вести поиск, либо параллельно веди хеш-таблицу вида <имя, Node&> и ищи через неё

XMs ★★★★★
()
Ответ на: комментарий от deep-purple
struct Node
  {
	list<Node&> children;
	Node &root;
	T data;
	Node &next() { return root.next(*this); }
	Node &next(const Node &node)
	  { return *(find(node) + 1); }
	list<Node&>::iterator find(node)
	  { return find(begin(children), end(children), node); }
  }

Аналогично всё остальное

XMs ★★★★★
()
Ответ на: комментарий от XMs

Годится. Осталось только найти способ отличать «b», «e» и «h» от остальных «не первых» в «отростке». Допустим, ввести св-во тип узла.

deep-purple ★★★★★
() автор топика

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

двумерный массив уже предлагали?

mos ★★☆☆☆
()
Ответ на: комментарий от deep-purple

убил?

возьми код какого-нибудь bdb/gdbm/mdb и сделай так же.

mos ★★☆☆☆
()
Ответ на: комментарий от XMs

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

deep-purple ★★★★★
() автор топика

Какое-то соц. извращение: чем отличается «родитель» от «соседа»? Ты сперва определись с иерархией, потом рисуй дополнительные связи - иерархические (соц.) лифты.

anonymous
()
Ответ на: комментарий от XMs

А не проще ли будет тогда сделать так, как я в старт посте предположил? Там без вот этого всего лишнего и по первым в отростках можно пробежаться сразу.

deep-purple ★★★★★
() автор топика
Ответ на: комментарий от deep-purple

Если честно, в стартовом посте написано не очень просто для понимания, поэтому я так и не понял, что там за вариант предлагается

XMs ★★★★★
()
Ответ на: комментарий от deep-purple

чем отличается «родитель» от «соседа»

Ничем. Только уровнем вложенности.

Ты хочешь получить «прошитое дерево» для быстрого обхода всех узлов?

anonymous
()
Ответ на: комментарий от XMs

Там в список к родителю добавляются только первые узлы отростков. И все узлы отростков (включая первые) связываются как prev-curr-next, где предыдущего или следующего может не быть, если узел стоит вначале или в конце отростка.

deep-purple ★★★★★
() автор топика
Ответ на: комментарий от anonymous

для быстрого обхода всех узлов

Не для обхода, а для движения вправо. На примере схемы из стартпоста, движение вправо:

Первый шаг. У «a» два потомка «b» и «e», у них нет потомков, работаем с ними.

Второй шаг. Тут «c» и «f». У «f» нет потомков, а вот у «c» есть — «h», значит работаем с «h» и «f».

Третий шаг. Работаем с «i» и «g».

Четвертый шаг с «j».

Пятый с «k».

deep-purple ★★★★★
() автор топика
Ответ на: комментарий от anonymous

«d» для «c» не потомок, а сосед, он будет рассматриваться, когда шагну вправо.

Да, я очепятался там выше — «d» рассматривается в один шаг вместе с «i» и «g».

deep-purple ★★★★★
() автор топика
Последнее исправление: deep-purple (всего исправлений: 2)
Ответ на: комментарий от deep-purple

Я же говорю - соц. извращение. Тебе никто не поможет. У тебя иерарихия в иерархии и иерархией погоняет. Сперва определись, и нарисуй непротиворечивое(ые) дерево(ья), а потом задавой вопросы по ним.

anonymous
()
Ответ на: комментарий от anonymous

Ок, представь это не деревом, а разветвлёнными рельсами, на которых стоят вагоны. Над вагонами слева направо едет кран-балка. За один шаг разгружаются те вагоны, которые оказались в тот момент под кран-балкой. А «a» и «c» в данном случае, паровозики, которые разгружать не надо.

deep-purple ★★★★★
() автор топика
Ответ на: комментарий от deep-purple

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

anonymous
()
Ответ на: комментарий от deep-purple

Что мне представлять? ЖД-состав с разветвляющейся цепочкой вагонов? У тебя абсолютно выдуманая структура данных, котороя не прошла проверку ни на формальность, ни на реальность. То есть она нерешаема ни формально, ни реально. Тебе никто не поможет из формального или из реального мира. Иди в свой выдуманный мир и проси там помощи.

anonymous
()
Ответ на: комментарий от anonymous

выдуманая структура данных

А другие были не выдуманы и появились раньше человечества?

нерешаема

Я её решил ещё в старт посте. И лишь спросил нет ли более простого и удобного варианта.

deep-purple ★★★★★
() автор топика
Ответ на: комментарий от deep-purple

Я её решил ещё в старт посте.

В противоречивой теории можно доказать любое утверждение, или опровергнуть.

anonymous
()

Посмотри как в OpenCV иерархия контуров сделана.

iamweasel
()

посмотри (вроде даже у Кнута в томе где и про В+ и В* деревушки) как бинарным деревом всегда можно представлять n-арные деревья - ну и подтюнь чанкованием по нужной тебе константе.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.