php实现映射操作的方法_F11 - 专业站长和开发者的学习网站

分享到

php实现映射操作的方法

php 来源：互联网搜集作者：秩名发布时间：2019-10-03 23:04:49 人浏览

摘要

映射映射，或者射影，在数学及相关的领域经常等同于函数。基于此，部分映射就相当于部分函数，而完全映射相当于完全函数。映射（Map）是用于存取键值对的数据结构（key,value），一个键只能对应一个值且键不能重复。实现映射的实现方式可以使用链表或二

映射

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

映射（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）

您可能感兴趣的文章 :

原文链接 : https://www.cnblogs.com/followyou/p/11388922.html

Tag : PHP(381)映射(3)

PHP获取系统毫秒数时间方法

前言 php中获取时间方法是date()，在php中获取时间戳方法有time()、strtotime()； date()：date(format, timestamp)，format为格式、timestamp为时间戳（可选
PHP中的DI依赖注入的详细介绍

什么是 DI / 依赖注入依赖注入DI 其实本质上是指对类的依赖通过构造器完成自动注入通俗来说，就是你当前操作一个类，但是这个类的某
PHP8.1 Fiber交叉执行多任务（附代码）

拿平时大家写的 for 循环举例。像 go 你可以写两个go每个里面各写一个循环同时输入，你可以看到输出是交替。在过去的php版本中，如果只开
PHP8.0的编译安装与使用的介绍

安装与配置本次使用的操作系统Ubuntu 18.04.4 LTS 安装 1.准备必要库 1 2 apt-get install -y autoconf libxml2-dev libsqlite3-dev \ libcurl4-openssl-dev libssl-dev l
Mac如何编译PHP 8.0 到MxSrvs工具

开始准备工作下载 PHP 8.0 PHP 官方下载 https://www.php.net/downloads.php 进入到 MxSrvs 的主程序路径下的/Applications/MxSrvs/bin，根据 Mxsrvs 的命名规则，
PHP8 中的 JIT的详细介绍

PHP 8 的 JIT（Just In Time）编译器将作为扩展集成到 php 中 Opcache 扩展用于运行时将某些操作码直接转换为从 cpu 指令。这意味着使用JIT后，
PHP8.2不再支持字符串中用${}插入变量了

PHP 社区 4 月底通过了一项只有一张反对票的提案，提案内容是在即将发布的 PHP 8.2 中，不再支持使用 ${} 在字符串中插入变量的语法（标记
PHP8.2两个新的强类型：null和false的详细介绍

PHP 从 7.0 开始不断地在完善强类型，我们可以给方法参数、返回值、类属性等声明类型。强类型可以让代码更加健壮，易于维护，可读性增
PHP从txt文件中读取数据的介绍

一、打开/关闭文件 1、对文件操作时首先要打开文件，打开文件用 fopen（）函数，语法是： fopen(filename,mode,include_path,context); 2、对文件操作
PHP中token的生成

php token的生成接口特点汇总： 1、因为是非开放性的，所以所有的接口都是封闭的，只对公司内部的产品有效； 2、因为是非开放性的，所以