评论

收藏

[PHP] php实现映射操作实例详解

开发技术 开发技术 发布于:2021-08-26 15:31 | 阅读数:375 | 评论:0

本文实例讲述了php实现映射操作。分享给大家供大家参考,具体如下:

映射
映射,或者射影,在数学及相关的领域经常等同于函数。基于此,部分映射就相当于部分函数,而完全映射相当于完全函数。
映射(Map)是用于存取键值对的数据结构(key,value),一个键只能对应一个值且键不能重复。

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


链表实现:
<?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程序设计有所帮助。
原文链接:https://www.cnblogs.com/followyou/p/11388922.html

关注下面的标签,发现更多相似文章