这是计算机必修课，很搞脑子，但要让编程能力有质的飞跃，而不是简单调用各种现成API去实现各种功能，却不懂内部原理，就必须学习这门课，自己设计结构和算法。

一、基础知识

1. 数据结构是什么？

• 官方版回答：
  研究程序设计中的操作对象，以及它们之间的关系的学科。
• 简单版回答：
  数据结构就是关系，是数据元素之间的一种或多种特定关系的集合。

2. 算法是什么？

定义

算法是解决特定问题的步骤描述，表现为有限的指令序列，每条指令表示1个或多个操作。
对于给定问题，可以用多种算法解决，变幻无穷的，但我们要学习一些经典算法，把他们掌握并灵活运用；一个算法也不能作为通解解决多个问题。

算法是程序的灵魂。

算法的五个特征

• 输入
  0或多个输入
• 输出
  至少一个输出，返回运算结果
• 有穷性
  有限步骤后自动结束，
• 确定性
  每个步骤都有确定含义，被精确定义，不允许二义性
  一定条件下，算法只有一条执行路径，比如相同输入必须有相同输出结果
• 可行性
  每一步都可以通过有限次数完成

算法设计的要求

• 正确性
  算法程序没有语法错误；对于合法输入能产生满足要求的输出；对于非法输入能产生满足规格的说明；对于故意刁难的测试输入有满足要求的输出结果。

• 可读性
  设计要便于阅读和理解，交流。写代码也是这样，除了正确执行以外，还要便于他人阅读和自己日后阅读修改。

• 健壮性
  输入不合法时，算法也能做出相应处理，而非产生异常，崩溃或不正确的结果。

• 时间效率高和存储量低

下图来源于小甲鱼的数据结构与算法视频课程截图（高斯算法）：

第一个for语句实现的算法需要计算n次，高斯算法却只需要1次，和n完全没关系。

3. 数据结构和算法为什么要一起学？

二者关系类似于一辈子的好基友，总是要结合在一起。
数据结构就那么几种，单纯讲很快就看完了，但仍然不明白他们有什么用，结合各种算法才能展示出这些数据结构的厉害之处。

以前程序员实际上主要是女孩的职业，就像缝纫一样。

二、数据结构分为逻辑结构和物理结构

1. 逻辑结构

数据对象中，数据元素之间的相互关系，是我们关注的重点。

四大逻辑结构：

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

2. 物理结构

逻辑结构在计算机中的存储形式（一般指内存，不是硬盘），不太关注。
U盘，硬盘，光盘等外部存储器

两种物理结构：

• 顺序存储结构
  把数据元素存放在地址连续的存储单元，数据元素之间的逻辑关系和物理关系一致
  像排队一样
  数组结构就采用顺序存储结构。数组结构是一个最基础的结构，几乎每门编程语言都有这个结构
• 链式存储结构
  数据元素存放在物理上的任意位置，不需要必须挨着放，可以挨着也可以不挨着，所以数据元素之间的逻辑关系需要用一个指针来实现，每个元素除了存放内容，还要存放下一个元素的指针，多费一点空间。
  像银行排号，有了编号（地址）后，人可以随意走动
  相比顺序存储结构，要复杂得多，也灵活得多

三、程序=数据结构+算法