Implémenter une liste chaînée unique en utilisant PHP

Cet article présente principalement l'utilisation de PHP pour implémenter des listes à lien unique. Il a une certaine valeur de référence. Maintenant, je le partage avec vous. Les amis dans le besoin peuvent s'y référer<.>

Une liste chaînée unique, comme son nom l'indique, est une structure de données liée. Elle a un en-tête et tous les nœuds sauf le dernier nœud ont leur successeur. nœuds. 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 à lien unique enregistre son champ de données et son pointeur de retour

[php] voir en clair copier

1. //链表节点   
   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, insérer et supprimer . 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.

[php] view plain copy

1. //单链表   
   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 ();

相关推荐：

使用php来解析实现二级域名重定向

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!