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

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

基本的数据结构类型

什么是数据结构

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

数据结构的子类-链表

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

数据结构的子类-数组

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

数据结构的子类-栈

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

数据结构的子类-队列

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

数据结构的子类-哈希表

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

{
    "蔡徐坤" ："篮球"，
    "吴亦凡" ："说唱"
}

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

数据结构的子类-堆

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

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

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

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

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