1.什么是数据结构
? ?概括说，数据结构是一门讨论“描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中如何表示实现”的学科。
2.基本概念和术语
? ?数据（data）：是对信息的一种符号表示。在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称。
? ?数据元素（data element）：是数据的基本单位，在程序中通常作为一个整体进行考虑和处理。
? ? 一个数据元素可由若干个数据项组成，数据项是数据的不可分割的最小单位。
? ? 数据结构（data structure）：有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。
? ? 数据结构是相互之间存在某种逻辑关系的数据元素的集合。
从关系或结构分，数据结构可归结为四类：线性结构? 树形结构? 图形结构? 集合结构
? ? 数据结构的形式化描述：
? ? 数据结构是一个二元组
? ? data_structures=（d，s）? ? ? ?d是数据元素的有限集，s是d上关系的有限集。
? ? 数据结构包括“逻辑结构”和物理结构两个方面：
? ? 逻辑结构，是对数据元素之间的逻辑关系的描述，它可以应一个数据元素的集合和定义在此集合上的若干关系来表示；
? ? 物理结构（存储结构）是数据结构在计算机中的表示和实现。
? ? 数据的存储结构—逻辑结构在存储器中的映像：
数据元素的映像：
用二进制位的位串表示数据元素。
“关系”映像方式：
顺序映像：以相对的存储位置表示后继关系。
非顺序映像：链式存储方式：
以附加信息（指针）表示后继关系。
索引存储方式：除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，兼有静态和动态特性。
散列存储方式：通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。
数据类型：
在一种程序设计语言中，变量所具有的数据种类。
数据对象：
某种数据类型元素的集合。
数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。
逻辑结构的特别注意：
?逻辑结构与数据元素本身的形式、内容无关。
?逻辑结构与数据元素的相对位置无关。
?逻辑结构与所含数据元素的个数无关。
?逻辑结构与数据的存储无关，它是独立于计算机的。
一般的，一种数据的逻辑结构根据需要可用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。
3.算法和算法分析：
算法：是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。
特性：有穷性 确定性 可行性 输入 输出
算法与程序
一个程序不一定满足有穷性，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定实现。一个算法若用程序设计语言来描述，则它就是一个程序。
算法和数据结构
是相辅相成的，解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。
算法设计要求：
（1）正确性（correctness)
（2）可读性（readability）
（3）健壮性（robustness）
（4）效率与存储量需求：
效率指的是算法执行的时间
存储
量需求指算法执行过程中所需要的最大存储空间。
算法效率的衡量方法和准则
事后统计法
缺点：1.必须执行程序；
? ? ? 2.其他因素掩盖算法本质。
事前分析估算法
和算法执行时间相关的因素
1.算法选用的策略
2.问题的规模
3.编写程序的语言
4.编译程序产生的机器代码质量
5.计算机执行命令的速度
算法效率的衡量方法和准则
一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数n表示），或者说，它是问题规模的函数
设随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：
t(n)=o(f(n))
称t(n)为算法的（渐近）时间复杂度 。
如何估算算法时间复杂度？
算法 = 控制结构 + 原操作
(固有数据类型的操作)
算法的执行时间 = 原操作(i)的执行次数*原操作(i)的执行时间
算法的执行时间与原操作执行次数之后成正比
从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。
频度：是指该语句重复执行的次数
常数阶：
例1：{++x;s=0;}
将x自增看成是基本操作，则语句频度为1，即时间复杂度为o(1)。
如果将s=0也看成是基本操作，则语句频度为2，其时间复杂度仍为o(1),即常量阶。
线性阶：
例2：
for(i=1;i<=n;++i)
{++x;s+=x;}
语句频度为：2n
其时间复杂度为：o(n)，即时间复杂度为线性阶。
对数阶：
例3：
void f(int n){
int x=1;
while(x<n)
x=2*x;
}
分析：基本运算是语句x=2*x,
设其执行时间为t(n),则有2^t(n)<=n,
即t(n<log?n)=o(log?n)。
解答：其时间复杂度为：o(log?n),即时间复杂度为对数阶。
平方阶：
例4：
for(i=1;i<n;++i)
for(j=i;j<=n;++j)
{++x;s+=x;}
语句频度为：2n2
其时间复杂度为：o(n2),即时间复杂度为平方阶。
立方阶：
例5：
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];
}
由于是一个三重循环，每个循环从1到n，则总次数为n*n*n=n3
时间复杂度为t(n)=o(n3)
定理：
若a(n)=a_m n^m+a_(m-1) n^(m-1)+?+a_(1^n )+a_0? ? ? ? ?（见图1）