PHP实现双向链表的一例代码

2. /**
3. * **双向链表
4. * @author zhiyuan12@
5. * @modified 2012-10-25
6. * @site: bbs.it-home.org
7. */
8. /**
9. * 链表元素结点类
10. */
11. class Node_Element {
12. public $pre = NULL; // 前驱
13. public $next = NULL; // 后继
14. public $key = NULL; // 元素键值
15. public $data = NULL; // 结点值
16. function __Construct($key, $data) {
17. $this->key = $key;
18. $this->data = $data;
19. }
20. }
21. /**
22. * 双向链表类
23. */
24. class DoubleLinkedList {
25. private $head; // 头指针
26. private $tail; // 尾指针
27. private $current; // 当前指针
28. private $len; // 链表长度
29. function __Construct() {
30. $this->head = self::_getNode ( null, null );
31. $this->curelement = $this->head;
32. $this->tail = $this->head;
33. $len = 0;
34. }
35. /**
36. * @ desc: 读取链表全部结点
37. */
38. public function readAll() {
39. $tmp = $this->head;
40. while ( $tmp->next !== null ) {
41. $tmp = $tmp->next;
42. var_dump ( $tmp->key, $tmp->data );
43. }
44. }
45. public function move($pos1, $pos2) {
46. $pos1Node = $this->findPosition ( $pos1 );
47. $pos2Node = $this->findPosition ( $pos2 );
48. if ($pos1Node !== null && $pos2Node !== null) {
49. $tmpKey = $pos1Node->key;
50. $tmpData = $pos1Node->data;
51. $pos1Node->key = $pos2Node->key;
52. $pos1Node->data = $pos2Node->data;
53. $pos2Node->key = $tmpKey;
54. $pos2Node->data = $tmpData;
55. return true;
56. }
57. return false;
58. }
59. /**
60. * @ desc: 在指定关键词删除结点
61. *
62. * @param : $key
63. * 指定位置的链表元素key
64. */
65. public function delete($key) {
66. $pos = $this->find ( $key );
67. if ($pos !== null) {
68. $tmp = $pos;
69. $last = null;
70. $first = true;
71. while ( $tmp->next !== null && $tmp->next->key === $key ) {
72. $tmp = $tmp->next;
73. if (! $first) {
74. $this->delNode ( $last );
75. } else {
76. $first = false;
77. }
78. $last = $tmp;
79. }
80. if ($tmp->next !== null) {
81. $pos->pre->next = $tmp->next;
82. $tmp->next->pre = $pos->pre;
83. } else {
84. $pos->pre->next = null;
85. }
86. $this->delNode ( $pos );
87. $this->delNode ( $tmp );
88. }
89. }
90. /**
91. * @ desc: 在指定位置删除结点
92. *
93. * @param : $key
94. * 指定位置的链表元素key
95. */
96. public function deletePosition($pos) {
97. $tmp = $this->findPosition ( $pos );
98. if ($tmp === null) {
99. return true;
100. }
101. if ($tmp === $this->getTail ()) {
102. $tmp->pre->next = null;
103. $this->delNode ( $tmp );
104. return true;
105. }
106. $tmp->pre->next = $tmp->next;
107. $tmp->next->pre = $tmp->pre;
108. $this->delNode ( $tmp );
109. }
110. /**
111. * @ desc: 在指定键值之前插入结点
112. *
113. * @param : $key
114. * //指定位置的链表元素key
115. * @param : $data
116. * //要插入的链表元素数据
117. * @param : $flag
118. * //是否顺序查找位置进行插入
119. */
120. public function insert($key, $data, $flag = true) {
121. $newNode = self::_getNode ( $key, $data );
122. $tmp = $this->find ( $key, $flag );
123. if ($tmp !== null) {
124. $newNode->pre = $tmp->pre;
125. $newNode->next = $tmp;
126. $tmp->pre = $newNode;
127. $newNode->pre->next = $newNode;
128. } else {
129. $newNode->pre = $this->tail;
130. $this->tail->next = $newNode;
131. $this->tail = $newNode;
132. }
133. $this->len ++;
134. }
135. /**
136. * @ desc: 在指定位置之前插入结点
137. *
138. * @param : $pos
139. * 指定插入链表的位置
140. * @param : $key
141. * 指定位置的链表元素key
142. * @param : $data
143. * 要插入的链表元素数据
144. */
145. public function insertPosition($pos, $key, $data) {
146. $newNode = self::_getNode ( $key, $data );
147. $tmp = $this->findPosition ( $pos );
148. if ($tmp !== null) {
149. $newNode->pre = $tmp->pre;
150. $newNode->next = $tmp;
151. $tmp->pre = $newNode;
152. $newNode->pre->next = $newNode;
153. } else {
154. $newNode->pre = $this->tail;
155. $this->tail->next = $newNode;
156. $this->tail = $newNode;
157. }
158. $this->len ++;
159. return true;
160. }
161. /**
162. * @ desc: 根据key值查询指定位置数据
163. *
164. * @param : $key
165. * //指定位置的链表元素key
166. * @param : $flag
167. * //是否顺序查找
168. */
169. public function find($key, $flag = true) {
170. if ($flag) {
171. $tmp = $this->head;
172. while ( $tmp->next !== null ) {
173. $tmp = $tmp->next;
174. if ($tmp->key === $key) {
175. return $tmp;
176. }
177. }
178. } else {
179. $tmp = $this->getTail ();
180. while ( $tmp->pre !== null ) {
181. if ($tmp->key === $key) {
182. return $tmp;
183. }
184. $tmp = $tmp->pre;
185. }
186. }
187. return null;
188. }
189. /**
190. * @ desc: 根据位置查询指定位置数据
191. *
192. * @param : $pos
193. * //指定位置的链表元素key
194. */
195. public function findPosition($pos) {
196. if ($pos $this->len)
197. return null;
198. if ($pos len / 2 + 1)) {
199. $tmp = $this->head;
200. $count = 0;
201. while ( $tmp->next !== null ) {
202. $tmp = $tmp->next;
203. $count ++;
204. if ($count === $pos) {
205. return $tmp;
206. }
207. }
208. } else {
209. $tmp = $this->tail;
210. $pos = $this->len - $pos + 1;
211. $count = 1;
212. while ( $tmp->pre !== null ) {
213. if ($count === $pos) {
214. return $tmp;
215. }
216. $tmp = $tmp->pre;
217. $count ++;
218. }
219. }
220. return null;
221. }
222. /**
223. * @ desc: 返回链表头节点
224. */
225. public function getHead() {
226. return $this->head->next;
227. }
228. /**
229. * @ desc: 返回链表尾节点
230. */
231. public function getTail() {
232. return $this->tail;
233. }
234. /**
235. * @ desc: 查询链表节点个数
236. */
237. public function getLength() {
238. return $this->len;
239. }
240. private static function _getNode($key, $data) {
241. $newNode = new Node_Element ( $key, $data );
242. if ($newNode === null) {
243. echo "new node fail!";
244. }
245. return $newNode;
246. }
247. private function delNode($node) {
248. unset ( $node );
249. $this->len --;
250. }
251. }
252. // $myList = new DoubleLinkedList ();
253. // $myList->insert ( 1, "test1" );
254. // $myList->insert ( 2, "test2" );
255. // $myList->insert ( "2b", "test2-b" );
256. // $myList->insert ( 2, "test2-c" );
257. // $myList->insert ( 3, "test3" );
258. // $myList->insertPosition ( 5, "t", "testt" );
259. // $myList->readAll ();
260. // echo "+++";
261. // $myList->deletePosition(0);
262. // $myList->readAll ();
263. // echo "..." . $myList->getLength ();
264. // var_dump ( $myList->findPosition ( 3 )->data );
265. ?>

复制代码