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

问题描述：

我有一个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) 
    } 
}

我需要将此一维数组转换为多维数组。我已经采取了一些措施，但我无法找到一个方法来完成没有每个级别的嵌套循环。该算法需要能够适应假设无限级别的嵌套。我试过使用一些递归技术，但我从来没有得到它很正确。

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

理想上面的例子会变成这样的：

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

       ) 

     ) 

)

您的示例数据中有父/子递归。节点3的父节点是2，节点2的父节点是3.你有打字错误吗？ – 2009-11-10 17:48:53

我做到了，谢谢你的发现。它现在已经修复。 – macinjosh 2009-11-10 17:56:54

这里的伪代码答案是否合适，或者您是否正在寻找PhP响应？ – aperkins 2009-11-10 18:00:11

答

试试这个算法：

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

我用的ID直接跳转到该节点查找表（$idtable）。

答

所以，就像一个前兆 - 我不知道PHP，真的。我主要是一个c风格的语言开发人员（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;

希望这有助于。

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

相关推荐