数据结构与算法导论-理论篇

写在前面

这一篇侧重数据结构与算法的理论知识，最近应该会再写一篇–代码实践篇（如果过年期间我没有偷懒的话）
因为理论不是很复杂，简单的概念我就不再赘述了，挑一些我最近复习时发现的重点（其实就是我大学没有记牢的知识点）。。

数据结构

什么是数据结构

数据结构起源于程序设计，是用计算机来存储、组织数据的的方式。
数据结构不是使我们学会敲代码，而是为我们提供一种编程思想，具有更好的思路

• 广义的定义： 数据结构 = 数据存储 + 算法
• 狭义的说法： 数据结构 = 数据的存储

数据结构能做什么

• 程序员的内功心法之一
• 有效的管理数据对象
• 解决处理性能问题
• 面试加分项

数据结构与算法的关系

数据元素互相之间的关系称为结构

• 逻辑结构：反应数据元素之间的逻辑关系
• 存储结构：数据结构在计算机中的表示
• 算法：对数据的操作

四种基本数据结构及衍生结构

四种基本数据类型是：集合，线性结构，树状结构，图状结构（网状结构）

集合

• 数据成员是无序的
• 每个数据成员在集合中不能重复， 仅且仅出现一次

比如JS ES6中的set数据结构

线性表

按照物理结构又分为 顺序表和链表

• 顺序表：占用 连续 的内存空间，不能有空洞
• 链表：可以占用不连续的内存空间，使用 引用 来记录互相之间的地址

另外：链表又分为，单链表和双链表，各自的区别和优缺点就不在赘述了

线性表的衍生结构–栈

操作受限的线性表
操作原则：LIFO（Last In First Out） 后进先出
用途：

• 函数调用
• KOA的中间件执行机制
• 括号匹配检查
• 浏览器后退，编辑器undo功能等等

线性表的衍生结构–队列

操作受限的线性表
操作原则：FIFO（First In First Out） 先进先出
用途：

• 消息队列
• 视频弹幕
• 维护打印机任务等等

树

树是有若干个有限节点组成的一个具有层次关系的集合
几个核心概念：

• 边：两个节点直接相连； 路径： 非直接相连
• 树和图的区别：任意两个节点之间只有 一条路径 ，是树；否则就是图；
• 度：有几个子节点就有几个度，度为0的叫叶子节点

树的遍历

先区别下两个概念：

• 经过： 只操作树节点的引用部分，不操作数据部分；
• 访问： 会操作数节点的数据部分

树的遍历：按照某种规则，不重复的 访问 某种树的所有节点

深度优先

比如，AlphaGo下围棋用的就是深度优先，如果人最多可以深度考虑到下面3步的情况，哪儿AlphaGo可以用深度优先算法考虑到10步甚至更多步之后的情况，自然就比人类厉害了

先序遍历

访问节点的顺序： 根，左，右

中序遍历

访问节点的顺序： 左，根，右

后序遍历

访问节点的顺序： 左，右，根

广度优先-层序遍历

典型的例子：搜索引擎
访问节点特点：一层一层的

树的衍生

1.根据边是否是向量，分为有序树和无序树
2.有序树，边的权值不同的情况下，带权路径最短的树叫做霍夫曼树，也叫最优二叉树
使用场景： 压缩软件，压缩视频和音频
3.二叉树的两种情况： 完全二叉树，满二叉树

图

由顶点的集合（不能是空集）和边的集合组成的结构，变现是多对多的关系
也分为有向图和无向图

注意这几种结构的叫法：
线性表中叫元素； 数中叫节点； 图中叫顶点；

算法

算法是完成某个特定任务的过程。
一般认为： 程序 = 数据结构 + 算法

常见的算法

• 排序算法
• 查找算法
• 推荐算法
• 贪心算法

算法五大特征

有穷性； 确切性； 输入项； 输出项； 可行性；

衡量算法标准

• 时间复杂度
• 空间复杂度
• 正确性
• 可读性
• 健壮性

1.时间复杂度：
因为计算机硬件等原因会导致同样的程序再不同机器上运行时间不一样
所以时间复杂度并不是真正执行的时间，而是用单个基本步骤执行次数表示；

2.空间复杂度
算法运算是需要额外使用的内存大小
当然，它也不是绝对的字节大小，而是用多少个基本元素的大小来衡量

高手必会十大算法

作为普通程序员，左边的排序算法和查找算法两大类，是我们必须掌握的

排序算法

1.前三列表示时间复杂度
best表示运气比较好，初始的时候基本排好了；
worst表示运气很差，初始的时候很乱，甚至完全相反。
一般我们着重看中间average平均的情况；
注意：log对数，比较小，是比较好的排序算法；JS原生的 sort排序 ，就是使用的快排哦。
2.第四列是空间复杂度
一般来说，时间复杂度高的，空间复杂度就会低些；所以要在二者中权衡。
3.最后一列是稳定性；
可能细心地人看见了，想要时间复杂度和空间复杂度都要好的话，用堆排啊！
没错，但是堆排不稳定；不稳定表现在：
有重复的数据，出现的结果可能不一样哦。
4.整体综合起来，最好的是 快排！

查找算法

1.顺序查找：
时间复杂度是n，适合小数据量
2.二分查找：
时间复杂度是log对数，也只适合小数据量，而且前提是数据必须排序好了；
3.分块查找：
适合大数据量，可以看做是二分查找的 增强升级版。
时间复杂度是log/n，但是需要对数据进行更多的处理，而且不适合数据库数据的这种情况。
4.散列表：
适合数据库大数据量的情况，使用索引查找。

总结

至此，把数据结构与算法导论的基本理论过了一遍，下一篇会对排序算法进行具体的JS代码实现~