Comment implémenter une liste à chaînage unique en php

Comment implémenter une liste chaînée en PHP : écrivez d'abord la classe du nœud de la liste chaînée ; puis définissez deux méthodes dans la liste chaînée, à savoir l'insertion et la suppression, puis obtenez la longueur de la liste chaînée et ajoutez ; données du nœud ; obtenez enfin le nom du nœud et supprimez-le ou mettez-le simplement à jour.

L'environnement d'exploitation de cet article : système Windows 7, PHP7.1, ordinateur Dell G3.

Liste chaînée unique implémentée en PHP

Comme son nom l'indique, une liste chaînée unique est une structure de données liée. Elle a un en-tête et tous les nœuds sauf le dernier. Le nœud a son nœud successeur. Comme indiqué ci-dessous.

Tout d'abord, nous écrivons la classe du nœud de liste chaînée. Chaque nœud de la liste chaînée enregistre son champ de données et son pointeur de retour en arrière

//链表节点 
class node { 
    public $id; //节点id 
    public $name; //节点名称 
    public $next; //下一节点 
   
    public function __construct($id, $name) { 
        $this->id = $id; 
        $this->name = $name; 
        $this->next = null; 
    } 
}

Il existe deux méthodes particulièrement importantes dans la liste chaînée, l'insertion et la suppression. L'insertion nécessite de trouver la position d'insertion, de pointer le pointeur suivant de l'élément précédent vers le nœud inséré et de pointer le pointeur suivant du nœud inséré vers le nœud suivant, comme indiqué sur le côté gauche de la figure ci-dessous. La suppression pointe le pointeur suivant du nœud précédent vers le nœud suivant et renvoie le contenu des données de l'élément supprimé, comme indiqué sur le côté droit de la figure ci-dessous.

Recommandé : "Tutoriel vidéo PHP"

//单链表 
class singelLinkList { 
    private $header; //链表头节点 
   
    //构造方法 
    public function __construct($id = null, $name = null) { 
        $this->header = new node ( $id, $name, null ); 
    } 
 
    //获取链表长度 
    public function getLinkLength() { 
        $i = 0; 
        $current = $this->header; 
        while ( $current->next != null ) { 
            $i ++; 
            $current = $current->next; 
        } 
        return $i; 
    } 
 
    //添加节点数据 
    public function addLink($node) { 
        $current = $this->header; 
        while ( $current->next != null ) { 
            if ($current->next->id > $node->id) { 
                break; 
            } 
            $current = $current->next; 
        } 
        $node->next = $current->next; 
        $current->next = $node; 
    } 
 
    //删除链表节点 
    public function delLink($id) { 
        $current = $this->header; 
        $flag = false; 
        while ( $current->next != null ) { 
            if ($current->next->id == $id) { 
                $flag = true; 
                break; 
            } 
            $current = $current->next; 
        } 
        if ($flag) { 
            $current->next = $current->next->next; 
        } else { 
            echo "未找到id=" . $id . "的节点！<br>"; 
        } 
    }
 
    //判断连表是否为空
    public function isEmpty(){
            return $this->header == null;
    }
 
    //清空链表
    public function clear(){
            $this->header = null;
    } 
 
    //获取链表 
    public function getLinkList() { 
        $current = $this->header; 
        if ($current->next == null) { 
            echo ("链表为空!"); 
            return; 
        } 
        while ( $current->next != null ) { 
            echo &#39;id:&#39; . $current->next->id . &#39;   name:&#39; . $current->next->name . "<br>"; 
            if ($current->next->next == null) { 
                break; 
            } 
            $current = $current->next; 
        } 
    } 
 
    //获取节点名字 
    public function getLinkNameById($id) { 
        $current = $this->header; 
        if ($current->next == null) { 
            echo "链表为空!"; 
            return; 
        } 
        while ( $current->next != null ) { 
            if ($current->id == $id) { 
                break; 
            } 
            $current = $current->next; 
        } 
        return $current->name; 
    } 
 
    //更新节点名称 
    public function updateLink($id, $name) { 
        $current = $this->header; 
        if ($current->next == null) { 
            echo "链表为空!"; 
            return; 
        } 
        while ( $current->next != null ) { 
            if ($current->id == $id) { 
                break; 
            } 
            $current = $current->next; 
        } 
        return $current->name = $name; 
    } 
}
$lists = new singelLinkList (); 
$lists->addLink ( new node ( 5, &#39;eeeeee&#39; ) ); 
$lists->addLink ( new node ( 1, &#39;aaaaaa&#39; ) ); 
$lists->addLink ( new node ( 6, &#39;ffffff&#39; ) ); 
$lists->addLink ( new node ( 4, &#39;dddddd&#39; ) ); 
$lists->addLink ( new node ( 3, &#39;cccccc&#39; ) ); 
$lists->addLink ( new node ( 2, &#39;bbbbbb&#39; ) ); 
$lists->getLinkList (); 
echo "<br>-----------删除节点--------------<br>"; 
$lists->delLink ( 5 ); 
$lists->getLinkList ();
echo "<br>-----------更新节点名称--------------<br>"; 
$lists->updateLink ( 3, "222222" ); 
$lists->getLinkList ();
echo "<br>-----------获取节点名称--------------<br>"; 
echo $lists->getLinkNameById ( 5 );
echo "<br>-----------获取链表长度--------------<br>"; 
echo $lists->getLinkLength ();

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!