本文實(shí)例講述了PHP雙向鏈表定義與用法。分享給大家供大家參考，具體如下：
由于需要對(duì)一組數(shù)據(jù)多次進(jìn)行移動(dòng)操作，所以寫個(gè)雙向鏈表。但對(duì)php實(shí)在不熟悉，雖然測(cè)試各個(gè)方法沒啥問(wèn)題，就是不知道php語(yǔ)言深層的這些指針和unset有什么注意的地方，貼出來(lái)讓大家教育吧。效率沒測(cè)試....求諒解～
<?php
/**
* **雙向鏈表
* @author zhiyuan12@
*/
/**
* 鏈表元素結(jié)點(diǎn)類
*/
class Node_Element {
public $pre = NULL; // 前驅(qū)
public $next = NULL; // 后繼
public $key = NULL; // 元素鍵值
public $data = NULL; // 結(jié)點(diǎn)值
function __Construct($key, $data) {
$this->key = $key;
$this->data = $data;
}
}
/**
* 雙向鏈表類
*/
class DoubleLinkedList {
private $head; // 頭指針
private $tail; // 尾指針
private $current; // 當(dāng)前指針
private $len; // 鏈表長(zhǎng)度
function __Construct() {
$this->head = self::_getNode ( null, null );
$this->curelement = $this->head;
$this->tail = $this->head;
$len = 0;
}
/**
* @ desc: 讀取鏈表全部結(jié)點(diǎn)
*/
public function readAll() {
$tmp = $this->head;
while ( $tmp->next !== null ) {
$tmp = $tmp->next;
var_dump ( $tmp->key, $tmp->data );
}
}
public function move($pos1, $pos2) {
$pos1Node = $this->findPosition ( $pos1 );
$pos2Node = $this->findPosition ( $pos2 );
if ($pos1Node !== null && $pos2Node !== null) {
$tmpKey = $pos1Node->key;
$tmpData = $pos1Node->data;
$pos1Node->key = $pos2Node->key;
$pos1Node->data = $pos2Node->data;
$pos2Node->key = $tmpKey;
$pos2Node->data = $tmpData;
return true;
}
return false;
}
/**
* @ desc: 在指定關(guān)鍵詞刪除結(jié)點(diǎn)
*
* @param : $key
* 指定位置的鏈表元素key
*/
public function delete($key) {
$pos = $this->find ( $key );
if ($pos !== null) {
$tmp = $pos;
$last = null;
$first = true;
while ( $tmp->next !== null && $tmp->next->key === $key ) {
$tmp = $tmp->next;
if (! $first) {
$this->delNode ( $last );
} else {
$first = false;
}
$last = $tmp;
}
if ($tmp->next !== null) {
$pos->pre->next = $tmp->next;
$tmp->next->pre = $pos->pre;
} else {
$pos->pre->next = null;
}
$this->delNode ( $pos );
$this->delNode ( $tmp );
}
}
/**
* @ desc: 在指定位置刪除結(jié)點(diǎn)
*
* @param : $key
* 指定位置的鏈表元素key
*/
public function deletePosition($pos) {
$tmp = $this->findPosition ( $pos );
if ($tmp === null) {
return true;
}
if ($tmp === $this->getTail ()) {
$tmp->pre->next = null;
$this->delNode ( $tmp );
return true;
}
$tmp->pre->next = $tmp->next;
$tmp->next->pre = $tmp->pre;
$this->delNode ( $tmp );
}
/**
* @ desc: 在指定鍵值之前插入結(jié)點(diǎn)
*
* @param : $key
* //指定位置的鏈表元素key
* @param : $data
* //要插入的鏈表元素?cái)?shù)據(jù)
* @param : $flag
* //是否順序查找位置進(jìn)行插入
*/
public function insert($key, $data, $flag = true) {
$newNode = self::_getNode ( $key, $data );
$tmp = $this->find ( $key, $flag );
if ($tmp !== null) {
$newNode->pre = $tmp->pre;
$newNode->next = $tmp;
$tmp->pre = $newNode;
$newNode->pre->next = $newNode;
} else {
$newNode->pre = $this->tail;
$this->tail->next = $newNode;
$this->tail = $newNode;
}
$this->len ++;
}
/**
* @ desc: 在指定位置之前插入結(jié)點(diǎn)
*
* @param : $pos
* 指定插入鏈表的位置
* @param : $key
* 指定位置的鏈表元素key
* @param : $data
* 要插入的鏈表元素?cái)?shù)據(jù)
*/
public function insertPosition($pos, $key, $data) {
$newNode = self::_getNode ( $key, $data );
$tmp = $this->findPosition ( $pos );
if ($tmp !== null) {
$newNode->pre = $tmp->pre;
$newNode->next = $tmp;
$tmp->pre = $newNode;
$newNode->pre->next = $newNode;
} else {
$newNode->pre = $this->tail;
$this->tail->next = $newNode;
$this->tail = $newNode;
}
$this->len ++;
return true;
}
/**
* @ desc: 根據(jù)key值查詢指定位置數(shù)據(jù)
*
* @param : $key
* //指定位置的鏈表元素key
* @param : $flag
* //是否順序查找
*/
public function find($key, $flag = true) {
if ($flag) {
$tmp = $this->head;
while ( $tmp->next !== null ) {
$tmp = $tmp->next;
if ($tmp->key === $key) {
return $tmp;
}
}
} else {
$tmp = $this->getTail ();
while ( $tmp->pre !== null ) {
if ($tmp->key === $key) {
return $tmp;
}
$tmp = $tmp->pre;
}
}
return null;
}
/**
* @ desc: 根據(jù)位置查詢指定位置數(shù)據(jù)
*
* @param : $pos
* //指定位置的鏈表元素key
*/
public function findPosition($pos) {
if ($pos <= 0 || $pos > $this->len)
return null;
if ($pos < ($this->len / 2 + 1)) {
$tmp = $this->head;
$count = 0;
while ( $tmp->next !== null ) {
$tmp = $tmp->next;
$count ++;
if ($count === $pos) {
return $tmp;
}
}
} else {
$tmp = $this->tail;
$pos = $this->len - $pos + 1;
$count = 1;
while ( $tmp->pre !== null ) {
if ($count === $pos) {
return $tmp;
}
$tmp = $tmp->pre;
$count ++;
}
}
return null;
}
/**
* @ desc: 返回鏈表頭節(jié)點(diǎn)
*/
public function getHead() {
return $this->head->next;
}
/**
* @ desc: 返回鏈表尾節(jié)點(diǎn)
*/
public function getTail() {
return $this->tail;
}
/**
* @ desc: 查詢鏈表節(jié)點(diǎn)個(gè)數(shù)
*/
public function getLength() {
return $this->len;
}
private static function _getNode($key, $data) {
$newNode = new Node_Element ( $key, $data );
if ($newNode === null) {
echo "new node fail!";
}
return $newNode;
}
private function delNode($node) {
unset ( $node );
$this->len --;
}
}
$myList = new DoubleLinkedList ();
$myList->insert ( 1, "test1" );
$myList->insert ( 2, "test2" );
$myList->insert ( "2b", "test2-b" );
$myList->insert ( 2, "test2-c" );
$myList->insert ( 3, "test3" );
$myList->insertPosition ( 5, "t", "testt" );
$myList->readAll ();
echo "+++";
$myList->deletePosition(0);
$myList->readAll ();
echo "..." . $myList->getLength ();
var_dump ( $myList->findPosition ( 3 )->data );
?>
運(yùn)行結(jié)果：
int(1) string(5) "test1" int(2) string(7) "test2-c" int(2) string(5) "test2" string(2) "2b" string(7) "test2-b" string(1) "t" string(5) "testt" int(3) string(5) "test3" +++int(1) string(5) "test1" int(2) string(7) "test2-c" int(2) string(5) "test2" string(2) "2b" string(7) "test2-b" string(1) "t" string(5) "testt" int(3) string(5) "test3" ...6string(5) "test2"
希望本文所述對(duì)大家PHP程序設(shè)計(jì)有所幫助。
