数据结构笔记1-概论

请注意：本文编写于 2020-10-08，其中某些信息可能已经失去时效性。

基本概念

数据

数据是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符合的集合。

数据大致可分为两类，一类是数值性数据，包括整数、浮点数、复数、双精度数等，主要用于工程和科学计算，以及商业事务处理；另一类是非数值性数据，主要包括字符和字符串，以及文字、图形、图像、语音等数据。

数据元素

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可以有若干个数据项组成，数据项是数据元素的不可分割的最小单位。例如：学生记录作为一个数据元素，它由学号、姓名、性别等数据项组成。

数据对象

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

数据类型

数据类型是一个值的集合和定义在此集合上一组操作的总称。

1. 原子类型：其值不可在分割的数据类型；
2. 结构类型：其值可以在分割成若干成分的数据类型；
3. 抽象数据类型：抽象数据组织和与之相关的操作。

抽象数据类型（ADT: Abstract Data Type）

一个数学模型以及定义在该模型上的一组操作。

抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。通常用数据对象（D)、 数据关系（S)、基本操作集（P)这样的三元组来表示抽象数据类型。

数据结构

数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所釆用的存储结构。

数据结构是由某一数据元素的集合和该集合中数据元素之间的关系组成的。

Data_Structure = {D, R}

D 是某一数据元素的集合，R 是该集合中所有数据元素之间的关系的有限集合。

有关数据结构的讨论主要涉及数据元素之间的关系，不涉及数据元素本身的内容。

数据的逻辑结构

数据的逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，与数据的存储无关。

逻辑结构的第一种分类方式

依据元素之间关系的不同，数据的逻辑结构分为两大类：线性结构和非线性结构。

逻辑结构的第二种分类方式

线性结构：数据元素之间存在一对一的关系
树形结构：数据元素之间存在一对多的关系
图形结构：数据元素之间存在多对多的关系
集合结构：数据元素属于同一个集合

数据的存储结构

数据的存储结构是指数据结构在计算机中的具体表示（又称映像），也成物理结构。包括数据元素的表示和数据元素间关系的表示。数据的存储结构是数据的逻辑结构用计算机语言实现的。它依赖于计算机语言。主要有如下四种结构：

1. 顺序存储结构：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里，元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
2. 链式存储结构：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针表示元素之间的逻辑关系。其优点是不会出现碎片现象，充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，并且只能实现顺序存取。
3. 索引存储结构：在存储元素信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址）。其优点是检索速度快；缺点是增加了附加的索引表，会占用较多的存储空间。另外，在增加和删除数据时要修改索引表，因而会花费较多的时间。
4. 散列存储结构：根据元素的关键字直接计算出该元素的存储地址，又称为Hash存储。其优点是检索、增加和删除结点的操作都很快；缺点是如果散列函数不好可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

数据的运算

施加再数据上的运算包括运算的定义和实现。运算的定义时针对逻辑结构的，之处运算的功能；运算的实现是针对存储结构的，之处运算的具体操作步骤。

算法

算法的基本概念

算法（algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

算法的特性

1. 有穷性：总是（对任何合法的输入值）在执行又穷步之后结束，且每一步都可在有穷时间内完成
2. 确定性：每一条指令必须有确切的含义，读者理解时不会产生二义性。即对于相同的输入只能得出相同的输出（幂等性？）
3. 可行性：算法中描述的操作都是已经实现的基本操作执行有限次来实现的
4. 输入：有零个或多个输入
5. 输出：有一个或多个输出

算法的性能标准

1. 正确性：正确的执行预定的功能和性能要求
2. 可读性
3. 健壮性：输入非法数据时也能适当的做出反应进行处理。
4. 效率和低存储量需求

算法效率的度量

算法效率的度量可分为事前估计和后期测试。

时间复杂度

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记作 T(n)，它是该算法问题规模 n 的函数，时间复杂度主要分析 T(n) 的数量级。算法中的基本运算（最深层循环内的语句）的频度与 T(n) 同数量级，所以通常釆用算法中基本运算的频度 f(n) 来分析算法的时间复杂度。因此，算法的时间复杂度也记为：
T(n)=O(f(n))

上式中 O 的含义是 T(n) 的数量级，其严格的数学定义是：若 T(n) 和 f(n) 是定义在正整数集合上的两个函数，则存在正常数 C 和 n_0，使得当 n >= n_0 时，都满足 0 <= T(n) <= C * f(n)。

注意：取 f(n) 中随 n 增长最快的项将其系数置为 1 作为时间复杂度的度量。例如，fi(n) = a * n^3 + b * n^2 + c * n，则其时间复杂度为 O(n^3)。

算法的时间复杂度不仅依赖于问题的规模 n，也取决于待输入数据的性质（如输入数据元素的初始状态）。

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。

在分析一个程序的时间复杂性时，有以下两条规则：

1. 加法规则：T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
2. 乘法规则：T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O( f(n) * g(n) )

常见的渐近时间复杂度有：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

空间复杂度

算法的空间复杂度 S(n)，定义为该算法所耗费的存储空间，它是问题规模 n 的函数。渐近空间复杂度也常简称为空间复杂度，记作 S(n)=O(g(n))。

一个上机程序除了需要存储空间来存放本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间，若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。

算法原地工作是指算法所需辅助空间是常量，即 O(1)。

参考

1. 数据结构C语言版：经典数据结构与算法分析教程
2. 知乎-码匠：数据结构与算法是什么？