V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
DavidNineRoc
V2EX  ›  PHP

[数据结构]链表的实现在 PHP 中

  •  
  •   DavidNineRoc · 2018-04-24 10:13:26 +08:00 · 2520 次点击
    这是一个创建于 2165 天前的主题,其中的信息可能已经有所发展或是发生改变。

    开始对数据结构的学习


    今天写代码换了一个字体,以前一直用console很好看,今天发现一个更喜欢的风格Source Code Pro 上两张图,还是挺好看的!!!


    步入正题,讲讲链表的操作

    节点

    • 首先得有一个节点类,用于存储数据
    <?php
    
    namespace 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;
        	}
    }
    

    链表管理类(用于操作节点数据)

    • 操作类的代码由于太长,我们分部分解析

    头插入(因为比较简单,所以先讲这个)

    • 听名字,就知道是从头部插入一个节点
    • 当链表为空,则初始化当前节点
    • 当链表不为空,把新节点作为头结点
    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 是头结点,依次下去,超出位置返回 false )

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

    以上两个这是插入的基本操作。看一下实例的代码。

    <?php
    // 自动加载的代码就不贴了,直接在 github
    require __DIR__.'/../vendor/bootstrap.php';
    
    // 实例化一个链表管理对象
    $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);
    

    查找

    • 查找链表的值也是很简单的,只要遍历即可
    /**
    * 查找链表的值中的索引
    * 成功返回索引值,找不到返回 -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;
    }
    
    • 只需要遍历一次链表,找到相等的值,找到返回索引值,找不到返回 -1

    删除

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

    End

    • 代码已托管在github
    • 后续有时间继续学习数据结构,双链表,树之类的!!!
    第 1 条附言  ·  2018-04-24 11:23:03 +08:00
    Node 的构造错了,是里面的那层
    7 条回复    2018-04-24 14:12:20 +08:00
    gouchaoer
        2
    gouchaoer  
       2018-04-24 12:19:27 +08:00   ❤️ 1
    gouchaoer
        3
    gouchaoer  
       2018-04-24 12:20:51 +08:00
    php 写东西快么,一个原因就是数组是 array,链表是 array,字典是 array,hash 表是 array,json 是 array,啥都是 array
    MeteorCat
        4
    MeteorCat  
       2018-04-24 12:41:29 +08:00
    学习数据结构我感觉用 C/C++更好点,还能扩展其他的语言,顺便造个轮子自己用
    dobelee
        5
    dobelee  
       2018-04-24 12:49:42 +08:00 via Android   ❤️ 1
    array 和 stdClass 是 php 重要的组成部分,可以屏蔽大量的类型操作和异常处理,极大提升开发效率,堪称神作。
    但是对于高性能应用程序开发和新人数据结构的学习和理解是极其不利的。
    Junjunya
        6
    Junjunya  
       2018-04-24 13:49:26 +08:00
    好奇注释是怎么打的
    DavidNineRoc
        7
    DavidNineRoc  
    OP
       2018-04-24 14:12:20 +08:00
    @Cbdy 基本差不多,如果不写判断基本一样。
    @gouchaoer 在学习数据结构的实现 >_<, PHP 本身的数组就已经很强大了,所以我在写数据结构不用,而且参数定义强类型。
    @MeteorCat 哪门语言都一样,我已经在避开 PHP 的方便,用基础的实现
    @dobelee 新人倒算不上,学了好几年,只是最近在看到有些朋友发招聘 PHP 的,也问到算法,自己回来复习一下。以前学习 C 的时候学了一点

    @Junjunya 用的这个 http://asciiflow.com/
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5886 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 02:13 · PVG 10:13 · LAX 19:13 · JFK 22:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.