浅谈php实现映射的两种方法（链表和二叉树）

本篇文章给大家介绍一下php使用链表或二叉树来实现映射的方法。有一定的参考价值，有需要的朋友可以参考一下，希望对大家有所帮助。

【推荐学习：《PHP视频教程》】

映射

映射，或者射影，在数学及相关的领域经常等同于函数。基于此，部分映射就相当于部分函数，而完全映射相当于完全函数。

映射（Map）是用于存取键值对的数据结构（key,value），一个键只能对应一个值且键不能重复。

实现

映射的实现方式可以使用链表或二叉树实现。

链表实现：

<?php
/**
 * 接口 字典
 * Interface Dict
 * @package app\models
 */
Interface Dict
{

    public function set( $key , $value );

    public function get( $key );

    public function isExist( $key );

    public function delete($key);

    public function getSize();


}

class DictLinkList implements Dict
{
    protected $size=0;
    public $key;
    public $value;
    public $next;

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

    public function set($key,$value){
   $node = $this;
   while( $node && $node->next ){
  if( $node->next->key==$key ){
 $node->next->value = $value;
 return $node->next;
  }
  $node = $node->next;
   }

   $node->next =  new self($key,$value,$node->next);
   $this->size++;
   return  $node->next;
    }


    public function get($key){
   $node = $this;
   while($node){
  if( $node->key ==$key  ){
 return $node->value;
  }
  $node = $node->next;
   }

   throw new \Exception('cannot found key');
    }


    public function isExist($key)
    {
   $node = $this;
   while($node){
  if( $node->key ==$key  ){
 return true;
  }
  $node = $node->next;
   }
   return false;
    }

    public function delete($key)
    {
   if( $this->size==0)
  throw new \Exception('key is not exist');

   $node = $this;
   while($node->next){
  if( $node->next->key == $key  ){
 $node->next = $node->next->next;
 $this->size--;
 break;
  }
  $node = $node->next;
   }

   return $this;
    }

    public function getSize()
    {
   return $this->size;
    }
}

测试：

<?php
   $dict = new DictLinkList();
   $dict->set('sun',111); //O(n)
   $dict->set('sun',222);
   $dict->set('w',111);
   $dict->set('k',111);
   var_dump($dict->get('w'));   //O(n)
   var_dump($dict->isExist('v'));   //O(n)
   var_dump($dict->delete('sun'));    //O(n)
   var_dump($dict->getSize());
   
/******************************************/
//111
//false
//true
//2

二叉树实现

<?php
class DictBtree implements Dict
{
    public $key;
    public $value;

    public $left;
    public $right;
    private $size;

    public function __construct($key=null,$value=null)
    {
   $this->key = $key;
   $this->value = $value;
   $this->left = null;
   $this->right = null;
   $this->size = 0;
    }

    public function set( $key , $value ){
   if( $this->size ==0 ){
  $node = new static( $key,$value );
  $this->key = $node->key;
  $this->value = $node->value;
  $this->size++;
   }else{
  $node = $this;
  while($node){
 if( $node->key == $key ){
$node->value = $value;
break;
 }
 if($node->key>$key){
if($node->left==null){
    $node->left = new static( $key,$value );
    $this->size++;
    break;
}
$node = $node->left;
 }else{
if($node->right==null){
    $node->right = new static( $key,$value );
    $this->size++;
    break;
}
$node = $node->right;
 }
  }
   }

   return $this;
    }

    public function get( $key ){
   if( $this->size ==0 )
  throw new \Exception('empty');
   $node = $this;
   while($node) {
  if ($node->key == $key) {
 return $node->value;
  }
  if ($node->key > $key) {
 $node = $node->left;
  } else {
 $node = $node->right;
  }
   }
   throw new \Exception('this key not exist');
    }

    public function isExist( $key ){
   if( $this->size ==0 )
  return false;
   $node = $this;
   while($node) {
  if ($node->key == $key) {
 return true;
  }
  if ($node->key > $key) {
 $node = $node->left;
  } else {
 $node = $node->right;
  }
   }
   return false;
    }

    public function delete($key){

   //找到元素，寻找元素左边最小元素
   $node = $this->select($key);
   if( $node->right!=null ){
  $node1 = $node->selectMin($node->right);

  //替换当前node
  $node->key = $node1->key;
  $node->value = $node1->value;

  //删除$node->right最小元素，获取最终元素赋给$node->right
  $nodeMin = $this->deleteMin($node->right);
  $node->right = $nodeMin;
   }else{
  $node1 = $node->selectMax($node->left);

  $node->key = $node1->key;
  $node->value = $node1->value;

  $nodeMax = $this->deleteMax($node->left);
  $node->left = $nodeMax;
   }

  return $this;

    }

    protected function deleteMin( $node ){
//   if( $this->size ==0 )
//  throw new \Exception('empty');

//   $prev = new static();
//   $prev->left = $node;
//   while($prev->left->left!=null){
//
//  $prev = $prev->left;
//   }
//   $prev->left = $prev->left->right;

   if( $node->left==null ){
  $rightNode = $node->right;
  $node->right = null;
  $this->size--;
  return $rightNode;
   }

  $node->left = $this->deleteMin($node->left);

   return $node;
    }

    protected function deleteMax($node){

   if( $node->right==null ){
  $leftNode = $node->left;
  $node->left = null;
  $this->size--;
  return $leftNode;
   }

   $node->right = $this->deleteMax($node->right);
   return $node;

    }

    public function getSize(){
   return $this->size;
    }


    public function select($key){
   $node = $this;

   while($node){
  if($node->key==$key){
 return $node;
  }
  if ($node->key > $key) {
 $node = $node->left;
  } else {
 $node = $node->right;
  }
   }

   throw new \Exception('this key not exist');
    }

    public function selectMin( $node ){
   while($node->left){

  $node = $node->left;
   }
   return $node;
    }


    public function selectMax( $node ){
   while($node->right){

  $node = $node->right;
   }
   return $node;
    }
}

复杂度分析

链表 O(n)

二分搜索树 O（log n）

更多编程相关知识，请访问：编程视频！！

以上就是浅谈php实现映射的两种方法（链表和二叉树）的详细内容！

查看更多关于浅谈php实现映射的两种方法（链表和二叉树）的详细内容...