PHP实现链表

蘇甦發表於 2019-7-10 10:00:00

<p></p><div class="toc"><div class="toc-container-header">目录</div><ul><li>链表</li><li>php实现对链表的增删改查操作</li><li>利用链表实现栈</li><li>链表实现队列</li></ul></div><p></p>
<h1 id="链表">链表</h1>
<p>链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。</p>
<p>形式：单链表、双链表、跳表（redis 集合数据结构就是跳表实现，时间复杂度O（log N））</p>
<p>跳表了解：https://lotabout.me/2018/skip-list/</p>
<h1 id="php实现对链表的增删改查操作">php实现对链表的增删改查操作</h1>
<p>定义节点类：</p>
<pre><code class="language-PHP"><?php
class Node
{
public $val;
public $next;

public function __construct( $val = null, $next = null )
{
   $this->val= $val;
   $this->next = $next;
}

}
</code></pre>
<p>链表类：</p>
<pre><code class="language-php"><?php
/**链表
* Class Linklist
* @package app\models
*/
class Linklist
{
public $head;       //头节点(默认一个虚拟头节点)
public $size;       //长度

public function __construct()
{
   $this->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";
   }

}
</code></pre>
<p>调用操作如下：</p>
<pre><code class="language-php"><?php
$node = new Linklist();
$node->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());
</code></pre>
<p>分析下链表操作的时间复杂度：</p>
<pre><code>增： O(n)只对链表头操作：O(1)

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

改：O(n)

查：O(n) 只对链表头操作：O(1)
</code></pre>
<h1 id="利用链表实现栈">利用链表实现栈</h1>
<pre><code class="language-php"><?php
/**
* 链表实现栈
* Class LinklistStack
* @package app\models
*/
class LinklistStack extends Linklist
{
/**
* @param $value
*/
public function push( $value ){
   $this->addFirst($value);
}

/**
* @return mixed
*/
public function pop(){
   $r = $this->head->next->val;
   $this->delete(0);
   return $r;
}
}
</code></pre>
<pre><code class="language-php"><?php
   $stack = new LinklistStack();
   $stack->push(1);
   $stack->push(3);
   $stack->push(6);
   $stack->push(9);

   print_r($stack->pop());
   print_r($stack->head);
</code></pre>
<h1 id="链表实现队列">链表实现队列</h1>
<p><img src="https://raw.githubusercontent.com/WalkingSun/WindBlog/gh-pages/images/blog/linklist_queue.png" alt="image" loading="lazy"></p>
<pre><code class="language-php"><?php

/**
* 链表实现队列
* Class LinkListQueue
* @package app\models
*/
class LinkListQueue extends Linklist
{
public $tail; //尾节点

/**
* push
* @param $value
*/
public function push( $value ){

   if( $this->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);
}
}
</code></pre>
<p>测试</p>
<pre><code class="language-php"><?php
$stack = new LinkListQueue();
   $stack->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
(
=> 3
=> app\models\Node Object
   (
         => 6
         => app\models\Node Object
            (
               => 9
               =>
            )

   )

)
3
9
3->6->9
**/
</code></pre><br><br>
来源：https://www.cnblogs.com/followyou/p/11162030.html

頁: [1]

琼殿技术论坛's Archiver

PHP实现链表