数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

数据结构的基本概念

数据

数据是对客观事物的符号表示

在计算机科学中是指所有能输入到计算机中并且被计算机程序处理的符号的总称

例如，整数、实数和字符串是数据

数据元素

数据元素是数据的基本单位，是数据结构这门课讨论的最小单位

在计算机程序中通常将其作为一个整体进行考虑和处理

有时，一个数据元素可由若干数据项组成

例如，一本书的书目信息为一个数据元素，而书目信息的每一项（如书名、作者名等）为一个数据项

数据对象

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

例如，大写字母就是一个数据对象，大写字母数据对象是集合{'A'，'B'，...，'Z'}

数据结构

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

数据结构包含三方面的内容：

逻辑结构
存储结构
对数据的运算

数据的逻辑结构

数据的逻辑结构是对数据之间关系的描述，它与数据的存储结构无关，同一种逻辑结构可以有多种存储结构。归纳起来数据的逻辑结构主要有以下两大类：

线性结构：简单地说，线性结构是一个数据元素的有序（次序）集合。它有以下4个基本特征：
1. 集合中必存在唯一的一个"第一个元素"
2. 集合中必存在唯一的一个"最后一个元素"
3. 除最后一个元素之外，其他数据元素均有唯一的"后继"
4. 除第一个元素之外，其他数据元素均有唯一的"前驱"
非线性结构：与线性结构不同，非线性结构中的结点存在着一对多的关系，它又可以细分为树形结构和图形结构。

数据的物理结构

数据的物理结构又称为存储结构，是数据的逻辑结构在计算中的表示。它包括数据元素的表示和关系的表示。

当数据元素是由若干数据项构成的时候，数据项的表示称为数据域。

例如，一个链表结点，结点包含值域和指针域，这里结点可以看作一个数据元素，其中的值域和指针域都是这个数据元素的数据域

数据结构中有以下4种常用的存储方法

顺序存储方法：把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的领接关系来体现
链式存储方法：结点间的逻辑关系是由附加的指针字段表示
索引存储方法：存储结点信息时建立存储结点信息和附加的索引表来标识结点的地址，一般形式是<关键字，地址>
散列存储方法：根据结点的关键字通过散列函数直接计算出该结点的存储地址

算法

由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照要求设计好的有限的确切的计算序列

特性

有穷性：一个算法必须保证执行有限步骤之后结束
确定性：算法的每一个步骤必须有确定的定义
输入：一个算法有0个或多个输入
输出：一个算法有一个或多个输出
可行性：算法中的所有操作都必须通过已经实现的基本操作进行运算，并且在有限次内实现

设计目标

正确性：算法能正确执行预先规定的功能和性能要求
可读性：算法易于人的理解
健壮性：算法能够对不合理的数据进行检查
高效率与低储蓄量要求：对于同一个问题如果有多种算法可以求解，执行时间短的算法效率高。算法执行过程中所需要的最大存储空间越少越好

时间复杂度

将算法中基本操作的执行次数作为算法时间复杂度的度量

时间复杂度的大小如下：

O(1) \le O(log_2n) \le O(n) \le O(nlog_2n) \le O(n^2) \le O(n^3) \le O(n^k) \le O(2^n)

计算时间复杂度的操作：

找基本操作：多数情况下取最深层循环内的语句所描述的操作作为基本操作
确定规模：由循环条件i < n可知，循环执行的次数（基本操作执行的次数）和参数n有关，因此参数n就是我们所说的规模n
计算出n的函数f(n)

空间复杂度

算法的空间复杂度指算法在运行时所需存储空间的度量，主要考虑在算法运行过程中临时占用的存储空间大小