2

我写了这个类来实现链表： 

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错误。

如果我将 cals 的两行 30 和 38 更改为正常的 LinkedList，则效果很好。（通过删除最后一个节点链接到第一个节点）。

那么问题是什么以及如何解决呢？

更新：通过将push()函数更改为 this ，它可以作为线性链表正常工作： 

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++;       
}
4

2 回答 2

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
   )
于 2012-11-06T14:57:52.893 回答
1

您可以使用

$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;
    }
}
于 2012-11-06T15:00:36.500 回答