PHP数据结构(二)——链式结构线性表

PHP数据结构(二)——链式结构线性表

(原创内容,转载请注明来源,谢谢)

线性表分为顺序结构和链式结构,链式结构里每一个数据单元除了有数据之外,还有一个空间指向下一个数据的位置(双向链表里面还有一个指向前一个单元的位置)。

链式结构根据其方向性分为单向链表和双向链表,根据其循环性分为普通链表和循环链表。

单向链表:每个数据单元有数据和指向后继数据单元的位置。

双向链表:每个数据单元有数据和指向前驱以及后继单元的位置。

循环链表:链表的最后一个数据指向链表的第一个数据。

普通链表:链表的最后一个数据指向空(Null)。

另外,通常链表里面还有两个概念:

1:头指针,表示链表的开始,本身没有数据内容,指向链表第一个数据。

2:尾指针,表示链表的结束,本身没有数据内容,指向null(循环链表中指向头指针)。

优点:由于链表的每个单元之间的连接是根据指向的,因此对于链表的插入和删除操作较为方便,只需要修改链表中的指向即可。

缺点:查询、修改链表中的某个元素时,不好查找,需要遍历整个链表。对于单向链表,甚至链表前面的元素都无法快速查找,需要从头遍历。

用PHP实现双向循环链表的生成、增删改查。

结果如下:

源代码如下:

<?php
class chain{
         //数值、前驱、后继
         public $chaintable;
         public $prev;
         public $next;
         //构造
         public function__construct($chaintable=null){
                   $this->chaintable =$chaintable;
         }
         //生成链表
         public function generate($arrChain){
                   $tail = new chain();
                   $this->prev = $tail;
                   $tail->next = $this;
                   $cur = $this;
                   foreach($arrChain as $item){
                            $tmp = newchain($item);
                            $cur->next =$tmp;
                            $tmp->prev =$cur;
                            $cur = $tmp;
                   }
                   $cur->next = $tail;
                   $tail->prev = $cur;
         }
         //展示链表
         public function show(){
                   $tmp = $this;
                   while($tmp->next->chaintable!=null){
                            echo '<br/>'.$tmp->next->chaintable;
                            $tmp =$tmp->next;
                   }                
         }
         //获取链表长度
         public function length(){
                   $i = 0;
                   $tmp = $this;
                   while($tmp->next->chaintable!=null){
                            $i++;
                            $tmp = $tmp->next;
                   }                
                   return $i;
         }
         //查找第i个元素
         public function search($i){
                   $tmp = $this;
                   $chain_length =$tmp->length();
                   if($i<=0 ||$i>$chain_length){
                            echo '<br />元素超出链表长度';
                   }else{
                            $j = 0;
                            while($j<$i){
                                     $j++;
                                     $tmp =$tmp->next;
                            }
                            echo '<br />第'.$i.'个元素是:'.$tmp->chaintable;
                   }
         }
         //合并有序链表
         public function merge($old_chain,$new_chain){
                   $old_length =$old_chain->length();
                   $new_length =$new_chain->length();
                   $old_chain =$old_chain->next;//跳过头部
                   $new_chain = $new_chain->next;
                   $i = 1;
                   $j = 1;
                   $k = 1;//循环次数
                   $final_chain = new chain();
                   $tmp = new chain();
                   while($i<=$old_length&& $j<=$new_length){
                            if($old_chain->chaintable<= $new_chain->chaintable){
                                     $old_chain->prev= $final_chain;
                                     $final_chain->next= $old_chain;
                                     $final_chain= $old_chain;//***把final_chain的指针往后一步 
                                     $old_chain= $old_chain->next;
                                     $i++;
                            }else{
                                     $new_chain->prev= $final_chain;
                                     $final_chain->next= $new_chain;
                                     $final_chain= $new_chain;//***把final_chain的指针往后一步 
                                     $new_chain= $new_chain->next;
                                     $j++;                                    
                            }
                            $k++;
                   }
                   if($i <= $old_length){
                            $final_chain->next= $old_chain;
                            $old_chain->prev= $final_chain;
                   }else{
                            $final_chain->next= $new_chain;
                            $new_chain->prev= $final_chain;                    
                  }
                   echo '<br />合并成功';
                   return $final_chain;
         }
         //修改链表第i个元素
         public function modify($i, $data){
                   $tmp = $this;
                   $chain_length =$tmp->length();
                   if($i<=0 ||$i>$chain_length){
                            echo '<br />元素超出链表长度';
                   }else{
                            $j = 0;
                            while($j<$i){
                                     $j++;
                                     $tmp =$tmp->next;
                            }
                            $tmp->chaintable= $data;
                            echo '<br />修改成功';
                   }                
         }
         //删除链表第i个元素
         public function delete($i){
                   $tmp = $this;
                   $chain_length =$tmp->length();
                   if($i<=0 ||$i>$chain_length){
                            echo '<br />元素超出链表长度';
                   }else{
                            $j = 0;
                            while($j<$i-1){//找到第i个元素的前一个元素
                                     $j++;
                                     $tmp =$tmp->next;
                            }
                            $tmp->next =$tmp->next->next;
                            $tmp->next->next->prev= $tmp;
                            echo '<br />删除成功';
                   }                
         }
}
$my_chain = newchain();
$my_chain->generate(array(1,3,7,9,12,15,16));
$my_chain->show();
$chain_length =$my_chain->length();
echo '<br/>链表长度:'.$chain_length;
$my_chain->search(2);
$new_chain = newchain();
$new_chain->generate(array(2,3,5,8,13,19,20));
$my_chain->merge($my_chain,$new_chain);
$my_chain->show();
$my_chain->modify(3,6);
$my_chain->show();
$my_chain->delete(5);
$my_chain->show();
?>

