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

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


  • 2017-03-16 13:37:58

    mysql中如何使用INSERT一次性插入多条记录

    看到这个标题也许大家会问,这有什么好说的,调用多次INSERT语句不就可以插入多条记录了吗!但使用这种方法要增加服务器的负荷,因为,执行每一次 SQL服务器都要同样对SQL进行分析、优化等操作。

  • 2017-03-18 20:17:09

    Linux上vi(vim)编辑器使用教程

    vi(vim)是上Linux非常常用的编辑器,很多Linux发行版都默认安装了vi(vim)。vi(vim)命令繁多但是如果使用灵活之后将会大大提高效率。vi是“visual interface”的缩写,vim是vi IMproved(增强版的vi)。在一般的系统管理维护中vi就够用,如果想使用代码加亮的话可以使用vim。下面vps侦探整理一下vi的使用教程:包含vi的基本介绍、使用模式、文件的打开关闭保存、插入文本或新建行、移动光标、删除、恢复字符或行、搜索等等,算是一篇比较适合新手学习vi的教程。

  • 2017-03-20 17:31:55

    Nodejs express 获取url参数,post参数的三种方式

    127.0.0.1:3000/index,这种情况下,我们为了得到index,我们可以通过使用req.params得到,通过这种方法我们就可以很好的处理Node中的路由处理问题,同时利用这点可以非常方便的实现MVC模

  • 2017-03-20 17:33:55

    forever守护nodejs进程

    这样可以正常启动应用,但是如果断开客户端连接,应用也就随之停止了。也就是说这样的启动方式没有给应用一个守护线程。

  • 2017-03-22 14:00:51

    Andriod Studio结合Visual Studio Emulator for Android调试Android App

    说到开发就绕不开调试程序,调试Android App我们有2种选择,真机调试和模拟器调试:真机调试相对简单,就不做介绍了,还有一方面原因是由于安卓手机一旦插到电脑上,开始ADB调试后,各种的流氓软件净是往手机上装垃圾应用,妈蛋的;随后就试了几次Android Studio的模拟器之后,无限感慨,真尼玛的卡,卡,卡,,,是可忍孰不可忍.....

  • 2017-03-22 16:26:36

    最全面的Android Webview详解

    现在很多App里都内置了Web网页(Hyprid App),比如说很多电商平台,淘宝、京东、聚划算等等,如下图

  • 2017-03-23 22:29:52

    Android开发中Handler的经典总结

    当应用程序启动时,Android首先会开启一个主线程(也就是UI线程),主线程为管理界面中的UI控件,进行事件分发。