本文實例講述了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數據對象映射模式實例分析
