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와 그 기록 있도록 배열의이 종류를 분류하기 위해 먼저, 그리고 nullnext와 함께 한 마지막?

Answer 1

내가 작성한 usort가 사용자가 설명하는 데이터 구조에 잘 작동한다고 생각합니다.

편집 : 올바르게 작동하지 않습니다. 취소하면 취소 할 수 있습니다.

<?php 
//$arr = your array as described 

usort($arr, 'subkey_compare_next'); 

function subkey_compare_next($a, $b) { 
    $a = $a['next']; 
    $b = $b['next']; 
    if($a === null) { 
     return -1; 
    } 
    if ($a == $b) { 
     return 0; 
    } 
    return ($a < $b) ? -1 : 1; 

} 
?> 

Answer 2

흠, 그래서 당신은 같은으로 배열을하고 싶지 :

$array[] = array('id'=>1324, 'prev'=>null, 'next'=>15834); 
$array[] = array('id'=>15834, 'prev'=>1324, 'next'=>1023); 
$array[] = array('id'=>1023, 'prev'=>15834, 'next'=>12482); 
$array[] = array('id'=>12482, 'prev'=>1023, 'next'=>null); 

에 상관없이 그들이 시작 어떤 순서로? 글쎄, 그건 기본 정렬 패턴이되지 않습니다, 그래서 내가 좋아하는 뭔가 갈 것 : 배열은 하지 연결리스트의 컨테이너입니다

// Find the first entry 
foreach($arr as $index => $row) { 
    if ($row['prev'] == null) { 
    // This is the first row 
    $cur_row = $row; 
    break; // Jump out of the foreach loop 
    } 
} 
$sorted = array(); 
$sorted[] = $cur_row; 
while ($cur_row['next'] != null) { 
    // Find the next row 
    foreach($arr as $index => $row) { 
    if ($row['id'] = $cur_row['next']) { 
     // This is the next row 
     $sorted[] = $row; 
     $cur_row = $row; 
     break; // Jump out of the foreach loop 
    } 
    } 
} 
print_r($sorted); // $sorted now has your sorted array 

Answer 3

. A linked list is a list with linked objects, 관계가있는 개체 목록이 아닙니다. 기본적으로 두 컨테이너 중 최악의 상황입니다. 그 구조를 다른 데이터 컨테이너로 변환하려고합니다. 실제 링크 된 목록은 데이터를 정렬하는 데 필요한 방식으로 정렬 될 필요가 없습니다.

좋은 방법은 이와 비슷한 것이 될 것입니다. 목록의 중간에 개체를 삽입하는 방법을 여러분에게 남겨 드릴 것입니다. 그리 어렵지 않습니다. 자신에게 부탁을,

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

하지만 실제로는, 그리고 실제 작업을 수행합니다 일부 오컬트 이유 당신이 정말로, 정말로 배열을 필요로하는 경우

<?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" 
?> 

하지만, 여기 당신이 필요로하는 것이 무엇인가 개체가 아니라 배열을 사용하여 연결된 목록. 위의 정렬 방법은 제 생각에 제약 조건을 잘 알고 있지만, 은 어색하게 느립니다.은 각 ID에 대한 배열을 조회해야하기 때문입니다.

Answer 4

나는 첫 번째로 ID를 배열 키로 사용하여 라운드를 수행합니다. 동시에 첫 번째 요소를 녹음하십시오.

$newArray = array(): 
$firstElement = null; 
foreach($array as $row) { 
    $newArray[$row['id']] = $row; 
    if($row['prev'] == null) $firstElement = $row['id']; 
} 

그 후이 같은 목록을 반복 할 수 있습니다 : 당신이 당신의 데이터 하이드 레이터에서 (배열의 데이터베이스에서 데이터를의 얻을 기능)을 찾고 고려 수도 효율성을

$curId = $firstElement; 
while($curId != null) { 
    do_something($newArray[ $curId ]) 
    $curId = $newArray[ $curId ]['next']; 
} 

참조하거나 ID를 배열 키로 즉시 추가 할 수 있습니다. 또한 쿼리 정렬 순서로 첫 번째 요소가 항상 원래 배열의 첫 번째 요소인지 확인하여 해당 ID를 쉽게 찾을 수 있습니다.

Btw, 링크 된 목록은 다음 요소 (인덱스가 아님)에 대한 개체 참조로 특성 지어지기 때문에이 링크 된 구현을 호출하지 마십시오.

편집 : 아직 언급하지 않은 한 가지. 배열에서 정렬 된 목록을 원한다면 do_something ($ newArray [$ curId]); $ array [] = $ newArray [$ curId];와 함께.

저는이 솔루션이 전체 배열에 대해 2 라운드 비용이 들기 때문에 훨씬 더 투명하고 빠른 해결책이라고 생각합니다. 또는 비용을 들이지 않고 수분법의 첫 번째 부분을 통합 할 수 있다면 배열을 통해 한 번만 반복하십시오. . 당신이 코드 복사본의 같은 라인이 이유는 무엇입니까

Answer 5

이 코드를 붙여 넣기/세 번

$a[0] = array('0', '00', '000'); 
$a[1] = array('1', '11', '111'); 
$a[2] = array('2', '22', '222'); 
$a[3] = array('3', '33', '333'); 
$a[4] = array('4', '44', '444'); 
$result = count($a); 
echo $result; // print count 


list ($result1, $result2, $result3) = $a[4]; // array to list 
echo $result3; // print data in list