您好,登錄后才能下訂單哦!
這篇文章主要介紹了PHP實(shí)現(xiàn)鏈表的方法,具有一定借鑒價(jià)值,感興趣的朋友可以參考下,希望大家閱讀完這篇文章之后大有收獲,下面讓小編帶著大家一起了解一下。
鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)(鏈表中每一個(gè)元素稱(chēng)為結(jié)點(diǎn))組成,結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。
形式:?jiǎn)捂湵?、雙鏈表、跳表(redis 集合數(shù)據(jù)結(jié)構(gòu)就是跳表實(shí)現(xiàn),時(shí)間復(fù)雜度O(log N))
跳表了解:https://lotabout.me/2018/skip-list/
定義節(jié)點(diǎn)類(lèi):
<?php class Node { public $val; public $next; public function __construct( $val = null, $next = null ) { $this->val = $val; $this->next = $next; } }
鏈表類(lèi):
<?php /**鏈表 * Class Linklist * @package app\models */ class Linklist { public $head; //頭節(jié)點(diǎn)(默認(rèn)一個(gè)虛擬頭節(jié)點(diǎn)) public $size; //長(zhǎng)度 public function __construct() { $this->head = new Node(); $this->size = 0; } //頭插法 public function addFirst( $value ){ // $node = new Node($value); // $node->next = $this->head; // $this->head = $node; //簡(jiǎn)化 // $this->head = new Node( $value, $this->head ); // $this->size++; $this->add(0,$value); } /**指定索引位置插入 * @param $index * @param $value * @throws Exception */ public function add( $index, $value ){ if( $index > $this->size ) throw new Exception('超過(guò)鏈表范圍'); // if( $index==0 ){ // $this->addFirst($value); // }else{ $prev = $this->head; for($i=0;$i<$index;$i++){ $prev = $prev->next; } // $node = new Node($value); // $node->next = $prev->next; // $prev->next = $node; $prev->next = new Node($value,$prev->next); // } $this->size++; } /**尾插法 * @param $value */ public function addLast( $value ){ $this->add($this->size,$value); } /*** * 編輯 * @param $index * @param $value * @throws Exception */ public function edit( $index, $value ){ if( $index > $this->size-1 ) throw new Exception('超過(guò)鏈表范圍'); $prev = $this->head->next; for($i=0;$i<=$index;$i++){ if( $i==$index ) $prev->val = $value; $prev = $prev->next; } } /** * 查詢(xún) * @param $index * @return null * @throws Exception */ public function select($index){ if( $index > $this->size-1 ) throw new Exception('超過(guò)鏈表范圍'); $prev = $this->head->next; for($i=0;$i<=$index;$i++){ if( $i==$index ) return $prev; $prev = $prev->next; } } /**刪除 * @param $index * @throws Exceptionr */ public function delete( $index ){ if( $index > $this->size-1 ) throw new Exception('超過(guò)鏈表范圍'); $prev = $this->head; for($i=0;$i<=$index;$i++){ if( $i==$index ) $prev->next = $prev->next->next; $prev = $prev->next; } $this->size--; } /**檢索值是否存在 * @param $value * @return bool */ public function iscontain( $value ){ $prev = $this->head->next; while( $prev ){ if( $prev->val==$value ){ return true; } $prev = $prev->next; } return false; } /**轉(zhuǎn)換為字符串 * @return string */ public function tostring(){ $prev = $this->head->next; $r = []; while( $prev ){ $r[] = $prev->val; $prev = $prev->next; } return implode('->',$r); } /** * 刪除指定的節(jié)點(diǎn)值 * @param $value */ public function removeFileds( $value ){ $prev = $this->head; while( $prev->next ){ if( $prev->val == $value ){ $prev->val = $prev->next->val; $prev->next = $prev->next->next; }else{ $prev = $prev->next; } } } /** * 通過(guò)遞歸方式刪除指定的節(jié)點(diǎn)值 * @param $value */ public function removeFiledsByRecursion( $value ){ $this->head = $this->removeByRecursion( $this->head ,$value); return $this->head; } public function removeByRecursion( $node , $value, $level=0 ){ if( $node->next == null ){ $this->showDeeep($level,$node->val); return $node->val == $value ? $node->next:$node; } $this->showDeeep($level,$node->val); $node->next = $this->removeByRecursion( $node->next,$value,++$level ); $this->showDeeep($level,$node->val); return $node->val == $value ? $node->next:$node; } /** * 顯示深度 * 幫助理解遞歸執(zhí)行過(guò)程,回調(diào)函數(shù)執(zhí)行層序遵循系統(tǒng)棧 * @param int $level 深度層級(jí) * @param $val * @return bool */ public function showDeeep( $level=1,$val ){ if( $level<1 ){ return false; } while($level--){ echo '-'; } echo "$val\n"; } }
調(diào)用操作如下:
<?php $node = new Linklist(); $node->addFirst(1); $node->add(1,7); $node->add(2,10); $node->edit(1,8); var_dump($node->select(1)) ; $node->delete(1); $node->addLast(99); var_dump($node->iscontain(2)); var_export($node); var_export($node->tostring());
分析下鏈表操作的時(shí)間復(fù)雜度:
增: O(n) 只對(duì)鏈表頭操作:O(1) 刪: O(n) 只對(duì)鏈表頭操作:O(1) 改:O(n) 查:O(n) 只對(duì)鏈表頭操作:O(1)
<?php /** * 鏈表實(shí)現(xiàn)棧 * Class LinklistStack * @package app\models */ class LinklistStack extends Linklist { /** * @param $value */ public function push( $value ){ $this->addFirst($value); } /** * @return mixed */ public function pop(){ $r = $this->head->next->val; $this->delete(0); return $r; } }
<?php $stack = new LinklistStack(); $stack->push(1); $stack->push(3); $stack->push(6); $stack->push(9); print_r($stack->pop()); print_r($stack->head);
<?php /** * 鏈表實(shí)現(xiàn)隊(duì)列 * Class LinkListQueue * @package app\models */ class LinkListQueue extends Linklist { public $tail; //尾節(jié)點(diǎn) /** * push * @param $value */ public function push( $value ){ if( $this->head->val==null ){ $this->tail = new Node( $value ); $this->head = $this->tail; }else{ $this->tail->next = new Node( $value ); $this->tail = $this->tail->next; } $this->size++; } /** * pop * @return null * @throws \Exception */ public function pop(){ if( $this->size<=0 ) throw new \Exception('超過(guò)鏈表范圍'); $val = $this->head->val; $this->head = $this->head->next; $this->size--; return $val; } /** * 查看隊(duì)首 */ public function checkHead(){ return $this->head->val; } /** * 查看隊(duì)尾 */ public function checkEnd(){ return $this->tail->val; } /** * toString */ public function toString(){ $r = []; while( $this->head ){ $r[] = $this->head->val; $this->head = $this->head->next; } return implode('->',$r); } }
測(cè)試
<?php $stack = new LinkListQueue(); $stack->push(1); $stack->push(3); $stack->push(6); $stack->push(9); print_r($stack->pop()); print_r($stack->head); print_r($stack->checkHead()); print_r($stack->checkEnd()); print_r($stack->toString()); /** 1 app\models\Node Object ( [val] => 3 [next] => app\models\Node Object ( [val] => 6 [next] => app\models\Node Object ( [val] => 9 [next] => ) ) ) 3 9 3->6->9 **/
php是一個(gè)嵌套的縮寫(xiě)名稱(chēng),是英文超級(jí)文本預(yù)處理語(yǔ)言,它的語(yǔ)法混合了C、Java、Perl以及php自創(chuàng)新的語(yǔ)法,主要用來(lái)做網(wǎng)站開(kāi)發(fā),許多小型網(wǎng)站都用php開(kāi)發(fā),因?yàn)閜hp是開(kāi)源的,從而使得php經(jīng)久不衰。
感謝你能夠認(rèn)真閱讀完這篇文章,希望小編分享的“PHP實(shí)現(xiàn)鏈表的方法”這篇文章對(duì)大家有幫助,同時(shí)也希望大家多多支持億速云,關(guān)注億速云行業(yè)資訊頻道,更多相關(guān)知識(shí)等著你來(lái)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。