• 企业400电话
  • 微网小程序
  • AI电话机器人
  • 电商代运营
  • 全 部 栏 目

    企业400电话 网络优化推广 AI电话机器人 呼叫中心 网站建设 商标✡知产 微网小程序 电商运营 彩铃•短信 增值拓展业务
    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数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

    希望本文所述对大家PHP程序设计有所帮助。

    您可能感兴趣的文章:
    • 详解PHP的Laravel框架中Eloquent对象关系映射使用
    • ThinkPHP中公共函数路径和配置项路径的映射分析
    • 回答PHPCHINA上的几个问题:URL映射
    • 解密ThinkPHP3.1.2版本之模块和操作映射
    • PHP实现路由映射到指定控制器
    • 浅析php设计模式之数据对象映射模式
    • PHP面向对象之领域模型+数据映射器实例(分析)
    • 老生常谈PHP面向对象之标识映射
    • PHP实现的数据对象映射模式详解
    • PHP数据对象映射模式实例分析
    上一篇:PHP-FPM 设置多pool及配置文件重写操作示例
    下一篇:laravel-admin 中列表筛选方法
  • 相关文章
  • 

    © 2016-2020 巨人网络通讯 版权所有

    《增值电信业务经营许可证》 苏ICP备15040257号-8

    php实现映射操作实例详解 php,实现,映射,操作,实例,