1. 前言

对于一名有追求的程序猿来说，数据结构和算法是一门必修课，它是内功，内功的深厚直接决定了解决问题的能力和学习新技术的能力。

2. 定义

广义上：
数据结构就是数据的存放方式，就像图书馆中的书排列的规则。
算法就是操作数据的方式，就像如何从图书馆中找一本书的方法。

狭义上：
数组、链表、队列、栈、树、图就是数据结构
冒泡排序、堆排序、二分查找、Dijkstra就是算法

它们相辅相成，总结来说：

程序设计 = 数据结构 + 算法

3.意义

1. 写出高质量的代码， 程序在性能上有质的提升。
2. 提升逻辑思维能力，更容易看懂别人写的代码。
3. 助攻面试，进大厂。
4. 为转战AI，打下基础。

4. 数据结构

4.1 数据结构的分类

数据结构可分为：

1. 逻辑结构：指数据对象中数据元素之间的相互关系，也是我们研究的重点
2. 物理结构：数据的逻辑结构在计算机中的存储形式

4.2 逻辑结构

四大逻辑结构

1. 集合结构：集合结构中的元素除了同属于一个集合外，它们之间没有其他关系

   
   集合.png

2. 线性结构： 线性结构中的数据之间是一对一的关系

   
   线性.png

3. 树形结构：树形结构中的数据元素之间是一对多的层次关系

   
   树形.png

4. 图形结构： 图形结构的数据元素是多对多的关系

   
   图形.png

四种逻辑结构的对比如下：

序号	名称	元素之间的关系
1	集合结构	没有关系
2	线性结构	一对一
3	树形结构	一对多
4	图形结构	多对多

4.3 物理结构

物理结构其实就是研究如何将数据元素存储到计算机的存储器中，这里指的存储器是针对内存而言，像硬盘、软盘、光盘等外部存储设备通常是以文件的形式来描述的。

数据元素的存储结构形式有两种：顺序存储和链式存储

1. 顺序存储结构：是把元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。例如数组

   
   顺序存储.png

2. 链式存储结构： 把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

这个时候其存储单元的位置不能表达其逻辑关系，所以就需要指针来表示元素之间的逻辑关系 链式存储.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 特性

1. 输入：零个或多个输入
2. 输出：至少一个或多个输出
3. 有穷性：指算法在执行有限的步骤后，自动结束而不会出现无限循环，并且每一个步骤在可接受的范围之内
4. 确定性：算法的每一个步骤都具有确定的含义，不会出现二义性
5. 可行性：算法的每一步都必须是可行的，也就是说，每一步都能够执行有限次数完成。

5.3 要求

设计算法主要追求如下两个方面

1. 时间效率高（时间复杂度）
2. 存储量低（空间复杂度）

6. 总结

1. 数据结构和算法很重要，是内功。
2. 程序设计 = 数据结构 + 算法
3. 数据结构包括：逻辑结构和物理结构
4. 逻辑结构包括：集合结构、线性结构、树形结构、图形结构
5. 物理结构包括: 顺序存储结构和链式存储结构
6. 算法就是特定问题解决方法的步骤描述
7. 算法的考量主要使用时间复杂度和空间复杂度

参考资料：小甲鱼的数据结构..