动图解释递归,按值传递和按引用传递的区别,线性查找和二分查找,二叉查找树

2019-10-15 09:52:00

参考地址 硬核动图让你轻松弄懂递归,查找等概念


更多动图学程序参考 penjee  一个很有意思的网站,动图解释程序。

对于大部分人,数据结构一直是一个短板,当然我也是,不是学不会,而是容易忘,就拿最简单的排序来说吧,当时学习的时候明明已经弄得很清楚了,过了一段时间不用又忘记了,还要重新再看一遍,不知道有多少小伙伴和我有一样的烦恼。今天让我们用用动图的方式学习一下数据结构中的递归和二分查找吧,这种讲解方式非常生动,而且非常容易记住和理解。


 


一、递归


 


1.概念


递归简单的来说就是程序自己调用自己,就像下面这幅图一样,一直循环往复。


 




 


2.出口


如果程序一直这样循环往复的调用自己,一直都不结束,就是一个死循环,


这没什么意义。所以我们需要为递归定义一个结束条件,即递归的出口,当条件不满足时,递归一直前进,不断地调用自己;当边界条件满足时,递归返回。




递归的应用通常是把一个大型的比较复杂的问题,通过层层转化为一个与原问题相似的小的问题来求解,就像上边统计排队人数的问题。上边的这个小姐姐问第一个排队的人,有多少人排队,第一个人回答:我(1个人)+后边的人,小姐姐没有得到具体的答案,但是她知道只要弄清楚第一个人后边有多少人排队+第一个人就是排队的人数,所以她继续问后边的人,结果得到了相同的回答,于是她得到的答案变成了:1+1+后边的人。于是她不得不一直这样问下去,等到问到最后一个人的时候,最后一个人回答,就我一个人,到此刻小姐姐终于得到了想要的答案即:1+1+········+1。上边就是一个经典的递归的例子,这里的递归结束条件为是否是最后一个人,,只要不是最后一个人,就一直问下去。


 


3.递归经典问题:递归求斐波那契数列


    斐波那契数列(Fibonacci sequence),又称黄金分割数列、指的是这样的数列:0、1、1、2、3、5、8、13、21、34、……,从第三项开始,这个数列每一项都等于前两项之和。在数学上,斐波那契数列被以递推的方法定义:F(0)=0,F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)。下面的动图描述了如何用递归的方式来求斐波那契数列的第8项,即F(7)。根据定义F(7)=F(6)+F(5),求F(7)只需要知道F(6)和F(5)即可,而F(6)=F(5)+F(4),F(5)=F(4)+F(3).......依次类推,因为F(0)=0,F(1)=1是已知的,所以到第一项和第二项的时候就可以结束了,即递归的结束条件是n=0或n=1.




 


4.递归经典问题:递归求阶乘


n的阶乘,就是从1开始乘到n,即1*2*3*...*(n-1)*n,即n!=1*2*3*...*(n-1)*n=n*(n-1)!,而(n-1)!=1*2*3*...*(n-1)=(n-1)*(n-2)!,......依次类推当n=1时,1!=1*0!=1,即递归的结束条件为1,由此,可以得出递归求阶乘函数factorial()的算法如下:




 


 


二、按值传递和按引用传递的区别


按引用传递指的是在方法调用时,传递的参数是引用的地址,也就是变量所对应的内存空间的地址,传递的是值的引用,传递前和传递后都指向同一个引用(同一个内存空间)。


按值传递,指的是在方法调用时,传递的是值的拷贝,也就是说传递后就互不相关了。


就像下图中的咖啡杯,直接把它递给他人用,他人直接往杯子里倒咖啡,原来的咖啡杯里也会出现咖啡,因为他们本质上就是一个杯子。这就是引用传递。


参照一个咖啡杯,仿制了一个一模一样的咖啡杯给他人,他人在仿制的杯子里注入咖啡,不会影响原来的杯子。这就是按值传递。




 


三、线性查找和二分查找


线性查找,即在给定的一组元素值中,从一端开始逐一检查每个元素进行搜索查找,直到找到所需要的元素。


二分查找又称折半查找,进行折半查找的一组元素必须是有序的。假设表中元素是按升序排列,查找的时候,首先将表中间位置记录的关键字与要查找的关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于要查找的关键字,则接着重复使用上述方法查找前一子表,否则重复使用上述方法查找后一子表,一直重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。我们可以定义一个low和high还有mid,通过目标值比较中间值,对比大小,来移动begin或end到之前mid的位置,从而得到目标值的位置


使用线性查找和二分查找求 23 的位置动图演示:




使用线性查找和二分查找求 1 的位置动图演示:


 


 




使用线性查找和二分查找求 37 的位置动图演示:




 


二叉查找树


 


定义:对于一棵二叉树


  1.若它的左子树不为空,则左子树上所有结点的值均小于等于根结点的值;


  2.若它的右子树不为空,则右子树上所有结点的值均大于等于根结点的值;


  3.它的左右子树也分别为二分查找树。


以下十个数21,28,14,32,25,18,11,30,19,15,构造二叉查找树的过程如下:




下图演示了查找27时,对于二叉查找树和普通数组两种数据结构,分别用的步数:


 



————————————————

版权声明:本文为CSDN博主「Albert Yang」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。

原文链接:https://blog.csdn.net/qq_23853743/article/details/102539388


  • 2020-04-08 22:46:28

    Element的操作方法

    Element 是一个通用性非常强的基类,所有 Document 对象下的对象都继承自它。这个接口描述了所有相同种类的元素所普遍具有的方法和属性。一些接口继承自 Element 并且增加了一些额外功能的接口描述了具体的行为。例如, HTMLElement 接口是所有 HTML 元素的基本接口,而 SVGElement 接口是所有 SVG 元素的基础。大多数功能是在这个类的更深层级(hierarchy)的接口中被进一步制定的。

  • 2020-04-12 17:42:43

    Node.js设置CORS跨域请求中多域名白名单的方法

    在Node.js中,res的响应头Header中的 Access-Control-Allow-Origin 属性不能匹配除 (*) 以外的正则表达式的,域名之间不能也用逗号分隔。也就是说, Access-Control-Allow-Origin 的属性值只允许设置为单个确定域名字符串或者 (*)。

  • 2020-04-14 09:40:59

    CSS3实现文字描边的2种方法

    首先想到去看CSS3有没有什么属性可以实现,后来被我找到了text-stroke     该属性是一个复合属性,可以设置文字宽度和文字描边颜色      该属性使用很简单:text-stroke:1px #f00;(1px是文字宽度,#ff是文字描边颜色)

  • 2020-04-14 09:42:47

    用 TypeScript 编写 npm 模块

    自从开始使用 Node.js 已经一年多,写的代码越多,越是觉得自己提高的越慢。想来应该有没有将单一功能的代码封装在一个独立模块,而导致代码稍微多一点就维护困难的原因。

  • 2020-04-14 09:46:25

    TypeScript 入门教程

    TypeScript 是 JavaScript 的超集,扩展了 JavaScript 的语法,因此现有的 JavaScript 代码可与 TypeScript 一起工作无需任何修改,TypeScript 通过类型注解提供编译时的静态类型检查。 TypeScript 可处理已有的 JavaScript 代码,并只对其中的 TypeScript 代码进行编译。

  • 2020-04-14 09:51:03

    package.json 字段说明

    package.json 有很多字段,也有很多官方字段,我们需要知道他们的具体是做什么的才能很好的运用