数据结构概述
基本概念
数据，数据元素，数据对象
数据是客观事物的符号表示。数据元素是数据的基本单位，一个数据元素又可以由若干个数据项组成。包括两种：初等项不可分割；组合项，它又由若干个数据项组成。
数据对象是性质相同的数据元素的集合，是数据集合的一个子集。数据元素则是对象集合中的数据成员。
数据结构
数据元素之间存在一种或多种特定的关系，这种关系称为结构。
Data Structure = (D, R)
D为数据元素的有限集，R为数据对象中所有数据元素之间关系的有限集。
一般表示
- 数据元素及数据元素之间的逻辑关系，也称为数据的逻辑结构；
- 数据元素及数据元素之间的关系在计算机中的存储表示，也称为数据的存储结构或物理结构；
- 数据的运算，即对数据施加的操作。
数据结构分类
对于一个数据结构而言，每一个数据元素可以称为一个结点，数据结构中所包含的数据元素之间的关系就是结点之间的关系。
比如对关系<k, k'>，称k'是k的后继，k是k'的前驱，k和k'互为相邻结点。没有后继称为终端结点，没有前驱称为开始结点。
- 线性结构：一个结点最多只有一个前驱与后继。
- 非线性结构，树：一个结点最多只有一个前驱，而可以有多个后继。
- 非线性结构，图；对结点的前驱与后继数量不做限制。
存储方法：
- 顺序存储：逻辑上相邻的结点存储在物理位置相邻的存储单元里。通常用数据描述
- 链接存储：结点之间的逻辑关系由附加的指针表示。
- 索引存储：在建立存储结点数据的同时还，建立附加的索引表。
- 散列存储：根据结点的关键字计算出该结点的存储地址，然后按存储地址存放该关键字对应的数据元素。
数据类型
基本类型与组合类型
抽象数据类型
数据抽象是一种对数据和操作数据算法的抽象。数据抽象包括模块化和信息隐蔽两种抽象。
抽象数据类型(Abstract Data Type, ADT)是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及在逻辑结构上定义的操作。可用如下形式描述。
ADT ADT_NAME
{
Data: /*数据说明*/
/*数据元素之间逻辑关系的描述*/
Operations: /*操作说明*/
Operation1
Input: /*对输入数据的说明*/
preconditions: /*执行操作前系统应该满足的状态*/
Process: /*对数据执行的操作*/
Output: /*对返回数据的说明*/
Postconditions: /*执行操作后系统的状态*/
Operation2
...
}/*ADT*/
算法和算法分析
算法概念
通常人们将算法定义为一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算系列。算法应该具有以下特性：
- 输入
- 输出
- 确定性
- 有穷性
- 可靠性
把一个问题的功能需求转变为一个算法，使用的方法是自顶向下，逐步求精的结构批程序设计方法。
算法分析
- 正确性
- 可读性
- 健壮性
- 时间效率和存储占用量。
用O表示复杂度，O定义：若T(n)和f(n)是定义在正整数集合上的两个函数，则$T(n)=O(f(n))$表示存在正的常数C和n0使得当$n \ge n_0$时都满足$0\le T(n) \le C \times f(n)$
(渐近)时间复杂度由$T(n) = O(f(n))$表示，而空间复杂度由$ S(n) = O(f(n))$ 表示
一般讨论最坏时间复杂度与最好时间复杂度