数据结构与算法

最近打算趁着过年这段时间，从头的开始梳理一下数据结构与算法的相关知识，一步一步慢慢来进行学习，在这里顺便记录一下相关笔记，方便以后进行复习

主要参考的是 大话数据结构 与 数据结构与算法分析，方向也主要是偏向于 JavaScript 当中的实现

既然是数据结构与算法，那么我们就先来看看什么是数据结构

数据结构

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的科学，简单总结如下

• 程序设计 = 数据结构 + 算法
• 数据元素相互之间存在的一种或多种特定关系的集合

传统上数据结构分为逻辑结构和物理结构

• 逻辑结构（主要），指数据对象中数据元素之间的相互关系
• 物理结构（次之），数据的逻辑结构在计算机中的存储形式

逻辑结构

• 集合结构，集合结构中的数据元素除了同属于一个集合外，没有其他任何关系
• 线性结构，线性结构中的元素之间是一对一的关系
• 树形结构，树形结构中的数据元素之间存在一种一对多的层次关系
• 图形结构，图形结构的数据元素是多对多的关系

物理结构

物理结构实际上研究的就是如何把数据元素存储到计算机的存储器当中，存储器主要是针对内存而言，像硬盘，软盘等外部存储器的数据组织通常用文件结构来描述

顺序存储和链式存储

• 顺序存储结构是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一直的（数组）
• 链式存储结构是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的（叫号）

针对链式存储结构，其数据元素存储关系并不能反应其逻辑关系，所以需要用一个指针存放数据元素的地址，这样就可以通过地址来找到相关联数据元素的位置

算法

算法并不是唯一的，同一个问题可以有多种解决问题的算法，以下是两种方式计算一到一百累加的结果

1
2
3
4
5
6
7
8
9

let result = 0
for (let i = 1; i <= 100; i++) {
  result += i
}

// VS

let m = 1, n = 100
let result = (m + n) * (n / 2)

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作，算法具备五个基本特征，输入，输出，有穷性，确定性和可行性

• 输入，具有零个或多个输入
• 输出，至少有一个或多个输出
• 有穷性，在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成
• 确定性，每一个步骤都有明确的含义，在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果，每个步骤都应该被精确定义而无歧义
• 可行性，每一步都是可行的，即都能够通过执行有限次数完成

设计

• 正确性，指算法至少应该具有输入、输出和加工处理无歧义性，能正确反映问题的需求，能够得到问题的正确答案
• 可读性，目的是为了便于阅读、理解和交流
• 时间效率高和存储量低

算法效率的度量方法

事前分析估算方法，即在计算机程序编写前，依据统计方法对算法进行估算

时间复杂度

在进行算法分析时，语句总的执行次数 T(n) 是关系问题规模 n 的函数，进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级，也就是算法的时间量度，记作 T(n) = O(f(n))，它表示随问题规模 n 的增大，算法执行时间的『增长率』和 f(n) 的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度

其中 f(n) 是问题规模 n 的某个函数

推导大 O 阶

• 用常数 1 取代运行时间中的所有加法常数（例如 (1 + n) * n / 2 记作 O(1)）
• 在修改后的运行次数函数中，只保留最高阶项（例如单层 for 循环，记作 O(n)）
• 如果最高阶项存在且不是 1，则去除与这个项相乘的常数（例如双重 for 循环，记作 O(n^2)，三重则是 O(n^3)）

对于下列函数

1
2
3
4
5

for (let i = 0; i < n; i++) {
  for (let j = i; j < n; j++) {
    // ...
  }
}

也是一致的，复杂度为 O(n^2)，但是还有一种比较特殊的，先来看下面这个示例

1
2
3
4
5

let i = 1, n = 100

while (i < n) {
  i = i * 2
}

由于每次 i * 2 之后，就距离 n 更进一步，假设有 x 个 2 相乘后大于或等于 n，则会退出循环，所以由 2^x = n 可以得到 x = log(2)n，所以上述循环的时间复杂度为 O(logn)

