LINUX.ORG.RU

Простой алгоритм построения многуровнегого списка (дерева) из совокупности простых.


0

0

Я не программист, поэтому простота алгоритма имеет бо'льшее значение, чем, к примеру, его эффективность.

Вот что нужно. Имеется совокупность списков. Каждый список простой, то есть включает только элементы второго уровня. Любой список может быть сам элементом другого списка, а элемент данного списка может содержать в себе другой список. Для примера. Пусть есть список А, содержащий элементы А1, А2, А3..., Список В, содержащий В1, В2, В3..., списки А1, А2, соответственно, содержат А11, А12, А13 и А21, А22, А23, В. При этом в списке А2 нет информации, что В - сам по себе список. Эта информаци - косвенная, основана только на том, что список В существует. То есть изначально неизвестно ничего - ни уровни списков, ни вложенность одного списка в другой. Только то, что есть какой-то двухуровневый список. И таких списков - много. А нужно найти все уровни списков и составить собственно сам многоуровневый список. При этом возможно, к примеру, что многоуровневых списков будет несколько, когда "верхних" элементов будет несколько. Возможно также "пересечение" списков, когда один список частично содержит элементы другого. Каждый список хранится в файле, название которого совпадает с названием списка. К примеру, файл А содержит список А.

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

Заранее спасибо за ответ.

anonymous

Как-то не очень понятно :) 
может ли получится так, что элементы списка находящиеся в разных ветвях
 имеют одинаковые имена ?

Например так 


          A 
         / \  
   ----A1  A2-----
  /  |  |   |  |  \ 
A11 A12 B  A21 A22 B

Тут два разных элемента B.

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

Нет. "В" только один. Каждому имени списка соответствует только один список элементов, в него входящих.

anonymous
()

похоже, конопля уже начала расти на деревьях

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

Тогда я бы попробывал такой способ:

1) просматриваешь все имеющиеся файлы и создаешь массив M, содержащий все элементы всех списков. Изначально связи между элементами непроставлены. Т.е. массив M это просто массив никак не связанных элементов, которые удалось выявить просматривая файлы.

2) Выбираем произвольный файл B, содержащий элементы B1,B2,...BN. Находим элемент B в массиве M. Запоминаем где он лежит. Далее находим элемент B1 в массиве M и добавляем иерархическую связь между B и B1 (начинаем cтроим список). Помечаем что B1 обработан. Далее ищем B2. Устанавливаем между B и B2 иерархическую связь (продолжаем строить список). Помечаем что B2 обработан. и т.д. до BN

3) Выбриаем следующий файл и выполняем для него тот же набор дейсвий

Заметь, что если мы теперь выберем файл А cодержащий элементы B, С, D, E, ... Z на первой итерации сразу же установится иерархическая связь между А и B, а B к тому же будет еще и помечен как обработанный.

4) В итоге, если промоделируешь этот алгоритм на примере, то увидишь, что в конце не помеченными останутся только корневые узлы иерархии. Просматривая массив и выбриая непомеченные элементы ты найдешь все возможные корни. Далее от корней, спускаясь вниз по иерархии можешь обойти все полученные деревья.

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