算法笔记-入门-数据结构篇

算法笔记-入门-数据结构篇
从大学毕业之后就没研究过算法,都快忘光了,现在开个新坑,从头学起算法,哈哈,希望自己能够坚持住,不过我一定可以坚持住的,我就像易筋洗髓一样,将自己全身打断,重塑自己的一切,回归初心,以一个听者的名义对待一切,因为我做的都是我自己喜欢的事儿。

基本的数据结构类型

什么是数据结构

说白了很简单,数据存计算机里,总得有个存放规律,不能乱来,就像你查字典,你可以一页一页翻着找字儿,你也可以直接按拼音跳转找字儿,这就是查字典的数据结构,数据结构就是决定数据顺序和位置的关系

数据结构的子类-链表

链表,这玩意儿理解起来会抽象一些,大学课本上表示它的数据是一个线性排列的,要我说不用这么麻烦,链表其实就是一列火车,举例来说,现在有4节车厢,你必须通过一节车厢才能到下一节去,也就是说,车厢(链表)都有一个指示牌(指针),你必须一个个往下,到达下面的车厢(指向下一个地址)。
链表这玩意儿吧,慢,查东西你得一个个往下,添加,删除数据都先要改变指针。
查一个东西,拿大O表示法,它的复杂度是O(n),算是相当慢的一种算法了。

数据结构的子类-数组

数组,也是线性排列的数据结构,还记得链表么,链表是靠指针指向,告诉你我下一个老哥是谁,但是数组不一样,它是靠一个叫数组下标的东西来告诉你,我是第几个,在Python中,这玩意儿被运用在列表里,就像a = [1,2,3,4,5] 这种形式,a[0] = 1, a[1] = 2…….
其实你想查一个数组里面的东西,一般都是随机访问,可以直接去访问数组下标,这东西就相当于你吃饭取的号儿,到你了,人家就喊“XXX号用餐了!”数组下标就这个功能。
数组里面,你要添加或者删除一个元素,那可有点麻烦,你要先在数组尾部,加一个多的存储空间,总不可能让新元素没地方去吧,然后你要让旧元素给新朋友腾个位置,然后把旧朋友往后面赶,然后新朋友才能顺利插队。。。

数据结构的子类-栈

栈这位老哥会理解麻烦一点,这么想,你随时随地都能吃到最新鲜的水果,每天都有新的水果,你总能拿到新水果,旧水果就只有在下面,所以你如果想吃旧水果,你就要把水果箱子一点点拿出来,被称为出栈,把水果放回去,叫进栈,这个东西就是你只能拿最新的,后进先出,LIFO结构,这玩意儿还是挺不方便的。
不过在业务中,如果你需要时刻保持最新数据在前面,例如,时事热点,附近的人等等,拿这玩意儿就好用多了。

数据结构的子类-队列

和上面的栈老哥相反,队列的意思就是,你先进来的啊,你边儿待着,该需要的时候要我旧数据先上,拿数据从最老的数据拿,新数据一边玩去。想拿新数据?不好意思,一个个出来吧你,直到该你出去为止。

数据结构的子类-哈希表

这个在这说有点那啥,但是啊,你们写过Python的应该知到,Python里面有个dict(字典),字典这玩意儿就是一个key 对应 一个value,例如

1
2
3
4
{
"蔡徐坤" :"篮球",
"吴亦凡" :"说唱"
}

这就实现了一个字典,你会问,这和TM哈希表有啥关系,哈希表这玩意儿,是存dict的东西,它是个类数组的东西,但是存的东西很变态,一般我们会用hash函数,计算”蔡徐坤”的键,也就是”蔡徐坤”的哈希值,然后我们将得到的哈希值除以数组长度(哈希表长)取余数,计算出”蔡徐坤”在数组中的位置,然后把它放进去。这里比较抽象,后面会专门讲一下哈希这个算法。
那么怎么查呢,首先我们拿到”蔡徐坤”的哈希值,然后通过刚才的计算就能找到”蔡徐坤”在哈希表中的位置了。

数据结构的子类-堆

重头戏来了,这玩意儿是一个树形结构,树形,顾名思义,是分叉的,想象一下,一棵树的样子,这玩意儿是拿来搞优先队列用的,堆里面有个老大,叫结点,所有的数据都是结点的小弟,受他罩着,其中他有多个手下,叫子结点,子结点一般比父结点大,最小的值一般都在堆的顶点。
堆中最顶端的数据始终最小,所以无论数据量有多少,取出最小值的时间复杂度都 为 O(1)。
另外,因为取出数据后需要将最后的数据移到最顶端,然后一边比较它与子结点数据 的大小,一边往下移动,所以取出数据需要的运行时间和树的高度成正比。假设数据量为 n,根据堆的形状特点可知树的高度为 log2n ,那么重构树的时间复杂度便为 O(logn)。
添加数据也一样。在堆的最后添加数据后,数据会一边比较它与父结点数据的大 小,一边往上移动,直到满足堆的条件为止,所以添加数据需要的运行时间与树的高度 成正比,也是 O(logn)

数据结构的子类-二叉查找树

和楼上那位一样,也是个树形结构,不一样的是,二叉树每个结点的值大于左子树上任意一个结点的值,比较抽象对吧,来看个图

意思就是,无论怎么样,左边老哥总会比我小。
第二个分歧就是,右边老哥总比我大,继续看图

这就是一部分基础,做了粗略写作,写得不好,见谅,over!

  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2019-2024 Yemilice lau
  • Powered by Hexo Theme Ayer
  • PV: UV:

觉得帮到你了么?赏我点儿~

支付宝
微信