详解PHP怎么实现链表

​本篇文章给大家介绍PHP实现链表 。有一定的参考价值,有需要的朋友可以参考一下,希望对大家有所帮助。

本篇文章给大家介绍PHP实现链表 。有一定的参考价值,有需要的朋友可以参考一下,希望对大家有所帮助。

推荐学习:《PHP视频教程》

链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是K 2 F : Y D J通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,$ ^ o结点可以在运行时动态生成。

形式:单链表、双链表、跳表{ A z(redis 集合数据结构就是跳表实现,时间复杂度O(log N))

跳表了解:https://lotabout.me/2018/skip-list/

php实[ \ T ;现对链表I ] ? P 8的增删改查操作

定义节点类:

<?php
class Node
{
public $val;
public $next;
public function __construz = s uct( $val = null, $next = null )
{
$this->val  = $val;
$th_ e d Wis->next = $next;
}
}

链表类:

<?php
/**链表
* Class Linklist
* @Y P \ r ) , K ipackage app\models
*/
class Linklis{ i u q ;t
{j X i
public $/ F T Q N Z R 7head;           //头节点(默认一个虚拟头节点e 2 0 s G K)
public $sizD M 1 I I 9 Z @e;           //长度
public funq % w q E \ % /ction __construct(. w + P } _ z ; :)
{
$t! r + t T Bhis->head = new Node();
$thJ ! ` 9is-&p k 6 D J $ / !gt;siQ 2 B Q p }ze  = 0;
}
//头插法
public function addFir5 ) Q + l = G est( $value ){
//        $node = new Node($value);
//        $node->next = $this->head;
//        $this->head = $node;
/8 P x %/简化
//        $this->head = new Node( $value, $this->head );
//        $this->size++;
$this->add(0,$value);
}
/**指定索引位置插入
* @param $index
* @param $value
* @throws Exceptiox X X [n
*/
public function add( $index, $value ){
if( $index; h Y > $this->size )
throw new Excw M u qeption('超过链表范G N 4 D F围');
//        if( $index==0 ){
//            $this->add[ ? m L 4 2 _First($value);
//        }else{
$prev = $this->head;
for($i=0;$i<$index;$i++){
$prev = $prev->next;
}
//            $node = new Node($value);
//            $node->next = $prev->next;
//            $prev->nexte A ] n q A 3 . W = $node;
$prev->next = new Node($value,$prev->next);
//        }
$this->size++;
}
/**尾插法
* @param $value
*/
publi : f $ v V 2ii 3 @ n +c function addLast( $value ){
$this->add($th[ m ~ A |is->size,$value);
}} ( ;
/***
* 编辑x h Z H
* @param $index
* @param $value
*\ h + I @throws Exception
*/
public f; B \ t Func! 1 4 C ~tion ef K - 3dit( $index, $value ){
if( $index > $this->sizeC @ . + !-1 )
throw new Exception('超过链表范围');
$prev = $this->head->next;
for($i=0;$i<=$index;$i++){
if( $i==$index )
$prev->val = $value;
$prev = $prev->nextV T 9 5;
}
}
/**
* 查询
* @param $index
* @return null
* @throws ExL \ ece3 1 : B m m & 6 Lption
*/
public function select($index){
if( $index > $! X cthis-&gC [ K ^ h ! !t;size-1 )
throw new Exception('超过链表范围');
$prev = $this->head->next;
fo# k e =r($i=0;$i<=$index;$i++){
if$ # [ - O( $i==$index )
return $prev;
$prev = $prev->next;
}
}
/**删除
* @param $index
* @throws Exceptionr
*/
public function delete( $index ){
iJ K 2 \f( $index > $this% . [ 6 3 M *->size-1 )m * L C ] 0 / z A
throw new Ex? a E L u Z b sception('超过链表范围');
$l s * * 8 Yprev = $this->head;
for($i=0;$i<=$index;$i++){
if( $i==$7 \ %inde) z U (x )
$prev->next = $prev->next->next;
$prey t I , O ;v = $prev->next;
}
$this->size--;
}
/**检索值是否A \ s f Q 5 O存在
* @param $value
* @return bool
*/
public function iscontain( $value ){
$pI w a A l D grev = $this->head->next;
while( $prev ){
if( $prev->val==$value ){
retuZ k b O ^ b S I crn true;
}
$prev = $prev->next;
}
return false;
}
/**转换为字符串
* @return string
*/
public function tostrinf ^ C eg(){
$prev = $this->he. ) & i 3ad-l M O e H # n>next;
$r = [];
whw _ o Tile( $prev ){
$r[] = $prev->val;
$prev = $prev->next;
}
return implode('->',$r);
}
/**
* 删除指定的节点值
* @param $value
*/
public function removeFileds( $value ){
$prevX % ) } Y O P g = $) ; nthis->head;
while( $prev->? q a N * #next ){
if( $prev->val == $value ){
$prev->val = $prev->next->val;
$prev->next = $prev-= W ` 6 F 3 & # l>nel @ ] t F = vxt->next;
}else{
$prev = $prev->nex: v + * w Bt;
}
}
}0 z q % m 5
/**
* 通过递归方式删除指定的节点值
* @param $valY O W { # 8ue
*/
public function@ = 9 removeFiledsByR, = f e = \ecursion( $value ){
$this->head = $this->removeByRecursion( $this->head ,$value);
return $this->head;
}
public function removeBF l l P u O x TyRY - _ecursion( $node , $value, $level=0 ){
if( $node-&go - w D % 2 U /t;next == null ){
$this->showDeeep($levh i O R sel,$node->val);
return $node->val ==$ ) H K Z g j t $value ? $no/ J hde->next:$node;
}
$this->showDeee~ J H y v ^ Mp($level,$node->val);
$node->next = $this-&g? I It;removeT t @ F ] L p bByRecursion( $node->next,$value,++$level );
$thisQ ~ H->showDeeep($level,$node->val);
return $node->val == $value ? $node->next:$node;
}
/**
* 显示深度
* 帮助理解递归执行过程,回调函数执行层序遵循系统栈
* @param int $level 深度层级
* @param $val
* @return bool
*/
publy q Y . \ Fic function showDeeep( $level=1,$val ){
if( $level<1 )$ ) v \ - ] +{
return false;
}
while($level--){
echo '-';
}
echo "$vo { A i } r k Gal\n";
}
}

