Implementierung einer verknüpften Liste in PHP-PHP-Tutorial-php.cn

Der Inhalt dieses Artikels befasst sich mit der Implementierung verknüpfter Listen in PHP. Jetzt kann ich ihn mit allen teilen, die ihn benötigen

Beginnen Sie mit dem Erlernen von Datenstrukturen

Heute habe ich Code geschrieben und eine Schriftart geändert, die ich verwendet habe console Heute habe ich einen Stil gefunden, der mir besser gefällt Source Code Pro
Die beiden Bilder oben sehen immer noch aus Gut! ! !

Lassen Sie uns zur Sache kommen und über die Funktionsweise verknüpfter Listen sprechen

Knoten

Zuerst muss es eine Knotenklasse geben, die zum Speichern von Daten verwendet wird

<?phpnamespace LinkedList;class Node{
    /**
     * @var $data integer
     */
    public $data;    /**
     * 节点指向的下一个元素
     *
     * @var $next Node
     */
    public $next;    public function __construct(int $data = -1)
    {
        public function __construct(int $data = null)
        {
            // 初始化赋值 data，也可通过 $node->data = X; 赋值
            $this->data = $data;
        }
}

Nach dem Login kopieren

Verwaltungsklasse für verknüpfte Listen (wird zum Betreiben von Knotendaten verwendet)

Da der Code der Operationsklasse zu lang ist, werden wir ihn in Teilen analysieren

Header-Einfügung (da es relativ einfach ist, werde ich sprechen dazu zuerst)

Hören Sie sich den Namen an, Sie werden wissen, dass ein Knoten vom Kopf aus eingefügt wird
Wenn die verknüpfte Liste leer ist , der aktuelle Knoten wird initialisiert
Wenn die verknüpfte Liste nicht leer ist, fügen Sie den neuen Knoten als Kopfknoten ein

public function insertHead(int $data) : bool{
    ///////////////////////////////////////////////////////////////////////////
    // +-----------+    +--------+    +--------+
    // |           |    |        |    |        |
    // | head node | +> |  node  | +> |  node  | +>
    // |           | |  |        | |  |        | |
    // |           | |  |        | |  |        | |
    // |    next   | |  |  next  | |  |  next  | |
    // +------+----+ |  +----+---+ |  +----+---+ |
    //        |      |       |     |       |     |
    //        +------+       +-----+       +-----+
    ///////////////////////////////////////////////////////////////
    //                   +-----------+    +--------+    +--------+
    //                   |           |    |        |    |        |
    //             +---> | head node | +> |  node  | +> |  node  | +>
    //             |     |           | |  |        | |  |        | |
    //             |     |           | |  |        | |  |        | |
    //             |     |    next   | |  |  next  | |  |  next  | |
    //             |     +------+----+ |  +----+---+ |  +----+---+ |
    //             |            |      |       |     |       |     |
    //  +--------+ |            +------+       +-----+       +-----+
    //  |        | |
    //  |new node| |
    //  |        | |
    //  |        | |
    //  |  next  | |
    //  +----+---+ |
    //       |     |
    //       +-----+
    //
    // 1. 实例化一个数据节点
    // 2. 使当前节点的下一个等于现在的头结点
    //        即使当前头结点是 null，也可成立
    // 3. 使当前节点成为头结点
    //        即可完成头结点的插入
    $newNode = new Node($data);    $newNode->next = $this->head;    $this->head = $newNode;    return true;
}

Nach dem Login kopieren

( Index = 0 ist der Hauptknoten. Gehen Sie der Reihe nach nach unten und geben Sie false zurück, wenn die Position überschritten wird.

public function insert(int $index = 0, int $data) : bool{
    // 头结点的插入, 当头部不存在，或者索引为0
    if (is_null($this->head) || $index === 0) {        return $this->insertHead($data);
    }    // 正常节点的插入, 索引从 0 开始计算
    // 跳过了头结点，从 1 开始计算
    $currNode = $this->head;    $startIndex = 1;    // 遍历整个链表，如果当前节点是 null，则代表到了尾部的下一个，退出循环
    for ($currIndex = $startIndex; ! is_null($currNode); ++ $currIndex) {        ////////////////////////////////////////////////////////////////////////////
        ///
        //   +--------+    +--------+    +-------------+    +--------+
        //   |        |    |        |    |             |    |        |
        //   |  node  | +> |currNode| +> |currNode next| +> |  node  | +>
        //   |        | |  |        | |  |             | |  |        | |
        //   |        | |  |        | |  |             | |  |        | |
        //   |  next  | |  |  next  | |  |     next    | |  |  next  | |
        //   +----+---+ |  +----+---+ |  +------+------+ |  +----+---+ |
        //        |     |       |     |         |        |       |     |
        //        +-----+       +-----+         +--------+       +-----+
        ////////////////////////////////////////////////////////////////////////////
        //   +--------+    +--------+                +-------------+    +--------+
        //   |        |    |        |                |             |    |        |
        //   |  node  | +> |currNode|             +> |currNode next| +> |  node  | +>
        //   |        | |  |        |             |  |             | |  |        | |
        //   |        | |  |        |             |  |             | |  |        | |
        //   |  next  | |  |  next  |             |  |     next    | |  |  next  | |
        //   +----+---+ |  +--------+             |  +------+------+ |  +----+---+ |
        //        |     |              +--------+ |         |        |       |     |
        //        +-----+              |        | |         +--------+       +-----+
        //                             |new node| |
        //                             |        | |
        //                             |        | |
        //                             |  next  | |
        //                             +----+---+ |
        //                                  |     |
        //                                  +-----+
        ////////////////////////////////////////////////////////////////////////////
        //
        //   +--------+    +--------+                +-------------+    +--------+
        //   |        |    |        |                |             |    |        |
        //   |  node  | +> |currNode|             +> |currNode next| +> |  node  | +>
        //   |        | |  |        |             |  |             | |  |        | |
        //   |        | |  |        |             |  |             | |  |        | |
        //   |  next  | |  |  next  |             |  |     next    | |  |  next  | |
        //   +----+---+ |  +----+---+             |  +------+------+ |  +----+---+ |
        //        |     |       |      +--------+ |         |        |       |     |
        //        +-----+       |      |        | |         +--------+       +-----+
        //                      +----> |new node| |
        //                             |        | |
        //                             |        | |
        //                             |  next  | |
        //                             +----+---+ |
        //                                  |     |
        //                                  +-----+
        //
        // 1. 当前索引等于传入参数的索引
        // 2. 实例化新数据节点
        // 3. 新节点的下一个指向当前节点的下一个节点
        // 4. 当前节点的下一个节点指向新节点
        if ($currIndex === $index) {            $newNode = new Node($data);            $newNode->next = $currNode->next;            $currNode->next = $newNode;            return true;
        }        // 移动到下一个节点
        $currNode = $currNode->next;
    }    return false;
}

Nach dem Login kopieren

Die beiden oben genannten sind die grundlegenden Operationen des Einfügens. Schauen Sie sich den Beispielcode an.

<?php
// 自动加载的代码就不贴了，直接在 githubrequire __DIR__.&#39;/../vendor/bootstrap.php&#39;;
// 实例化一个链表管理对象$manager = new \LinkedList\Manager();
// 8$manager->insertHead(8);
// 5 8$manager->insertHead(5);
// 1 5 8$manager->insertHead(1);
// 1 2 5 8$manager->insert(1, 2);
// false 节点元素不足 6 个$manager->insert(5, 4);
// 1 2 5 8 9$manager->insertEnd(9);
// 3$manager->find(8);
// 1 2 8 9$manager->delete(2);

Nach dem Login kopieren

Suchen

Das Ermitteln des Werts der verknüpften Liste ist ebenfalls sehr einfach. Durchlaufen Sie ihn einfach

/**
* 查找链表的值中的索引
* 成功返回索引值，找不到返回 -1
*
* @param int $data
* @return int
*/public function find(int $data) : int{
    $currNode = $this->head;    // 查找还是很简单的，只要遍历一次链表，然后再判断值是否相等就可以了
    for ($i = 0; ! is_null($currNode); ++ $i) {        if ($currNode->data === $data) {            return $i;
        }        $currNode = $currNode->next;
    }    return -1;
}

Nach dem Login kopieren

Sie müssen die verknüpfte Liste nur einmal durchlaufen, gleiche Werte finden und den Indexwert zurückgeben, falls nicht gefunden, -1 zurückgeben

Löschen

/**
 * 删除链表的节点
 *
 * @param int $index
 * @return bool
 */public function delete(int $index) : bool{
    // 没有任何节点，直接跳过
    if (is_null($this->head)) {       return false;
    } elseif ($index === 0) {        // 头结点的删除
        $this->head = $this->head->next;
    }    // 这里的开始的索引是 1
    // 但当前节点指向的确实 头结点
    // 因为删除的时候必须标记删除的前一个节点
    // for 的判断是判断下一个节点是否为 null
    // $currNode 是操作的节点
    //    $currNode->next 是要删除的节点
    $startIndex = 1;    $currNode = $this->head;    for ($i = $startIndex; ! is_null($currNode->next); ++ $i) {        if ($index === $i) {            // 使当前节点等于要删除节点的下一个
            // 即可完成删除
            $currNode->next = $currNode->next->next;            break;
        }        $currNode = $currNode->next;
    }    return true;
}

Nach dem Login kopieren

Ende

Der Code wurde auf Github gehostet
Es wird Zeit sein, mit dem Erlernen von Datenstrukturen fortzufahren , doppelt verkettete Listen, Bäume und dergleichen! ! !

Verwandte Empfehlungen:

PHP zur Implementierung verknüpfter Listen in umgekehrter Reihenfolge

Verwenden Sie PHP zur Implementierung einfach verknüpfter Listen

So implementieren Sie eine doppelt verkettete Liste und sortieren sie in PHP

Das obige ist der detaillierte Inhalt vonImplementierung einer verknüpften Liste in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!