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 />";
}

スクリプトは2回目のプッシュでハングアウトし、max_execution_timeエラーが発生します。

通常のLinkedListとして、上記のようにcalsの2行30と38を変更すると、正常に機能します。（最初のノードへの最後のノードリンクを削除することによって）。

それで、問題は何ですか、そしてそれをどのように解決するのですか？

更新：関数をこれに変更することにより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++;       
}
4

2 に答える 2

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 に答える
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 に答える