—— written by linhxx 2017.06.14

相关阅读:

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-06-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏GreenLeaves

JS框架设计之对象数组化一种子模块

类数组对象是一个很好的存储结构,但是功能太弱了,为了享受纯数组的哪些便捷的方法,使用前可以做下转换,通常可以使用$.slice.call()方法做转换,但是旧版...

1745
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-12(02)总结Scanner,String

(6)字符串的案例 A:模拟用户登录 B:字符串遍历 C:统计字符串中大写,小写及数字字符的个数 D:把字符串的首字母转成大写,其他小写 E:把int...

34210
来自专栏和蔼的张星的图像处理专栏

35. 翻转链表

样例 给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null

703
来自专栏GreenLeaves

Js正则Replace方法

JS正则的创建有两种方式: new RegExp() 和 直接字面量。 //使用RegExp对象创建 var regObj = new RegExp("(^\s...

19810
来自专栏iOS开发随笔

iOS Swift基础语法(一)

1084
来自专栏互联网杂技

Javascript获取数组中的最大值和最小值的方法汇总

比较数组中数值的大小是比较常见的操作,下面同本文给大家分享四种放哪广发获取数组中最大值和最小值,对此感兴趣的朋友一起学习吧 比较数组中数值的大小是比较常见的操作...

2535
来自专栏Crossin的编程教室

【Python 第47课】 面向对象(1)

我们之前已经写了不少小程序,都是按照功能需求的顺序来设计程序。这种被称为“面向过程”的编程。 还有一种程序设计的方法,把数据和对数据的操作用一种叫做“对象”的...

2739
来自专栏python3

python3--函数初识

函数能提高应用的模块性,和代码的重复利用率。已经知道python提高了许多内建函数,比如print(),len()等。但你也可以自己创建函数,这被叫做用户自定义...

801
来自专栏老马说编程

(16) 继承的细节

上节我们介绍了继承和多态的基本概念,基本概念是比较简单的,子类继承父类,自动拥有父类的属性和行为,并可扩展属性和行为,同时,可重写父类的方法以修改行为。 但继承...

1789
来自专栏Crossin的编程教室

【Python 第67课】函数的参数传递(1)

本篇面向读者:有一点点 Python 基础 关键字:函数,参数,默认值 先说下上次课最后留的那题,我自己的解法: print ';'.join([str(i) ...

2535

扫描关注云+社区