函数调用的时间复杂度

先看下面这个示例

1
2
3
4
5
6
7

for (let i = 0; i < 100; i++) {
  log(i)
}

function log(n) {
  console.log(n)
}

在这种情况下，时间复杂度为 O(n)，稍微调整一下

1
2
3
4
5
6
7
8
9

for (let i = 0; i < 100; i++) {
  log()
}

function log() {
  for (let i = 0; i < 100; i++) {
    console.log(i)
  }
}

这样一来跟之前的示例是一样的，但是它的复杂度是 O(n^2)

常见的时间复杂度

可以参考下表

耗费时间从小到大依次是

1

O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

时间曲线如下所示

算法一般要求尽量的简洁实用，但是对于 O(n^3) 之后的复杂度，由于 n 值的增大都会使得结果大的难以想象，所以一般不会去讨论它们，谁用谁傻逼

最坏情况与平均情况

比如我们查找一个有 n 个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么复杂度就为 O(1)，但是也有可能这个数字在最后一个位置，那么复杂度就为 O(n) 了

平均运行时间是期望的运行时间

最坏运行时间是一种保证，在应用中是一种最重要的需求，通常除非特别指定，我们提到的『运行时间都是最坏的运行时间』

空间复杂度

空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式为

1

S(n) = O(f(n))

其中 n 为问题的规模，f(n) 为语句关于 n 所占存储空间的函数

• 时间复杂度来指运行时间的需求
• 空间复杂度来指运行空间的需求

空间复杂度涉及到的较少，除非明确指明，否则我们在平常一般所讨论到的复杂度都是指时间复杂度

数据结构与算法知识梳理

最后更新于 2020-06-12

这部分内容算是针对文章当中所涉及到的数据结构与算法相关内容的一个汇总

线性表

线性表由零个或多个数据元素组成的有序序列，它有以下特点

• 它是一个序列，也就是说元素之间是先来后到的
• 若元素存在多个，则第一个元素无前驱，而最后一个元素无后继，其他元素都有且只有一个前驱和后继
• 另外，线性表强调是有限的，事实上无论计算机发展到多大，它所处理的元素都是有限的

它有两种物理存储结构，顺序存储结构和链式存储结构，物理上的存储方式事实上就是在内存中找一个初始地址，然后通过占位的形式，把一定的内存空间给占用，然后把相同数据类型的数据元素依次放在这块空地中，具体内容可以见下方列表

• 顺序存储结构
  • 读取操作/插入操作/删除操作
  • 顺序存储结构的优缺点
• 链式存储结构
  • 单链表
  • 读取操作/插入操作/删除操作
  • 单链表整表创建（头插法/尾插法）与删除
  • 单链表结构与顺序存储结构优缺点
• 静态链表
  • 插入操作/删除操作
  • 静态链表的优缺点
• 循环链表
  • 约瑟夫问题
  • 循环链表的特点
  • 判断链表中是否有环
• 双向链表与双向循环链表
  • 双向链表结点结构
  • 双向链表的插入操作
  • 双向链表的删除操作

栈和队列

使用栈结构存储数据，讲究『先进后出』，即最先进栈的数据，最后出栈，而使用队列存储数据，讲究『先进先出』，即最先进队列的数据，也最先出队列，既然栈和队列都属于线性表，所以根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链表，队列也分为顺序队列和链队列

• 栈
  • 栈的定义
  • 入栈操作和出栈操作
  • 栈的链式存储结构
    • 进栈操作
    • 出栈操作
  • JavaScript 中的栈的实现
    • 顺序存储
    • 链式存储
• 队列
  • 队列的定义
  • 队列的顺序存储结构
  • 队列的链式存储结构
    • 入队列操作
    • 出队列操作
    • 销毁一个队列
  • 循环队列定义以及操作
  • JavaScript 中的队列实现
    • 链式存储
    • 顺序存储

递归

递归（Recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法，递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念，绝大多数编程语言支持函数的自调用，简单来说，就是函数直接或间接调用函数本身，则该函数称为『递归函数』，详细可见 递归，内容包括

