Implémentation de liste chaînée en PHP

Le contenu de cet article concerne l'implémentation de listes chaînées en PHP. Il a une certaine valeur de référence. Maintenant, je le partage avec tout le monde. Les amis dans le besoin peuvent s'y référer

Commencez à vous renseigner sur les structures de données. 🎜 >

---

J'ai changé la police lors de l'écriture du code aujourd'hui. J'utilisais

et ça a l'air bien Aujourd'hui, j'ai trouvé un style que j'aime mieux console Source Code ProLes deux images ci-dessus sont toujours aussi belles. bien! ! !

---

Passons aux choses sérieuses et parlons du fonctionnement des listes chaînées

Noeud

• Il doit d'abord y avoir une classe de nœuds, utilisée pour stocker les données

<?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;
        }
}

Classe de gestion de liste chaînée (utilisée pour exploiter les données de nœuds)

• Parce que le code de la classe d'opération est trop long, nous allons l'analyser par parties

Insertion d'en-tête (car c'est relativement simple, donc je vais parlez-en en premier)

• Écoutez le nom, vous saurez qu'un nœud est inséré depuis la tête

• Lorsque la liste chaînée est vide, le nœud actuel est initialisé

• Lorsque la liste chaînée n'est pas vide, insérez le nouveau nœud comme nœud principal

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;
}

(index=0 est le nœud principal, descend dans l'ordre, renvoie false si la position est dépassée)

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;
}

---

Les deux ci-dessus sont les opérations de base de l'insertion. Jetez un œil à l’exemple de code.

<?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);

Rechercher

• Trouver la valeur de la liste chaînée est également très simple, il suffit de la parcourir

/**
* 查找链表的值中的索引
* 成功返回索引值，找不到返回 -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;
}

• Vous n'avez besoin de parcourir la liste chaînée qu'une seule fois, de trouver des valeurs égales et de renvoyer la valeur d'index si elle est trouvée. Si elle n'est pas trouvée, renvoyez -1

Supprimer.

/**
 * 删除链表的节点
 *
 * @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;
}

Fin

• Le code a été hébergé sur github

• Il sera temps de continuer à apprendre les structures de données , des listes doublement chaînées, des arbres et autres ! ! !

Recommandations associées :

php pour implémenter l'ordre inversé des listes chaînées

Utiliser PHP pour implémenter une liste chaînée unique

Comment implémenter une liste doublement chaînée et la trier en 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!