Создайте многомерный массив С помощью алгоритма, используя данные в Одномерном массиве
-
19-09-2019 - |
Вопрос
У меня есть одномерный массив объектов PHP.Каждый объект имеет два атрибута, один атрибут - это уникальный идентификатор объекта, а другой - уникальный идентификатор другого объекта в массиве, который является его родительским.Например:
array(3) {
[0]=>
object(stdClass)#1 (2) {
["ID"]=>
int(1)
["parentID"]=>
int(0)
}
[1]=>
object(stdClass)#2 (2) {
["ID"]=>
int(3)
["parentID"]=>
int(2)
}
[2]=>
object(stdClass)#3 (2) {
["ID"]=>
int(2)
["parentID"]=>
int(1)
}
}
Мне нужно преобразовать этот одномерный массив в многомерный массив.Я предпринял несколько попыток в этом направлении, но я не могу найти способ сделать это без наличия цикла для каждого уровня вложенности.Алгоритм должен быть способен адаптироваться к гипотетически бесконечным уровням вложенности.Я пробовал использовать некоторые методы рекурсии, но у меня так и не получилось сделать это совершенно правильно.
Чтобы немного усложнить ситуацию, объекты в массиве, который я получаю, не всегда расположены в определенном порядке.Я попытался воспроизвести это в моем примере выше;вы заметите, что объект с идентификатором 3 появляется в массиве перед объектом с идентификатором 2.Так что, вероятно, в них также будет задействован алгоритм сортировки.
В идеале приведенный выше пример получился бы примерно таким:
Array
(
[0] => Array
(
[ID] => 1
[parentID] => 0
[0] => Array
(
[ID] => 2
[parentID] => 1
[0] => Array
(
[ID] => 3
[parentID] => 2
)
)
)
)
Решение
Попробуйте этот алгоритм:
// sort objects by parentID
function cmpNodes($a, $b) {
return $a->parentID - $b->parentID;
}
usort($objects, 'cmpNodes');
// define first node as root of tree
$tree = (array) array_shift($objects);
// lookup table for direct jumps
$idTable = array($tree['ID'] => &$tree);
foreach ($objects as $object) {
$node = (array) $object;
// test if parent node exists
if (!isset($idTable[$node['parentID']])) {
// Error: parent node does not exist
break;
}
// append new node to the parent node
$idTable[$node['parentID']][] = $node;
// set a reference in the lookup table to the new node
$idTable[$node['ID']] = &$idTable[$node['parentID']][count($idTable[$node['parentID']])-3];
}
// unset($idTable);
var_dump($tree);
Я использовал таблицу подстановки ($idtable
) для того, чтобы идентификаторы переходили непосредственно к узлам.
Другие советы
Итак, просто как предшественник - я вообще не знаю php, на самом деле.Я в первую очередь разработчик языка в стиле c (он же c, Objective c и Java).Так что кое-что из этого может быть сложнее сделать в php, но вот попытка, которую я бы предпринял:
//the original input array
oldArray;
//the output array
array[] newArray = new array[];
foreach (element : oldArray) {
//if the element is at the top, put it at the top of the array
if (element.parentId == 0) {
newArray.add(element);
} else {
//otherwise, find it's parent and put it in the child array of the parent
for (potentialParent : oldArray) {
if (potentialParent.id = element.parentId) {
potentialParent.array.add(element);
break;
}
}
}
}
Пара заметок:Я предполагаю, что вы передаете все с помощью указателей.Если вы делаете копии объектов, это сложнее, но не невозможно.Я также предполагаю, что вы можете динамически изменять размер массива.Опять же, я не слишком разбираюсь в php - если вы не можете этого сделать, то вам понадобится процедурный способ выполнения такого поведения.В Java я бы использовал тип списка или просто скопировал массив и сбросил его снова.
Ключом к работе этого алгоритма является то, что дочерние элементы помещаются под своего родителя - где бы они ни находились - за один проход.Это означает, что, независимо от порядка, иерархия будет создана за один проход.Если вам нужен массив-оболочка вокруг родительского элемента, который вы показываете в своем примере, вы можете просто добавить что-то вроде этого в конец кода:
finalArray = new array[];
finalArray[0] = newArray;
Надеюсь, это поможет.