• 什么是递归
• 斐波那契数列
• 尾调用
• 分治思想
• 汉诺塔
• 八皇后问题

树和二叉树

在上面我们介绍了 单链表，循环链表，双向链表与双向循环链表，栈和队列 等相关知识，但是如果细心观察可以发现，我们之前介绍的种种，它们其实都是一种『一对一』 的线性结构，无论是线性表也好，或者说是栈和队列，都是一样的，所以下面我们就来看一种『一对多』 的数据结构，那就是『树结构』，内容如下

• 树
  • 树的定义
  • 结点分类
  • 结点间的关系
  • 树的存储结构（双亲表示法/孩子表示法）
• 二叉树
  • 二叉树的定义
  • 特殊二叉树（斜树/满二叉树/完全二叉树）
  • 二叉树的存储结构（顺序存储结构/二叉链表）
• 二叉树的遍历
  • 前序遍历/中序遍历/后序遍历/层序遍历
• 线索二叉树
  • 为什么需要线索二叉树
  • 线索二叉树的定义与遍历
• 树、森林与二叉树之间的转换
  • 普通树转换为二叉树
  • 森林转换为二叉树
  • 二叉树转换为树、森林
  • 树与森林的遍历
  • 赫夫曼树
  • 赫夫曼编码

图结构

在上面的 单链表，循环链表 等链表章节当中我们知道了每个元素之间只有一个直接前驱和一个直接后继元素，同样的在 树 与 二叉树 等章节当中知道了树这种结构中，数据元素之间是层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关，但是以上这些仅仅都只是一对一，一对多的简单模型，那么如果元素之间存在多对多的关系呢，我们又该如何来处理呢？下面我们就来看看图这种结构

• 图结构
  • 图的定义（无向边/有向边）
  • 简单图/无向完全图/有向完全图/稀疏图/稠密图/网/子图
  • 连通图/连通分量/强连通图
  • 生成树/有向树
• 图的存储结构
  • 邻接矩阵（无向图/有向图/网）
  • 邻接表（无向图/有向图/网）
  • 十字链表
  • 邻接多重表
  • 边集数组
• 图的遍历
  • 深度优先遍历/广度优先遍历
  • 马踏棋盘算法
  • 普里姆算法/克鲁斯卡尔算法
• 最短路径
  • 迪杰斯特拉算法/弗洛伊德算法
• 关键路径
  • 拓扑序列/拓扑排序
  • 关键路径的作用
  • AOV 网与 AOE 网的比较

查找算法

在小节当中，我们会介绍一类在平常开发过程当中经常会使用的算法，那就是查找算法，关于查找算法肯定不需要多说，都是耳熟能详的，什么顺序、二分之类的就算是没有用过应该也听闻过，那么今天我们就来简单的总结整理一下查找算法的分类和一些比较常用的算法

• 查找算法
  • 查找算法的分类
  • 顺序查找/二分查找/插值查找/斐波那契查找/线性索引查找（有序）
  • 散列表查找（无序）
• 二叉排序树
  • 为什么需要二叉排序树
  • 二叉排序树
  • 查找/删除
• 平衡二叉排序树
  • 二叉排序树存在的问题
  • 平衡二叉排序树
  • 平衡二叉排序树的构建过程
  • 平衡二叉排序树的旋转（LL 型/RR 型/LR 型/RL 型）
• 散列表查找
  • 散列函数设计（直接定址法/数字分析法/平方取中法/折叠法/除留余数法/随机数法）
  • 处理散列冲突的方法（开放定址法/再散列函数法/链地址法/公共溢出区法）

排序算法

排序算法算得上是在所有的算法当中应该算是应用最为广泛的一类算法，详细可见 排序算法，总共有十种方式，如下

• 比较排序（冒泡排序/选择排序/插入排序/希尔排序/归并排序/快速排序/堆排序）
• 非比较排序（计数排序/基数排序/桶排序）