参考：https://www.bilibili.com/video/BV1b7411N798?p=7&vd_source=5989fd3e1c060952835417b0c71343ce

第一章 绪论

1.1 数据结构的基本概念

1.1.1 基本概念和术语

• 数据：信息的载体；
• 数据元素：数据的基本单位；
• 数据项：一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位；
• 数据对象：具有相同性质的数据元素的集合，是数据的一个子集；
• 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

数据类型：一个值的集合和定义在此集合上的一组操作的总称。

• 原子类型：其值不可再分，如bool类型、int类型。
• 结构类型：其值可以再分解成若干成分的数据类型，如struct类型。
• 抽象数据类型：抽象数据组织及与之相关的操作。

数据结构课程主要关注数据元素之间的关系，和对这些数据元素的操作。

1.1.2 数据结构三要素

1. 数据的逻辑结构

• 集合：结构中的数据元素除“同属于一个集合”外，没有其它关系
• 线性结构：结构中的数据元素是一对一的关系（第二章）
• 树形结构：一对多（第三、四章）
• 图（网）状结构：多对多（第五章）

2. 数据的运算

针对某种逻辑结构，结合实际需求，定义基本运算。

3. 数据的存储结构

• 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中；
• 链式存储：逻辑上相邻的元素在物理位置上可以不相邻；借助指示元素存储地址的指针来表示元素之间的逻辑关系；
• 索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）；
• 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希存储。

1.2 算法与算法评价

1.2.1 算法的基本概念

$$程序=数据结构+算法$$

算法是对特定问题求解步骤的一种描述。

算法的特性：

• 有穷性：步骤有穷，时间有穷
• 确定性：每条指令含义明确，对于相同输入有相同输出
• 可行性：算法描述的操作都可以通过基本运算执行有限次实现
• 输入：一个算法有0个或多个输入
• 输出：一个算法有1个或多个输出

“好”算法的特质：

• 正确性
• 可读性
• 健壮性
• 高效率与低存储量需求

1.2.2 算法效率的度量

1. 时间复杂度

2. 空间复杂度

算法原地工作是指算法所需的辅助空间为常量，即$O(1)$