前段时间受
PHPX里一个帖子的启发,突然想到了写这些
代码。
众所周知,PHP的数组
系统功能超级强大,关联数组+变量的弱类型特性使得PHP的数组可以实现非常多的灵活的功能。以前在
学习C的时候,就学过
数据结构,当时是利用C的指针来实现,但是接触PHP半年,没有发现谁在PHP中讨论数据结构,这大概是由语言的特性以及其应用领域所造成的。不过,我们依然可以在PHP中“模拟”出一些常用的数据结构,当然这些并不能算做真正意义上的数据结构。
我写这个完全是凭借个人兴趣,可能实用性并不是非常强。但是也许偶尔一两个比较复杂的
问题正好需要这来求解,我会给出一些简单的应用
实例。也许你会说,那些例子直接用PHP的数组也能够做到,的确如此,但是你仔细观察也会发现,这些结构的引入简化了程序的
设计,划分了不同的关注层次,使我们思考范围缩小。比如我们熟悉的ISO/OSI模型和
MVC开发模式等都是把复杂问题分层的机制。而直接用数组不仅掩盖了问题的本质,还要分散精力去考虑数组下标增减等问题。
这些代码还没有经过非常严格的测试,所以如果大家发现一些BUG,请回贴说明,或则给我发邮件。
QQ:21058652 MSN\E-mail:xiuluo-999@163.com
另外关于设计方面有不合理的地方,还希望各位大鸟
帮忙指出,感激不尽。
1:单链表
单链表是最简单的链表表示。用它来表示线性表时,每一个数据元素占用一个结点(node)。一个结点一般由两个域组成,一个域存放数据元素data;
另一个域存放一个指向链表中下一个结点的指针link,它指出下一个结点 的开始存储地址。而最后一个结点的指针为空。单链表中数据元素之间的逻
辑关系是由结点中的指针指示的,换句话说,指针为数据元素之间的逻辑关系的映象,则逻辑上相邻的两个元素其存储的物理位置不要求紧邻,因此,
这种存储结构为非顺序映像或链式映像。
/**
* PHP数组实现单链表结构
* 此类主要是依靠PHP强大的数组系统来模拟出单链表类型的数据结构。 本人完全凭借自己的
* 兴趣来编写此类,并未考虑其实用性,主要是给大家理解一些简单的数据结构知识,同时也训练
* 一下PHP中的数组运用能力。
*单链表简介:
* 单链表是最简单的链表表示。用它来表示线性表时,每一个数据元素占用一个结点(node)。一个
* 结点一般由两个域组成,一个域存放数据元素data; 另一个域存放一个指向链表中下一个结点的
* 指针link,它指出下一个结点 的开始存储地址。而最后一个结点的指针为空。单链表中数据元素
* 之间的逻 辑关系是由结点中的指针指示的,换句话说,指针为数据元素之间的逻辑关系的映象,则
* 逻辑上相邻的两个元素其存储的物理位置不要求紧邻,因此, 这种存储结构为非顺序映像或链式映像。
* 当然,在PHP没有指针这个概念,但是我们可以用关联数组来模拟。
* @version 1.0
* @author 玉面修罗
*/
class LinkList
{
/**
* 成员变量
* @var array $linkList 链表数组
* @var number $listHeader 表头索引
* @var number $listLength 链表长度
* @var number $existedCounts 记录链表中出现过的元素的个数,和$listLength不同的是, 删除一
* 个元素之后,该值不需要减1,这个也可以用来为新元素分配索引。
*/
protected $linkList =array();
protected $listLength=0;
protected $listHeader=null;
protected $existedCounts=0;
/**
* 构造函数
* 构造函数可以带一个数组参数,如果有参数,则调用成员方法
* createList将数组转换成链表,并算出链表长度.如果没有参
* 数,则生成一空链表.空链表可以通过调用成员方法createList
* 生成链表.
* @access public
* @param array $arr 需要被转化为链表的数组
*/
public function __construct($arr='')
{
$arr!=null&&$this->createList($arr);
}
/**
* 生成链表的函数
* 将数组转变成链表,同时计算出链表长度。分别赋值给成员标量
* $linkList和$listLength.
* @access public
* @param array $arr 需要被转化为链表的数组
* @return boolean true表示转换成功,false表示失败
*/
public function createList($arr)
{
if (!is_array($arr))
return false;
$length=count($arr);
for($i=0;$i<$length;$i++)
{
if($i==$length-1)
{
//每个链表结点包括var和next两个索引,var表示结点值,next为下一个结点的索引
//最后一个结点的next为null
$list[$i]['var'] =$arr[$i];
$list[$i]['next'] =null;
}
else
{
$list[$i]['var'] =$arr[$i];
$list[$i]['next'] =$i+1;
}
}
$this->linkList =$list;
$this->listLength =$length;
$this->existedCounts =$length;
$this->listHeader=0;
return true;
}
/**
* 将链表还原成一维数组
* @access public
* @return array $arr 生成的一维数组
*/
public function returnToArray()
{
$arr=array();
$tmp=$this->linkList[$this->listHeader];
for($i=0;$i<$this->listLength;$i++)
{
$arr[]=$tmp['var'];
if ($i!=$this->listLength-1)
{
$tmp=$this->linkList[$tmp['next']];
}
}
return $arr;
}
/**
* 返回链表的长度
* @access public
* @return number $listLength 链表的长度
*/
public function getLength()
{
return $this->listLength;
}
/**
* 计算一共删除过多少个元素
* @access public
* @return number $count 到目前为止删除过的元素个数
*/
public function getDeletedNums()
{
$count=$this->existedCounts-$this->listLength;
return $count;
}
/**
* 通过元素索引返回元素序号
* @access protected
* @param $index 元素的索引号
* @return $num 元素在链表中的序号
*/
public function getElemLocation($index)
{
if (!array_key_exists($index,$this->linkList))
return false;
$arrIndex=$this->listHeader;
for($num=1;$tmp=$this->linkList[$arrIndex];$num++)
{
if ($index==$arrIndex)
break;
else
{
$arrIndex=$tmp['next'];
}
}
return $num;
}
/**
* 获取第$i个元素的引用
* 这个保护方法不能被外界直接访问,许多服务方法以来与次方法。
* 它用来返回链表中第$i个元素的引用,是一个数组
* @access protected
* @param number $i 元素的序号
* @return reference 元素的引用
*/
protected function &getElemRef($i)
{
//判断$i的类型以及是否越界
$result=false;
if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength)
return $result;
//由于单链表中的任何两个元素的存储位置之间没有固定关系,要取得第i个元素必须从
//表头开始查找,因此单链表是非随机存储的存储结构。
$j=0;
$value=&$this->linkList[$this->listHeader];
while ($j<$i-1)
{
$value=&$this->linkList[$value['next']];
$j++;
}
return $value;
}
/**
* 返回第i个元素的值
* @access public
* @param number $i 需要返回的元素的序号,从1开始
* @return mixed 第i个元素的值
*/
public function getElemvar($i)
{
$var=$this->getElemRef($i);
if ($var!=false)
{
return $var['var'];
}
else return false;
}
/**
* 在第i个元素之后插入一个值为var的新元素
* i的取值应该为[1,$this->listLength],如果i=0,表示在表的最前段插入,
* 如果i=$this->listLength,表示在表的末尾插入,插入的方法为,将第$i-1个元素
* 的next指向第$i个元素,然后将第$i个元素的next指向第$i+1个元素,这样就实现了插入
* @access public
* @param number $i 在位置i插入新元素
* @param mixed $var 要插入的元素的值
* @return boolean 成功则返回true,否则返回false
*/
public function insertIntoList($i,$var)
{
if (!is_numeric($i)||(int)$i<0||(int)$i>$this->listLength)
return false;
if ($i==0)
{
//如果$i-0,则在表最前面添加元素,新元素索引为$listLength,这样是确保不会
//覆盖原来的元素,另外这种情况需要重新设置$listHeader
$this->linkList[$this->existedCounts]['var'] =$var;
$this->linkList[$this->existedCounts]['next']=$this->listHeader;
$this->listHeader=$this->existedCounts;
$this->listLength++;
$this->existedCounts++;
return true;
}
$value=&$this->getElemRef($i);
$this->linkList[$this->existedCounts]['var'] =$var;
$this->linkList[$this->existedCounts]['next']=($i==$this->listLength?null:$value['next']);
$value['next']=$this->existedCounts;
$this->listLength++;
$this->existedCounts++;
return true;
}
/**
* 删除第$i个元素
* 删除第$i个元素,该元素为取值应该为[1,$this->listLength],需要注意,删除元素之后,
* $this->listLength减1,而$this->existedCounts不变。删除的方法为将第$i-1个元素的
* next指向第$i+1个元素,那么第$i个元素就从链表中删除了。
* @access public
* @param number $i 将要被删除的元素的序号
* @return boolean 成功则返回true,否则返回false
*/
public function delFromList($i)
{
if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength)
return false;
if ($i==1)
{
//若删除的结点为头结点,则需要从新设置链表头
$tmp=$this->linkList[$this->listHeader];
unset($this->linkList[$this->listHeader]);
$this->listHeader=$tmp['next'];
$this->listLength--;
return true;
}
else
{
$value =&$this->getElemRef($i);
$prevValue=&$this->getElemRef($i-1);
unset($this->linkList[$prevValue['next']]);
$prevValue['next']=$value['next'];
$this->listLength--;
return true;
}
}
/**
* 对链表的元素排序
* 谨慎使用此函数,排序后链表将被从新初始化,原有的成员变量将会被覆盖
* @accse public
* @param boolean $sortType='true' 排序方式,true表示升序,false表示降序,默认true
*/
public function listSort($sortType='true')
{
//从新修改关联关系可能会更复杂,所以我选择先还原成一维数组,然后对数组排序,然后再生成链表
$arr=$this->returnToArray();
$sortType?sort($arr):rsort($arr);
$this->createList($arr);
}
}
/**
* 返回链表的长度
* @access public
* @return number $listLength 链表的长度
*/
public function getLength()
{
return $this->listLength;
}
/**
* 计算一共删除过多少个元素
* @access public
* @return number $count 到目前为止删除过的元素个数
*/
public function getDeletedNums()
{
$count=$this->existedCounts-$this->listLength;
return $count;
}
/**
* 通过元素索引返回元素序号
* @access protected
* @param $index 元素的索引号
* @return $num 元素在链表中的序号
*/
public function getElemLocation($index)
{
if (!array_key_exists($index,$this->linkList))
return false;
$arrIndex=$this->listHeader;
for($num=1;$tmp=$this->linkList[$arrIndex];$num++)
{
if ($index==$arrIndex)
break;
else
{
$arrIndex=$tmp['next'];
}
}
return $num;
}
/**
* 获取第$i个元素的引用
* 这个保护方法不能被外界直接访问,许多服务方法以来与次方法。
* 它用来返回链表中第$i个元素的引用,是一个数组
* @access protected
* @param number $i 元素的序号
* @return reference 元素的引用
*/
protected function &getElemRef($i)
{
//判断$i的类型以及是否越界
$result=false;
if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength)
return $result;
//由于单链表中的任何两个元素的存储位置之间没有固定关系,要取得第i个元素必须从
//表头开始查找,因此单链表是非随机存储的存储结构。
$j=0;
$value=&$this->linkList[$this->listHeader];
while ($j<$i-1)
{
$value=&$this->linkList[$value['next']];
$j++;
}
return $value;
}
/**
* 返回第i个元素的值
* @access public
* @param number $i 需要返回的元素的序号,从1开始
* @return mixed 第i个元素的值
*/
public function getElemvar($i)
{
$var=$this->getElemRef($i);
if ($var!=false)
{
return $var['var'];
}
else return false;
}
/**
* 在第i个元素之后插入一个值为var的新元素
* i的取值应该为[1,$this->listLength],如果i=0,表示在表的最前段插入,
* 如果i=$this->listLength,表示在表的末尾插入,插入的方法为,将第$i-1个元素
* 的next指向第$i个元素,然后将第$i个元素的next指向第$i+1个元素,这样就实现了插入
* @access public
* @param number $i 在位置i插入新元素
* @param mixed $var 要插入的元素的值
* @return boolean 成功则返回true,否则返回false
*/
public function insertIntoList($i,$var)
{
if (!is_numeric($i)||(int)$i<0||(int)$i>$this->listLength)
return false;
if ($i==0)
{
//如果$i-0,则在表最前面添加元素,新元素索引为$listLength,这样是确保不会
//覆盖原来的元素,另外这种情况需要重新设置$listHeader
$this->linkList[$this->existedCounts]['var'] =$var;
$this->linkList[$this->existedCounts]['next']=$this->listHeader;
$this->listHeader=$this->existedCounts;
$this->listLength++;
$this->existedCounts++;
return true;
}
$value=&$this->getElemRef($i);
$this->linkList[$this->existedCounts]['var'] =$var;
$this->linkList[$this->existedCounts]['next']=($i==$this->listLength?null:$value['next']);
$value['next']=$this->existedCounts;
$this->listLength++;
$this->existedCounts++;
return true;
}
/**
* 删除第$i个元素
* 删除第$i个元素,该元素为取值应该为[1,$this->listLength],需要注意,删除元素之后,
* $this->listLength减1,而$this->existedCounts不变。删除的方法为将第$i-1个元素的
* next指向第$i+1个元素,那么第$i个元素就从链表中删除了。
* @access public
* @param number $i 将要被删除的元素的序号
* @return boolean 成功则返回true,否则返回false
*/
public function delFromList($i)
{
if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength)
return false;
if ($i==1)
{
//若删除的结点为头结点,则需要从新设置链表头
$tmp=$this->linkList[$this->listHeader];
unset($this->linkList[$this->listHeader]);
$this->listHeader=$tmp['next'];
$this->listLength--;
return true;
}
else
{
$value =&$this->getElemRef($i);
$prevValue=&$this->getElemRef($i-1);
unset($this->linkList[$prevValue['next']]);
$prevValue['next']=$value['next'];
$this->listLength--;
return true;
}
}
/**
* 对链表的元素排序
* 谨慎使用此函数,排序后链表将被从新初始化,原有的成员变量将会被覆盖
* @accse public
* @param boolean $sortType='true' 排序方式,true表示升序,false表示降序,默认true
*/
public function listSort($sortType='true')
{
//从新修改关联关系可能会更复杂,所以我选择先还原成一维数组,然后对数组排序,然后再生成链表
$arr=$this->returnToArray();
$sortType?sort($arr):rsort($arr);
$this->createList($arr);
}
}
?>/**
* 返回链表的长度
* @access public
* @return number $listLength 链表的长度
*/
public function getLength()
{
return $this->listLength;
}
/**
* 计算一共删除过多少个元素
* @access public
* @return number $count 到目前为止删除过的元素个数
*/
public function getDeletedNums()
{
$count=$this->existedCounts-$this->listLength;
return $count;
}
/**
* 通过元素索引返回元素序号
* @access protected
* @param $index 元素的索引号
* @return $num 元素在链表中的序号
*/
public function getElemLocation($index)
{
if (!array_key_exists($index,$this->linkList))
return false;
$arrIndex=$this->listHeader;
for($num=1;$tmp=$this->linkList[$arrIndex];$num++)
{
if ($index==$arrIndex)
break;
else
{
$arrIndex=$tmp['next'];
}
}
return $num;
}
/**
* 获取第$i个元素的引用
* 这个保护方法不能被外界直接访问,许多服务方法以来与次方法。
* 它用来返回链表中第$i个元素的引用,是一个数组
* @access protected
* @param number $i 元素的序号
* @return reference 元素的引用
*/
protected function &getElemRef($i)
{
//判断$i的类型以及是否越界
$result=false;
if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength)
return $result;
//由于单链表中的任何两个元素的存储位置之间没有固定关系,要取得第i个元素必须从
//表头开始查找,因此单链表是非随机存储的存储结构。
$j=0;
$value=&$this->linkList[$this->listHeader];
while ($j<$i-1)
{
$value=&$this->linkList[$value['next']];
$j++;
}
return $value;
}
/**
* 返回第i个元素的值
* @access public
* @param number $i 需要返回的元素的序号,从1开始
* @return mixed 第i个元素的值
*/
public function getElemvar($i)
{
$var=$this->getElemRef($i);
if ($var!=false)
{
return $var['var'];
}
else return false;
}
/**
* 在第i个元素之后插入一个值为var的新元素
* i的取值应该为[1,$this->listLength],如果i=0,表示在表的最前段插入,
* 如果i=$this->listLength,表示在表的末尾插入,插入的方法为,将第$i-1个元素
* 的next指向第$i个元素,然后将第$i个元素的next指向第$i+1个元素,这样就实现了插入
* @access public
* @param number $i 在位置i插入新元素
* @param mixed $var 要插入的元素的值
* @return boolean 成功则返回true,否则返回false
*/
public function insertIntoList($i,$var)
{
if (!is_numeric($i)||(int)$i<0||(int)$i>$this->listLength)
return false;
if ($i==0)
{
//如果$i-0,则在表最前面添加元素,新元素索引为$listLength,这样是确保不会
//覆盖原来的元素,另外这种情况需要重新设置$listHeader
$this->linkList[$this->existedCounts]['var'] =$var;
$this->linkList[$this->existedCounts]['next']=$this->listHeader;
$this->listHeader=$this->existedCounts;
$this->listLength++;
$this->existedCounts++;
return true;
}
$value=&$this->getElemRef($i);
$this->linkList[$this->existedCounts]['var'] =$var;
$this->linkList[$this->existedCounts]['next']=($i==$this->listLength?null:$value['next']);
$value['next']=$this->existedCounts;
$this->listLength++;
$this->existedCounts++;
return true;
}
/**
* 删除第$i个元素
* 删除第$i个元素,该元素为取值应该为[1,$this->listLength],需要注意,删除元素之后,
* $this->listLength减1,而$this->existedCounts不变。删除的方法为将第$i-1个元素的
* next指向第$i+1个元素,那么第$i个元素就从链表中删除了。
* @access public
* @param number $i 将要被删除的元素的序号
* @return boolean 成功则返回true,否则返回false
*/
public function delFromList($i)
{
if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength)
return false;
if ($i==1)
{
//若删除的结点为头结点,则需要从新设置链表头
$tmp=$this->linkList[$this->listHeader];
unset($this->linkList[$this->listHeader]);
$this->listHeader=$tmp['next'];
$this->listLength--;
return true;
}
else
{
$value =&$this->getElemRef($i);
$prevValue=&$this->getElemRef($i-1);
unset($this->linkList[$prevValue['next']]);
$prevValue['next']=$value['next'];
$this->listLength--;
return true;
}
}
/**
* 对链表的元素排序
* 谨慎使用此函数,排序后链表将被从新初始化,原有的成员变量将会被覆盖
* @accse public
* @param boolean $sortType='true' 排序方式,true表示升序,false表示降序,默认true
*/
public function listSort($sortType='true')
{
//从新修改关联关系可能会更复杂,所以我选择先还原成一维数组,然后对数组排序,然后再生成链表
$arr=$this->returnToArray();
$sortType?sort($arr):rsort($arr);
$this->createList($arr);
}
/**
* 返回链表的长度
* @access public
* @return number $listLength 链表的长度
*/
public function getLength()
{
return $this->listLength;
}
/**
* 计算一共删除过多少个元素
* @access public
* @return number $count 到目前为止删除过的元素个数
*/
public function getDeletedNums()
{
$count=$this->existedCounts-$this->listLength;
return $count;
}
/**
* 通过元素索引返回元素序号
* @access protected
* @param $index 元素的索引号
* @return $num 元素在链表中的序号
*/
public function getElemLocation($index)
{
if (!array_key_exists($index,$this->linkList))
return false;
$arrIndex=$this->listHeader;
for($num=1;$tmp=$this->linkList[$arrIndex];$num++)
{
if ($index==$arrIndex)
break;
else
{
$arrIndex=$tmp['next'];
}
}
return $num;
}
/**
* 获取第$i个元素的引用
* 这个保护方法不能被外界直接访问,许多服务方法以来与次方法。
* 它用来返回链表中第$i个元素的引用,是一个数组
* @access protected
* @param number $i 元素的序号
* @return reference 元素的引用
*/
protected function &getElemRef($i)
{
//判断$i的类型以及是否越界
$result=false;
if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength)
return $result;
//由于单链表中的任何两个元素的存储位置之间没有固定关系,要取得第i个元素必须从
//表头开始查找,因此单链表是非随机存储的存储结构。
$j=0;
$value=&$this->linkList[$this->listHeader];
while ($j<$i-1)
{
$value=&$this->linkList[$value['next']];
$j++;
}
return $value;
}
/**
* 返回第i个元素的值
* @access public
* @param number $i 需要返回的元素的序号,从1开始
* @return mixed 第i个元素的值
*/
public function getElemvar($i)
{
$var=$this->getElemRef($i);
if ($var!=false)
{
return $var['var'];
}
else return false;
}
/**
* 在第i个元素之后插入一个值为var的新元素
* i的取值应该为[1,$this->listLength],如果i=0,表示在表的最前段插入,
* 如果i=$this->listLength,表示在表的末尾插入,插入的方法为,将第$i-1个元素
* 的next指向第$i个元素,然后将第$i个元素的next指向第$i+1个元素,这样就实现了插入
* @access public
* @param number $i 在位置i插入新元素
* @param mixed $var 要插入的元素的值
* @return boolean 成功则返回true,否则返回false
*/
public function insertIntoList($i,$var)
{
if (!is_numeric($i)||(int)$i<0||(int)$i>$this->listLength)
return false;
if ($i==0)
{
//如果$i-0,则在表最前面添加元素,新元素索引为$listLength,这样是确保不会
//覆盖原来的元素,另外这种情况需要重新设置$listHeader
$this->linkList[$this->existedCounts]['var'] =$var;
$this->linkList[$this->existedCounts]['next']=$this->listHeader;
$this->listHeader=$this->existedCounts;
$this->listLength++;
$this->existedCounts++;
return true;
}
$value=&$this->getElemRef($i);
$this->linkList[$this->existedCounts]['var'] =$var;
$this->linkList[$this->existedCounts]['next']=($i==$this->listLength?null:$value['next']);
$value['next']=$this->existedCounts;
$this->listLength++;
$this->existedCounts++;
return true;
}
/**
* 删除第$i个元素
* 删除第$i个元素,该元素为取值应该为[1,$this->listLength],需要注意,删除元素之后,
* $this->listLength减1,而$this->existedCounts不变。删除的方法为将第$i-1个元素的
* next指向第$i+1个元素,那么第$i个元素就从链表中删除了。
* @access public
* @param number $i 将要被删除的元素的序号
* @return boolean 成功则返回true,否则返回false
*/
public function delFromList($i)
{
if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength)
return false;
if ($i==1)
{
//若删除的结点为头结点,则需要从新设置链表头
$tmp=$this->linkList[$this->listHeader];
unset($this->linkList[$this->listHeader]);
$this->listHeader=$tmp['next'];
$this->listLength--;
return true;
}
else
{
$value =&$this->getElemRef($i);
$prevValue=&$this->getElemRef($i-1);
unset($this->linkList[$prevValue['next']]);
$prevValue['next']=$value['next'];
$this->listLength--;
return true;
}
}
/**
* 对链表的元素排序
* 谨慎使用此函数,排序后链表将被从新初始化,原有的成员变量将会被覆盖
* @accse public
* @param boolean $sortType='true' 排序方式,true表示升序,false表示降序,默认true
*/
public function listSort($sortType='true')
{
//从新修改关联关系可能会更复杂,所以我选择先还原成一维数组,然后对数组排序,然后再生成链表
$arr=$this->returnToArray();
$sortType?sort($arr):rsort($arr);
$this->createList($arr);
}
}
?>2:循环链表
/**
* 循环链表结构
* 循环链表是另外一种形式的链式存储结构。他的特点是表中最后的一个结点的指针
* 是指向头结点的,这样整个链表就构成了一个环。循环链表和单链表有很多相似之处
* 因此我们这里直接继承LinkList类来得到循环链表。
* @version 1.0
* @author 玉面修罗<[email=xiuluo-999@163.com]xiuluo-999@163.com[/email]>
*/
class CirLinkList extends LinkList
{
/**
* 生成循环链表
* 这里直接重写父类的createList方法,将最后一个结点的指针指向头结点
* @access public
* @param array $arr 需要被转化为循环链表的数组
* @return boolean true表示转换成功,false表示失败
*/
public function createList($arr)
{
if (parent::createList($arr))
{
$this->linkList[$this->listLength-1]['next']=$this->listHeader;
return true;
}
else return false;
}
/**
* 在第i个元素之后插入一个值为var的新元素
* 这里直接重写父类中的insertIntoList函数,需要注意的是:当$i=0,表示插入到头结点之前,
* 并且新元素变成头结点;当$i=$this->listLength时,表示插到链表最后,并把指针域指向头结点。
* 虽然它们在环中的位置可以说是相同的,但是意义不同。
* @access public
* @param number $i 在位置i插入新元素
* @param mixed $var 要插入的元素的值
* @return boolean 成功则返回true,否则返回false
*/
public function insertIntoList($i,$var)
{
if (parent::insertIntoList($i,$var))
{
//insertIntoList会使listLength加1,所以这里listLength-1实际是原来的listLength
if ($i==0||$i=$this->listLength-1)
{
$elem=&parent::getElemRef($this->listLength);
$elem['next']=$this->listHeader;
return true;
}
}
else return false;
}
/**
*删除第$i个元素
* 和父类中的此方法相比,只是当$i=1的时候,需要把尾结点的指针指向新的头结点
* @access public
* @param number $i 将要被删除的元素的序号
* @return boolean 成功则返回true,否则返回false
*/
public function delFromList($i)
{
if (parent::delFromList($i)&&$i==1)
{
$elem=&$this->getElemRef($this->listLength);
$elem['next']=$this->listHeader;
return true;
}
else return false;
}
}
循环链表的应用:
现在将a-z26个小写字母按照字母表的顺序逆时针围绕成一个圈,现在从a开始取字母:取字母的方法为跳1取,比如先取了a,跳过a后面的一个字母b,然
后取c,然后取e............如此反复下去, 直到26个字母全部取完,将取出的字母连成一个字符串,请求出此字符串。
/**
* 循环链表的运用
* 问题:现在将a-z26个小写字母按照字母表的顺序逆时针围绕成一个圈,现在从a开始取字母:取字母的
* 方法为跳1取,比如先取了a,跳过a后面的一个字母b,然后取c,然后取e............如此反复下去,
* 直到26个字母全部取完,将取出的字母连成一个字符串,请输出此字符串.
*/
class CatchChar extends CirLinkList
{
private $objectString;
/**
* 求字符串的方法
* @access public
* @return boolean
*/
public function createString()
{
$str='';
$arrIndex=$this->listHeader;
while ($this->listLength!=0)
{
$curr=$this->linkList[$arrIndex];
$this->delFromList($this->getElemLocation($arrIndex));
$arrIndex=@$this->linkList[$curr['next']]['next'];
$str.=$curr['var'];
}
$this->objectString=$str;
return true;
}
/**
* 取出字符串
*/
public function getString()
{
return $this->objectString;
}
}
复制代码求解过程:
$test=new CatchChar(range('a','z'));
$test->createString();
echo $test->getString();
?>
复制代码结果为:
- acegikmoqsuwybfjnrvzhpxldt
阅读(511) | 评论(0) | 转发(0) |