共计 7678 个字符，预计需要花费 20 分钟才能阅读完成。
1 什么是数据结构
1.1 数据结构基本概念
数据(data) 是对客观事物的符号示意，在计算迷信中是指所有能输出到计算机中并被计算机程序解决的符号的总称问题。图像、声音等都能够通过编码从而纳入到数据的领域。
数据元素 (data element) 是数据的根本单位，在计算机中通过作为一个整体进行思考和解决。一个数据元素能够由若干个数据项(data item) 组成。
数据对象(data object) 是性质雷同的数据元素的汇合，是数据的一个子集。
数据结构(data structure) 是相互之间存在一种或多种特定关系的数据元素的汇合。从学科角度，数据结构是一门钻研非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
在任何问题中，数据元素都不是孤立存在的，而是在他们之间存在某种关系，这种数据元素之间的关系称为 构造(structure)。依据数据元素之间关系的不同个性，通常有以下 4 种根本构造：
- 汇合：构造中的数据元素除了同属一个汇合的关系外，无其余关系。
- 线性构造：构造中的数据元素之间存在一个对一个的关系。
- 树形构造：构造中的数据元素之间存在一个对多个的关系。
- 图状构造 或网状结构：构造中的数据元素之间存在多个对多个的关系。
1.2 数据结构的模式定义
数据结构的模式定义：
数据结构是一个二元组：
$$
Data\_ Structure = (D, S)
$$
其中，$D$ 是数据元素的汇合，$S$ 是 $D$ 上关系的无限集。
例如，复数是一种数据结构：
$$
Complex = (C, R)
$$
其中，C 是两个实数的汇合 {c1, c2}，R={P}，而 P 是定义在汇合 C 上的一张关系 {<c1, c2>}，其中有序偶 <c1, c2> 示意 c1 是复数的实部，c2 是复数的虚部。
构造定义中的“关系”形容的是数据元素之间的逻辑关系，因而又称为数据的 逻辑构造。
1.3 数据结构的计算机示意
数据结构在计算机中的示意 (又称映像) 称为数据的 物理构造 ，又称 存储构造 ，它包含数据元素的示意和关系的示意。计算机中示意信息的最小单位是二进制的 位(bit)，能够用若干个位组合起来造成一个位串示意一个数据元素 (如用 8 位二进制示意一个字符)，通常称这个位串为 元素 (element) 或结点 (node)。当数据元素由若干个数据项组成时，位串中对应于各个数据项的子位串称为 数据域(data field)。因而，元素或结点能够看做数据元素在计算机中的映射。
数据元素之间的关系在计算机中有两种不同的示意办法：
- 程序映像：借助元素在存储器中的绝对地位来示意元素之间的逻辑关系。
- 非程序映像：借助批示元素存储地址的指针示意元素之间的逻辑关系。
由此失去两种不同的存储构造：顺序存储构造 和链式存储构造。
留神：任何一个算法的设计取决于选定的数据 (逻辑) 构造，而算法的实现依赖于采纳的存储构造。
存储构造波及数据元素及其关系在存储器中的物理地位，从高级程序语言的角度，能够借用高级程序语言中提供的“数据类型”来形容它，例如，能够应用一维数组来形容顺序存储构造，用 C 语言提供的指针来形容联赛存储构造。
1.4 数据类型、抽象数据类型和多形数据类型
数据类型 (data type) 是一个值的汇合和定义在这个值集上的一组操作的总称，是一个和数据结构密切相关的概念，最早呈现在高级编程语言中，用来刻画(程序) 操作对象的个性。按“值”的不同个性，高级程序语言中的数据类型可分为两类：
- 原子型：非构造的，不可拆解的，如 C 语言中的根本类型(整型、实型、字符型、枚举类型)、指针类型和空类型。
- 构造类型：由若干个成分按某种构造组成，是可分解的，其成分能够是非构造的，也能够是构造的，如数组。
抽象数据类型(abstract data type，简称 ADT) 是指一个数学模型以及定义在该模型上的一组操作抽象数据类型的定义仍取决于它的一组逻辑个性，而与其在计算机外部如何示意和实现无关，无论其内部结构如何变动，只有它的数学个性不变，都不影响其内部应用。
抽象数据类型和数据类型实际上是一个概念，“形象”的意义在于数据类型的数学形象个性。另一方面，抽象数据类型的领域更广，它不再局限于各处理器中已定义并实现的数据类型(固有数据类型)，还包含用户在设计软件系统时本人定义的数据类型。
留神：一个软件系统的框架应建设的数据之上，而不是建设在操作之上。
一个含抽象数据类型的软件模块通常应蕴含定义、示意和实现 3 个局部。抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。若按其值的不同个性，可细分为 3 种类型：
- 原子类型(atomic data type)：属于该类型的变量的值不可合成，个别状况下已有的固有数据类型足以满足需要，较少用。
- 固定聚合类型(fixed-aggregate data type)：属于该类型的变量的值由确定数目的成分依照某种构造组成。如复数由连个实数依确定的秩序组成。
- 可变聚合类型(variable-aggregate data type)：和固定聚合类型比拟，形成可变聚合类型的值的成分数目不确定。例如长度可变的有序整数序列。
后两种类型统称为构造类型。
和数据结构的模式定义绝对应，抽象数据类型可用以下三元组示意：
$$
(D, S, P)
$$
其中，D 是数据对象，S 是 D 上的关系集，P 是对 D 的基本操作集。
往后的介绍默认应用上面的格局定义抽象数据类型：
ADT 抽象数据类型名 {
数据对象: < 数据对象的定义 >
数据关系: < 数据关系的定义 >
基本操作: < 基本操作的定义 >
} ADT 抽象数据类型名其中，数据对象和数据关系的定义用伪代码形容，基本操作的定义格局为：
基本操作名(参数表)
初始条件: < 初始条件形容 >
操作后果: < 操作后果形容 >基本操作有两种参数：
- 赋值参数：只为操作提供输出值。
- 援用参数：一
&结尾，除可提供输出值外，还将返回操作后果。
“初始条件”形容了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败并返回相应出错信息。“操作后果”阐明了操作失常实现之后数据结构的变动情况和应返回的后果。若初始条件为空，则省略。
上面定义一个抽象数据类型三元组：
ADT Triplet {数据对象: D = {e1, e2, e3 | e1, e2, e3 ∈ ElemSet}
数据关系: R1 = {<e1, e2>, <e2, e3>}
基本操作:
InitTriplet(&T, v1, v2, v3)
操作后果: 结构三元组 T，元素 v1，v2，v3 别离赋值给 e1，e2，e3
Get(T, i, &e)
初始条件: 三元组 T 已存在
操作后果: 用 e 返回 T 的第 i 元的值
Max(T, &e)
初始条件: 三元组 T 已存在
操作后果: 用 e 返回 T 的三个元素中的最大值
} ADT Triplet多形数据类型(polymorphic data type) 是指其值的成分不确定的数据类型。例如下面定义的抽象数据类型 Triplet，其元素 e1、e2、e3 能够是整数、字符或字符串，甚至是更简单地由多种成分组成(只有能进行关系运算即可)。无论其元素具备何种个性，元素之间的关系雷同，基本操作雷同。从抽象数据类型的角度看，具备雷同的形象个性，因而称为多形数据类型。显然，多形数据类型须要借助面向对象的程序设计语言来实现，这里默认应用类 C 语言作为形容工具，故只探讨含有确定成分的数据元素的状况，如下面例子中的 ElemSet。
2 抽象数据类型的示意与实现
抽象数据类型可通过固有数据类型来示意和实现。这里采纳类 C 语言作为描述语言，并进行了适当的裁减批改。简要阐明如下：
-
预约义常量和类型：
// 函数后果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVEFLOW -2 // Status 时函数类型，其值时函数后果状态代码 typedef int Status; - 数据结构的示意 (存储构造) 用类型定义
typedef形容，数据元素类型约定为 ElemType，由用户在应用该数据时自行定义。 -
基本操作的算法用以下模式的函数形容：
函数类型 函数名(函数参数表) { // 算法阐明 语句序列 } // 函数名除了函数参数须要阐明类型外，算法中应用的辅助变量能够不作变量申明，必要时对其作正文阐明。个别 a、b、c、d、e 等用作数据元素名，i、j、k、l、m、n 等用作整型变量名，q、p、r 等用作指针变量名。当函数返回值为函数后果状态代码时，函数定义用
Status类型名。除了值调用形式外，减少了 C++ 语言的援用调用的参数传递形式，在形参表列中，以&结尾的参数即为援用参数。 -
赋值语句有：
简略赋值 变量名 = 表达式; 串联赋值 变量名 1 = 变量名 2 = ... = 变量名 k = 表达式; 成组赋值 (变量名 1, ..., 变量名 k) = (表达式 1, ... , 表达式 k); 构造名 = 构造名; 构造名 = (值 1, ... , 值 k); 变量名[] = 表达式; 变量名[起始下标.. 终止下标] = 变量名[起始下标.. 终止下标]; 替换赋值 变量名 <-> 变量名; 条件赋值 变量名 = 条件表达式 ? 表达式 T : 表达式 F; -
抉择语句有：
条件语句 1 if(表达式) 语句; 条件语句 2 if(表达式) 语句; else 语句; 开关语句 1 switch(表达式) { case 值 1: 语句序列 1; break; ... case 值 n: 语句序列 n; break; default: 语句序列 n +1; } 开关语句 2 switch { case 条件 1: 语句序列 1; break; ... case 条件 n: 语句序列 n; break; default 语句序列 n +1; } -
循环语句有：
for 语句 for(赋值表达式序列; 条件; 批改表达式序列) 语句; while 语句 while(条件) 语句; do-while 语句 do {语句序列;} while(条件); -
完结语句有：
函数完结语句 return 表达式; return; case 完结语句 break; 异样解决语句 exit(异样代码); -
输入输出语句有：
输出语句 scanf([格局串], 变量 1, ..., 变量 n); 输入语句 printf([格局串], 表达式 1, ..., 表达式 n); -
正文：
单行正文 // 文字序列 -
根本函数有：
求最大值 max(表达式 1, ..., 表达式 n) 求最小值 min(表达式 1, ..., 表达式 n) 求绝对值 abs(表达式) 求有余整数值 floor(表达式) 求进位整数值 ceil(表达式) 断定文件完结 eof(文件变量) 或 eof 断定行完结 eoln(文件变量) 或 eoln -
逻辑运算约定：
与运算 && 或运算 ||
以抽象数据类型 Triplet 的示意和实现为例：
// 采纳动态分配的顺序存储构造
typedef ElemType * Triplet; // 由 InitTriplet 调配 3 个元素存储空间
// 基本操作的函数原型阐明
Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3);
// 操作后果：结构三元组 T，元素 v1，v2 和 v3 别离赋值给 e1，e2，e3
Status Get(Triplet T, int i, ElemType &e);
// 初始条件：三元组 T 已存在，1≤i≤3
// 操作后果：用 e 返回 T 的第 i 元的值
Status Max(Triplet T, ElemType &e)
// 初始条件：三元组 T 已存在
// 操作后果：用 e 返回 T 三个元素中的最大值
// 基本操作的实现
Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3) {
// 结构三元组 T
T = (ElemType *) malloc (3 * sizeof(ElemType)); // 调配 3 个元素的存储空间
if(!T) exit(OVERFLOW); // 调配存储空间失败
T[0] = v1; T[1] = v2; T[2] = v3;
return OK;
} // InitTriplet
Status Get(Triplet T, int i, ElemType &e) {
// 1≤i≤3，用 e 返回 T 的第 i 元的值
if(i<1 || i>3) return ERROR;
e = T[i-1];
return OK;
} // Get
Status Max(Triplet T, ElemType &e) {
// 用 e 返回 T 中最大元素的值
e = (T[0]>=T[1]) ? ((T[0]>=T[2]) ? T[0]:T[2]) : ((T[1]>=T[2]) ? T[1]:T[2])
return OK;
} // Max3 算法和算法剖析
3.1 算法
算法(algorithm) 是对特定问题求解步骤的一种形容，它是指令的无限序列，其中每一条指令示意一个或多个操作。此外，一个算法还具备下列 5 个重要个性：
- 有穷性 ：一个算法必须总是(对任何非法的输出值) 在执行有穷步之后完结，且每一步都可在有穷工夫内实现。
- 确定性：算法中每一条指令必须有确切的含意，读者了解时不会产生二义性。并且，在任何条件下，算法只有惟一的一条执行门路，即对于雷同的输出只能得出雷同的输入。
- 可行性：一个算法是能行的，即算法中形容的操作都是能够通过曾经实现的根本运算执行无限次来实现的。
- 输出：一个算法有零个或多个的输出，这些输出取自于某个特定的对象的汇合。
- 输入：一个算法有一个或多个的输入，这些输入是同输出有着某些特定关系的量。
3.2 算法设计的要求
一个好的算法应思考达到以下指标：
- 正确性：算法要满足具体问题的要求。
- 可读性：便于了解、调试和批改。
- 健壮性：当输出非法数据时可能做出适当的反馈或解决，而不是参数不合理的输入后果。
- 效率与低存储量需要：效率波及程序运行工夫，低储存量波及程序运行时所须要的最大存储空间。
3.3 算法效率的度量
度量一个程序的运行工夫通常有两种办法：
- 预先统计：利用计算机外部的计时性能，不同的算法程序可通过一组或若干组雷同的统计数据以分辨优劣。
缺点：必须先运行根据算法编制的程序；所得工夫的统计量依赖于计算机的软件、硬件等环境因素，有时容易覆盖算法自身优劣。 -
事先剖析估算：一个用高级程序语言编写的程序在计算机上运行所耗费的工夫取决于以下因素：
- 根据的算法选用的策略；
- 问题的规模；
- 书写程序的语言：语言级别越高，执行效率越低；
- 编译程序所产生的的机器代码的品质；
- 机器执行指令的速度。
由此，应用相对工夫掂量算法的效率是不适合的。抛开计算机软件、硬件因素，可认为 一个特定算法的效率只依赖于问题的规模(通常用整数 n 示意)，或者说，它是问题规模的函数。
一个算法由控制结构和原操作 (固有数据类型的操作) 形成，算法工夫取决于两者的综合成果。为了便于比拟同一问题的不同算法，通常的做法是：从算法中选取一种对所钻研的问题 (或算法类型) 来说是基本操作的原操作，以该基本操作反复执行的次数作为算法的工夫量度。
工夫复杂度：个别状况下，算法中基本操作反复执行的次数是问题规模 n 的某个函数 f(n)，算法的工夫量度记作：
$$
T(n) = O(f(n))
$$
它示意随问题规模 n 的增大，算法执行工夫的增长率和 $f(n)$ 的增长率雷同，称为算法的 渐近工夫复杂度 (asymptotic time complexity)，简称 工夫复杂度。
O 的模式定义：若 $f(n)$ 是正整数 n 的一个函数，则 x_n=O(f(n)) 示意存在一个正的常数 M，使得当 n ≥ n0 时都满足 |xn| ≤ | M(f(n)) |。
显然，被称做问题的基本操作的原操作应是其反复执行次数和算法的执行工夫成正比的原操作，少数状况下它是最深层循环内的语句中的原操作，它的执行次数和蕴含它的语句的频度雷同。语句的 频度(frequency count) 指的是该语句反复执行的次数。
例如，两个 N x N 矩阵相乘的算法：
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j) {c[i][j] = 0;
for(k=1; k<=n; ++k)
c[i][j] += a[i][k] * b[k][j];
}其中，乘法运算是矩阵相乘问题的基本操作，整个算法的执行工夫与该基本操作的反复执行次数的三次方成正比，记作
$$
T(n) = O(n^3)
$$
常见的工夫复杂度如 \(O(1) \)、\(O(n)\)、\(O(n^2)\) 等别离称为常量阶、线性阶、平方阶，此外还有对数阶 \(O(\log n) \)、指数阶 \(O(2^n) \) 等。思考到不同数量级的复杂度性状，应尽可能地选用多项式阶 \(O(n^k)\) 的算法，而不是应用指数阶的算法。
个别状况下，对一个问题 (或一类算法) 只需抉择一种基本操作来探讨算法的工夫复杂度即可，有时也须要思考几种基本操作，甚至能够对不同的操作赋予不同的权值。
因为算法的工夫复杂度只思考问题规模 n 的增长率，因而，在难以准确计算基本操作的执行次数 (或语句的频度) 的状况下，只需 求出它对于 n 的增长率或阶 即可。如上面的程序：
for(i=2; i<=n; ++i)
for(j=2; j<=i-1; ++j) {
++x;
a[i][j] = x;
}语句 ++x 的执行次数对于 n 的增长率为 \(n^2\)，它是语句频度表达式 \((n-1)(n-2)/2\) 中增长最快的项。
有的状况下，算法中基本操作的反复执行次数还随输出的数据集的不同而不同，如起泡排序算法：
void bubble_sort(int a[], int n) {
// 将 a 中整数序列由小到大重新排列
for(i=n-1,change=TRUE; i>=1&&change; --i) {
change = FALSE;
for(j=0; j<i; ++j) {if(a[j] > a[j+1]) {a[j] <-> a[j+1];
change = TRUE;
}
}
}
} // bubble_sort下面程序中的基本操作为 a[j]<->a[j+1]，当 a 的初始序列为由小到大排列时，基本操作执行次数为 0，当 a 初始序列为由大到小排列时，基本操作执行次数为 \(n(n-1)/2\)。对这类算法的剖析，有两种解决办法：
- 思考所有可能输出数据集的期望值，此时相应的工夫复杂度为算法的 均匀工夫复杂度。
- 探讨算法在最坏状况下的工夫复杂度，即估算算法执行工夫的上界。
假如 a 初始输出数据可能呈现 \(n!\) 种排列状况的概率相等，则起泡排序额算法的工夫复杂度为 \(T_{arg}(n)=O(n^2)\)。起泡排序算法的最坏状况为 a 中初始序列为由大到小排列，则起泡排序算法在最坏状况下的工夫复杂度为 \(T(n)=O(n^2)\)。
很多状况下各种输出数据呈现的概率难以确定，因而通常第二种办法更加可行。往后探讨的工夫复杂度均默认为最坏状况下的工夫复杂度。
3.4 算法的存储空间需要
相似于算法的工夫复杂度，以 空间复杂度(space complexity) 作为算法所需存储空间的量度：
$$
S(n) = O(f(n))
$$
其中，n 为问题的规模。
一个上机执行的程序除了须要存储空间来存放自身所用指令、常数、变量和输出数据外，也须要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输出数据所占空间只取决于问题自身，和算法无关，则只须要剖析除输出和程序之外的额定空间，否则应同时思考输出自身所需空间(和输出数据的示意模式无关)。若额定空间绝对于输出数据量来说是常数，则称此算法为原地工作。如果所占空间量依赖于特定的输出，则除特地指明外，均按最坏状况来剖析。
