数据结构

一般用计算机解决问题，需经过以下几个步骤：首先要从具体问题抽象成一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进行测试、调整直至得到最终解答。

数据是对客观事物的符号表示。
数据元素是数据的基本单位，一个数据元素可由若干个数据项组成。
数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。通常有下列4类基本结构：集合、线性结构、树形结构、图状结构或网状结构。

数据结构的形式定义为：数据结构是一个二元组Data_Strucutre=(D,S)，其中D是数据元素的有限集，S是D上关系的有限集。而结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。

数据结构在计算机中的表示称为数据的物理结构，又称存储结构。在计算机中表示信息的最小单位是位(bit)。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。

顺序映象的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
非顺序映象的特点是借助指示元素存储地址的指针数据元素之间的逻辑关系。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称，如C中的整型变量，其值集为某个区间上的整数，定义在其上的操作为加、减、乘、除和取模等算术运算。高级程序语言中的数据类型可分为两类：一类是非结构的原子类型，另一类是结构类型。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作，其不再局限于处理器已定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型。和数据结构的形式定义相对应，抽象数据类型可用以下三元组表示：(D,S,P)，其中D是数据对象，S是D上的关系集，P是对D的基本操作集。

算法和算法分析

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。另外，算法还具有5个重要特性：有穷性、确定性、可行性、输入、输出。

算法设计的要求你：正确性、可读性、健壮性、效率与低存储量需求。

算法效率的度量：

(1)事后统计的方法
(2)事前分析估算的方法: 依据的算法选用何种策略、问题的规模(求100以内还是1000以内的素数)、书写程序的语言、编译程序所产生的机器代码的质量、机器执行指令的速度。
一般来说，认定一个特定算法“运行工作量”的大小，只依赖于问题的规模，即为问题规模的函数。算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作: T(n) = O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的时间复杂度。

常见的时间复杂度大小比较：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)。

算法的存储空间需求，类似算法的时间复杂度，我们以空间复杂度作为算法所需存储空间的量度，记作 S(n) = O(f(n))。若输入数据所占的空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间，否则应同时考虑输入本身所需空间。如果额外空间相对于输入数据量来说是常数，则称此算法为原地工作。