• 技术文章 >后端开发 >PHP问题

    php 怎么实现单链表

    藏色散人藏色散人2021-02-23 09:30:09原创89

    php实现单链表的方法:首先写出链表节点的类;然后在链表中还定义两个方法,分别是插入和删除;接着获取链表长度并添加节点数据;最后获取节点名字并进行删除或更新操作即可。

    本文操作环境:Windows7系统、PHP7.1、Dell G3电脑。

    用PHP实现的单链表

    单链表顾名思义就是一个链式数据结构,它有一个表头,并且除了最后一个节点外,所有节点都有其后继节点。如下图。

    首先,我们写出链表节点的类。单链表中的每一个节点,都保存其数据域和后驱指针

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

    链表中还有两个特别重要的方法,插入和删除。插入需要找到插入的位置,把前一个元素的next指针指向被插入的节点,并将被插入节点的next指针指向后一个节点,如下图左侧所示。而删除则是把前一个节点的next指针指向后一个节点,并返回被删除元素的数据内容,如下图右侧所示。

    推荐:《PHP视频教程

    //单链表 
    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 'id:' . $current->next->id . '   name:' . $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, 'eeeeee' ) ); 
    $lists->addLink ( new node ( 1, 'aaaaaa' ) ); 
    $lists->addLink ( new node ( 6, 'ffffff' ) ); 
    $lists->addLink ( new node ( 4, 'dddddd' ) ); 
    $lists->addLink ( new node ( 3, 'cccccc' ) ); 
    $lists->addLink ( new node ( 2, 'bbbbbb' ) ); 
    $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 怎么实现单链表的详细内容,更多请关注php中文网其它相关文章!

    本文原创发布php中文网,转载请注明出处,感谢您的尊重!
    专题推荐:php
    上一篇:php 除不尽怎么办 下一篇:php 怎么修改响应时间
    第15期线上培训班

    相关文章推荐

    • php怎么关闭debug模式• php5.3怎么安装redis扩展• php7如何安装yaf扩展• php如何实现日期转unix时间戳• php 除不尽怎么办

    全部评论我要评论

  • 取消发布评论发送
  • 1/1

    PHP中文网