PHP中如何实现并处理链表

这篇“PHP中如何实现并处理链表”除了程序员外大部分人都不太理解，今天小编为了让大家更加理解“PHP中如何实现并处理链表”，给大家总结了以下内容，具有一定借鉴价值，内容详细步骤清晰，细节处理妥当，希望大家通过这篇文章有所收获，下面让我们一起来看看具体内容吧。

我们注重客户提出的每个要求，我们充分考虑每一个细节，我们积极的做好网站设计、做网站服务，我们努力开拓更好的视野，通过不懈的努力，成都创新互联公司赢得了业内的良好声誉，这一切，也不断的激励着我们更好的服务客户。 主要业务：网站建设,网站制作,网站设计,重庆小程序开发公司,网站开发,技术开发实力，DIV+CSS，PHP及ASP，ASP.Net，SQL数据库的技术开发工程师。

php有什么用

php是一个嵌套的缩写名称，是英文超级文本预处理语言，它的语法混合了C、Java、Perl以及php自创新的语法，主要用来做网站开发，许多小型网站都用php开发，因为php是开源的，从而使得php经久不衰。

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

形式：单链表、双链表、跳表（redis 集合数据结构就是跳表实现，时间复杂度O（log N））

跳表了解：https://lotabout.me/2018/skip-list/

php实现对链表的增删改查操作

定义节点类：

val  = $val;
        $this->next = $next;
    }


}

链表类：

head = new Node();
        $this->size  = 0;
    }

    //头插法
    public function addFirst( $value ){
//        $node = new Node($value);
//        $node->next = $this->head;
//        $this->head = $node;

        //简化
//        $this->head = new Node( $value, $this->head );
//        $this->size++;

        $this->add(0,$value);
    }

    /**指定索引位置插入
     * @param $index
     * @param $value
     * @throws Exception
     */
    public function add( $index, $value ){

        if( $index > $this->size )
            throw new Exception('超过链表范围');

//        if( $index==0 ){
//            $this->addFirst($value);
//        }else{
            $prev = $this->head;
            for($i=0;$i<$index;$i++){
                $prev = $prev->next;
            }

//            $node = new Node($value);
//            $node->next = $prev->next;
//            $prev->next = $node;

            $prev->next = new Node($value,$prev->next);
//        }

        $this->size++;
    }

    /**尾插法
     * @param $value
     */
    public function addLast( $value ){

        $this->add($this->size,$value);

    }


    /***
     * 编辑
     * @param $index
     * @param $value
     * @throws Exception
     */
    public function edit( $index, $value ){
        if( $index > $this->size-1 )
            throw new Exception('超过链表范围');

        $prev = $this->head->next;
        for($i=0;$i<=$index;$i++){
            if( $i==$index )
                $prev->val = $value;
            $prev = $prev->next;
        }

    }

    /**
     * 查询
     * @param $index
     * @return null
     * @throws Exception
     */
    public function select($index){
        if( $index > $this->size-1 )
            throw new Exception('超过链表范围');

        $prev = $this->head->next;
        for($i=0;$i<=$index;$i++){
            if( $i==$index )
                return $prev;
            $prev = $prev->next;
        }
    }


    /**删除
     * @param $index
     * @throws Exceptionr
     */
    public function delete( $index ){
        if( $index > $this->size-1 )
            throw new Exception('超过链表范围');

        $prev = $this->head;
        for($i=0;$i<=$index;$i++){
            if( $i==$index )
               $prev->next = $prev->next->next;
            $prev = $prev->next;
        }
        $this->size--;
    }

    /**检索值是否存在
     * @param $value
     * @return bool
     */
    public function iscontain( $value ){
        $prev = $this->head->next;
        while( $prev ){

            if( $prev->val==$value ){
                return true;
            }
            $prev = $prev->next;
        }

        return false;
    }

    /**转换为字符串
     * @return string
     */
    public function tostring(){

        $prev = $this->head->next;

        $r = [];
        while( $prev ){
            $r[] = $prev->val;
            $prev = $prev->next;
        }
        return implode('->',$r);

    }
    
     /**
      * 删除指定的节点值
      * @param $value
      */
      public function removeFileds( $value ){
           $prev = $this->head;
           while( $prev->next ){
               if( $prev->val == $value ){
                   $prev->val = $prev->next->val;
                   $prev->next = $prev->next->next;
               }else{
                   $prev = $prev->next;
               }
           }
      }
      
       /**
        * 通过递归方式删除指定的节点值
        * @param $value
        */
       public function removeFiledsByRecursion( $value ){
           $this->head = $this->removeByRecursion( $this->head ,$value);
           return $this->head;
       }
   
        public function removeByRecursion( $node , $value, $level=0 ){
               if( $node->next == null ){
                   $this->showDeeep($level,$node->val);
                   return $node->val == $value ? $node->next:$node;
               }
       
               $this->showDeeep($level,$node->val);
               $node->next = $this->removeByRecursion( $node->next,$value,++$level );
               $this->showDeeep($level,$node->val);
               return $node->val == $value ? $node->next:$node;
           }
       
        /**
        * 显示深度
        * 帮助理解递归执行过程，回调函数执行层序遵循系统栈 
        * @param int $level 深度层级
        * @param $val
        * @return bool
        */
        public function showDeeep( $level=1,$val ){
             if( $level<1 ){
                 return false;
             }
    
             while($level--){
                 echo '-';
             }
             echo "$val\n";
        }

}

