<?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;
    }
}