數據結構之線性表——鏈式存儲結構之單鏈表（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;
    }
}