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）