Создание многомерного массива с помощью алгоритма с использованием данных в одномерном массиве

У меня есть одномерный массив объектов 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
                        )

                )

        )

)
Источник

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-style (aka 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;

Надеюсь это поможет.

Источник
Другие вопросы по тегам