数据结构 - 算法

1. 线性表

线性表是为了解决单线存储而出现的。最基础结构为数组和链表，栈和堆是线性表的特殊形态，在操作上进行了限制。构造一个栈或堆结构，既可以使用数组，也可以使用链表。

1.1 数组

数组：就是最简单粗暴的存储方法。就是直接拉出一大块数据存在那里。数组的快速存取其实只是一个副作用，因为所有的数据都在一起，可以直接算出来数据的地址。数组的优势是连续内存，可以快速读取。缺点是插入比较困难，需要后面数据挪位置。

c/c++语言的数组更接近数据结构的数组概念，默认是不能动态扩容的。js高级语言的数组概念就包含更多，比如动态扩容、语言层自实现栈、队列特性。

1.2 链表

链表：则是为了解决可以无线增长的需求。因为找不到一大块可以连续的存入数据，甚至也不知道程序可能使用的数据总量，所以就没办法划分一块数据来使用，划小了不够用，划大了浪费（这在早年是非常大的事情）。所以必须想办法解决问题。最后采用的方法就是从入口开始，每一个数据块不仅仅有数据，还会有指向下一个数据块的线索，用来寻找下一个数据。这就是链表。

数组和链表都是一种数据结构，数组是开辟整块内存，链表则拥有next指针，指向下一个node节点。

1.3 总结

• 数组（连续存储）；
• 链表（离散存储）；
  • 有序表：要求插入元素时，对元素对值进行比较，以找到相应的插入位置。
  • 顺序表、单链表、循环链表、双向链表
• 栈（线性结构常见应用，由链表或数组增删和改进功能实现），特点是先进后出；
• 队列（线性结构常见应用，由链表或数组增删和改进功能实现），特点是先进先出；

数组和链表是最基础的数据结构，相同的功能实现可以用数组结构，也可以用链表结构，如栈与队列的实现，可以底层存储是用数组，也可以是小块内存链接起来的链表。再比如数组的reverse翻转，使用数组或链表数据结构，相关算法是完全不一样的。

2. 树

树是为了解决单一入口下的非线性关联性的数据存储或者排序这样的功能而来的。

• 二叉树：二叉树的节点最多只能有两个节点（左、右节点）
  • 二叉搜索树：二叉树的一种，左节点比父节点小，右节点比父节点大。
• B树、B+树
• 红黑树

最常见的应用是编程时候的map，就是利用了二叉树的可排序和可以快速插入并且保持序列完整的特性来构建键值数据对，来实现数据的插入增加以及快速查找的能力的。

还有做语法解析，文字处理等等很多场景也会用到树。这就不一一赘述了。当然在吃透线性表的基础上，再去理解树也并不难。因为在本质上，树相对于链表，就是每个节点不止有一个后续节点但是只有一个前置节点。

3. 图

待更新。。。

4. 算法

通过算法来学习数据结构很有效。

常见算法：

• 数组操作：
  • 翻转reverse
  • 推入push
  • 查询search（二分法/折半搜索法，针对有序数组查找）
• 数组排序
  • 快速排序(以某个值为基准，左右排列)
  • 冒泡排序
• 深度优先搜索
• 广度优先搜索
• 贪心算法: 算法简单，运算非常快。可能不能获得最优解，但非常接近
• 分治法
• 回溯法

常见大O运行时间：

• O(log n),也叫对数时间，如：二分查找
• O(n), 线性时间，如：简单查找
• O(nlog n) 如：快速排序
• O(n²) 如：冒泡算法、选择排序算法,属于较慢的一种算饭
• O(n!) 非常慢的算法

对数概念：log₁₀100等同于“将多少个10相乘的结果为100”，所以log₁₀100=2（2个10相乘等于100）。对数运算是幂运算的逆运算，使用大O表示法时，log指的是log₂，所以一般二分法是logn。

O(log n)比O(n)快，当搜索的元素越多时，前者比后者快的越多。