酷站(www.ku0.com)-致力于为互联网从业者提供动力!

热门关键词:  企业  as  baidu  c4rp3nt3r  美女
酷站

【云小站】新老客都返现+现金红包+瓜分60万奖池
酷站

php

旗下栏目: php js asp Flex Ajax JSP jquery asp.net C语言 java 正则表达式 微信小程序 Android IOS

php实现映射操作的方法

来源:互联网搜集 作者:秩名 人气: 发布时间:2019-10-03
本篇文章主要介绍了php实现映射操作的方法,对大家的学习或者工作具有一定的参考学习价值,感兴趣的小伙伴们可以参考一下,也感谢大家对酷站(ku0.com)的支持。

映射

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

映射(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)

版权声明:本文内容来源于互联网或用户自行发布贡献,该文观点仅代表原作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 959677720#qq.cn(#换@) 举报,一经查实,本站将立刻删除。
原文链接:https://www.cnblogs.com/followyou/p/11388922.html

相关文章

  • php-7.3.6编译安装过程介绍

    php-7.3.6编译安装过程介绍

    1.、安装编译工具及库文件(使用yum命令安装) yum install -y apr* autoconf automake bison bzip2 bzip2* cloog-ppl cpp curl curl-devel fontconfig fontconfig-devel freetype freetype* freetype-devel gcc gcc-c++ gtk+-devel gd g......
    02-12
  • ThinkPHP5&5.1实现验证码的生成,使用及点击刷新

    ThinkPHP5&5.1实现验证码的生成,使用及点击刷新

    验证码现在是用户登录、支付等很多环节的必备元素,ThinkPHP55.1给我们提供了验证码的生成方式,也是非常的简单,在这里写一个完整的验证码验证的使用方法,供大家参考。 前台用户在登录时候需要验证码验证才能登录。首先使用Composer安......
    02-09
  • laravel邮件发送的代码教程

    laravel邮件发送的代码教程

    laravel自带SwiftMailer库,集成了多种邮件API,可以很方便的实现邮件的发送。在本教程中使用到的是SMTP(Simple Message Transfer Protocol)简单邮件传输协议,通常理解为邮件发送服务器。 以126邮箱为例 使用126邮箱的话,需要开启POP......
    01-31
  • Laravel框架自定义分页样式操作代码

    Laravel框架自定义分页样式操作代码

    操作步骤如下: (1) 对应public/css/paging.css 文件建立分页样式. (2) 控制器查出分页数据使用 paginate函数进行分页处理.(禁止使用group by处理查询). (3) 对应视图引入分页样式. 例如: paging.css 样式文件代码(复制即可用,实际操作过)......
    01-26
  • 实现Laravel jwt多表(多用户端)验证隔离教程

    实现Laravel jwt多表(多用户端)验证隔离教程

    Tips: tymon/jwt-auth 作者已通过增加 prv 字段修复这一问题#1167,但是如果你是用 dingo api + jwt 的话,该问题依然存在。# JWT 多表验证隔离 为什么要做隔离 当同一个 laravel 项目有多端(移动端、管理端......)都需要使用 jwt 做用......
    12-19
  • ThinkPHP类似AOP思想的参数验证的实现代码

    ThinkPHP类似AOP思想的参数验证的实现代码

    思路讲解:不管是在开发 API 还是做后台项目的时候,后端永远不要相信前端传输的参数,通常要做的是验证参数的合法性和安全性。那么在实际项目开发的时候,怎么简便的验证参数呢。 TP 提供了好几种参数验证的方式,比如验证器,独立验证......
    12-19
  • PHP实现微信公众号验证Token的教程

    PHP实现微信公众号验证Token的教程

    缘起 很久之前做过一次公众号的开发,当时就遇到了一个验证的小坑,但是由于时间紧任务急处理完了也就没在意,可谁知最近刚刚上马一个新的公众号项目又遇到了同样的小坑,痛定思痛决定奋笔疾书留下痕迹,省的以后再次忘记了。 开始验证 ......
    12-17
  • PHP防止sql注入小技巧之sql预处理原理与实现方法介绍

    PHP防止sql注入小技巧之sql预处理原理与实现方法介绍

    我们可以把sql预处理看作是想要运行的 SQL 的一种编译过的模板,它可以使用变量参数进行定制。 我们来看下它有什么好处: 预处理语句大大减少了分析时间,只做了一次查询(虽然语句多次执行)。 绑定参数减少了服务器带宽,你只需要发送......
    12-14
  • PHP实用小技巧之调用录像的方法

    PHP实用小技巧之调用录像的方法

    主要功能 把你实际的调用操作录下来,然后在你想要的地方重新调用 和匿名函数的作用基本一样,暂存你的调用操作 一般用于链式调用, 然后实际作用于你想要操作的对象上面 好像和没说一样 使用场景 假如 laravel 项目用到了 仓库模式, 然......
    12-06
  • laravel的框架中表单请求类型和CSRF防护

    laravel的框架中表单请求类型和CSRF防护

    laravel中为我们提供了绑定不同http请求类型的函数。 Route::get(/test, function () {});Route::post(/test, function () {});Route::put(/test, function () {});Route::patch(/test, function () {});Route::delete(/test, function (......
    11-24

最新更新