数据结构-PHP 类对象实现 ‘链表’

码农天地 - 2020-10-20 23:47:59

这篇文章是展示如何使用PHP语言实现 链表(Linked List) 这种数据结构，Linked List 是一种最简单的动态数据结构，学习 Linked List 可以帮助更深入地理解指针和递归，可以用来组织更复杂的数据结构，它的特点是数据存储在 节点(Node) 中，节点中还存储了指向下一个节点的引用变量，Linked List 不需要处理固定容量的问题。

1.output_linked_list.php

这是一个调用和打印输出结果的展示文件：

<?php
require 'LinkedList.php';

$linkedList = new LinkedList();
$linkedList->addFirst("aa");
$linkedList->addFirst("bb");
$linkedList->addFirst("cc");
$linkedList->addFirst("dd");
$linkedList->addFirst("ee");
$linkedList->addFirst("ff");
$linkedList->addFirst("gg");
$linkedList->addFirst("hh");
$linkedList->addFirst("ii");
echo $linkedList->toString(); //打印 ii->hh->gg->ff->ee->dd->cc->bb->aa->null

$linkedList->add(3, "100");
echo "<br>";
echo $linkedList->toString(); //打印 ii->hh->gg->100->ff->ee->dd->cc->bb->aa->null

$linkedList->remove(2);
echo "<br>";
echo $linkedList->toString(); //打印 ii->hh->100->ff->ee->dd->cc->bb->aa->null

$linkedList->removeFirst();//删除链表头元素
echo "<br>";
echo $linkedList->toString(); //打印 hh->100->ff->ee->dd->cc->bb->aa->null

$linkedList->removeLast();//删除链表末尾元素
echo "<br>";
echo $linkedList->toString(); //打印 hh->100->ff->ee->dd->cc->bb->null

2.LinkedList.php

这个类是一个封装好的链表类：

<?php

/**
 * 链表的实现
 * Class LinkedList
 */
class LinkedList {
    private $dummyHead;
    private $size;

    /**
     * 初始化链表 null->null
     * LinkedList constructor.
     */
    public function __construct() {
        $this->dummyHead = new Node(null, null);
        $this->size = 0;
    }

    /**
     * 获取链表大小
     * @return int
     */
    public function getSize(): int {
        return $this->size;
    }

    /**
     * 判断链表是否为空
     * @return bool
     */
    public function isEmpty(): bool {
        return $this->size == 0;
    }

    /**
     * 在链表的第 index 位置添加元素
     * @param int $index
     * @param $e
     */
    public function add(int $index, $e): void {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        $prve = $this->dummyHead;
        for ($i = 0; $i < $index; $i++) {
            $prve = $prve->next;
        }
        //将上插入位置的上一个位置的 next 节点指向插入节点，插入节点的 next 节点信息指向原上节点的 next 节点
        $prve->next = new Node($e, $prve->next);
        $this->size++;
    }

    /**
     * 向链表开头添加元素
     * @param $e
     */
    public function addFirst($e): void {
        $this->add(0, $e);
    }

    /**
     * 向链表末尾添加元素
     * @param $e
     */
    public function addLast($e): void {
        $this->add($this->size, $e);
    }

    /**
     * 获取链表第 index 位置元素
     * @param $index
     */
    public function get($index) {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }

        $node = $this->dummyHead;
        for ($i = 0; $i < $node + 1; $i++) {
            $node = $node->next;
        }
        return $node->e;
    }

    /**
     * 获取链表第一个元素
     * @return mixed
     */
    public function getFirst() {
        return $this->get(0);
    }

    /**
     * 获取链表最后一个元素
     * @return mixed
     */
    public function getLast() {
        return $this->get($this->size - 1);
    }

    /**
     * 修改链表中第 index 位置元素值
     * @param $index
     * @param $e
     */
    public function update($index, $e) {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        $node = $this->dummyHead;

        for ($i = 0; $i < $index + 1; $i++) {
            $node = $node->next;
        }
        $node->e = $e;
    }

    /**
     * 判断链表中是否存在某个元素
     * @param $e
     * @return bool
     */
    public function contains($e): bool {
        for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {
            if ($node->e == $e) {
                return true;
            }
        }
        return true;
    }

    /**
     * 删除链表中第 index 位置元素
     * @param $index
     */
    public function remove($index) {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        if ($this->size == 0) {
            echo "链表已经是空";
            exit;
        }

        $prve = $this->dummyHead;
        for ($i = 0; $i < $index; $i++) {
            $prve = $prve->next;
        }
        $node = $prve->next;
        $prve->next = $node->next;

        $this->size--;
        return $node;
    }

    /**
     * 删除链表头元素
     */
    public function removeFirst() {
        $this->remove(0);
    }

    /**
     * 删除链表末尾元素
     */
    public function removeLast() {
        $this->remove($this->size - 1);
    }

    /**
     * 链表元素转化为字符串显示
     * @return string
     */
    public function toString(): string {
        $str = "";
        for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {
            $str .= $node->e . "->";
        }
        return $str . "null";
    }
}

class Node {
    public $e;//节点元素
    public $next; //下个节点信息

    /**
     * 构造函数 设置节点信息
     * Node constructor.
     * @param $e
     * @param $next
     */
    public function __construct($e, $next) {
        $this->e = $e;
        $this->next = $next;
    }
}

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。