2021-06-08 JavaScript数据结构与算法

JS中的堆栈-内存的分配和使用

• 堆是动态分配内存，内存大小不一，也不会自动释放
• 栈是自动分配相对固定大小的内存空间，并由系统自动释放

JS的数据类型分为基本数据类型（也称为原始数据类型）和复杂数据类型（引用数据类型） 原始数据类型又分为string、number、boolean、undefined和null（ES6中新增Symbol），这些都是直接按值存储在栈中的，每种类型数据占用的内存空间大小是确定的，并有系统自动分配和释放，这样带来的好处是内存可以及时得到回收，相对于堆来说，更加容易管理内存空间

引用数据类型又分为对象、数组和函数等，这些是通过拷贝和new出来的，这样的数据存储于堆中，其实是引用类型的数据的地址指针是存储在栈中的，当我们想要访问值时，需要先从栈中获取对象的地址指针，然后通过地址指针找到堆中的所需要的数据

栈，线性结构，后进先出，便于管理；堆，一个混乱、杂乱五章，方面存储和开辟空间

内存空间管理： JavaScript的内存生命周期是： 1、分配你所需要的内存 2、使用分配到的内存（读、写） 3、不需要时将其释放、归还

JavaScript有自动垃圾收集机制，最常用的就是用过标记清除算法来找到哪些对象是不再继续使用的（如a = null），会在下次垃圾回收中找到并释放，在局部作用域中，当函数执行完毕后，局部变量也就没有存在的必要了，因此垃圾收集器很容易做出判断并且回收，但是全局变量很难判断什么时候需要自动释放内存空间，因此开发中，尽量避免使用全局变量

深拷贝和浅拷贝

赋值

定义：将某一数值或对象赋给某个变量的过程，分为下面两个部分：

• 基本数据类型：赋值，赋值后两个变量互不影响
• 引用数据类型：赋址：两个变量具有相同的引用，指向同一个对象，相互之间有影响

浅拷贝

1. 定义：创建一个新对象，这个对象有着原始对象属性值的一份精确拷贝。如果属性是基本类型，拷贝的是就是基本类型的值；如果属性是引用类型，拷贝的就是内存地址，所有如果其中一个对象改变了这个地址，就会影响到另外一个对象

2. 使用场景：

    	- `Object.assign()`：该方法用于将所有可枚举属性的值从一个或多个源对象复制到目标对象，返回目标对象
    	- 展开语法`Spread`：扩展运算符...和`Object.assign()`效果是一样的
    	- `Array.prototype.slice()`：返回一个新的数组对象，由一个`begin`和`end`（不包括`end`）决定的原数组的浅拷贝，原始数组不会改变
   

深拷贝

1. 定义：会拷贝所有的属性，并拷贝属性指向的动态分配的内存。当对象和它所引用的对象一起拷贝时即发生深拷贝，深拷贝相比于浅拷贝速度较慢并且花销较大，拷贝前后两个对象互不影响

2. 使用场景：

    	`JSON.parse(JSON.stringify(object))`：完全改变变量1对变量2的影响，但是该方法会有一下几个问题。
    		- 会忽略`undefined` 
    		- 会忽略`symbol`
    		- 不能序列化函数
    		- 不能解决循环引用的对象
    		- 不能正确处理`new Date()`
    		- 不能处理正则
   

数据结构

一般可以从两个维度来理解，逻辑结构和存储结构 逻辑结构：

简单来说逻辑结构就是数据之间的关系，分为两种：线性结构和非线性结构

线性结构：是一个有序数据元素的集合。 其中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的，如栈、队列、链表、线性表

非线性结构：各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生联系，如二维数组、树

存储结构：逻辑结构指的是数据间关系，而存储结构是逻辑结构用计算机语言的实现。常见的存储结构有顺序存储、链式存储、索引存储以及散列存储

经典的数据结构就那么几种，list、stack、queue、linkedList、dictionary、hash、set、tree、graph等等

数组是基础，然后为数组封装好一个List构造函数，增加长度、插入、删除、索引、遍历等工具接口，这样就构造了一个列表

列表（List），是计算机中一种常见的数据结构，是一组有序的数据，每个列表中的数据项称为元素，其中元素可以是任意数据类型

栈（Stack），又叫堆栈，是和列表类似的一种数据结构，但是更高效，因为栈内的元素只能通过列表的一端访问，称为栈顶，数据只能在栈顶添加和删除，具有后进先出的特点（LIFO，last in first out）

