php实现映射操作实例详解

这篇文章主要介绍了php实现映射操作,结合实例形式详细分析了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; } }