大话数据结构之php实现单链表
2021-06-22 09:05
标签：线性表 单链表 最近想起来两件事1.大话数据结构和大话设计模式 这两本书很有意思，C语言有指针，所以实现起来容易理解，所以突然想到用PHP写一下来熟悉一下数据结构的线性表，不过看的比较慢。一般两三天才看完一部分，毕竟还要工作，老板还安装摄像头看着每天干了啥。。。。。老板事业兴隆，嘻嘻。 线性表的概念不赘述，直接去看大话数据结构，代码也是在参考众多实现方案，比较符合大话数据结构的原本思想，就是基本上还原C语言的实现过程。 直接上代码 线性表 本文出自 “一站式解决方案” 博客，请务必保留此出处http://10725691.blog.51cto.com/10715691/1947480 大话数据结构之php实现单链表 标签：线性表 单链表 原文地址：http://10725691.blog.51cto.com/10715691/1947480
self::MAXSIZE){
echo "对不起，数组的长度超过了最大允许值".self::MAXSIZE;
}elseif($n... 你创建了一张空表，数组长度为0‘;
$this->arr=$arr;
$this->length=$n;
}else{
echo ‘
... 你成功创建了一张表
‘;
$this->arr=$arr;
$this->length=$n;
}
}
/*
*按位查找，返回查找到的值
*@param int $n 查找的位置
* @ruturn string;
*/
function findValue($n){
if($n$this->length){
echo ‘输入的位置有误，请在1到‘.$this->length.‘范围内选择‘;
}
return ‘你要找的第‘.$n.‘位的值为‘.$this->arr[$n-1];
}
/*
*按值查找，返回查找到的位置
* @ruturn string;
* @param int $n 查找的值
*/
function findLocation($n){
$v=true;
foreach($this->arr as $key=>$value){
if($value==$n){
$b=$key+1;
return ‘你要找的‘.$n.‘的位置是‘.$b;;
}else{
$v=false;
}
}
if(!$v){
return ‘你要找的值‘.$n.‘不存在‘;
}
}
/*
*在选定的位置处插入某个值
* @param int $i 插入位置
* @param int $v 插入的值
* @ruturn array;
*/
function insertValue($i,$v){
if($iself::MAXSIZE){
echo ‘输入的位置有误，请在1到‘.self::MAXSIZE.‘范围内选择‘;
return;
}
//现将所有i之后的值往后移动一位
for($h=$this->length;$h>=$i;$h--){
$this->arr[$h]=$this->arr[$h-1];
}
if($i>$this->length){
$this->arr[$this->length]=$v;
}else{
$this->arr[$i-1]=$v;
}
$this->length++;
return $this->arr;
}
/*
*在选定的位置删除某个值
* @param int $i 位置
* @ruturn array;
*/
function deleteValue($i){
if($iself::MAXSIZE){
echo ‘输入的位置有误，请在1到‘.self::MAXSIZE.‘范围内选择‘;
return;
}
//现将所有i之后的值往前移动一位
for($j=$i;$jlength;$j++){
$this->arr[$j-1]=$this->arr[$j];
}
unset($this->arr[$this->length-1]);
$this->length--;
return $this->arr;
}
function __destruct(){
if($this->length==0){
echo ‘
...销毁一张空表...
‘;
}else{
echo ‘
...成功销毁一张表..
‘;
}
}
}
?>线性表测试
require_once(‘linearList.php‘);
$arr=array(10,125,123,1,4);
$n=5;
$list = new linearList($arr,$n);
echo $list->findValue(5).‘
‘;
echo $list->findLocation(4).‘
‘;
echo ‘‘;
print_r($list->insertValue(20,300));
echo ‘
‘;
echo ‘‘;
print_r($list->deleteValue(1));
echo ‘
‘;单链表data=$data;
$this->next=null;
}
}
class SingleLinkList{
public $data;
public $next;
//单链表的创建都是从空表逐渐增加上去的
//这相当于头结点
public function __construct(){
$this->data=null;//公用信息
$this->next=null;
}
//每个节点的数据这么传进来呢
//头插法，每个新数据都是第一个位置
public function CreateListHead($num){
for($i=0;$idata = mt_rand(100,200);
$node->next=$this->next;
var_dump($node);
$this->next=$node;
}
}
//尾插法
public function CreateListTail($num){
$tail=$this;
//把新节点当成当前节点的下一节点
for($i=0;$idata = mt_rand(100,200);
$tail->next=$node;
$tail=$node;
var_dump($node);
}
$node->next=null;
}
//销毁单链表
public function DestroyList(){
//
$that=$this;
while($that){
$temp=$that->next;
unset($that);
$that=$temp;
}
}
//清空单链表
//只留下头结点
public function ClearList(){
$temp=$this->next;
while($temp){
$tmp=$temp->next;
unset($temp);
$temp=$tmp;
}
$this->next=null;
}
//判断单链表是否为空
public function ListEmpty(){
if($this->next){
return false;
}else{
return true;
}
}
//单链表的长度
public function ListLength(){
$temp=$this->next;
$count=0;
while($temp){
$count++;
$temp=$temp->next;
}
return $count;
}
//查找特定位置的数据
public function FindValue($pos){
$count=1;
$temp=$this->next;
//也可以吧count与pos判断放在循环里
while($temp && $countnext;
}
if(!$temp ||$count>$pos){
return ‘该位置没有数据‘;
}
//这里可以利用该节点找出下一个值，也就能找出上一个节点
return $p->data;
}
//查找数据所在的位置
public function LocateElem($value){
$count=1;
$temp=$this->next;
//也可以吧count与pos判断放在循环里
while($temp){
$count++;
if($value == $temp->data){
return $count;
}
}
if(!$temp){
return ‘没有该数据:‘.$value;
}
}
//特定值的前一个值
public function PriorElem($value){
$temp=$this->next;
if($temp&&$temp->data==$value){
return $p->data.‘已经是第一个元素，已无前驱元素‘;
}
while($temp&&$temp->next){
$tmp=$temp->next;
if($tmp->data==$value){
return $temp->data;
}
$temp=$tmp;
}
return ‘该单链表没有该数值‘.$value;
}
//特定值的下一个值
public function NextElem($value){
$temp=$this->next;
if($temp&&$temp->next==null){
return $temp->data.‘已经是尾节点数据，已无后续‘;
}
while($temp){
if($this->data==$value){
return $temp->data;
}
}
return ‘该单链表没有该数值‘.$value;
}
//在指定位置之前插入数据
/**
*@param class LNode $node
*
**/
public function ListInsert($pos,$node){
$count=1;
$temp=$this;
//也可以吧count与pos判断放在循环里
while($temp && $countnext;
}
if(!$temp ||$count>$pos){
return ‘该位置没有数据‘;
}
//这里可以利用该节点找出下一个值，也就能找出上一个节点
$node->next=$temp->next;
$temp->next=$node;
return ‘ok‘;
}
//删除单链表指定位置的数据元素
public function ListDelete($pos){
$count=0;
$temp=$this;
while($temp->next){
$count++;
if($count==$pos){
$tmp=$temp->next;
$temp->next=$tmp->next;
unset($tmp);
return ‘OK‘;
}
$temp=$temp->next;
}
return ‘该位置没有数据‘;
}
public function ListTraverse(){
$arr=array();
$temp=$this;
while($temp->next){
$arr[]=$temp->data;
$temp=$temp->next;
}
return $arr;
}
}
?>单链表测试require_once(‘LinkList.php‘);
$list = new SingleLinkList();
$listt = $list->CreateListHead(5);
$list = $list->ListTraverse();
var_dump($listt);
注意：应该没有注意的了，这个还是很有用武之地，只不过理论偏多，不喜欢的就跳过吧。本来也没有多大问题
上一篇：用jq修改css
下一篇：Jmeter中处理json