您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
今天就跟大家聊聊有关如何在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; } }
看完上述内容,你们对如何在php项目中实现一个映射操作有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注亿速云行业资讯频道,感谢大家的支持。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。