数据结构学习笔记（1）
教材选择：《数据结构》 严蔚敏 清华大学
本次主要内容：数据结构中的基本概念；算法及其量度。
一．基本概念：
1． 数据：所有能被输入到计算机中，且被计算机处理的符号的集合。
2． 数据元素：数据中的一个“个体”，数据结构中讨论的基本单位，不是最小单位。
3． 数据项：数据结构中讨论的最小单位。数据元素是数据项的集合。
4． 数据结构：带结构的数据元素的集合。结构指数据之间存在的约束关系。
5． 数据的逻辑结构：可分为四类：线形结构；树形结构；图状结构；集合结构。
6． 关系的映象方法（表示<x,y>的方法）：
a.
顺序映象：以存储位置的相邻表示后继关系，y的存储位置和x的存储位置之间差一个常量C，而C是一个隐含值，整个存储结构中只含数据元素本身的信息。
b.
链式映象：以附加信息（指针）表示后继关系，需要用一个和x在一起的附加信息指示y的存储位置。
7．抽象数据类型（ADT）：是指一个数学模型以及定义在此数学模型上的一组操作。具有两个重要的特征：数据抽象，数据封装。抽象数据类型可用（D，S，P）三元组表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。
ADT抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
} ADT抽象数据类型名
其中，数据对象和数据关系的定义用伪码表示，基本操作的定义格式为：
基本操作名（参数表）
初始条件：〈初始条件描述〉
操作结果：<操作结果描述>
二．算法及其量度：
1． 算法：为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足5个特征：有穷性；确定性；可行性；有输入；有输出。
2． 算法设计的原则：正确性；可读性；健壮性；高效率与低存储量需求。
3． 衡量算法效率的方法：
a.
事后统计法：即运行程序后，检查其运行的时间。
b.
事前分析估算法：在程序运行前估算程序运行的时间。一个特定算法的“运行工作量”的大小，只依赖问题的规模（用整数量n表示），或者说，它是问题规模的函数。
4． 时间复杂度：随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记做T(n) = O(f(n))，称T(n)为算法的（渐进）时间复杂度。
5． 如何估算时间复杂度：
算法 = 控制结构+原操作（固有数据类型的操作），算法的执行时间 = ∑原操作(i)的执行次数*原操作(i)的执行时间，算法的执行时间与原操作执行次数之和成正比。
从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。
例一：矩阵相乘
for( i = 1; I <= n; ++I)
for(j = 1; j<=n; ++j){
c[I,j]=0;
for(k=1;k<=n;++k)
c[I,j] += a[I,k] * b[k,j];
}
基本操作：乘法操作
时间复杂度：O（
n * n * n）
例二：选择排序
void select_sort(int a[], int
n)
{
for(i=0; i<n-1; ++i){
j=i;
for(k=i+1; k<n; ++k)
if(a[k] < a[j])
j=k;
if(j!=i)
a[j] <---> a[i]
}
}
基本操作：比较（数据元素）操作
时间复杂度：O（
n(n-1)/2）
6. 算法的空间复杂度：随着问题规模n的增大，算法运行所需存贮量的增长率与g(n)的增长率相同。S(n)=O(g(n))
