PHP循环链表实现

Question

我写这个类来实现链表：

class Node{ 
    public $data; 
    public $link; 

    function __construct($data, $next = NULL){ 
     $this->data = $data; 
     $this->link = $next; 
    }  
} 

class CircularLinkedList{ 
    private $first; 
    private $current; 
    private $count; 

    function __construct(){ 
     $this->count = 0; 
     $this->first = null; 
     $this->current = null; 
    } 

    function isEmpty(){ 
     return ($this->first == NULL); 
    } 

    function push($data){ 
     //line 30 
     $p = new Node($data, $this->first); 
     if($this->isEmpty()){ 
      $this->first = $p; 
      $this->current = $this->first; 
     } 
     else{   
      $q = $this->first; 
      //line 38 
      while($q->link != $this->first) 
       $q = $q->link; 
      $q->link = $p;  
     } 
     $this->count++;  
    } 

    function find($value){ 
     $q = $this->first; 
     while($q->link != null){ 
      if($q->data == $value) 
       $this->current = $q; 
      $q = $q->link;  
     } 
     return false;  
    } 

    function getNext(){ 
     $result = $this->current->data; 
     $this->current = $this->current->link; 
     return $result;   
    } 
} 

但是当我试图把一些价值，

$ll = new CircularLinkedList(); 

$ll->push(5); 
$ll->push(6); 
$ll->push(7); 
$ll->push(8); 
$ll->push(9); 
$ll->push(10); 

//$ll->find(7); 

for($j=0;$j<=30;$j++){ 
    $result = $ll->getNext(); 
    echo $result."<br />"; 
} 

脚本在第二推挂出并给出max_execution_time错误。

它工作正常，如果我改变上面所示calss的两条线30和38，作为一个正常的LinkedList。 （通过删除到第一个节点的最后一个节点链接）。

那么这有什么问题，以及如何解决它？

UPDATE：通过改变push()功能这一点，工作细如线性链表：

function push($data){ 
    $p = new Node($data); 
    if($this->isEmpty()){ 
     $this->first = $p; 
     $this->current = $this->first; 
    } 
    else{ 
     $q = $this->first; 
     while($q->link != null) 
      $q = $q->link; 
     $q->link = $p;  
    } 
    $this->count++;  
} 

Answer 1

对于线性链表 - 以下变化：

 function push($data){ 

     if($this->isEmpty()){ 
     $this->first = new Node($data); 
     $this->current = $this->first; 
     $this->count++; 
     } 
     else{ 

     $this->current->link = new Node($data); 
     $this->current = $this->current->link; 
     $this->count++; 

     } 

    } 

这种结构的产量：

CircularLinkedList Object 
    (
     [first:CircularLinkedList:private] => Node Object 
     (
     [data] => 2 
     [link] => Node Object 
      (
       [data] => 10 
       [link] => Node Object 
        (
         [data] => 3 
         [link] => Node Object 
          (
           [data] => 9 
           [link] => 
          ) 

        ) 

      ) 

    ) 

    [current:CircularLinkedList:private] => Node Object 
    (
     [data] => 9 
     [link] => 
    ) 

    [count:CircularLinkedList:private] => 4 
) 

对于圆形 - 改成这样：

 function push($data){ 

     if($this->isEmpty()){ 
     $this->first = new Node($data); 
     $this->current = $this->first; 
     $this->count++; 
     } 
     else{ 

     $this->current->link = new Node($data, $this->first); 
     $this->current = $this->current->link; 
     $this->count++; 

     } 

    } 

这种结构产生了：

CircularLinkedList Object 
    (
     [first:CircularLinkedList:private] => Node Object 
     (
     [data] => 2 
     [link] => Node Object 
      (
       [data] => 10 
       [link] => Node Object 
        (
         [data] => 3 
         [link] => Node Object 
          (
           [data] => 9 
           [link] => Node Object 
     *RECURSION* 
          ) 

        ) 

      ) 

     ) 

    [current:CircularLinkedList:private] => Node Object 
    (
     [data] => 9 
     [link] => Node Object 
      (
       [data] => 2 
       [link] => Node Object 
        (
         [data] => 10 
         [link] => Node Object 
          (
           [data] => 3 
           [link] => Node Object 
     *RECURSION* 
          ) 

        ) 

      ) 

    ) 

    [count:CircularLinkedList:private] => 4 
    ) 

Answer 2

您可以使用

$ll = new CircularLinkedList(); 

$ll->push(5); 
$ll->push(6); 
$ll->push(7); 
$ll->push(8); 
$ll->push(9); 
$ll->push(10); 
echo "<pre>"; 

使用

echo count($ll); // returns 6 

$ll->find(7); 
echo $ll->getCurrent(); // returns 7 


$ll->reset(); // Reset from current position to beginning 

while ($ll->isValid()) { 
    echo $ll->getCurrent() . "<br />"; 
    $ll->getNext(); 
} 

输出

5 
6 
7 
8 
9 
10 

等级节点

class Node { 
    public $data; 
    public $link; 

    function __construct($data, $next = NULL) { 
     $this->data = $data; 
     $this->link = $next; 
    } 

    function __toString() { 
     return "$this->data"; 
    } 
} 

类CircularLinkedList

class CircularLinkedList implements Countable { 
    private $data; 
    private $current; 
    private $count; 

    function __construct() { 
     $this->count = 0; 
     $this->data = null; 
     $this->current = null; 
    } 

    function isEmpty() { 
     return ($this->data == NULL); 
    } 

    function push($data) { 
     $p = new Node($data); 
     if ($this->isEmpty()) { 
      $this->data = $p; 
      $this->current = $this->data; 
     } else { 
      $this->current->link = $p ; 
      $this->current = $this->current->link; 
     } 
     $this->count ++; 
    } 

    function find($value) { 
     $q = $this->data; 
     while ($q->link != null) { 
      if ($q->data == $value) 
       $this->current = $q; 
      $q = $q->link; 
     } 
     return false; 
    } 

    function getCurrent() { 
     return $this->current; 
    } 

    function getNext() { 
     $this->current = $this->current->link; 
    } 

    function hasNext() { 
     return isset($this->current->link); 
    } 

    function isValid() { 
     return isset($this->current); 
    } 

    function reset() { 
     $this->current = $this->data; 
    } 

    function count() { 
     return $this->count; 
    } 
}