从零开始学算法:5.万能数组

作者: | 更新日期:

数组是万能的,那是不能的;因为他万能的时候名字不叫数组了。

这篇文章涉及的源代码可以全部免费获得,在公众号中回复“万能数组”可以获得。

一、背景

大家好,我是tiankonguse。
由于某些原因,经常有人想学习算法但之前又没有相关经验,不知道从何做起。 我思考了许久,计划写一个系列来分享如何入门学习算法。

之前已经分享了《认识算法》、《了解套路长啥样》、《排序算法》、《二分查找》,这是第五篇《万能数组》。

考虑到很多人不是科班出身的,或者当初没好好学习,很多基础知识都忘记了。
还有上次说的交接给我的一个项目,其中的关键逻辑就是使用数组实现的,没想到O(n)复杂度的操作到处都是,真实惨不忍睹。
所以这篇文章来给大家普及下数组上的知识点,大家使用的时候对于复杂度高的操作应该尽量避免,不然后面就是一个瓶颈点。
以后这些问题即使解决了,性能翻了几倍,也没什么好炫耀的,因为这些本来就是基础,最初实现的时候就应该避免。

一、基础知识

C语言中的数组,使用的时候被当做一个定长的连续的空间。
我们可以通过下标在O(1)的时间上直接读取或者修改对应位置的值。
所以数组在很多时候是一种最常见高效的数据结构(姑且算数据结构)。

但是使用数组的时候也会遇到一些问题。
比如数组的空间不管我们有没有使用,长度都是那么多,不知道用了多少。
如果数组满了,想继续加元素,就会数组越界。
如果数组前面想删除,涉及到后面的元素copy到前面,时间复杂度是O(n)。

所以我们希望对数组进行一个封装,名字就叫做万能数组,可以实现任何我们想操作的事情。
为了代码简单点,这里不使用模板,直接以整数为例。

二、自动扩展数组

使用数据时经常会发现空间不够了,所以能够自动扩大空间就好了。
自动扩展的基本思想是追加数据的时候,先判断空间是不是用完了,如果用完了,申请一个更大的内存,旧数据copy过去,旧内存释放,新数据赋值即可。

三、栈

栈是一种很常用的数据结构,特点就是后进先出。
可以想象你们一排车开进死胡同了,最先进去的在最里面,最后进去的在最外面。
那大家想出来,肯定是最外面的先出来,也就是最后进去的先出来(后进先出)。

栈的使用场景有:序列反选、逆序输出、括号匹配、DFS等。

四、队列

队列是一种先进先出的数据结构。
最常见的例子就是排队吃饭,先打饭的肯定是队首的那个人。

由于队列涉及到删除数组前面的元素,这里可以使用一个标记来标记前面删除了多少个元素。
对于内存扩展时,数据从头对齐问题,这里暂时不处理。

五、双向队列

栈大家都听过,队列大家也都听过,那双向队列听过的人就不多了吧。
双向队列,顾名思义,就是两边都可以进也都可以出的队列,也就是栈和队列的合体了。

不过这里会有一个问题,队首也可以插入数据了,有可能前面的空间用完不够用了。
所以,我们到了不得不面对队首空间的问题了,下一小节分享一个比较实用的方法。

六、循环队列

在队列和双向队列小节里,我们发现了两个问题。
问题1:队列的队尾没空间了,队首可能还有空间,我们没办法用起来,只能直接扩大内存。
问题2:双向队列的队首没空间了,队尾可能有空间,我们也没用起来,不但需要扩大内存,还要对数据进行偏移,好给队首预留一些位置来。

我们要做的是,在还有空间时,尽量利用已有的空间。
比如队尾的空间用完了,队首还有,那入队就放在队首那一头。
直到确实没有空间了,我们才去扩展空间。

双向循环队列与循环队列的思想是类似的,这里以循环队列为例来看看实现吧。

七、其他操作

上面对于数组只进行了简单的操作,即首尾增删数据。
实际情况是可能在中间插入数据,也可能删除中间的数据,还需要使用下标定位。
这个时候如果粗暴的实现的话,会发现复杂度是O(n)的。

比如删除数组的第一个元素,那么数组后面所有的元素都需要前移一下(通过循环队列可以不移动)。
而在中间插入或删除一个元素,操作位置后面的空间依旧需要移动,这个时候循环队列就没辙了。
面对这个问题该怎么办呢?
后续的文章慢慢介绍一些方法来。

这篇文章涉及的源代码可以全部免费获得,在公众号中回复“万能数组”可以获得。


本文首发于公众号:天空的代码世界,微信号:tiankonguse-code。

推荐阅读:

今天长按识别上面的二维码,在公众号中回复“ACM模板”,你将免费获得我大学耗时四年整理的《ACM算法模板》。
回复“算法的世界”,或点击阅读原文加入“tiankonguse的朋友们”,已有三百多个小伙伴加入。

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越