调用操作如下：

addFirst(1);
$node->add(1,7);
$node->add(2,10);
$node->edit(1,8);
var_dump($node->select(1)) ;
$node->delete(1);
$node->addLast(99);
var_dump($node->iscontain(2));
var_export($node);
var_export($node->tostring());

分析下链表操作的时间复杂度：

增： O(n)  只对链表头操作：O(1)

删： O(n)  只对链表头操作：O(1)

改：O(n)

查：O(n)   只对链表头操作：O(1)

利用链表实现栈

addFirst($value);
    }

    /**
     * @return mixed
     */
    public function pop(){
        $r = $this->head->next->val;
        $this->delete(0);
        return $r;
    }
}

push(1);
        $stack->push(3);
        $stack->push(6);
        $stack->push(9);

        print_r($stack->pop());
        print_r($stack->head);

链表实现队列

head->val==null ){
            $this->tail = new Node( $value );
            $this->head = $this->tail;
        }else{
            $this->tail->next =  new Node( $value );
            $this->tail = $this->tail->next;
        }
        $this->size++;
    }

    /**
     * pop
     * @return null
     * @throws \Exception
     */
    public function pop(){
        if( $this->size<=0 )
            throw new \Exception('超过链表范围');
        $val = $this->head->val;
        $this->head = $this->head->next;

        $this->size--;
        return $val;
    }

    /**
     * 查看队首
     */
    public function checkHead(){
        return $this->head->val;
    }

    /**
     * 查看队尾
     */
    public function checkEnd(){
        return $this->tail->val;
    }

    /**
     * toString
     */
    public function toString(){
        $r = [];
        while( $this->head ){
            $r[] = $this->head->val;
            $this->head = $this->head->next;
        }
        return implode('->',$r);
    }
}

测试

push(1);
        $stack->push(3);
        $stack->push(6);
        $stack->push(9);

        print_r($stack->pop());
        print_r($stack->head);
        print_r($stack->checkHead());
        print_r($stack->checkEnd());
        print_r($stack->toString());
/**        
1
app\models\Node Object
(
    [val] => 3
    [next] => app\models\Node Object
        (
            [val] => 6
            [next] => app\models\Node Object
                (
                    [val] => 9
                    [next] => 
                )

        )

)
3
9
3->6->9
**/

感谢你的阅读，希望你对“PHP中如何实现并处理链表”这一关键问题有了一定的理解，具体使用情况还需要大家自己动手实验使用过才能领会，快去试试吧，如果想阅读更多相关知识点的文章，欢迎关注创新互联行业资讯频道！