天天综合日日夜夜,暴草美女,日韩一区二区三区精品

本文實例講述了PHP雙向鏈表定義與用法。分享給大家供大家參考，具體如下：

由于需要對一組數據多次進行移動操作，所以寫個雙向鏈表。但對php實在不熟悉，雖然測試各個方法沒啥問題，就是不知道php語言深層的這些指針和unset有什么注意的地方，貼出來讓大家教育吧。效率沒測試....求諒解～

001<?php
002/**
003 * **雙向鏈表
004 * @author zhiyuan12@
005 */
006/**
007 * 鏈表元素結點類
008 */
009class Node_Element {
010  public $pre = NULL; // 前驅
011  public $next = NULL; // 后繼
012  public $key = NULL; // 元素鍵值
013  public $data = NULL; // 結點值
014  function __Construct($key, $data) {
015    $this->key = $key;
016    $this->data = $data;
017  }
018}
019/**
020 * 雙向鏈表類
021 */
022class DoubleLinkedList {
023  private $head; // 頭指針
024  private $tail; // 尾指針
025  private $current; // 當前指針
026  private $len; // 鏈表長度
027  function __Construct() {
028    $this->head = self::_getNode ( null, null );
029    $this->curelement = $this->head;
030    $this->tail = $this->head;
031    $len = 0;
032  }
033  /**
034   * @ desc: 讀取鏈表全部結點
035   */
036  public function readAll() {
037    $tmp = $this->head;
038    while ( $tmp->next !== null ) {
039      $tmp = $tmp->next;
040      var_dump ( $tmp->key, $tmp->data );
041    }
042  }
043  public function move($pos1, $pos2) {
044    $pos1Node = $this->findPosition ( $pos1 );
045    $pos2Node = $this->findPosition ( $pos2 );
046    if ($pos1Node !== null && $pos2Node !== null) {
047      $tmpKey = $pos1Node->key;
048      $tmpData = $pos1Node->data;
049      $pos1Node->key = $pos2Node->key;
050      $pos1Node->data = $pos2Node->data;
051      $pos2Node->key = $tmpKey;
052      $pos2Node->data = $tmpData;
053      return true;
054    }
055    return false;
056  }
057  /**
058   * @ desc: 在指定關鍵詞刪除結點
059   *
060   * @param : $key
061   *     指定位置的鏈表元素key
062   */
063  public function delete($key) {
064    $pos = $this->find ( $key );
065    if ($pos !== null) {
066      $tmp = $pos;
067      $last = null;
068      $first = true;
069      while ( $tmp->next !== null && $tmp->next->key === $key ) {
070        $tmp = $tmp->next;
071        if (! $first) {
072          $this->delNode ( $last );
073        } else {
074          $first = false;
075        }
076        $last = $tmp;
077      }
078      if ($tmp->next !== null) {
079        $pos->pre->next = $tmp->next;
080        $tmp->next->pre = $pos->pre;
081      } else {
082        $pos->pre->next = null;
083      }
084      $this->delNode ( $pos );
085      $this->delNode ( $tmp );
086    }
087  }
088  /**
089   * @ desc: 在指定位置刪除結點
090   *
091   * @param : $key
092   *     指定位置的鏈表元素key
093   */
094  public function deletePosition($pos) {
095    $tmp = $this->findPosition ( $pos );
096    if ($tmp === null) {
097      return true;
098    }
099    if ($tmp === $this->getTail ()) {
100      $tmp->pre->next = null;
101      $this->delNode ( $tmp );
102      return true;
103    }
104    $tmp->pre->next = $tmp->next;
105    $tmp->next->pre = $tmp->pre;
106    $this->delNode ( $tmp );
107  }
108  /**
109   * @ desc: 在指定鍵值之前插入結點
110   *
111   * @param : $key
112   *     //指定位置的鏈表元素key
113   * @param : $data
114   *     //要插入的鏈表元素數據
115   * @param : $flag
116   *     //是否順序查找位置進行插入
117   */
118  public function insert($key, $data, $flag = true) {
119    $newNode = self::_getNode ( $key, $data );
120    $tmp = $this->find ( $key, $flag );
121    if ($tmp !== null) {
122      $newNode->pre = $tmp->pre;
123      $newNode->next = $tmp;
124      $tmp->pre = $newNode;
125      $newNode->pre->next = $newNode;
126    } else {
127      $newNode->pre = $this->tail;
128      $this->tail->next = $newNode;
129      $this->tail = $newNode;
130    }
131    $this->len ++;
132  }
133  /**
134   * @ desc: 在指定位置之前插入結點
135   *
136   * @param : $pos
137   *     指定插入鏈表的位置
138   * @param : $key
139   *     指定位置的鏈表元素key
140   * @param : $data
141   *     要插入的鏈表元素數據
142   */
143  public function insertPosition($pos, $key, $data) {
144    $newNode = self::_getNode ( $key, $data );
145    $tmp = $this->findPosition ( $pos );
146    if ($tmp !== null) {
147      $newNode->pre = $tmp->pre;
148      $newNode->next = $tmp;
149      $tmp->pre = $newNode;
150      $newNode->pre->next = $newNode;
151    } else {
152      $newNode->pre = $this->tail;
153      $this->tail->next = $newNode;
154      $this->tail = $newNode;
155    }
156    $this->len ++;
157    return true;
158  }
159  /**
160   * @ desc: 根據key值查詢指定位置數據
161   *
162   * @param : $key
163   *     //指定位置的鏈表元素key
164   * @param : $flag
165   *     //是否順序查找
166   */
167  public function find($key, $flag = true) {
168    if ($flag) {
169      $tmp = $this->head;
170      while ( $tmp->next !== null ) {
171        $tmp = $tmp->next;
172        if ($tmp->key === $key) {
173          return $tmp;
174        }
175      }
176    } else {
177      $tmp = $this->getTail ();
178      while ( $tmp->pre !== null ) {
179        if ($tmp->key === $key) {
180          return $tmp;
181        }
182        $tmp = $tmp->pre;
183      }
184    }
185    return null;
186  }
187  /**
188   * @ desc: 根據位置查詢指定位置數據
189   *
190   * @param : $pos
191   *     //指定位置的鏈表元素key
192   */
193  public function findPosition($pos) {
194    if ($pos <= 0 || $pos > $this->len)
195      return null;
196    if ($pos < ($this->len / 2 + 1)) {
197      $tmp = $this->head;
198      $count = 0;
199      while ( $tmp->next !== null ) {
200        $tmp = $tmp->next;
201        $count ++;
202        if ($count === $pos) {
203          return $tmp;
204        }
205      }
206    } else {
207      $tmp = $this->tail;
208      $pos = $this->len - $pos + 1;
209      $count = 1;
210      while ( $tmp->pre !== null ) {
211        if ($count === $pos) {
212          return $tmp;
213        }
214        $tmp = $tmp->pre;
215        $count ++;
216      }
217    }
218    return null;
219  }
220  /**
221   * @ desc: 返回鏈表頭節點
222   */
223  public function getHead() {
224    return $this->head->next;
225  }
226  /**
227   * @ desc: 返回鏈表尾節點
228   */
229  public function getTail() {
230    return $this->tail;
231  }
232  /**
233   * @ desc: 查詢鏈表節點個數
234   */
235  public function getLength() {
236    return $this->len;
237  }
238  private static function _getNode($key, $data) {
239    $newNode = new Node_Element ( $key, $data );
240    if ($newNode === null) {
241      echo "new node fail!";
242    }
243    return $newNode;
244  }
245  private function delNode($node) {
246    unset ( $node );
247    $this->len --;
248  }
249}
250$myList = new DoubleLinkedList ();
251$myList->insert ( 1, "test1" );
252$myList->insert ( 2, "test2" );
253$myList->insert ( "2b", "test2-b" );
254$myList->insert ( 2, "test2-c" );
255$myList->insert ( 3, "test3" );
256$myList->insertPosition ( 5, "t", "testt" );
257$myList->readAll ();
258echo "+++";
259$myList->deletePosition(0);
260$myList->readAll ();
261echo "..." . $myList->getLength ();
262var_dump ( $myList->findPosition ( 3 )->data );
263?>

運行結果：

01int(1)
02string(5) "test1"
03int(2)
04string(7) "test2-c"
05int(2)
06string(5) "test2"
07string(2) "2b"
08string(7) "test2-b"
09string(1) "t"
10string(5) "testt"
11int(3)
12string(5) "test3"
13+++int(1)
14string(5) "test1"
15int(2)
16string(7) "test2-c"
17int(2)
18string(5) "test2"
19string(2) "2b"
20string(7) "test2-b"
21string(1) "t"
22string(5) "testt"
23int(3)
24string(5) "test3"
25...6string(5) "test2"