数据结构与算法
认识数据结构与算法
编程的最终目的只有一个：对数据进行操作和处理
- 术之尽头炁体源流
- 编程尽头数据结构
数据结构与算法的本质就是一门专门研究数据如何组织、存储和操作的科目
系统、语言、框架源码随处可见数据结构与算法
- 无论是操作系统（Windows、Mac OS）本身，还是我们所使用的编程语言（JavaScript、Java、C++、Python等等）还是我们在平时应用程序中用到的框架（Vue、React、Spring、Flask等等），它们的底层实现到处都是数据结构与算法，所以你要想学习一些底层的知识或者某一个框架的源码（比如 Vue、React的源码）是必须要掌握数据结构与算法的
- 以前端为例：框架中大量使用到了栈结构、队列结构等来解决问题（比如之前框架源码时经常看到这些数据结构，Vue 源码、React 源码、Webpack 源码中可以看到队列、栈结构、队列结构等来解决问题，Webpack 中还可以看到很多 Graph 图结构）
- 实现语言或者引擎本身也需要大量的数据结构：哈希表结构、队列结构（微任务队列、宏任务队列），前端无处不在的数据结构：DOM Tree（树结构）、AST（抽象语法树）
因为对于很多企业来说，想要短时间考察一个人的能力以及未来的潜力，数据结构与算法是非常重要的指标，也会成为它们的硬性条件
- 对于可以将数据结构与算法掌握很好的开发人员来说，通常对于业务的把握肯定是没有问题的
- 并且对于系统的设计也会更加合理，可以写出更加高效的代码
数据结构
- 数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出————《数据结构、算法与应用》
- 数据结构是 ADT（抽象数据类型 Abstract Data Type）的物理实现————《数据结构与算法分析》
- 数据结构（data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法————中文维基百科
图书摆放规则
- 随便放
- 插入操作：哪里有空放哪里，一步到位
- 查找操作：找某本书，累死...
- 按照书名的拼音字母顺序摆放
- 插入操作：新进一本《阿Q正传》、《理想国》，按照字母顺序找到位置，插入
- 查找操作：二分查找法
- 把书架划分成几个区域，按照类别存放，类别中按照字母顺序
- 插入操作：先定类别，二分查找确定位置，移出空位
- 查找操作：先定类别，再二分查找
常见数据结构
- 数组（Array）
- 栈结构（Stack）
- 队列（Queue）
- 链表（LinkedList）
- 图结构（Graph）
- 散列表（Hash）
- 树结构（Tree）
- 堆结构（Heap）
算法
解决问题的过程中，不仅仅数据的存储方式会影响效率，算法的优劣也会影响效率
算法
- 一个有限的指令集，每条指令的描述不依赖于语言
- 接受一些输入（有些情况下不需要输入）
- 产生输出
- 一定在有限步骤之后终止
生活中的算法
找出线缆出题的地方:
- 假如上海和杭州之间有一条高架线，高架线长度是 100000 米，有一天高架线中有其中一米出现了故障
- 请你想出一种算法，可以快速定位到出问题的地方
线性查找:
- 从上海的起点开始一米一米的排查，最终一定能找到出问题的线段
- 但是如果线段在另一头，我们需要排查 100000 次，这是最坏的情况，平均需要 50000 次
二分查找:
- 从中间位置开始排查，看一下问题出在上海到中间位置，还是中间到杭州的位置
- 查找对应的问题后，再从中间位置分开，重新锁定一般的路程
- 最坏的情况，需要多少次可以排查完呢？最坏的情况是20次就可以找到出问题的地方
- 怎么计算出来的呢？log(100000，2)，以 2 为底，100000 的对数 ≈ 20
结论:
- 你会发现，解决问题的办法有很多，但是好的算法对比于差的算法，效率天囊之别
刷题
图片来源：全栈潇晨
