PHP实现链表的方法
这篇文章主要介绍了PHP实现链表的方法，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。
成都创新互联是一家专注于成都网站制作、网站设计与策划设计,高阳网站建设哪家好?成都创新互联做网站,专注于网站建设十年,网设计领域的专业建站公司;建站业务涵盖:高阳等地区。高阳做网站价格咨询:18980820575
链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
形式：单链表、双链表、跳表（redis 集合数据结构就是跳表实现，时间复杂度O（log N））
跳表了解：https://lotabout.me/2018/skip-list/
php实现对链表的增删改查操作
定义节点类：
val = $val; $this->next = $next; } }
链表类：
head = new Node();
$this->size = 0;
}
//头插法
public function addFirst( $value ){
// $node = new Node($value);
// $node->next = $this->head;
// $this->head = $node;
//简化
// $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('超过链表范围');
// 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('超过链表范围');
$prev = $this->head->next;
for($i=0;$i<=$index;$i++){
if( $i==$index )
$prev->val = $value;
$prev = $prev->next;
}
}
/**
* 查询
* @param $index
* @return null
* @throws Exception
*/
public function select($index){
if( $index > $this->size-1 )
throw new Exception('超过链表范围');
$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('超过链表范围');
$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;
}
/**转换为字符串
* @return string
*/
public function tostring(){
$prev = $this->head->next;
$r = [];
while( $prev ){
$r[] = $prev->val;
$prev = $prev->next;
}
return implode('->',$r);
}
/**
* 删除指定的节点值
* @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;
}
}
}
/**
* 通过递归方式删除指定的节点值
* @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;
}
/**
* 显示深度
* 帮助理解递归执行过程，回调函数执行层序遵循系统栈
* @param int $level 深度层级
* @param $val
* @return bool
*/
public function showDeeep( $level=1,$val ){
if( $level<1 ){
return false;
}
while($level--){
echo '-';
}
echo "$val\n";
}
}调用操作如下：
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());
分析下链表操作的时间复杂度：
增： O(n) 只对链表头操作：O(1) 删： O(n) 只对链表头操作：O(1) 改：O(n) 查：O(n) 只对链表头操作：O(1)
利用链表实现栈
addFirst($value);
}
/**
* @return mixed
*/
public function pop(){
$r = $this->head->next->val;
$this->delete(0);
return $r;
}
}push(1); $stack->push(3); $stack->push(6); $stack->push(9); print_r($stack->pop()); print_r($stack->head);
链表实现队列
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('超过链表范围');
$val = $this->head->val;
$this->head = $this->head->next;
$this->size--;
return $val;
}
/**
* 查看队首
*/
public function checkHead(){
return $this->head->val;
}
/**
* 查看队尾
*/
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);
}
}测试
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有什么用
php是一个嵌套的缩写名称，是英文超级文本预处理语言，它的语法混合了C、Java、Perl以及php自创新的语法，主要用来做网站开发，许多小型网站都用php开发，因为php是开源的，从而使得php经久不衰。
感谢你能够认真阅读完这篇文章，希望小编分享的“PHP实现链表的方法”这篇文章对大家有帮助，同时也希望大家多多支持创新互联，关注创新互联行业资讯频道，更多相关知识等着你来学习!
名称栏目：PHP实现链表的方法
分享链接：http://azwzsj.com/article/jspjie.html
