无限极分类的两种方式,递归和引用

说到无限极分类,比较常见的做法是在建表的时候,增加一个parnet_id字段用来区别自己所属的分类(是顶级分类还是子分类)

1111.png

由于展示数据的时候,需要表达出这种所属关系,所以必然要在读取数据的时候进行一系列处理,由此就牵涉到了两种算法


看下未无限极分类之前的数据结构如下(假设这个数组叫$data):

array (size=6)
  0 => 
    array (size=4)
      'cat_id' => int 7
      'cname' => string 'php' (length=3)
      'is_show' => int 1
      'parent_id' => int 80
  1 => 
    array (size=4)
      'cat_id' => int 6
      'cname' => string 'mysql' (length=5)
      'is_show' => int 1
      'parent_id' => int 80
  2 => 
    array (size=4)
      'cat_id' => int 74
      'cname' => string 'Linux' (length=5)
      'is_show' => int 1
      'parent_id' => int 80
  3 => 
    array (size=4)
      'cat_id' => int 80
      'cname' => string '软件开发' (length=12)
      'is_show' => int 1
      'parent_id' => int 0
  4 => 
    array (size=4)
      'cat_id' => int 87
      'cname' => string '生活随笔' (length=12)
      'is_show' => int 1
      'parent_id' => int 0
  5 => 
    array (size=4)
      'cat_id' => int 94
      'cname' => string '邻居' (length=6)
      'is_show' => int 1
      'parent_id' => int 0

一、巧妙的引用算法

由于众所周知的原因,递归对资源的消耗是非常大的,实际执行起来效率也很低,所以有了下面的通过引用算法

上代码:

/**
 * 无限极分类(引用方式)
 *@param  array $data需要分类的数组
 *@return array 返回一个已经无限极分类完成的数组
 */
function getTree($data)
{
    $items = array();
    
    //构建一个新的数组 新数组的key值是自己的主键id值(我这里表的主键是cat_id)
    //为何要构建这样一个数组 这就是和下面第二个foreach有关了,看了代码后就会明白何为巧妙引用了
    foreach($data as $v)
    {
        $items[$v['cat_id']] = $v;
    }

    $tree = array();

    //将数据进行无限极分类  
    foreach($items as $key => $val)
    {
        if(isset($items[$val['parent_id']]))
        {
            //关键是看这个判断,是顶级分类就给$tree,不是的话继续拼凑子分类(结合上述&用法)
            $items[ $val['parent_id'] ] ['child'] [] = &$items[$key];
        }
        else
        {
            $tree[] = &$items[$key];
        }
    }

    //返回无限极分类后的数据
    return $tree;
}

上面代码中第一个foreach之后 $items数组变成如下结构:

array (size=6)
  7 => 
    array (size=4)
      'cat_id' => int 7
      'cname' => string 'php' (length=3)
      'is_show' => int 1
      'parent_id' => int 80
  6 => 
    array (size=4)
      'cat_id' => int 6
      'cname' => string 'mysql' (length=5)
      'is_show' => int 1
      'parent_id' => int 80
  74 => 
    array (size=4)
      'cat_id' => int 74
      'cname' => string 'Linux' (length=5)
      'is_show' => int 1
      'parent_id' => int 80
  80 => 
    array (size=4)
      'cat_id' => int 80
      'cname' => string '软件开发' (length=12)
      'is_show' => int 1
      'parent_id' => int 0
  87 => 
    array (size=4)
      'cat_id' => int 87
      'cname' => string '生活随笔' (length=12)
      'is_show' => int 1
      'parent_id' => int 0
  94 => 
    array (size=4)
      'cat_id' => int 94
      'cname' => string '邻居' (length=6)
      'is_show' => int 1
      'parent_id' => int 0

第二个foreach之后 $tree数组变成如下结构:

array (size=3)
  0 => 
    array (size=5)
      'cat_id' => int 80
      'cname' => string '软件开发' (length=12)
      'is_show' => int 1
      'parent_id' => int 0
      'child' => 
        array (size=3)
          0 => 
            array (size=4)
              'cat_id' => int 7
              'cname' => string 'php' (length=3)
              'is_show' => int 1
              'parent_id' => int 80
          1 => 
            array (size=4)
              'cat_id' => int 6
              'cname' => string 'mysql' (length=5)
              'is_show' => int 1
              'parent_id' => int 80
          2 => 
            array (size=4)
              'cat_id' => int 74
              'cname' => string 'Linux' (length=5)
              'is_show' => int 1
              'parent_id' => int 80
  1 => 
    array (size=4)
      'cat_id' => int 87
      'cname' => string '生活随笔' (length=12)
      'is_show' => int 1
      'parent_id' => int 0
  2 => 
    array (size=4)
      'cat_id' => int 94
      'cname' => string '邻居' (length=6)
      'is_show' => int 1
      'parent_id' => int 0

二、国民级算法-递归

从数据库取得二维数组省略,递归的思路其实很简单,遍历数组,根据每条数据的id值去寻找所有parent_id值等于自己id值的数据,直到找不到为止。


好了 上代码:

/**
 * 无限极分类(递归方式)
 *@param  array $categoryies 需要分类的数组
 *@param  int   $parent_id   需要查询的顶级分类id,默认为0 表示顶级分类
 *@param  int   $level       默认0 表示是顶级分类  增加无限极分类的层级标识 用于在模板显示缩进层级关系
 
 *@return  array 返回一个已经无限极分类完成的数组
 */
function limit_category($categoryies, $parent_id = 0, $level = 0)
{
    //定义一个静态数组 用于保存每次遍历得到的结果
    static $res = [];

    //遍历数组 进行数据判断
    foreach($categoryies as $key => $val)
    {
        if($val['parent_id'] == $parent_id)
        {
            $val['level'] = $level;

            //是要找的父级分类内容
            $res[] = $val;

            //递归点 当前分类有可能有子分类
            limit_category($categoryies, $val['cat_id'], $level + 1); //注意这里是cat_id不是parent_id !!
        }
    }

    return $res;
}

//调用:
limit_category($data);

最后返回的数组结构如下:

array (size=6)
  0 => 
    array (size=5)
      'cat_id' => int 80
      'cname' => string '软件开发' (length=12)
      'is_show' => int 1
      'parent_id' => int 0
      'level' => int 0
  1 => 
    array (size=5)
      'cat_id' => int 7
      'cname' => string 'php' (length=3)
      'is_show' => int 1
      'parent_id' => int 80
      'level' => int 1
  2 => 
    array (size=5)
      'cat_id' => int 6
      'cname' => string 'mysql' (length=5)
      'is_show' => int 1
      'parent_id' => int 80
      'level' => int 1
  3 => 
    array (size=5)
      'cat_id' => int 74
      'cname' => string 'Linux' (length=5)
      'is_show' => int 1
      'parent_id' => int 80
      'level' => int 1
  4 => 
    array (size=5)
      'cat_id' => int 87
      'cname' => string '生活随笔' (length=12)
      'is_show' => int 1
      'parent_id' => int 0
      'level' => int 0
  5 => 
    array (size=5)
      'cat_id' => int 94
      'cname' => string '邻居' (length=6)
      'is_show' => int 1
      'parent_id' => int 0
      'level' => int 0


数据量不大的话 两种方式执行起来速度相差无几,数据量大的话,引用方式秒杀递归方式,无论是从性能速度还是内存占用空间大小


推荐一个参考网址吧:

https://blog.csdn.net/falcom_fans/article/details/75579663





冒泡排序,选择排序,插入排序,快速排序,堆排序,归并排序,希尔排序,桶排序,基数排序新年帮您排忧解难。

有向图,无向图,有环图,无环图,完全图,稠密图,稀疏图,拓扑图祝您新年宏图大展。

最长路,最短路,单源路径,所有节点对路径祝您新年路路通畅。

二叉树,红黑树,van Emde Boas树,最小生成树祝您新年好运枝繁叶茂。

最大流,网络流,标准输入流,标准输出流,文件输入流,文件输出流祝您新年顺顺流流。

线性动规,区间动规,坐标动规,背包动规,树型动归为您的新年规划精彩。

散列表,哈希表,邻接表,双向链表,循环链表帮您在新年表达喜悦。

O(1), O(log n), O(n), O(nlog n), O(n^2), O(n^3), O(2^n), O(n!)祝大家新年渐进步步高。


声明:禁止任何非法用途使用,凡因违规使用而引起的任何法律纠纷,本站概不负责。

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

精彩评论

全部回复12人评论7,777人参与