قم بإنشاء صفيف متعدد الأبعاد مع خوارزمية باستخدام البيانات في صفيف أحادي الأبعاد

Question

لدي مجموعة ذاتية الأبعاد من كائنات 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
                        )

                )

        )

)

Answer 1

جرب هذه الخوارزمية:

// 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) لمعرفات القفز مباشرة إلى العقد.

Answer 2

لذلك، تماما مثل السلائف - أنا لا أعرف PHP، حقا على الإطلاق. أنا في المقام الأول مطور لغة نمط C (AKA C، الهدف C وجافا). لذلك قد يكون بعض هذا الأمر أكثر صعوبة في 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;

أتمنى أن يساعدك هذا.