如何在PHP中对链表进行排序？

Question

$arr[] = array(...,'id'=1,'prev'=>2,'next'=>null);
$arr[] = array(...,'id'=2,'prev'=>3..,'next'=>1);
$arr[] = array(...,'id'=3,'prev'=>4,'next'=>2);
..

每条记录的顺序可以是任意的.

如何对这种数组进行排序,以便记录prev的值null是第一个,而null next最后一个是？

Answer 1

数组不是链表的容器.链表是包含链接对象的列表,而不是包含具有关系的对象的列表.基本上,你得到的是两个容器中最差的.我会尝试将该结构转换为其他数据容器; 真正的链接列表永远不需要按照您对数据进行排序的方式进行排序.

好方法会涉及到类似的东西.我将给你留下在列表中间插入对象的方式,这并不难.

<?php
class LinkedObject
{
    var $value;
    var $prev;
    var $next;

    public function __construct($value, $prev = null, $next = null)
    {
        $this->value = $value;
        $this->prev = $prev;
        $this->next = $next;
    }

    public function append(LinkedObject $insertee)
    {
        $link = $this;
        while($link->next != null)
            $link = $link->next;

        $link->next = $insertee;
        $insertee->prev = $link;
    }

    public function __toString()
    {
        $str = $this->value;
        if($this->next != null)
        {
            $str .= " » ";
            $str .= $this->next;
        }
        return $str;
    }
}

$head = new LinkedObject("foo");
$head->append(new LinkedObject("bar"));
$head->append(new LinkedObject("baz"));
echo $head . "\n"; // gives "foo » bar » baz"
?>

但是,如果出于某些神秘的原因,你真的需要它们在数组中,这就是你需要的:

<?php
function find_row($array, $id)
{
    foreach($array as $current_row)
    {
        if($current_row['id'] === $id)
            return $current_row;
    }
    return null;
}

function what_the_heck_sort($array)
{
    $start_record = $array[0];
    $working_record = $array[0];
    $result = array($working_record);
    while($working_record['prev'] !== null)
    {
        $working_record = find_row($array, $working_record['prev']);
        array_unshift($result, $working_record);
    }

    $working_record = $start_record;
    while($working_record['next'] !== null)
    {
        $working_record = find_row($array, $working_record['next']);
        array_push($result, $working_record);
    }
    return $result;
}

// the test code
$test = array(
    array("foo 01", 'id' => 0, 'prev' => null, 'next' => 1),
    array("foo 02", 'id' => 1, 'prev' => 0, 'next' => 2),
    array("foo 03", 'id' => 2, 'prev' => 1, 'next' => 3),
    array("foo 04", 'id' => 3, 'prev' => 2, 'next' => 4),
    array("foo 05", 'id' => 4, 'prev' => 3, 'next' => 5),
    array("foo 06", 'id' => 5, 'prev' => 4, 'next' => 6),
    array("foo 07", 'id' => 6, 'prev' => 5, 'next' => 7),
    array("foo 08", 'id' => 7, 'prev' => 6, 'next' => 8),
    array("foo 09", 'id' => 8, 'prev' => 7, 'next' => 9),
    array("foo 10", 'id' => 9, 'prev' => 8, 'next' => null));

shuffle($test);
print_r(what_the_heck_sort($test));
?>

但是,真的,帮自己一个忙,做一个真正的链表,使用对象而不是数组.在我看来,上面的排序方法非常适合了解约束,但它的速度非常慢,因为它需要为每个id查找数组.