队列（Queue），与栈不同，它也是一种特殊的列表，队列只能在队尾插入元素，在队首删除元素，具有先进先出（FIFO，first in first out）的特点

链表（Linked-list），前面说到的栈和队列其实都是列表的一种，底层存储的数据结构都是数组，除了其外，还有链表这种数据结构，链表是一组节点组成的集合，每个节点都使用一个对象的引用来指向它的后一个节点。指向另一节点的引用讲做链如下图，链表又分为单向链表、双向链表和循环链表（单双向）

字典（Dictionary），是一种以键-值对形式存储数据的数据结构，其实，JavaScript 中的 Object 类就是以字典的形式设计的

集合（set），是由一组无序但彼此之间又有一定关系性的成员构成，每个成员在集合中只能出现一次，不同于我们之前说的字典，链表之类的，它是一种包含了不同元素的数据结构(集合中的元素称为成员)，从其定义中我们可以看出它具有两个很重要的特征：首先，集合中的成员是无序的；其次，集合中的成员是不相同的，即集合中不存在相同的成员

排序搜索算法

排序算法

• 冒泡排序：比较任何两个相邻的项，如果第一个比第二个大，则交换它们；元素项向上移动至正确的顺序，好似气泡上升至表面一般，因此得名
• 选择排序：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，以此循环，直至排序完毕
• 插入排序：将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，此算法适用于少量数据的排序，时间复杂度为 O(n^2)
• 归并排序：将原始序列切分成较小的序列，只到每个小序列无法再切分，然后执行合并，即将小序列归并成大的序列，合并过程进行比较排序，只到最后只有一个排序完毕的大序列，时间复杂度为 O(n log n)
• 快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行上述递归排序，以此达到整个数据变成有序序列，时间复杂度为 O(n log n)

搜索算法

• 顺序搜索：让目标元素与列表中的每一个元素逐个比较，直到找出与给定元素相同的元素为止，缺点是效率低下
• 二分搜索：在一个有序列表，以中间值为基准拆分为两个子列表，拿目标元素与中间值作比较从而再在目标的子列表中递归此方法，直至找到目标元素

其他

• 贪心算法：在对问题求解时，不考虑全局，总是做出局部最优解的方法
• 动态规划：在对问题求解时，由以求出的局部最优解来推导全局最优解
• 复杂度概念：一个方法在执行的整个生命周期，所需要占用的资源，主要包括：时间资源、空间资源

时间复杂度和空间复杂度

时间复杂度和空间复杂度的高低决定着一段代码质量的好坏 时间复杂度：一个算法的时间复杂度反映了程序运行从开始到结束所需要的时间，把算法中的基本操作重复执行的次数（频度）作为算法的时间复杂度

没有循环语句，记作O(1)，也称为常数阶。只有一重循环，则算法的基本操作的执行频度与问题规模n呈线性增大关系，记作O（n），也叫线性阶

常见的时间复杂度有：

• O(1): Constant Complexity: Constant 常数复杂度
• O(log n): Logarithmic Complexity: 对数复杂度
• O(n): Linear Complexity: 线性时间复杂度
• O(n^2): N square Complexity 平⽅方
• O(n^3): N square Complexity ⽴立⽅方
• O(2^n): Exponential Growth 指数
• O(n!): Factorial 阶乘

空间复杂度：一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计

一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间

JavaScript设计模式

设计模式分三大类：

创建型设计模式： 创建型设计模式关注于对象创建的机制方法，通过该方法,对象以适应工作环境的方式被创建。基本的对象创建方法可能会给项目增加额外的复杂性，而这些模式的目的就是为了通过控制创建过程解决这个问题。

属于这一类的一些模式是：构造器模式（Constructor）,工厂模式（Factory）,抽象工厂模式 （Abstract）,原型模式 （Prototype）,单例模式 （Singleton）以及 建造者模式（Builder）

结构设计模式： 结构模式关注于对象组成和通常识别的方式实现不同对象之间的关系。该模式有助于在系统的某一部分发生改变的时候，整个系统结构不需要改变。该模式同样有助于对系统中某部分没有达到某一目的的部分进行重组。

在该分类下的模式有：装饰模式，外观模式，享元模式，适配器模式和代理模式

行为设计模式： 行为模式关注改善或精简在系统中不同对象间通信。

行为模式包括：迭代模式，中介者模式，观察者模式和访问者模式