找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法+数据结构(第05篇)走下神坛吧!算法

admin 2019-4-15 19:43 232人围观 C++相关

点击上方“猿程之家”,选择“置顶公众号”
关键时刻,第一时间送达!

阅读本文需要5分钟



引言


在本系列第一篇文章《走下神坛吧!算法》中提到了:

  1. 算法的作用对象是数据结构

  2. 数据结构的来源既有硬件维度也有软件维度




把项目或者工程看作是大楼的话,那么算法就是建造大楼的具体施工流程和方法,数据结构就是砖块等原材料。

常言道:“工欲善其事必先利其器”,既然要研究算法,那么首先就要把它操作的“原材料”一一搞清楚。从本篇文章起,将逐一来讲解各“原材料”的历史来源、使用方法与应用场景。



1. 数组就是带电梯的小高层



数组的形式:<数据类型> 数组名 [数组长度]

形象地讲,数组就是带电梯的小高层。每一个楼层就是数组的一个元素。数组元素的下标,就相当于楼层号然后按电梯楼层号。



1.1 访问数组元素


你按下楼层号(输入下标),电梯就直接把你送到对应的楼层(访问对应的数组元素),就这么简单!

从这里可以看出数组的一个最大优势:随机访问相当简单、相当爽!



1.2 添加数组元素


想想竣工的大楼,如果你要加楼层,怎么加?当然是在顶楼上继续加喽!

顶楼就是数组的末尾元素,所以向数组中添加元素,就是在数组的尾巴上添加该元素。

当然楼层是要占据物理空间的,对应到计算机语言,就是要分配内存。

看到这里,也许调皮的同学会问了:那能不能不在尾巴上添加,而在中间添加呢?

你见过竣工的大楼,在中间加楼层的吗?:)

变通的办法,还是在顶楼加,然后让从欲插入的楼层开始的住户依次往上一楼层搬家,腾出当前层给你这个调皮的同学住!:)





1.3 删除数组元素



你见过竣工的大楼,在中间“炸掉”某楼层的吗?:)

结果肯定是楼塌啦!



正确的做法:



从这里可以看出数组的一个最大弱点:添加与删除元素有点烦!



2. 链表就是单入口小火车



链表分为单向链表与双向链表。两者的区别:

单向链表从当前节点只能访问它的下一个节点,而双向链表可以从当前节点同时访问它的前一个节点和后一个节点。



2.1 访问链表节点



先来看看单向链表的“小火车”:

每节车厢就相当于链表的一个节点。



如果要到3号车厢,先进入1号车厢(入口车厢),再从1号车厢的后向挂钩到达2号车厢,最后从2号车厢的后向挂钩到达3号车厢。

因为没有前向挂钩,所以从3号车厢无法到达2号车厢;同理,从2号车厢也无法到达1号车厢。

从这里可以看出链表的一个最大弱点:随机访问元素有点烦!

再来看看双向链表的“小火车”:



因为有前向挂钩,所以从3号车厢可以到达2号车厢;同理,从2号车厢也可以到达1号车厢。



2.2 添加链表节点



先来看看单向链表的“小火车”如何添加新“车厢“(链表节点):

有两种情况:

1. 将新“车厢”加到火车尾巴上



2. 将新“车厢”插入到车节中间

第一步:“系住”后节车厢



为啥要“系住”呢?因为车厢脱钩之后就失控了啊:)

第二步:分离



第三步:与前一节车厢挂钩



第四步:与后一节车厢挂钩



在这一步其实可以真正看出第一步中“系住”的目的:)

不就是为了让4号车厢的前向挂钩找到3号车厢和2号车厢吗?:)

如果不提前“系住”,那么一旦2号车厢与3号车厢分离,我们就再也没有有效办法到达3号车厢了。

那么如何实现“系住”呢?用变量保存要“系住”的“车厢”(链表节点)位置。

对于3号车厢:用一个变量保存3号车厢的位置即可。

看到这里,相信对于单向链表的节点添加操作你再也不会忘记了:)

双向链表的节点添加操作与上类似,无非就是多了一个前向挂钩的处理。



2.3 删除链表节点



假如现在要去掉3号车厢,那么怎么做呢?



第一步:“系住”前节车厢



第二步:前向分离



第三步:“系住”后节车厢



第四步: 后向分离



第五步:前后节车厢挂接



双向链表的节点删除操作与上类似,无非就是多了一个前向挂钩的处理。

从这里可以看出链表的最大优点:增删元素相对于数组容易!


END


博主还有很优秀的技术交流群,很多技术大拿,CTO,活跃度百分八十以上。问题解答百分之90以上。加博主好友后回复【加群】,然后回答技术问题,答对者才能进入,其他博主和广告商勿扰进群介绍,当然也会有一些学习资源,群里直接回复资源介绍


推荐阅读

算法+数据解构(第04篇)空间复杂度你真的懂了吗?


数据结构+算法(第03篇)KO!大O——时间复杂度

算法+数据结构(第02篇)玩扫雷就是优化算法

算法+数据结构(第01篇)走下神坛吧!算法

【面试题】Microsoft面试真题

奔跑吧! HashMap,值得你一阅!

如何设计优秀的API(一)

如何设计优秀的API(二)

如何设计优秀的API(三)



是不是很棒!分享一下吧,小伙伴们!




----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:Java研发军团,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......