基本概念和术语
数据
数据-> 多个数据元素 -> 多个数据项
数据对象 是 性质相同的数据元素的集合
结构
数据元素相互之间的关系成为结构
- 集合
- 线性结构
- 树形结构
- 图状结构
数据结构是一个二元组 定义形式为 Data_Structure = ( D, S ), 其中D是元素有限集，S 是D上的关系有限集。
逻辑结构
对操作对象的数学描述，即从操作对象抽象出来的数学模型称为逻辑结构。
一般来说，数据结构代指逻辑结构
物理结构
数据结构在计算机的表示（又称映像）称为物理结构，又叫做存储结构。用由若干个位组合起来形成的一个位串表示一个数据元素。这个位串称为元素，也叫做结点。
当数据元素由多个数据项组成时，位串中对应于各个数据项的子位串称为数据域。
数据元素之间关系的表示方法
- 顺序映像
- 非顺序映像
由此得到两种不同的存储结构：顺序存储结构 和 链式存储结构
顺序映像
借助元素在存储器中的相对位置来表示元素之间的逻辑关系
非顺序映像
借助指针
虚拟存储结构
用一维数组描述顺序存储结构，用指针描述链式存储结构
任何一个算法的设计取决于选定的逻辑结构
算法的实现则依赖于采用的存储结构
数据类型
int a
数据类型决定取的字节数，变量名决定起始位置
按“值”的特性不同，数据类型可分为两类
- 非结构的原子类型
- 结构类型
原子类型
原子类型的值不可分解，例如基本类型（整型、实型、字符型和枚举型）、指针类型和空类型。
结构类型
结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且他的成分可以是非结构的，也可以是结构的。
某种意义上，数据结构（逻辑结构）可以看成是一组具有相同结构的值
结构类型可以看成由一种数据结构和定义在其上的一组操作组成
抽象数据类型（Abstract Data Type, ADT）
指一个数学模型以及定义在其上的一组操作，与数据类型相似。“抽象”的意义在于数据类型的数学抽象特性
抽象数据类型可细分为三种类型：
- 原子类型
不可分解。一般来说，此类型较少，因为原有固有类型足以满足需求。但有时也有必要定义新的原子数据类型，例如数位为100的整数。- 固定聚合类型
其值由确定数目的成分按某种结构组成，例如复数是由两个实数依确定次序关系构成。- 可变聚合类型
与固定聚合类型相比，其值的数目不确定。显然后两种类型统称结构类型
抽象数据类型的形式定义
抽象数据类型用三元组表示 ADT = (D, S, P),其中D是数据对象，S是D上的关系集，P是对D的基本操作集。
采用如下格式定义抽象数据类型：
ADT抽象数据类型名{
数据对象:(数据对象的定义)
数据关系:(数据关系的定义)
基本操作:(基本操作的定义)
}ADT抽象数据类型名
其中，数据对象和数据关系的定义用伪代码描述，基本操作的定义格式为
基本操作名(参数表)
初始条件:<初始条件描述>
操作结果:<操作结果描述>
基本操作有两种参数，形参和引用，引用参数以&打头。
初始条件描述了操作执行之前数据结构和参数应满足的条件，若不满足则操作失败并返回出错信息。
操作结果说明操作完成后，数据结构的变化状况和应返回的结果。
- 抽象类型三元组的定义
ADT Triplet{ 数据对象:D = {e1,e2,e3|e1,e2,e3∈（定义了关系运算符的某个集合）} 数据关系:R1 = {<e1,e2>,<e2,e3>} 基本操作: InitTriplet(&T, v1, v2, v3) 操作结果：构造了三元组T，元素e1, e2, e3分别被赋以参数v1, v2, v3的值 Get(T, i, &e) 初始条件：三元组T已经存在, 1≤i≤3 操作结果：用e返回T的第i个元素的值 Put(&T, i ,e) 初始条件：三元组T已经存在, 1≤i≤3 操作结果：改变T的第i个元素的值为e ...... }ADT Triplet
算法和算法分析
- 算法的五个特性
- 有穷性
- 确定性：算法指令具有明确的含义，阅读时不会出现二义性，且算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出
- 可行性
- 输入
- 输出
算法效率的度量
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作 T(n) = O(f(n))，称作时间复杂度。多数情况下，问题的基本操作指最深层循环内的语句中的原操作。
语句的频度
- {++x; s = 0; }
- for (i=1;i<=n; ++i) {++x; s += x;}
- for (j=1; j<=n; ++j)
for (k=1; k<=n; ++k) {++x; s+=x;}
以上x自增一的频度分别为1、n和n^2，他们的时间复杂度分别为O(1)、O(n)和O(n²)、分别称为常量阶，线性阶和平方阶。类似的，还有对数阶O(log n)、多项式阶O(n^k)和指数阶O(2^n)。
