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

二叉树实现

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

<?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.cnblogs.com/followyou/p/11388922.html

php实现映射操作实例详解

映射

实现

链表实现：

相关文章

快网idc优惠网

映射

实现

链表实现：

二叉树实现

复杂度分析

相关文章

微信

快网idc优惠网

QQ交流群