php实现映射操作实例详解

本文实例讲述了服务器端编程语言(专业超文本预处理器的缩写)实现映射操作。分享给大家供大家参考，具体如下：

映射

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

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

实现

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

链表实现：

?php/** *接口字典*接口字典* @包应用\模型*/接口字典{公共函数集($key，$ value)；公共函数get($ key)；公共函数isExist($ key)；公共函数delete($ key)；公共函数getSize()；}类字典链接列表实现了dict { protected $ size=0；公共$密钥公共$值；public $ next public function _ _ construct($ key=null，$value=null，$ next=null){ $ this-key=$ key；$ this-value=$ value；$ this-next=$ next；}公共函数集($key，$ value){ $ node=$ this；而($ node $ node-next){ if($ node-next-key==$ key){ $ node-next-value=$ value；返回$ node-next；} $ node=$ node-next；} $node-next=new self($key，$value，$ node-next)；$这个尺寸；返回$ node-next；} public function get($ key){ $ node=$ this；while($ node){ if($ node-key==$ key){ return $ node-value；} $ node=$ node-next；}抛出新\异常('找不到键');}公共函数isExist($ key){ $ node=$ this；while($ node){ if($ node-key==$ key){ return true；} $ node=$ node-next；}返回false}公共函数删除($key) { if($this-size==0)抛出新\异常('键不存在');$ node=$ this而($ node-next){ if($ node-next-key==$ key){ $ node-next=$ node-next-next；$这个大小的-;打破；} $ node=$ node-next；}返回$ this}公共函数getSiZe(){ return $ this-SiZe；}}测试：

？PHP $ dict=new dict link list()；$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//假//真//2

二叉树实现

?phpclass DictBtree实现Dict { public $ key公共$值；公共$左公共$对私人$大小；public function _ _ construct($ key=null，$ value=null){ $ this-key=$ key；$ this-value=$ value；$ this-left=null；$ this-right=null；$ this-size=0；}公共函数集($key，$ value){ if($ this-size==0){ $ node=new static($ key，$ value)；$this-key=节点-钥匙；$ this-value=$ node-value；$这个尺寸；} else { $ node=$ this while($ node){ if($ node-key==$ key){ $ node-value=$ value；打破；} if($ node-key $ key){ if($ node-left==null){ $ node-left=new static($ key，$ value)；$这个尺寸；打破；} $ node=$ node-left；} else { if($ node-right==null){ $ node-right=new static($ key，$ value)；$这个尺寸；打破；} $ node=$ node-right；} } }返回$ this}公共函数get($key ){ if($this-size==0)抛出新\异常('空')；$ node=$ this while($ node){ if($ node-key==$ key){ return $ node-value；} if($ node-key $ key){ $ node=$ node-left；} else { $ node=$ node-right；} }抛出新的\异常("此键不存在");}公共函数isExist($key ){ if($this-size==0)返回false $ node=$ this while($ node){ if($ node-key==$ key){返回true} if($ node-key $ key){ $ node=$ node-left；} else { $ node=$ node-right；} }返回false}公共函数删除($key){ //找到元素，寻找元素左边最小元素$ node=$ this-select($ key)；if($node-right！=null){ $ node 1=$ node-selectMin($ node-right)；//替换当前节点$ node-key=$ node 1-key；$ node-value=$ node 1-value；//删除$节点-右侧最小元素，获取最终元素赋给$ node-right $ nodeMin=$ this-delete min($ node-right)；$ node-right=$ nodeMin；} else { $ node 1=$ node-SelectMax($ node-left)；$ node-key=$ node 1-key；$ node-value=$ node 1-value；$ NodeMax=$ this-delete max($ node-left)；$ node-left=$ nodeMax；}返回$ this}受保护函数删除min($ node){//if($ this-size==0)//抛出新\异常('空')；//$ prev=new static()；//$ prev-left=$ node；//while($prev-left-left！=null){////$ prev=$ prev-left；//}//$ prev-left=$ prev-left-right；if($ node-left==null){ $ right node=$ node-right；$ node-right=null；$这个大小的-;返回$ right node } $ node-left=$ this-delete min($ node-left)；返回$ node}受保护函数删除max($ node){ if($ node-right==null){ $ left node=$ node-left；$ node-left=null；$这个大小的-;返回$ left node } $ node-right=$ this-delete max($ node-right)；返回$ node}公共函数getSiZe(){ return $ this-SiZe；}公共函数select($ key){ $ node=$ this；while($ node){ if($ node-key==$ key){ return $ node；} if($ node-key $ key){ $ node=$ node-left；} else { $ node=$ node-right；} }抛出新的\异常("此键不存在");}公共函数选择min($ node){ while($ node-left){ $ node=$ node-left；}返回$ node}公共函数select max($ node){ while($ node-right){ $ node=$ node-right；}返回$ node}}

复杂度分析

链表O(n)

二分搜索树o(对数n)

更多对PHP相关内容感兴趣的读者可以查看本网站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》、《PHP数学运算技巧总结》、0103010

希望本文对PHP编程有所帮助。