什么是数据结构？

其实每种不同的教材都有自己的定义，可是没有一个公共一致认同的定义，一般来说，用计算机解决一个具体的问题时，首先要从具体问题抽象出一个数学模型，然后为这个模型设计出一个算法，并实现这个算法。

然而，更多的程序是属于非数值计算的，因此，与其说他们依赖算法解决问题，不如说更依赖类似表、树、图之类的数据结构。

先说几个术语：

数据：指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理

数据对象：是性质相同的数据元素的集合，是数据的一个子集

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合

总之，数据元素相互之间的关系称之为结构。

因此，可以认为，数据结构讲究的是数据元素之间的关系问题，无论是存储的位置关系，还是计算的数学关系等等。

4种基本结构

根据相对关系，我们有了4种基本结构

1.集合：任何两个元素之间只有属于相同集合这一个特征（并查集）

2.线性结构：数据元素之间存在一个对一个的关系（线性表）

3.树形关系：数据元素之间存在一个对多个的关系

4.网(图)状关系：结构中的数据元素之间存在多个对多个的关系。

由于数据要在计算机中处理，所以不仅仅要考虑数据本身的数学性质，还要考虑数据的存储结构。

因此，数据结构又可以分为：

逻辑结构：结构定义中的“关系”描述的是数据元素之间的逻辑关系（可以抽象成模型的）

物理（存储）结构：包括数据元素的表示和关系的表示（可以被计算机认识的）

因为数据元素之间的关系在计算机中有两种不同的表示方法（根据数据元素之间存储位置的关系）：顺序映像和非顺序映像，并由此得掉两种不同的数据存储结构：顺序存储结构（数组）和链式存储结构（链表）。

顺序映像的特点是借助元素在存储器中的相对位置来表示元素之间的逻辑关系（首地址和偏移量）

非顺序映像的特点是借助指示元素存储地址的指针（类似链表中的next）表示数据元素之间的逻辑关系

任何一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构。

数据类型：规定了在程序执行期间变量或者表达式所由的可能取值范围以及在这些值上允许进行的操作。因此，数据类型是值的集合和定义在这个集合上的一组操作的总称。（有点像C++里的类）

抽象数据类型(ADT)

那么**抽象数据类型(ADT)**是指一个数学模型以及定义在该模型上的一组操作。（说白了，就是一个用伪代码些的C++类，可以方便转化成各种面向对象的高级语言代码）。

为什么要用抽象数据类型呢？一个软件系统的框架应该建立值数据之上（面向对象），来提高软件的复用性，因此不能把中心放在对数据的操作上（面向过程），有了ADT之后，以数据为核心，整个程序抽象的只剩下：怎么保存数据？对数据进行什么操作？这两个问题，那么在二次开发中，可以不用对原有软件进行大刀阔斧的改动。

ADT的表示方法：

ADT抽象类型名{
    数据对象：
    数据关系：
    基本操作：
}ADT的抽象数据类型名

基本操作的表示：

基本操作（参数表）
    初始化条件
    操作结果

基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头（和C++一样）

初始条件描述参数应该满足于什么条件，如果不满足则操作失败并返回错误信息

操作结果说明操作正常完成之后数据结构的变化状况和应返回的结果（若初始条件问空着省略之）。

如果组成数据结构的数据类型不同，则为多形数据类型

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

而设计一个算法的目标是：1.正确性（不对谈个J8）、2.可读性、3.健壮性（可以应对各种奇葩数据）、4.效率（时间复杂度）和低存储量需求（空间复杂度）。

算法效率的度量

1.事后统计法（受计算机本身硬件、软件环境影响严重）

2.事前分析法（相关因素：算法策略，问题规模，表达算法的语言，编译器转化成的机器代码的质量，机器执行指令的速度）。

因为算法是由控制结构（顺序，分支，循环）和原操作（固有数据的相关操作）构成的，则一套算法的时间取决于两者的综合效果。

一般来说，算法中基本操作重复执行的次数是问题规模决定的（比如n!，时间复杂度和n的大小有关），则

T（n） = O（f（n））；但是一般O（f（n））只考虑指数最大的一项。比如f(n) = n^3+n^2的时间复杂度为O(n^3)

一般算法的时间复杂度是考虑的最坏时间复杂度。

对于空间复杂度，除了需要的存储空间来寄存本身多用的指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。