PHP實作 單連結清單

<?php
/**
 * Created by PhpStorm.
 * User: BaiMayou
 * Date: 2019/2/23
 * Time: 14:22
 */
/*
* php，java這種面向對象行的語言，需要通過類的方式來定義連結清單,c,c++則可以直接定義一個連結清單
* 是以對連結清單的定義直接影響到對連結清單的操作，這裡采用的是最接近c的連結清單定義的一種，同時也是大部分面試的算法題中給出的單連結清單的定義
*/
//單連結清單的定義
class ListNode{
    public $data = '';//連結清單的資料域
    public $next = null;//連結清單的指針域
    public function __construct($val)
    {
        $this->data = $val;
    }
}
/*
* 單連結清單的操作
* 對于單連結清單的操作有基本的在末尾增加，删除新節點，統計節點數量，周遊單連結清單
* 稍複雜的是在指定位置增加，删除，修改等
* 對應的算法有連結清單的逆轉，查環等
* 是以完成這些功能時，即便很細心，但是因為類的原因或者寫的不夠完善，而産生一些奇怪的錯誤。例如，頭結點，和head到底表示什麼這些問題
* 從代碼上我們可以看到，$head表示的就是一個的對象，每一個對象的next屬性中存放着另一個對象或null，！
* 在了解的時候需要我們抽象為連結清單的結構，這樣更容易了解，而$head表示指針指向的位置，是以指針一開始在連結清單的第一個節點位置，及頭結點；
* $head->next = $a 也就表示在連結清單中，head節點的next指針域中存放着節點a的位址，對應為結構圖就為：！
*
* 有時候還會影響我們對這些資料結構的了解，這也是在寫算法中多使用c，c++等面向過程的語言的原因之一。
*/

//可以發現每個節點的next指針域中存放着一個對象，這個對象就是定義的單連結清單的一個節點
//
//統計節點數量
function CountNode($head){
    $current = $head;//将目前節點設定為頭結點
    $i = 0;
    while(!is_null($current->next)){
        ++$i;
        $current = $current->next;
    }
    return $i;
}
//周遊節點
function fetchNode($head){
    $current = $head;//在此需要注意一個問題，在php中對象的指派，其實是對象位址的指派，即$current = &$head，是以操作$current就相當于操作$head
    while(!is_null($current->next)){
        $current = $current->next;
        echo $current->data.'->';
    }
}
//在末尾增加節點（原理就是通過周遊連結清單，在連結清單末尾插入一個值為val，next為null的節點）
function addNode($head,$val){
    $current = $head;
    $b = $head;
    while(!is_null($current->next)){
        $current = $current->next;
    }
    $new = new ListNode($val);
    $current->next = $new;
    return $b;
}
//删除節點
function delNode($head){
    $current = $head;
    while(!is_null($current->next)){
        $current = $current->next;
    }
    $current->next->next = null;
}

//逆轉單連結清單
//單連結清單是從第一個節點開始周遊的
function reverseList($head) {
    if($head == null){
        return null;
    }
    $pre = null;
    while(!is_null($head)){
        $temp = $head->next;
        $head->next = $pre;
        $pre = $head;
        $head = $temp;
    }
    return $pre;
}
$head = new ListNode(null);
addNode($head,1);
echo CountNode($head);

//addNode($head,2);
//addNode($head,3);
//addNode($head,4);
//addNode($head,5);
//$a = reverseList($head);
//var_dump($a);
//fetchNode($a);