数据结构之线性表——链式存储结构之单链表（php代码实现）

<?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: 遍历单链表的所有数据元素  *  */ class LNode{     public $data;     public $next;     public function __construct($data=null){         $this->data=$data;         $this->next=null;     } } class SingleLinkList{     public $data;     public $next;     public function __construct(){         $this->data=null;         $this->next=null;     }     //具有$num个数据元素的单链表的创建——头插法     public function CreateListHead($num){         for($i=0;$i<$num;$i++){             $node=new LNode();             $node->data=mt_rand(100,200);             $node->next=$this->next;             $this->next=$node;         }     }     //具有$num个数据元素的单链表的创建——尾插法     public function CreateListTail($num){         $tail=$this;         for($i=0;$i<$num;$i++){             $node=new LNode();             $node->data=mt_rand(100,200);             $tail->next=$node;             $tail=$node;         }         $node->next=null;     }     //销毁单链表     public function DestroyList(){         //$this相当于头指针,它指向的是头结点，$this->next相当于第一个结点         //之所以需要将$this赋值给$that，是因为$this无法用作变量进行赋值         $that=$this;         while($that){             $node=$that->next;             unset($that);             $that=$node;         }     }     //将单链表清空     public function ClearList(){         $p=$this->next;         while($p){             $node=$p->next;             unset($node);             $p=$node;         }         $this->next=null;     }     //判断单链表是否为空     public function ListEmpty(){         if($this->next){             return false;         }else{             return true;         }     }     //返回单链表中数据元素的个数     public function ListLength(){         $count=0;//初始化变量         $p=$this->next;         while($p){             $count++;             $p=$p->next;         }         return $count;     }     //返回指定位置的数据元素     public function GetElem($pos){         $count=1;         $p=$this->next;         while($p && $count<$pos){             $count++;             $p=$p->next;         }         if(!$p || $pos<$count){             return 'ERROR';         }         return $p->data;     } //    或者     public function GetElem2($pos){         $count=0;         $p=$this->next;         while($p){             $count++;             if($count==$pos){                 return $p->data;             }             $p=$p->next;         }         return 'ERROR';     }     //查找指定元素在单链表中的位序     public function LocateElem($elem){         $count=0;         $p=$this->next;         while($p){             $count++;             if($p->data==$elem){                 return $count;             }         }         return 'ERROR';     }     //获取指定元素的前面一个元素     public function PriorElem($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';     }     //获取指定元素的后面一个元素     public function NextElem($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';     }     //在指定位置之前插入一个节点元素     public function ListInsert($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';     }     //或者 这种效率会高一些     public function ListInsert2($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';     }     //删除单链表指定位置的数据元素     public function ListDelete($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';     } //    或者     public function ListDelete2($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';     }     //单链表的遍历     public function ListTraverse(){         $arr=array();         $p=$this->next;         while($p){             $arr[]=$p->data;             $p=$p->next;         }         return $arr;     } }