浅谈php实现映射的两种方法（链表和二叉树）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了浅谈php实现映射的两种方法（链表和二叉树），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5190字，纯文字阅读大概需要8分钟。
内容图文
本篇文章给大家介绍一下php使用链表或二叉树来实现映射的方法。有一定的参考价值，有需要的朋友可以参考一下，希望对大家有所帮助。
【推荐学习：《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实现映射的两种方法（链表和二叉树）的详细内容。
本文系统来源：https://www.php.cn/php-weizijiaocheng-471503.html内容总结
以上是互联网集市为您收集整理的浅谈php实现映射的两种方法（链表和二叉树）全部内容，希望文章能够帮你解决浅谈php实现映射的两种方法（链表和二叉树）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】