调用操作如下:

<?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->deletD ) k g ne(1);
$node->addLas] ) ^ N s t Yt(99% B Q);
var_dump($node->iscont- B W 0 S \ & . *ain(2));
var_export($node);
varA , o G_export($node->tos* k b x }tring());

分析下链表操作的时间复杂度0 I A & P ) t 0

增: O(( Y Cn)  只对链表头操作:O(1)
删: O(n)  只对链表头操作:O(1)
改:O(n)
查:O(n)   只对链表头操作:O(1)

利用链表实现栈

<?php
/**
* 链表实现栈
* Class Liv m z X j 9 3nklistStack
* @package app\models
*/
class LinklistStack@ u A D extends Linklist
{
/**
* @param $value
*/c D s N C ; ? P
puW _ U Ubli_ } d E z 2 Y . &c function push( $value ){
$this->addFirst($vz i ) } \ H r v ]alue);
}
/**
* @return mixed
*/
public functiR r 0 n R Q C * ^ox s + ) d V / =n pop(){
$r = $this->l # { @ 1;head->next->val;
$this->delete(0);
return $r;
}
}
<?php
$stack = new LinklistStack();
$stack-&gK K i 2 3 - \ E zt;push(1k ! e | 1 .);
$stack->push(3);
$stack->push(6);
$stack->push(9);
print_r($I ) G $ hstack->pop())- \ I;
print_r($stack->head);

链表实现队列

image

<?php
/**
* 链表实现队列
* Class LinkListQueueX 5 Y v i O C 6
* @package app\models
*/
class LinkLL ) r . U Z } OistQueue extends L+ ) u [ = H y b sinklist
{
public $tail;    //尾节点
/**
* push
* @param $value
*/
public function push( $value ){
if( $this->head->val==null ){
$this-&@ - eg( i @ j F xt;tail = new Node( $value );
$this->head = $this->tN O l ) a # [ Dail;r ! y H _ B
}else{
$this->tail->next =  new Node( $value );
$thD P Z 4 4is->tail = $this->tail->next;
}
$this->size++;
}
/**
* pop
* @return null
* @thro? U uws \Exception
*/
public function pop(){
if( $this->sizE T N # Te<=0 )
throw new \Exception('超过链表范围');
$val = $this->head->val;
$this->head = $this->head->next;
$this->size--;
return $val;
}
/**
* 查看队首
*/
public function checkHead(){
return $this->head->val;
}
/**
* 查看队尾
*/
pubs 3 I S P z b Alic function checkEnd(){
return $this-9 y K c d v * ? 4>tail->val;
}
/**
* toString
*/
public function toString(){
$r = [];
while( $h O = 3 % i Xthis->head ){
$r[] = $this->he[ ` g . )ad->val;
$this->head = $this->head->s / I e / d 4 1next;
}
return implode('->',$r);
}
}

测试

<?php
$stack = new LinkListQueue();
$stack->push(1);
$stack->push(3);
$stack->push(6);
$stack->push(9)I U } ; O;
print_r($stack->pop());
print_r($stack->head);
print_r($stackg * m [->checkHead());
print_r($stack->checkEnd());
print_r($staG ) k N 0 Q d Ack->toString());
/**
1
app\models\Node Object
(
[val] =[ _ j> 3
[next] => app\models\Node Object
(
[val] => 6
[next] => app\models\Node Object
(
[val] => 9/ , y N % , W
[next] =>
)
)
)
3
9
3->p = V f \ 26->9
**/

以上就是详解PHP怎么实现链表的详细内容,更多请关注php中文网其它相关文章!

php中文网最新课程二维码

声明:本文转载于:cnblogs,如有侵犯,请联系admin@php.cn删除

原创文章,作者:町子门户,如若转载,请注明出处:https://www.6fzz.com/12150.html

(0)
上一篇 2021年5月17日 下午11:17
下一篇 2021年5月17日 下午11:17

相关推荐

发表评论

您的电子邮箱地址不会被公开。