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

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


  • 2018-12-13 17:17:02

    轻松实现动态获取Android手机CPU架构类型

    .so文件是unix的动态连接库,是二进制文件,作用相当于windows下的.dll文件。 他使用了C/C++代码编写的可以操作硬件比java更高级的 底层代码,执行速度和效率比其他语言要高。 在Android中调用动态库文件(*.so)都是通过jni的方式。

  • 2018-12-13 22:48:48

    Android MultiDex实践:如何绕过那些坑?

    MultiDex, 顾名思义,是指多dex实现,大多数App,解压其apk后,一般只有一个classes.dex文件,采用MultiDex的App解压后可以看到有classes.dex,classes2.dex,… classes(N).dex,这样每个dex都可以最大承载65k个方法,很大限度地缓解了单dex方法数限制。

  • 2018-12-14 13:32:18

    解决chrome调试手机模式没有鼠标问题

    F12后,切换到手机模式,方向没有鼠标,这对于调试前端页面来说无疑是一大难题,看不见只能盲点, 以为是浏览器问题,清理缓存,升级浏览器,清除插件等都不好使。 后来查到资料说是显卡问题。果然还真是显卡问题。

  • 2018-12-14 17:12:51

    Android APP适配全面屏手机的技术要点

    全面屏是手机业界对于超高屏占比手机设计的一个宽泛的定义。从字面上解释就是,手机的正面全部都是屏幕,四个边框位置都是采用无边框设计,追求接近100%的屏占比。但受限于目前的技术,还不能做到手机正面屏占比100%的手机。现在业内所说的全面屏手机是指真实屏占比可以达到80%以上,拥有超窄边框设计的手机。

  • 2018-12-14 17:15:50

    Android适配刘海屏沉浸式状态栏的一些坑

    18年简直是刘海元年,所有手机都在跟风刘海屏,甚至每个厂商还有自己的一套适配规范。我的初始需求很简单,就是做一个全屏显示的页面,一般情况下只需要开启Android规范的全屏模式就好:

  • 2018-12-16 12:12:12

    android:windowSoftInputMode属性具体解释

    android:windowSoftInputMode属性一共同拥有9个取值。各自是: stateUnspecified,stateUnchanged。stateHidden,stateAlwaysHidden。stateVisible,stateAlwaysVisible,adjustUnspecified,adjustResize。adjustPan。

  • 2018-12-16 18:14:23

    Android在代码中设置状态栏半透明/全透明

    顶部是有文字,小图标等,如果直接用透明半透明 状态栏上的东西会与内容重叠(你觉得无所谓也可以直接用上面2部分代码),这样我们就想做成类似支付宝这样的效果: