一、数据与数据结构
数据：所有能被输入到计算机中，且能被计算机处理的所有符号的集合的对象的总称，是计算机处理的信息的某种特定的符号表示形式。
数据元素：数据中的一个“个体”，数据元素师数据结构中讨论的基本单位，但不是最小单位。
数据项：数据结构中讨论的最小单位，数据元素师数据项的集合
例如：运动员（数据元素）
姓名俱乐部出生日期参加日期职务业绩 （数据项）
数据结构
带结构的数据元素的集合
例如：一个12位十进制书可以用三个4位的十进制数表示
3210,7689,9021->a1(3210),a2(7689),a3(9021)
a1、a2、a3之间存在“次序”关系，次序颠倒就不等了。
又例，2行3列的二维数组{a1,a2,a3,a4,a5,a6}
a1a2a3a4a5a6 行的次序关系：
row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}
列的次序关系：
col={<a1,a4>,<a2,a5>,<a3,a6>}
数据的逻辑结构可归结为以下四类：
线性结构
树形结构
图状结构
集合结构
数据结构的形式定义为：
数据结构式一个二元组
Data_Structures = (D,S)，
其中：D是数据元素的有限集，S是D上关系的有限集。
数据的存储结构：逻辑结构在存储器中的映象
数据元素的映象方法：
用二进制位（bit）的位串表示数据元素
关系集合的映象方法：（表示<x,y>的方法）
顺序映象：以存储位置的相邻表示后继关系（y的存储位置和x的存储位置之间差一个常量C，而C是一个隐含值，整个存储结构中只含数据元素本身的信息）
链式映象：以附加信息（指针）表示后继关系
需要用一个和x在一期的附加信息指示y的存储位置。
数据类型
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
抽象数据类型（Abstract Data Type 简称ADT）
是指一个数学模型以及定义在此数学模型上的一组操作。
ADT有两个重要特征：
数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即为界使用他的方法）
数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节
抽象数据类型的描述方法：熟悉那个数据类型可用（D,S,P）三元组表示。其中D是数据对象，S是D上的关系集，P是对D的基本操作集。
抽象数据类型的表示和实现：抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现。
二、算法和算法的衡量
算法
算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特征：
1，有穷性：算法中每个步骤都能在有限时间内完成；
2，确定性：每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且任何条件下，算法都只有一条执行路径；
3，可行性：算法中的所有操作必须足够基本，都可以通过已经实现的基本操作运算有限次实现；
4，有输入
5，有输出
设计原则：
正确性、可读性、健壮性、高效率与低存储量需求
算法效率的衡量方法和准则：
事后统计法
事前分析估算法（选用策略、问题规模、编写程序的语言、编译程序产生的机器代码的质量、计算机执行指令的速度）
随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作
T(n) = O(f(n))
称T(n)为算法的时间复杂度
算法 = 控制结构 + 原操作（固有数据类型的操作）
算法的执行时间 = ∑原操作(i)的执行次数 x 原操作(i)的执行时间（算法的执行时间与原操作的执行次数之和成正比）
随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同，怎可记作
S(n) = O(g(n))
称S(n)位算法的空间复杂度。（输入数据所占空间，程序本身所占空间，辅助变量所占空间）
