<?php/****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<$num;$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<$num;$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<$pos){$count++;$p=$p->next;}if(!$p||$pos<$count){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<$pos){$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<$pos){$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;}}