本文实例讲述了php实现映射操作。分享给大家供大家参考，具体如下：
映射
映射，或者射影，在数学及相关的领域经常等同于函数。基于此，部分映射就相当于部分函数，而完全映射相当于完全函数。
映射（Map）是用于存取键值对的数据结构（key,value），一个键只能对应一个值且键不能重复。
实现
映射的实现方式可以使用链表或二叉树实现。
链表实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
<?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; }} |
测试：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
<?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 |
二叉树实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
|
<?phpclass 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
