PHP数据结构(二十五)——并归排序 (原创内容,转载请注明来源,谢谢) 一、概述 并归排序是将两个或两个以上的有序表组合成一个新的有序表。采用并归的思想进行排序的方式如下: 假设初始序列含有n个记录,则看成是n个有序的子序列,每个子序列长度是1,然后两两合并,得到n/2个长度为2或者1(元素总数是奇数时,最后一个元素是单个的)的子序列。然后再进行归并,直至归并成一个数组。此方法也成为2-路并归排序。 二、算法 并归排序有两个核心——拆分、合并。 1)对于拆分,需要把数组拆成仅含一
PHP数据结构(二十二)——快速排序 (原创内容,转载请注明来源,谢谢) 一、概述 前面的插入排序,都是以移动的方式进行排序。快速排序,则是以交换的方式进行排序。 二、冒泡排序 提到交换的方式进行排序,首先可以提到冒泡排序。 1、算法 冒泡排序是逐个进行比较再进行交换的排序方式,假设是以从小到大的顺序排列。 1)先用第一个数和第二个数比较,如果第一个数比较大,则和第二个数进行互换,否则两个数保持不变。 2)再用第二个数与第三个数比较,直至第n-1个数与第n个数进行比较。这称为一轮的冒
树(tree)是包含 n(n≥0) [2] 个节点,当 n=0 时,称为空树,非空树中
在上一篇文章中,我们学习完了图的相关的存储结构,也就是 邻接矩阵 和 邻接表 。它们分别就代表了最典型的 顺序存储 和 链式存储 两种类型。既然数据结构有了,那么我们接下来当然就是学习对这些数据结构的操作啦,也就是算法的部分。不管是图还是树,遍历都是很重要的部分,今天我们就先来学习最基础的两种图的遍历方式。
节点的度:一个节点含有的子树的个数。 叶子节点/终端节点:度为0的节点。 分支节点/非终端节点:度不为0的节点。 父节点/双亲节点:含有至少一个子节点的节点。 子节点:一个节点含有的子树的根节点,称为该节点的子节点。 兄弟节点:具有相同父节点的节点,互称为兄弟节点。 树的度:一棵树中最大节点的度。 节点的层次:从跟开始定义,根为第1层,根的子节点为第二层,…,以此类推。 数的高度或深度:树中节点的最大层次。 堂兄弟节点:父节点在同一层的节点。 节点的祖先:从根到该节点所经分支上的所有节点。 子孙:以某一节点为根节点的子树中所有节点都是该节点的子孙。 森林:一颗及一颗以上的树组成的集合。
当时一看就懵逼了!基本的思路还是有的,不过是使用递归算法,但对PHP操作目录文件的方法却不是很了解,所以今天好好补习一下!
组合模式又称:对象树、Object Tree、Composite,组合 是一种结构型设计模式,使用它将对组合成树状结构,并且能像使用独立对象一样使用它们。
使用这种数据结构去存储树事实上存在一点的问题,只有在知道树的度的情况下使用这种结构才比较合理,另外也不是每个节点的度都是一样的,容易造成空间的浪费。
这次我们来介绍一个SPL库中的目录迭代器,它的作用其实非常简单,从名字就可以看出来,就是获取指定目录下的所有内容。之前我们要遍历目录获取目录及目录下的所有文件一般是需要进行递归遍历的,自己写这个代码说实话还是挺麻烦的,所以PHP为我们准备好了这一套内置API,当输入指定的目录后,直接返回该目录下所有子目录及文件内容。当然,并不是树型的,顺序并不一定,想要组织成树型还需要我们自己再进行处理。
这两种方案呢其实都可以,但在这里建议大家选择从1开始。 为什么呢? 因为如果我们认为根节点的层次是0,那要表示空树就是-1了。 而如果从1开始,那空树的层次就是0,空树是0 是不是好像更符合我们正常的逻辑啊。 当然只是建议,两种都可以。
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构) 1.子树的意思是包含了一个节点,就得包含这个节点下的所有节点,两棵树同时到底 2.子结构可以是A树的任意一部分 思路: 1.第一个递归:A和B两棵树,先在A中找到与B的根结点相同的点,如果A的根不是,那就递归A的左右子树来找 2.第二个递归:从两棵树的根结点开始进行比较,遍历的过程中,如果B树为空,则返回true;如果B不为空,A为空,返回false A树的结点值与B树的不同,返回fa
0x00 前言 在今年六月份的强网杯中,有一道叫做pop_master的题目。简单描述就是从一万个类中,筛选出可利用的pop链路。在赛前,笔者并未了解过抽象语法树的概念。当时是通过PHP的魔术方法完成了这一个有趣的题目。 作者提供了环境生成器,才有了这篇文章(题目生成器):https://gitee.com/b1ind/pop_master 官方的WP正解为AST抽象语法树以及它的污点分析,题目质量还是相当可以的,至此,笔者想到了多种解题思路,并给大家分享。 0x01 思考方向 笔者在刚拿到这16w行代码也
以笔试为目的的修炼都是耍流氓。但也许,我们就想当个好流氓。秋招已到,希望大家都能收货满意的offer。
geohash是实现空间索引的一种算法,其他实现空间索引的算法有:R树和其变种GIST树、四叉树、网格索引等
深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历。具体说明如下:
PHP数据结构(八)——赫夫曼树实现字符串编解码(实践2) (原创内容,转载请注明来源,谢谢) 公众号规定不能超过3000字,只能分两篇,见谅。 由于需要分两篇来讲,本篇接上篇的内容,假定已经获取到编
无限级分类是很常见的功能,算法的好坏对于获取分类树的性能起到决定性的作用。尤其当分类数据和层级多时,一个糟糕的算法将使服务器不堪重负
PHP数据结构(八)——赫夫曼树实现字符串编解码(实践1) (原创内容,转载请注明来源,谢谢) 公众号规定不能超过3000字,只能分两篇,见谅。 由于需要分两篇来讲,本篇主要讲解编码的
在开发过程中经常会遇到分级场景,如菜单分级、评论、商品类型分级等;在同一张mysql数据表中可能设计单表结构,如同如下数据:
二叉搜索树的后序遍历序列: 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 思路: 1.后序遍历是 左右中 , 最后一个元素是根结点 2.二叉搜索树,左子树<=根结点<=右子树 3.遍历数组,找到第一个大于root的位置,该位置左面为左子树,右面为右子树 4.遍历右子树,如果有小于root的返回false 5.递归左右左右子树 VerifySquenceOfBST(seq) judge(seq,0,se
当“人工智能”、“AlphaGo”、“无人驾驶”、“智能投顾”等词语不断在人们视野中出现的时候,意味着我们正步入一个算法的时代。计算机通过提供给人类每天要面临的各种选择的最优解,从而让我们能更加高效的生活在这个信息爆炸的时代。 而对于大多数非算法专业领域的程序员来说,也逐渐意识到了算法的重要性。学习算法,从而更好的应用算法,通过算法去优化代码,提高程序效率。 什么是算法 必须知道的十大程序员开发用到的基本算法 快速排序算法 最排序算法 归并排序 二分查找算法 BFPRT(线性查找算法) DFS(深度优化算
本文实例讲述了PHP树形结构tree类用法。分享给大家供大家参考,具体如下: <?php include 'tree.class.php'; //模拟数据库 $data=array( array(
树的概念:树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的
无限分类在日常开发中很常见至少对于PHP程序员来说,如网站常见的商品分类、面包屑、省市联动、新闻分类等等,一个栏目又包含很多个子栏目子栏目又包含很多子栏目...。 这里介绍无限分类的子孙树与家谱树实现。
1、数据交互经常用到XML或者Json,其中Json数据居多(优点不多说) 2、ZendFrameWork中如何将XML转换成Json以及数组和Json转换 直接上例子: $arr = array(‘status’ => 1, ‘info’ => ‘json测试’, ‘data’ => array(‘name’ => ‘用户名’, ‘password’ => ‘blog.phpfs.com’)); //数组转Json $json = Zend_Json::encode($arr);//$json =
某一天过去SY那儿,突发奇想说要写一个统计代码行数的小程序。说干就干,约定了一个时间——周六,来把这个想法给实现了。当然这个项目人家做过的也未必,google一下,果然有非常优秀的win下面的代码统计工具sourceCounter。当然我们是用python来写,确定了数据结构和算法之后,我们就开始实现了。
XHProf 是一个分层PHP性能分析工具。它报告函数级别的请求次数和各种指标,包括阻塞时间,CPU时间和内存使用情况。一个函数的开销,可细分成调用者和被调用者的开销,XHProf数据收集阶段,它记录调用次数的追踪和包容性的指标弧在动态callgraph的一个程序。它独有的数据计算的报告/后处理阶段。
前言 红黑树是数据结构中比较复杂的一种,最近与它交集颇多,于是花了一周的空闲时间跟它死磕,终于弄明白并实现了红黑树。写文总结一下,希望能给试图理解红黑树的同学一些灵感,也让我能记得更深刻。 在研究红黑树时吃了不少苦头,原因有二: 红黑树的插入和删除非常复杂,很多人并没有理解或完全实现,或实现了的没有任何注释,让人很难参考; 网络上红黑树的理解方式较为单一,一般是 双黑、caseN 法,而插入和删除的情况很多,每种都有对应的处理方式,如果死记硬背的话,再过一段时间再回忆各种情况可能就一头雾水了。 网络上讲红黑
递归函数是我们常用到的一类函数,最基本的特点是在函数或子过程的内部,直接或者间接地调用自己的算法,但必须在调用自身前有条件判断,否则无限调用下去,也就是所谓的死循环
Hiphop是Facebook开发一款PHP二进制化的一个工具,最开始是由php转为C++,但是后来发现编译为c++的话,许多的时间会花费在编译代码上面,调试不方便,对于代码来说也不是即见即所得。 所以hiphop经历了这么几个阶段: HPHPC=>HPHPI=>HHVM HPHPC是静态编译,也就是把php转为c++ HPHPI是一个过渡产品,类似php zend虚拟机,性能还不如zend虚拟机,但是可以运行查看效果; HHVM是在HPHPI基础上,应用了JIT技术,性能已经接近了HPHPC,目前face
这是前端面试中必然会问到的问题 前端开发多年来一直在不断改进。从简单的静态页面到现在复杂的单页面应用程序,我们的工具变得越来越强大。现在,三大前端框架统治着前端开发,那么你知道这三个框架的区别吗?为什么一直保持着三足鼎立的局面,而不是某种框架来统一其他人?让我们在本文中讨论这些问题。 前端开发的演变 PHP && JSP 早些年,网页的动态内容是在服务器端渲染的,主要使用PHP、JSP等技术。 此时,服务器通过模板引擎填充数据,然后生成HTML,并将HTML返回给浏览器进行渲染。 <!DOCTYPE
通过栈和队列的学习,我们似乎会感觉到其实数据结构还是非常简单的嘛。当然,这只是一个开始,我们从顺序表、链表开始,到现在的栈和队列,其实都是为了将来在铺路。在树和图的遍历算法中,都可以见到栈和队列的身影。在这里,我们先简单的看看栈和队列的一些实际应用。
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
https://www.python-course.eu/recursive_functions.php
函数直接或间接调用自身的过程称为递归,相应的函数称为递归函数。使用递归算法,可以很容易地解决某些问题。此类问题的示例包括汉诺塔 (TOH)、中序/先序/后序树遍历、图的 DFS 递归函数通过调用自身的副本并解决原始问题的较小子问题来解决特定问题。需要时可以生成更多的递归调用。重要的是要知道我们应该提供某种情况来终止这个递归过程。
二叉树的深度: 输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 思路: 1.非递归层序遍历 2.使用辅助队列,根结点先入队列 3. 循环判断队列是否为空,如果不为空就继续循环队列里面的每个结点 4. 循环队列时,当前当前结点出队列,把该结点的左右孩子入队列 TreeDepth(tree) if !tree return 0 array_push(queue,tree); depth=0 while(
树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点度不为0的结点称为非终端结点或分支结点。除根结点之外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。如图所示,这棵树结点的度的最大值是结点D的度为3,所以树的度为3
导读:说到无限极分类,这个在程序中是常见的一个功能点了。实现的方式也有很多种,今天着重分享一下涉及到数据库的无线分类,可以使用递归处理,也可以使用循环查询数据库处理。但是我们考虑到数据库的性能问题,都不建议采用循环查库。都是直接设计好数据表,直接查库,通过代码层实现。 1.我们实现准备好数据表,代码结构如下。 CREATE TABLE `bg_cate` ( `cate_Id` int(30) unsigned NOT NULL AUTO_INCREMENT, `cate_ParentId` int(3
有趣的算法(十一)——分治法:快速求最值 (原创内容,转载请注明来源,谢谢) 一、需求 一个数组,里面有若干的数字,现需要得到这一组数字的最大值和最小值。 二、简单分析 最基本的做法,是两两比对,可以区分出临时的最大值和最小值,再拿临时的最大值和最小值往后比较,有新的最值则更新。总的需要的比较次数是2n-2。 三、优化 使用分治法快速求最值。即把数组分到最小的1-2个数,两两比较后,仅将最大值和最小值回传,再两两比较最值,回传新的最值,最终得出最大值和最小值。 分析需要比较的次数。当数组只有1个数时,
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 思路: 1.利用递归形
本文结构: CART算法有两步 回归树的生成 分类树的生成 剪枝 ---- CART - Classification and Regression Trees 分类与回归树,是二叉树,可以用于分类,也可以用于回归问题,最先由 Breiman 等提出。 分类树的输出是样本的类别, 回归树的输出是一个实数。 ---- CART算法有两步: 决策树生成和剪枝。 决策树生成:递归地构建二叉决策树的过程,基于训练数据集生成决策树,生成的决策树要尽量大; 自上而下从根开始建立节点,在每个节点处要选择一个最好的属性来分
字典树 Trie 这个词来自于 retrieval,于 1912 年,Axel Thue 首次抽象地描述了一组字符串数据结构的存放方式为 Trie 的想法。这个想法于 1960 年由 Edward Fredkin 独立描述,并创造了 Trie 一词。你看看,多少程序员为了一个词、方法名、属性名,想破脑袋!
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。 有一个特殊的结点,称为根结点,根节点没有前驱结点。除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继。因此,树是递归定义的。
来源 | https://www.61mon.com/index.php/archives/208/
laravel-nestedset是一个关系型数据库遍历树的larvel4-5的插件包
作者 | Wray 来自 | http://www.codebelief.com/ Linux系统中的 find 命令在查找文件时非常有用而且方便。它可以根据不同的条件来查找文件,例如权限、拥有者、修改日期/时间、文件大小等等。在这篇文章中,我们将学习如何使用 find命令以及它所提供的选项来查找文件。 在绝大多数Linux发行版中,你都可以直接使用 find 命令而无需进行任何安装操作。如果你想在linux系统的命令行中变得特别高效,那么 find 是你必须掌握的命令之一。 find 命令的基本语法如
第一部分--拖拽介绍 在https://code.csdn.net/2013ossurvey中最后一个开源项目就是zTree,一方面是因为自己看到有项目中使用了zTree,而已大家表示还不错。另外一方面,自己需要实现一个zTree不支持的复杂逻辑的拖拽功能。总体来说,我要实现的是一个可以拖拽的树形列表。当然最新版zTree也支持多课树之间的数据交互。当然一般的企业开发或者web开发中,使用到2个或3个数就足够了。太多了树形结构对于用户来说,也非常复杂。个人推荐不是非常复杂的需求都可以考虑使用zTree,因为
领取专属 10元无门槛券
手把手带您无忧上云