文档内容基于 B 站视频： https://www.bilibili.com/video/BV1nJ411V7bd 数据结构以及算法的代码实现： https://github.com/BlckKn1fe/Data-Structure-and-Algorithm

1.1 数据结构与算法

通过计算机去解决一个问题通常要分以下三步：

1. 分析问题，并且找到合适的操作对象
2. 设计算法
3. 编程、调试

所谓的操作对象，需要具体问题具体分析，比如

• 信息表中的操作对象，就是每一行的信息，那么算法也就是 CRUD

• 人机对弈中，操作对象就是棋局的情况，而算法就是如何走下一步棋

很多问题没办法用公式或者方程来表示，归类为“非数值计算”的程序设计问题，描述这些问题的数学模型通常是表、树、或者图之类的具有逻辑关系的数据结构

综上：
数据结构是一门研究非数值计算的程序设计中计算机的操作对象，以及它们之间的关系和操作的学科

1.2 概念与术语

1.2.1 数据

• 数据（Data）：数据也就是信息的载体，并且可以被计算机 CRUD，包括数值型数据和非数值型数据（文字，图像等）
• 数据元素（Data Element）：数据的基本单位，也可以称之为记录、节点等
• 数据项（Data Item）：构成数据元素的最小单位，比如学籍表中的某一条数据，姓名就是一个数据项
• 数据对象（Data Object）：性质相同的数据元素的集合，是数据的子集，比如字母字符、整数等

数据元素和数据对象的区别：

1. 数据元素是数据大集合中的个体
2. 数据对象是数据大集合中的子集

不严谨表示：数据 >= 数据对象 >= 数据元素 > 数据项

1.2.2 数据结构

逻辑结构：数据元素之间的逻辑关系
可以划分为：

1. 集合结构
2. 线性结构：一对一（线性表，字符串，数组，队列，栈等）
3. 树形结构：一对多（非线性）
4. 图状结构：多对多（非线性）

（也可以按照线性结构和非线性结构划分）

物理结构（储存结构）：逻辑结构在计算机中的表示
可以划分为：

1. 顺序存储结构：计算机一片连续的存储单元，并按顺序存储，元素之间是连续的
2. 链式存储结构：元素可存储在任意的存储单元，元素之间关系用指针表示
3. 索引存储结构：最好的例子是通讯录
4. 散列存储结构：根据元素的关键字计算出储存地址（其实也就是 Hash）

1.2.3 数据类型和抽象数据类型（ADT）

（略，参考 P4，全篇基本都在说 OO）
https://www.bilibili.com/video/BV1nJ411V7bd?p=4

1.3 抽象数据类型实现

（略）

1.4 算法与算法算法分析

1.4.1 算法定义及其描述方式

算法的定义：说白了就是解决问题的方法和具体实现步骤

描述算法的有以下几种：

1. 自然语言：中英文等
2. 流程图
3. 伪代码
4. 程序代码：C/C++，Java等

有个重要的概念：
程序 = 数据结构 + 算法

• 数据结构通过算法实现操作
• 算法根据数据结构设计程序

  Algorithms + Data Structures = Programs is a 1976 book written by Niklaus Wirth covering some of the fundamental topics of computer programming, particularly that algorithms and data structures are inherently related. https://en.wikipedia.org/wiki/Algorithms%2B_Data_Structures%3D_Programs

1.4.2 算法效率

在一定前提下，主要通过考虑算法效率来判断算法优劣：

1. 时间效率：对时间效率的分析，主要采用事前分析的方式

（实际评估的时候，不使用实际的耗时，而是使用单位时间，所以只考虑执行次数总和）

当计算时间复杂度的时候，只比较最大的数量级，比如：

这两个算法的时间消耗做比时，不考虑最高次幂的系数以及其他的所有的低次幂，那么第二个算法耗时会更多。他们的时间复杂度通过大 O 表示法

有时候时间复杂度会根据问题的输入而产生一些变化，所以也分为：

• 最坏时间复杂度（考虑的最多）
• 平均时间复杂度
• 最好时间复杂度

当计算一个复杂的算法的时间复杂度的时候，可以把它分成容易评估的部分，然后利用大 O 加法和乘法法则来计算：

• 加法规则

• 乘法法则

1. 空间效率

记作：
n 为问题的规模

例如想要 reverse 一个数组，有以下两种方式

// 方式一
for (i = 0; i < n/2; i++) {
  t = a[i];
  a[i] = a[n - i  - 1];
  a[n - i - 1] = t;
} 
// 方式二
for (i = 0; i < n; i++)
  b[i] = a[n - i - 1];
for (i = 0l i < n; i++)
  a[i] = b[i];

那么方式一中的空间复杂度表示就是
方式二中的空间复杂度表示就是