1.1 数据结构的基本概念

• 数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。==一个数据元素可由多个数据项组成。==

• 数据项：是构成数据元素的不可分割的最小单位。

• 组合项：一个数据项有多个属性来组成，我们称这样的数据项为组合项。

• 数据对象：具有==相同性质==的数据元素的集合，是数据的一个子集。

• 数据结构：相互之间存在的一种或多种特定==关系==的数据元素的集合。
• 线性数据结构
• 网状数据结构

• ==同样的数据元素，可组成不同的数据结构==

• ==不同的数据元素，可组成相同的数据结构==

1.2 数据结构的三要素

集合结构

• 除第一个都有唯一前驱

• 除最后一个都有唯一后继

树形结构

数据的运算

存储结构

• 顺序存储

• 链式存储

• 索引存储

• 散列存储

数据类型、抽象数据类型

1.3 算法的概念

算法：求解问题的步骤

算法的特性

• 有穷性：有穷时间能做完

• 确定性： 相同输入，输出相同。

• 可行性： 算法的操作都可以通过有限次的基本运算来实现。

• 输入： 一个算法有零个或多个输入。

• 输出： 一个算法有一个或多个输出。

“好”算法的性质

• 正确性

• 可读性

• 健壮性：对非法数据可以做出反应或处理

• 高效率和低存储量要求

1.4 时间复杂度 T(n)

如何计算

1. 找到一个基本操作（最深层循环）

2. 分析该基本操作的执行次数x与问题规模n的关系 x = f(n)

3. x 的数量级 O(x) 就是算法的时间复杂度 T(n)

常用技巧

• 加法规则

• 乘法规则

• 常对幂指阶

最好时间复杂度(一般不用)

1.5 空间复杂度 S(n)

普通程序

常用技巧

• 加法规则

• 乘法规则

• 常对幂指阶