利用单维数据中的数据创建多维数组

I have an single-dimensional array of PHP objects. Each object has two attributes, one attribute is the object's unique ID and the other is the unique ID of another object in the array that is its parent. For example:

我有一个PHP对象的一维数组。每个对象都有两个属性,一个属性是对象的唯一ID,另一个属性是数组中另一个对象的唯一ID。例如:

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)
  }
}

I need to convert this single-dimensional array into a multi-dimensional array. I have taken a few stabs at this but I can't find a way to get it done without having a loop for each level of nesting. The algorithm needs to be able to adapt to hypothetically infinite levels of nesting. I've tried using some recursion techniques but I've never gotten it quite right.

我需要将这个单维数组转换为多维数组。我已经对此进行了一些尝试,但是如果没有针对每个嵌套级别的循环,我找不到完成它的方法。该算法需要能够适应假设的无限级别的嵌套。我尝试过使用一些递归技术,但我从来没有把它弄得很正确。

To add a bit of complexity, the objects in the array that I am getting are not always in a sensical order. I tried to replicate this in my example above; you'll notice that the object with the ID of 3 comes in the array before the object with the ID of 2. So their will probably be a sorting algorithm involved as well.

为了增加一点复杂性,我得到的数组中的对象并不总是处于一种感性的顺序。我试图在上面的例子中复制这个;你会注意到ID为3的对象在ID为2的对象之前进入数组。因此它们可能也是一个排序算法。

Ideally the example above would turn out something like this:

理想情况下,上面的例子会是这样的:

Array
(
    [0] => Array
        (
            [ID] => 1
            [parentID] => 0
            [0] => Array
                (
                    [ID] => 2
                    [parentID] => 1
                    [0] => Array
                        (
                            [ID] => 3
                            [parentID] => 2
                        )

                )

        )

)

2 个解决方案

#1

Try this algorithm:

试试这个算法:

// 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);

I used a lookup table ($idtable) for the IDs to jump directly to the nodes.

我使用查找表($ idtable)将ID直接跳转到节点。

#2

So, just as a precursor - I do not know php, really at all. I am primarily a c-style language developer (aka c, Objective c and Java). So some of this may be harder to do in php, but here is the attempt I would make:

所以,作为一个先驱 - 我不知道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;
            }
        }
    }
}

A couple of notes: I am assuming you are passing everything around with pointers. If you are making copies of the objects, it is harder, but not impossible. I am also assuming you can change the size of the array dynamically. Again, I am not too aware of php - if you cannot do that, then you would need a procedural way to do this behavior. In Java I would use a list type, or just copy the array and reset it again.

几个笔记:我假设你用指针传递一切。如果要复制对象,则更难,但并非不可能。我还假设您可以动态更改数组的大小。再一次,我不太了解php - 如果你不能这样做,那么你需要一种程序化的方法来做这种行为。在Java中我会使用列表类型,或者只是复制数组并重新重置它。

The key to this algorithm working is that the children are placed under their parent - wherever they are - in one pass. This means that, no matter the order, the hierarchy will be created in that single pass. If you need the wrapper array around the parent that you show in your example, you can simply add something like this to the end of the code:

这个算法工作的关键是孩子们被放置在他们的父母 - 无论他们身在何处 - 一次通过。这意味着,无论顺序如何,都将在该单个过程中创建层次结构。如果你需要在你的例子中显示的父元素周围的包装器数组,你可以简单地在代码的末尾添加这样的东西:

finalArray = new array[];
finalArray[0] = newArray;

Hope this helps.

希望这可以帮助。

#1