php实现映射操作实例详解

php  /  管理员 发布于 7年前   480

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

映射

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

映射（Map）是用于存取键值对的数据结构（key,value），一个键只能对应一个值且键不能重复。

实现

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

链表实现：

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;  }}

测试：

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

二叉树实现

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数据对象映射模式实例分析