Implementieren Sie einfach verknüpfte Listen mit PHP

Dieser Artikel stellt hauptsächlich die Verwendung von PHP zur Implementierung einfach verknüpfter Listen vor. Jetzt kann ich ihn mit Ihnen teilen.

Eine einfach verknüpfte Liste ist, wie der Name schon sagt, eine verknüpfte Datenstruktur. Sie hat einen Header und alle Knoten außer dem letzten Knoten haben ihren Nachfolger Knoten. Wie unten gezeigt.

Zuerst schreiben wir die Klasse des verknüpften Listenknotens. Jeder Knoten in der einfach verknüpften Liste speichert sein Datenfeld und seinen Back-Drive-Zeiger

[php]Einfach anzeigenkopieren

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

Es gibt zwei besonders wichtige Methoden in der verknüpften Liste: Einfügen und Löschen . Das Einfügen erfordert das Finden der Einfügeposition, das Zeigen des nächsten Zeigers des vorherigen Elements auf den eingefügten Knoten und das Zeigen des nächsten Zeigers des eingefügten Knotens auf den nächsten Knoten, wie auf der linken Seite der folgenden Abbildung dargestellt. Das Löschen zeigt den nächsten Zeiger des vorherigen Knotens auf den nächsten Knoten und gibt den Dateninhalt des gelöschten Elements zurück, wie auf der rechten Seite der folgenden Abbildung dargestellt.

[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来解析实现二级域名重定向

Das obige ist der detaillierte Inhalt vonImplementieren Sie einfach verknüpfte Listen mit PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!