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

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-01-17 21:20:06

    Nuxt重要点介绍和记录

    nuxt.js简单的说是Vue.js的通用框架,最常用的就是用来作SSR(服务器端渲染).Vue.js是开发SPA(单页应用)的,Nuxt.js这个框架,用Vue开发多页应用,并在服务端完成渲染,可以直接用命令把我们制作的vue项目生成为静态html。

  • 2020-01-17 21:21:42

    nuxtjs打包优化

    然后你再使用 npm run build 打包的时候,会弹出一个界面 当然了,它第一次出来的时候我立马关了,这啥玩意???别着急你慢慢的品,慢慢的看。 原来 这是打包后的JS,面积的大小就是体积的大小。这样我们一目了然的看到了到底那里大了

  • 2020-01-17 23:21:54

    webpack打包优化之外部扩展externals的实际应用

    使用vue-cli创建项目,使用webpack打包。其中,有一个webpack优化webpack.optimize.CommonsChunkPlugin,它会将node_modules中的必需模块提取到vendor文件中,项目开发中,增加第三方模块,比如element-ui、vue-echarts等,vendor的包都会增大。这个时候,就需要考虑减轻vendor包的大小,增加构建速度。我们可以使用webpack的外部扩展(externals)功能。

  • 2020-01-18 01:26:59

    anyProxy使用注意事项

    anyproxy-ca 运行这个命令,如果是mac电脑他会提醒你去通过证书。

  • 2020-01-18 08:54:06

    利用localStorage来处理你的Javascript脚本错误

    localStorage作为HTML5中的新特性,它的出现可以说对于前端性能体验来讲可以获得相当大的改善。存储一些用户经常用到而又不是涉及隐私和安全的东西,的确是一个非常好的选择。下面分享一下用localStorage来处理客户端代码错误的例子来了解一下它的用途吧。

  • 2020-01-20 08:29:14

    js如何生成唯一标识符UUID

    在JavaScript中生成uuid的代码如下,这个函数会直接给你返回uuid,所以直接调用,然后用变量接收即可!