数据结构（一）:数据结构的基本概念和算法的时间和空间复杂度 数据结构讨论的范畴 相关概念
计算机技术的两大支柱：1是数据结构，2是算法。在某种程度上讲，程序设计等同于数据结构+算法。
程序设计是为计算机设计一组指令集，算法是解决问题的策略，数据结构是模型。
问题包括：数值计算，解方程，
非数值计算的问题：计算机对弈，棋盘，棋子如何表示（模型），规则策略（算法）
我们讨论的是：实体的数学模型（非数值计算）及其上的操作如何在计算机上表示和实现。
相关概念
数据(Data)：是信息的载体，能够被计算机识别、存储和加工处理的数值、字符等。
数据元素(Data Element)：是数据的基本单位。也称为元素、结点、顶点、记录。程序中作为一个整体来处理。
数据项(Data Item):有独立含义的数据最小单位，也称域(Field)
关键码（key）：起标识作用的数据项
数据对象(Data Object)：是具有相同特性的数据元素的集合，是数据的一个子集。
数据结构涉及的内容
1. 逻辑结构(Logical Structure)：数据元素之间的逻辑关系。
2. 存储结构(Storage Structure)：数据元素及其关系在计算机存储器内的表示
3. 施加在该数据结构上的操作
数据的逻辑结构
线性结构的逻辑特征：有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和直接后继。
非线性结构的逻辑特征：一个结点可能有0,1,或者多个直接前趋和直接后继。如：树形、图状或者网状、纯集合。
数据的存储结构
顺序存储方法：把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系由附加的指针字段表示。
索引存储方法：在存储结点信息的同时，还建立附加的索引表。
散列存储方法：根据结点的关键字直接计算出该结点的存储地址。
线性表是一种逻辑结构，若采用顺序方法的存储表示，则为顺序表；若采用链接方法的存储表示，则为链表；若采用散列方法的存储表示，则为散列表；若对线性表上的插入、删除运算限制在表的一端进行，则为栈；若对插入限制在表的一端进行，而删除限制在表的另一端进行，则为队列。
什么是算法？
算法：通过数据结构解决某一特定问题的具体步骤的描述，是有限长的操作序列。
算法特性：
--有输入：具有零个或多个输入的外界量。
--有输出：至少产生一个输出。
--可行性：所有操作可以通过已实现的基本操作运算有限次实现
--有穷性：操作步骤有限，且每个步骤能在有限时间完成
--确定性：每条操作的含义都必须明确，无二义性。
算法评价
评价一个算法的好坏一般从4个方面进行：
--正确性：是指算法是否正确；
--运行时间：执行算法所耗费的时间；
--占用空间：执行算法所耗费的存储空间；
--简单性：是指算法的易读性等。
算法性能分析与度量
算法的性能标准: 正确性，可使用性，可读性，效率，健壮性
算法的后期测试
--在算法中的某些部位插装时间函数 time( )
--测定算法完成某一功能所花费时间
算法的事前估计
--空间复杂度
--时间复杂度
空间复杂度度量:存储空间的固定部分--程序指令代码的空间，常数、简单变量等变量所占空间 和
可变部分--尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间
假定时间复杂性函数的时间单位为us
时间复杂度度量：编译时间和运行时间（独立于机器的软硬件、假设每条语句的时间是单位时间、语句的频度）
#define n 自然数
MATRIXMLT(A，B，C)
float A[n][n]，B[n][n]，C[n][n]；
{
int i，j，k；
(1) for ( i=0；i<n；i++) n
(2) for (j=0；j<n；j++) n^2
{
(3) C[i][j]=0； n^2
(4) for (k=0；k<n；k++) n^3
(5) C[i][j]= C[i][j]+A[i][k]*B[k][j] ； 2n^3
}
}/* MATRIXMLT */
该算法中所有语句的频度之和（即算法的时间耗费）为：
T(n)=n+n2+n2+n3+2n3=3n3 +2n2+n
时间复杂度相应的数量级(阶)按递增排列常数阶O(1)
对数阶O(log2n)
线性阶O(n)
线性对数阶O(nlog2n)
平方阶O(n2)
立方阶O(n3)
指数阶O(2n)
假定时间复杂性函数的时间单位为us