/**
*
*1.类LNode用作创建单链表时，生成新的节点。
*2.类SingleLinkList用于创建单链表以及对单链表的一些操作方法(实例化此类就相当于创建了一个空链表)
*3.CreateListHead:具有$num个数据元素的单链表的创建——头插法
*4.CreateListTail:具有$num个数据元素的单链表的创建——尾插法
*5.DestroyList:销毁单链表
*6.ClearList：清空单链表
*7.ListEmpty：判断单链表是否为空
*8.ListLength：返回单链表数据元素的个数
*9.GetElem：返回单链表中指定位置的数据元素
*10.LocateElem：查找指定元素在单链表中的位序
*11.PriorElem：获取指定元素的前面一个元素
*12.NextElem：获取指定元素的后面一个元素
*13.ListInsert：在指定位置之前插入一个数据元素
*14.ListDelete:删除指定位置的数据元素
*15.ListTraverse:遍历单链表的所有数据元素
*
*/
classLNode{
public$data;
public$next;
publicfunction__construct($data=null){
$this->data=$data;
$this->next=null;
}
}
classSingleLinkList{
public$data;
public$next;
publicfunction__construct(){
$this->data=null;
$this->next=null;
}
//具有$num个数据元素的单链表的创建——头插法
publicfunctionCreateListHead($num){
for($i=0;$i
$node=newLNode();
$node->data=mt_rand(100,200);
$node->next=$this->next;
$this->next=$node;
}
}
//具有$num个数据元素的单链表的创建——尾插法
publicfunctionCreateListTail($num){
$tail=$this;
for($i=0;$i
$node=newLNode();
$node->data=mt_rand(100,200);
$tail->next=$node;
$tail=$node;
}
$node->next=null;
}
//销毁单链表
publicfunctionDestroyList(){
//$this相当于头指针,它指向的是头结点，$this->next相当于第一个结点
//之所以需要将$this赋值给$that，是因为$this无法用作变量进行赋值
$that=$this;
while($that){
$node=$that->next;
unset($that);
$that=$node;
}
}
//将单链表清空
publicfunctionClearList(){
$p=$this->next;
while($p){
$node=$p->next;
unset($node);
$p=$node;
}
$this->next=null;
}
//判断单链表是否为空
publicfunctionListEmpty(){
if($this->next){
returnfalse;
}else{
returntrue;
}
}
//返回单链表中数据元素的个数
publicfunctionListLength(){
$count=0;//初始化变量
$p=$this->next;
while($p){
$count++;
$p=$p->next;
}
return$count;
}
//返回指定位置的数据元素
publicfunctionGetElem($pos){
$count=1;
$p=$this->next;
while($p&&$count
$count++;
$p=$p->next;
}
if(!$p||$pos
return'ERROR';
}
return$p->data;
}
//或者
publicfunctionGetElem2($pos){
$count=0;
$p=$this->next;
while($p){
$count++;
if($count==$pos){
return$p->data;
}
$p=$p->next;
}
return'ERROR';
}
//查找指定元素在单链表中的位序
publicfunctionLocateElem($elem){
$count=0;
$p=$this->next;
while($p){
$count++;
if($p->data==$elem){
return$count;
}
}
return'ERROR';
}
//获取指定元素的前面一个元素
publicfunctionPriorElem($elem){
$p=$this->next;
if($p&&$p->data=$elem){
return$p->data.'已经是第一个元素，已无前驱元素';
}
while($p&&$p->next){
$q=$p->next;
if($q->data==$elem){
return$p->data;
}
$p=$q;
}
return'ERROR';
}
//获取指定元素的后面一个元素
publicfunctionNextElem($elem){
$p=$this->next;
while($p&&$p->next){
if($p->data==$elem){
return$p->next->data;
}
$p=$p->next;
}
if($p&&$p->next==null){
return$p->data.'已经是最后一个元素，已无后继元素';
}
return'ERROR';
}
//在指定位置之前插入一个节点元素
publicfunctionListInsert($pos,$node){
$p=$this;
$count=0;
while($p){
$count++;
if($count==$pos){
$node->next=$p->next;
$p->next=$node;
return'OK';
}
$p=$p->next;
}
return'ERROR';
}
//或者这种效率会高一些
publicfunctionListInsert2($pos,$node){
$p=$this;
$count=1;
while($p&&$count
$count++;
$p=$p->next;
}
if(!$p||$count>$pos){
return'ERROR';
}
$node->next=$p->next;
$p->next=$node;
return'OK';
}
//删除单链表指定位置的数据元素
publicfunctionListDelete($pos){
$count=1;
$p=$this;
while($p&&$count
$count++;
$p=$p->next;
}
if(!$p||$count>$pos){
return'ERROR';
}
$q=$p->next;
$p->next=$q->next;
unset($q);
return'OK';
}
//或者
publicfunctionListDelete2($pos){
$count=0;
$p=$this;
//此处之所以使用$p->next，而不是$p作为判断条件是因为这样可以在链表为空的时候，少一次无谓的循环。
while($p->next){
$count++;
if($count==$pos){
$q=$p->next;
$p->next=$q->next;
unset($q);
return'OK';
}
$p=$p->next;
}
return'ERROR';
}
//单链表的遍历
publicfunctionListTraverse(){
$arr=array();
$p=$this->next;
while($p){
$arr[]=$p->data;
$p=$p->next;
}
return$arr;
}
}
