现在安卓面试,对于数据结构的问题也越来越多了,要求也越来越多,所以我对于数据结构只能慢慢补起来了。(灬ꈍ ꈍ灬)
Android技能书系列:
Android基础知识
Android技能树 — 动画小结
Android技能树 — View小结
Android技能树 — Activity小结
Android技能树 — View事件体系小结
Android技能树 — Android存储路径及IO操作小结
Android技能树 — 多进程相关小结
Android技能树 — Drawable小结
数据结构基础知识
Android技能树 — 数组,链表,散列表基础小结
Android技能树 — 树基础知识小结(一)
算法基础知识
Android技能树 — 排序算法基础小结
本文主要讲 数组,链表,散列表(哈希表)。
当我们去看电影的时候,我们知道电影院门口会有一个储物柜,
上面还会有连续的数字,一个抽屉连着一个抽屉。 然后你就会把你的东西放在相应号码的小抽屉中,然后进去看电影了。
我们在将数据存储到内存时候,你请求计算机提供存储空间,计算机会给你一个存储地址,然后你把内容存进去。就类似上面的储物柜。
线性表:零个或多个数据元素的有限序列。
如果你有三袋东西,你一个抽屉只能存一袋东西,这时候你就可以使用了连续三个柜子。比如你使用了01,02,03号抽屉。
线性表的顺序存储结构:用一段地址连续的存储单元依次存储线性表的数据元素。
然后别人来使用了04号抽屉,这时候你朋友又给你一袋东西,说帮忙也去存一下,但是这时候因为04号抽屉已经被别人使用了,而你们又因为要求大家的东西都按照顺序放在一起,所以这时候你们只能重新找连续在一起的抽屉,比如08,09,10,11。万一12号被人使用了,然后你们又要再多存一袋物品呢??
这里我们看出数组的特点:
类似我们在排队买车票,突然半路有个人插队,你们所有人都需要往后退后了一位;最前面的人买好票走了一个,你们所有人都可以往前前进一位。
数组 | 时间复杂度 |
---|---|
读取 | O(1) |
插入/删除 | O(n) |
不知道大家有没有看过类似古墓丽影类似的探宝电影。
它们的步骤就是先知道到了一个地点,然后到了第一个目的地A,到了A之后根据线索才知道下一个目的地B在哪里,然后再去B,然后这样下去A-- B-- C --.....这样,一直到最终的藏宝地方。没错,我们的链表就是类似这种,比如我们知道一共有四袋物品,但是你不能直接知道最后一个物品在哪里,你只能从第一个开始,一个个找下去。
比如我们第一个存在了01号抽屉,存储内容为A,同时告诉大家,下一个物品在05号抽屉,里面内容为B,同时再下一个在08号。
由上面的图我们可以知道,结点由存放数据元素的数据域和存放后继节点地址的指针域组成。
由上面我们举例的古墓丽影的剧情可知,我们不能直接知道最后一个线索在哪里,只能一个个从头到尾查过去,所以链表的读取会很慢;但是我们如果想要插入和删除就很方便。
比如我们要插入一个新的结点:
比如我们要删除其中一个结点:
链表 | 时间复杂度 |
---|---|
读取 | O(n) |
插入/删除 | O(1) |
将单链表中终端结点的指针端改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表。
双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。
静态链表是为了让没有指针的高级语言也能够用数组实现链表功能。
这个我就直接用网上的截图来说明了:
静态链表是用类似于数组方法实现的,是顺序的存储结构,在物理地址上是连续的,而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的。然后在这个里面存的时候不仅存储数据域,同时存入了下一个数组index的位置。相当于我们上面的指针域换成了数组的index值。
由上面我们已经可以知道数组和链表各自的优势和缺点了。
操作 | 数组 | 链表 |
---|---|---|
读取 | 擅长(可以随机/顺序访问) | 不擅长(只能顺序访问) |
插入/删除 | 不擅长 | 擅长 |
有了上面的知识,我们就可以引入散列表了,我们用具体的故事需求来引入散列表:
如果你有一天开了一家水果店,你会拿一个本子来记各种水果的价格,因为大家知道数组对于读取来说很方便,所以我们用一个数组来记录各种水果的价格,并且是按照开头字母来进行顺序写入的。
这时候,如果有人问Apple,你就查询一下价格,但是如果水果很多,甚至很多都是A开头的水果,比如有20个A开头的水果,这时候你只能知道A开头的水果是前面20个,但是具体是哪个,你又要一个个的查过来,如果我们马上就知道Apple对应的数组index值就好了,这样就马上知道在数组的哪个位置,然后马上就可以读取出来了。
比如下图:
这样我们就在index为2的地方存储了苹果的价格,然后在index为8的地方存储了香蕉的价格,依次类推,所有水果都记录进去,这样顾客问你苹果价格时候,你就马上知道在index为2的地方去读取。
而把Apple变为2是通过散列函数来实现的。
我们要实现上面的需求,这个散列函数需要一些基本要求:
根据上面的情况我们知道了,我们输入不同的值的时候,通过散列函数换算后,最好的结果是每个值都是不同,这样的话他们的index 也不同。
但是如果我们的数组只有长度为6,但是我们有7种水果,那么一定会有二个水果得到的index是相同的。这时候我们称这种情况为冲突。
处理冲突的方式有很多,最简单的办法就是:如果二个键映射到了同一个位置,就在这个位置存储一个链表。
这样,我们在查询其他水果时候还是很快,只是在查询index为0的水果时候稍微慢一点,因为要在index为0的链表中找到相应的水果。
散列表操作 | 平均情况 | 最糟情况 |
---|---|---|
查找 | O(1) | O(n) |
插入 | O(1) | O(n) |
删除 | O(1) | O(n) |
我们可以看到:
所以针对最糟的情况,我们需要:
这样我们以后想要知道某个水果价格,只需要输入水果名字,然后通过散列函数返回一个index值就可以去数组中找相应的价格了。
哪里错误请帮忙指正,thanks。
参考:
《大话数据结构》
《算法图解》