前提
對(duì)于大多數(shù)的大一，大二的童鞋們來說咐蚯，可能最操蛋的就是數(shù)據(jù)結(jié)構(gòu)這個(gè)課了童漩，什么鏈表，堆棧春锋，隊(duì)列矫膨，圖，簡(jiǎn)直噩夢(mèng)期奔！對(duì)我也是侧馅，我也是在大三后實(shí)習(xí)后發(fā)現(xiàn)這個(gè)真的是個(gè)硬技能，
鏈表的實(shí)現(xiàn)
數(shù)據(jù)結(jié)構(gòu)第一個(gè)就是鏈表了呐萌，鏈表分為兩種有直接的數(shù)組形式的順序鏈馁痴，這里不討論，什么array_push(),array_pop()肺孤，函數(shù)基本能滿足日常的需求罗晕，但報(bào)告老板，我就是想裝個(gè)X
上代碼吧
<?php
/**
*@author:gongbangwei(18829212319@163.com)
*@version:1.0
*@date:2016-05-22
*單鏈表的基本操作
*1.初始化單鏈表 __construct()
*2.清空單鏈表 clearSLL()
*3.返回單鏈表長(zhǎng)度 getLength()
*4.判斷單鏈表是否為空 getIsEmpty()
*5.頭插入法建表 getHeadCreateSLL()
*6.尾插入法建表 getTailCreateSLL()
*7.返回第$i個(gè)元素 getElemForPos()
*8.查找單鏈表中是否存在某個(gè)值的元素 getElemIsExist()
*9.單鏈表的插入操作 getInsertElem()
*10.遍歷單鏈表中的所有元素 getAllElem()
*11.刪除單鏈中第$i個(gè)元素 getDeleteElem()
*12.刪除單鏈表所有重復(fù)的值 getElemUnique()
**/
header("content-type:text/html;charset=UTF-8");
class LNode{
public $mElem;
public $mNext;
public function __construct(){
$this->mElem=null;
$this->mNext=null;
}
}
class SingleLinkedList{
//頭結(jié)點(diǎn)數(shù)據(jù)
public $mElem;
//下一結(jié)點(diǎn)指針
public $mNext;
//單鏈表長(zhǎng)度
public static $mLength=0;
public function __construct(){
$this->mElem=null;
$this->mNext=null;
}
//返回單鏈表長(zhǎng)度
public static function getLength(){
return self::$mLength;
}
public function getIsEmpty(){
if(self::$mLength==0 && $this->mNext==null){
return true;
}
else{
return false;
}
}
public function clearSLL(){
if(self::$mLength>0){
while($this->mNext!=null){
$q=$this->mNext->mNext;
$this->mNext=null;
unset($this->mNext);
$this->mNext=$q;
}
self::$mLength=0;
}
}
public function getHeadCreateSLL($sarr){
$this->clearSLL();
if(is_array($sarr) and count($sarr)>0){
foreach ($sarr as $key => $value) {
$p= new LNode;
$p->mElem=$value;
$p->mNext=$this->mNext;
$this->mNext=$p;
self::$mLength++;
}
}
else{
return false;
}
return true;
}
public function getTailCreateSLL($sarr){
$this->clearSLL();
if(is_array($sarr) and count($sarr)>0){
$q=$this;
foreach($sarr as $value){
$p=new LNode;
$p->mElem=$value;
$p->mNext=$q->mNext;
$q->mNext=$p;
$q=$p;
self::$mLength++;
}
}
else{
return false;
}
}
public function getElemForPos($i){
if(is_numeric($i) && $i<self::$mLength && $i>0){
$p=$this->mNext;
for ($j=1; $j < $i ; $j++) {
$q=$p->mNext;
$p=$q;
}
return $p->mElem;
}
else{
return null;
}
}
public function getElemIsExist($value){
if($value){
$p=$this;
while($p->mNext!=null and $p->mElem!=value){
$q=$p->mNext;
$p=$q;
}
if($p->mElem==value){
return true;
}
else{
return false;
}
}
}
public function getElemPosition($value){
if($value){
$p=$this;
$pos=0;
while($p->mNext!=null and $p->mElem!=$value){
$q=$p->mNext;
$p=$q;
$pos++;
}
if($p->mElem==$value){
return $pos;
}
else{
return -1;
}
}
}
/*單鏈表的插入操作
*
*@param int $i 插入元素的位序赠堵，即在什么位置插入新的元素,從1開始
*@param mixed $e 插入的新的元素值
*@return boolean 插入成功返回true小渊，失敗返回false
*/
public function getInsertElem($i,$e){
if($i<self::$mLength){
$j=1;
$p=$this;
}
else{
return false;
}
while($p->mNext!=null and $j<$i){
$q=$p->mNext;
$p=$q;
$j++;
}
$q=new LNode;
$q->mElem=$e;
$q->mNext=$p->mNext;
$p->mNext=$q;
self::$mLength++;
return true;
}
/**
*刪除單鏈中第$i個(gè)元素
*@param int $i 元素位序
*@return boolean 刪除成功返回true,失敗返回false
*/
public function getDeleteElem($i){
if($i>self::$mLength || $i<1){
return false;
}
else{
$p=$this;
$j=1;
while($j<$i){
$p=$p->mNext;
$j++;
}
$q=$p->mNext;
$p->mNext=$q->mNext;
unset($q);
self::$mLength--;
return true;
}
}
public function getAllElem(){
$all=array();
if(!$this->getIsEmpty()){
$p=$this->mNext;
while($p->mNext){
$all[]=$p->mElem;
$p=$p->mNext;
}
if($p->mElem)
$all[]=$p->mElem;
return $all;
}
}
public function getElemUnique(){
if(!$this->getIsEmpty()){
$p=$this;
while($p->mNext!=null){
$q=$p->mNext;
$ptr=$p;
while($q->mNext!=null){
if(strcmp($p->mElem,$q->mElem)===0){
$ptr->mNext=$q->mNext;
$q->mNext=null;
unset($q->mNext);
$q=$ptr->mNext;
self::$mLength--;
}
else{
$ptr=$q;
$q=$q->mNext;
}
}
//處理最后一個(gè)元素
if(strcmp($p->mElem,$q->mElem)===0){
$ptr->mNext=null;
self::$mLength--;
}
$p=$p->mNext;
}//end of while
}
}
}
///////////////test//////////
$node=new SingleLinkedList;
$arr=array('gbw','michael','php','js');
//$node->getHeadCreateSLL($arr);
//print_r($node->getAllElem());
$node->getTailCreateSLL($arr);
echo $node->getElemForPos(2);
$pos=$node->getElemPosition('gbw');
echo $pos;
$node->getDeleteElem($pos);
$node->getInsertElem(1,'gbw2');
print_r($node->getAllElem());
希望對(duì)大家的php程序設(shè)計(jì)有所幫助！
