1. 前言
对于一名有追求的程序猿来说，数据结构和算法是一门必修课，它是内功，内功的深厚直接决定了解决问题的能力和学习新技术的能力。
2. 定义
广义上：
数据结构就是数据的存放方式，就像图书馆中的书排列的规则。
算法就是操作数据的方式，就像如何从图书馆中找一本书的方法。
狭义上：
数组、链表、队列、栈、树、图就是数据结构
冒泡排序、堆排序、二分查找、Dijkstra就是算法
它们相辅相成，总结来说：
程序设计 = 数据结构 + 算法
3.意义
- 写出高质量的代码， 程序在性能上有质的提升。
- 提升逻辑思维能力，更容易看懂别人写的代码。
- 助攻面试，进大厂。
- 为转战AI，打下基础。
4. 数据结构
4.1 数据结构的分类
数据结构可分为：
- 逻辑结构：指数据对象中数据元素之间的相互关系，也是我们研究的重点
- 物理结构：数据的逻辑结构在计算机中的存储形式
4.2 逻辑结构
四大逻辑结构
-
集合结构：集合结构中的元素除了同属于一个集合外，它们之间没有其他关系
集合.png -
线性结构： 线性结构中的数据之间是一对一的关系
线性.png -
树形结构：树形结构中的数据元素之间是一对多的层次关系
树形.png -
图形结构： 图形结构的数据元素是多对多的关系
图形.png
四种逻辑结构的对比如下：
| 序号 | 名称 | 元素之间的关系 |
|---|---|---|
| 1 | 集合结构 | 没有关系 |
| 2 | 线性结构 | 一对一 |
| 3 | 树形结构 | 一对多 |
| 4 | 图形结构 | 多对多 |
4.3 物理结构
物理结构其实就是研究如何将数据元素存储到计算机的存储器中，这里指的存储器是针对内存而言，像硬盘、软盘、光盘等外部存储设备通常是以文件的形式来描述的。
数据元素的存储结构形式有两种：顺序存储和链式存储
-
顺序存储结构：是把元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。例如数组
顺序存储.png 链式存储结构： 把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。
两种物理结构的对比如下所示：
| 序号 | 名称 | 元素存储特点 |
|---|---|---|
| 1 | 顺序存储结构 | 地址连续的存储单元里 |
| 2 | 链式存储结构 | 地址不一定连续的存储单元里 |
5. 算法
算法就是特定问题解决方法的步骤描述，在计算机中用指令来表达
5.1 举例
最经典的一个例子：1 + 2 + 3 ... + 100
如果我们按照顺序加下去，需要运算的次数就是99次加法运算，代码表达：
int sum = 0;
for (int i = 1; i <= 100; i++) {
sum += i;
}
但是，我们可以发现1 + 100 = 101， 2 + 99 = 101 ...... 50 + 55 = 101
所以和为 50 * 101 = 5050，找到规律以后，只要做1次乘法运算，代码表达：
int sum = 50 * 101;
这就是两个不同的算法，可以看出，算法2效率明显高于算法1
5.2 特性
- 输入：零个或多个输入
- 输出：至少一个或多个输出
- 有穷性：指算法在执行有限的步骤后，自动结束而不会出现无限循环，并且每一个步骤在可接受的范围之内
- 确定性：算法的每一个步骤都具有确定的含义，不会出现二义性
- 可行性：算法的每一步都必须是可行的，也就是说，每一步都能够执行有限次数完成。
5.3 要求
设计算法主要追求如下两个方面
- 时间效率高（时间复杂度）
- 存储量低（空间复杂度）
6. 总结
- 数据结构和算法很重要，是内功。
- 程序设计 = 数据结构 + 算法
- 数据结构包括：逻辑结构和物理结构
- 逻辑结构包括：集合结构、线性结构、树形结构、图形结构
- 物理结构包括: 顺序存储结构和链式存储结构
- 算法就是特定问题解决方法的步骤描述
- 算法的考量主要使用时间复杂度和空间复杂度
参考资料：小甲鱼的数据结构..
