遞歸通過數組進行迭代，並創建一個基於陣列的它的「路徑」

Question

我有一個非常困難的時期搞清楚如何我可以遞歸遍歷數組，並創建一個數組的它的「路徑」

我有兩個陣列。一個是目錄樹的排列，看起來是這樣的：

$directoryTree = [ 

    'accounting' => [ 

     'documents' => [ 
     ], 

     'losses' => [ 
     ], 

     'profit' => [ 
     ]    

    ], 
    'legal' => [ 

     'documents' => [ 
     ] 
    ] 
]; 

另一個原因是，指定文件應位於該目錄下的「路徑」的文件列表：

$fileList = [ 

    [ 
     'name' => 'Overview.doc', 
     'dir_path' => [] 
    ], 

    [ 
     'name' => 'Incorporation.doc', 
     'dir_path' => [] 
    ], 

    [ 
     'name' => 'Profit And Loss.xls', 
     'dir_path' => ['accounting'] 
    ], 

    [ 
     'name' => 'Profit 1.xls', 
     'dir_path' => ['accounting', 'profit'] 
    ], 

    [ 
     'name' => 'Loss 1.xls', 
     'dir_path' => ['accounting', 'losses'] 
    ], 

    [ 
     'name' => 'TOS Draft.doc', 
     'dir_path' => ['legal', 'documents'] 
    ] 

    [ 
     'name' => 'Accounting Doc.pdf', 
     'dir_path' => ['accounting', 'documents'] 
    ],  
]; 

我本質是什麼試圖做的是迭代遍歷$directoryTree並查看$fileList中是否有迭代器所在的「路徑」中的任何元素。如果有元素應該添加在那裏。

最終陣列應該是這個樣子this：

$finalOutput = [ 
    'accounting' => [ 

     'documents' => [ 
      'Accounting Doc.pdf' 
     ], 

     'losses' => [ 
      'Loss 1.xls' 
     ], 

     'profit' => [ 
      'Profit 1.xls' 
     ], 

     'Profit And Loss.xls' 

    ], 
    'legal' => [ 

     'documents' => [ 
      'TOS Draft.Doc' 
     ] 
    ], 

    'Overview.doc', 
    'Incorporation.doc', 

]; 

我還包括這個形象只是爲了進一步澄清：

---

我所做的嘗試都沒有真的讓我走得很遠。我試圖以遞歸方式遍歷數組時遇到卡住，但不知道下一步如何處理這個問題。

Answer 1

下面的代碼應該解決這個問題。不過考慮一下僞代碼。它真的是javascript，java和單詞的組合哈哈。

@stck是一個字符串數組，保持路徑

//function should return an empty $fileList signaling all files have been processed 
function treeTraversal($directoryTree, $fileList, stck) { 

    //begins by processing all the files that are children of the root directory 
    //e.g. those with dir_name =[] 
    //removes them from $fileList so we don't have to keep iterating over them 
    if(stck.length == 0) {// == 0 only once, when processing first child of root 
     for(var i = 0; i < $fileList.length; i ++) { 
      if($fileList[i].dir_name.length == 0) { 
       $directoryTree.push($fileList[i]); 
       $fileList.removeElementAtIndex(i) 
      } 
     } 
    } 

    // now recursively traverse the tree. Record the path in var called stck 
    for(var i = 0; i < $directoryTree.length; i++) { 
     stck.push($directoryTree[i]); // $directoryTree[i] refers to name of directory not its contents 
     if($directoryTree[i] is array) 
      $fileList = treeTraversal($directoryTree[i], $fileList, stck); 
    for(var j = 0; j < $fileList.length; j++) { 
     if($fileList[j].dir_path == stck) { 
      $directoryTree.push($fileList[j]); 
      $fileList.removeElementAtIndex(j); 
     } 
    } 
    stck.pop(); 
    return $fileList 
} 

Answer 2

的軌道，那豈不是更容易遍歷的$fileList，把他們放到合適的目錄下陣來代替？例如

$finalOutput = $directoryTree; 
foreach ($fileList as $file) { 
    $current_dir &= $finalOutput; 
    foreach ($file['dir_path'] as $dir) { 
     if (isset($current_dir[$dir])) { 
      $current_dir &= $current_dir[$dir]; 
     } else { 
      $current_dir = null; 
      break; 
     } 
    } 
    if (is_array($current_dir)) { 
     $current_dir[] = $file['name']; 
    } else { 
     // do you want to do anything if dir is not there? 
    } 
} 

注意：我沒有運行代碼，但應該給你一個想法如何工作。

如果出於某些未說明的原因，無論如何您都必須重複$directoryTree，您應該小心確保邏輯運行在O(n)（或其附近），而不是在O(n^2)時間內運行。一個簡單的算法將是如下：

• 運行通過$fileList和生成地圖中的所有目錄的 - >文件
• 現在通過$directoryTree運行，並從地圖

Answer 3

有趣的問題，文件填寫。我的回答實際上並沒有用「如何去做」的方式來回答這個問題，但它表明，一旦解決起來更容易，你就需要將複雜的問題分解得更簡單，並且這些小的解決方案可能會在以後重複使用。

基本上，您需要能夠設置「嵌套鍵」的值。我遇到了questions（並親自面對這個問題）關於獲取「嵌套密鑰」的值。

所以我決定實現一個隱藏了遞歸的數組訪問類，並有助於使用類似數組的鍵來獲取嵌套值。您可以查看repo。代碼的解釋實際上符合問題的範圍，但由於時間很長，我無法在這裏解釋它。主要觀點是數組訪問方法隱藏了遞歸。

鑑於這一課，你的問題可以減少到簡單的循環，在$fileList：

$directoryTree = new CompositeKeyArray($directoryTree); 

foreach ($fileList as $file) { 
    if (
     !empty($file['dir_path']) 
     && !isset($directoryTree[$file['dir_path']]) 
    ) { 
     throw new Exception; 
    } 

    array_push($file['dir_path'], []); 
    $directoryTree[$file['dir_path']] = $file['name']; 
} 

var_dump($directoryTree->toArray()); 

在一個評論，你剛纔提到你希望有一個例外，一個不存在的路徑上拋出。 if部分處理這個問題。

這是working demo。