下载掌阅APP，畅读海量书库
立即打开
算法是指对解题方案准确而完整的描述。简单地说，算法就是解决问题的操作步骤。
算法不等于数学上的计算方法，也不等于程序。程序可以描述算法。
算法的基本特征如下。
（1）可行性：步骤可以实现，执行结果达到预期目的。
（2）确定性：步骤明确，不模棱两可，不准有多义性。
（3）有穷性：有限的时间内完成。
（4）拥有足够的情报：当拥有足够的输入信息和初始化信息时，算法才是有效的；当提供的情报不够时，算法可能无效。
算法复杂度用来衡量算法的优劣，它包括算法的时间复杂度和算法的空间复杂度。
（1）算法的时间复杂度。
算法的时间复杂度是指执行算法所需要的计算工作量。
算法的时间复杂度不等于算法程序执行的具体时间。算法程序执行的具体时间受到所使用的计算机、程序设计语言，以及算法实现过程中的许多细节的影响，而算法的时间复杂度与这些因素无关。
算法所需要的计算工作量是用算法所执行的基本运算次数来度量的。算法所执行的基本运算次数与问题的规模有关。
当具体分析一个算法的工作量时，在同一个问题规模下，算法所执行的基本运算次数还可能与特定的输入有关。即输入不同时，算法所执行的基本运算次数不同。
（2）算法的空间复杂度。
算法的空间复杂度是指执行这个算法所需要的存储空间。
执行算法所需要的存储空间包括3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。其中，额外空间包括算法执行过程中的工作单元，以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模(输入数据所占的存储空间)来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地(in place)工作的。
为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间和算法执行过程中所需要的额外空间，通常采用压缩存储技术来实现。
数据结构是指相互有关联的数据元素的集合。它包含两个要素，即“数据”和“结构”。
数据是需要处理的数据元素的集合。一般来说，这些数据元素具有某个共同的特征。如早餐、午餐、晚餐这3个数据元素有一个共同的特征，即它们都是一日三餐的名称，从而构成了“一日三餐”的集合。
所谓“结构”，就是关系，是集合中各个数据元素之间存在的某种关系(或联系)。在数据处理领域中，通常把数据元素两两之间的关系用前件/后件关系(或直接前驱/直接后继关系)来描述。如当考虑一日三餐的时间顺序关系时，“早餐”是“午餐”的前件(或直接前驱)，而“午餐”是“早餐”的后件(或直接后继)；同样，“午餐”是“晚餐”的前件，“晚餐”是“午餐”的后件。
数据结构分为数据的逻辑结构和数据的存储结构。数据的逻辑结构指反映数据元素之间逻辑关系(前件/后件关系)的数据结构。数据的存储结构又称为数据的物理结构，是数据的逻辑结构在计算机存储空间中的存放方式。
数据的逻辑结构的数学形式定义——数据结构是一个二元组：
其中， B 表示数据结构； D 是数据元素的集合； R 是 D 上关系的集合，它反映了 D 中各数据元素之间的前件/后件关系。前件/后件关系也可以用一个二元组来表示。
如果把一日三餐看作数据结构，则可表示成
B =( D ， R )
D ={早餐，午餐，晚餐}
R ={(早餐，午餐)，(午餐，晚餐)}
如果把部队军职看作数据结构，则可表示成
B =( D ， R )
D ={连长，排长，班长，士兵}
R ={(连长，排长)，(排长，班长)，(班长，士兵)}
除了用二元关系表示外，一个数据结构还可以用图形来表示。用中间标有元素值的方框表示的数据元素，一般称为数据节点，简称节点。对于每一个二元组，用一条有向线段从前件指向后件。
一日三餐的数据结构如图2.7(a)所示。而部队军职的数据结构如图2.7(b)所示。
图2.7 数据结构的图形表示
由前件/后件关系还可引出3个节点基本概念，如表2.10所示。
表2.10 节点基本概念
根据数据结构中各数据元素之间前件/后件关系的复杂程度，一般将数据结构划分为两大类型，即线性结构和非线性结构，如表2.11所示。
表2.11 线性结构和非线性结构
如果一个数据结构中没有数据元素，则称该数据结构为空的数据结构。在只有一个数据元素的数据结构中，删除该数据元素，就得到一个空的数据结构。
数据结构中，线性结构习惯称为线性表。线性表是最简单、也是最常用的一种数据结构。
线性表是 n ( n ≥0)个数据元素构成的有限序列。表中除第一个元素外的每一个元素，有且只有一个前件；除最后一个元素外，有且只有一个后件。
线性表要么是空表，要么可以表示为
其中,a i ( i =1,2,…， n )是线性表的数据元素，也称为线性表的一个节点，同一线性表中的数据元素必定具有相同的特性，即属于同一数据对象。数组、矩阵、向量等都是线性表。
非空线性表具有以下结构特征。
● 只有一个根节点，即节点a 1 ，它无前件。
● 有且只有一个终端节点，即节点a n ，它无后件。
● 除根节点与终端节点外，其他所有节点有且只有一个前件，并有且只有一个后件。
节点个数 n 称为线性表的长度，当 n =0时，称为空表。
通常，线性表可以采用顺序存储和链式存储两种存储结构。
顺序存储结构是存储线性表最简单的存储结构之一，具体做法是将线性表中的元素一个接一个地存储在一片相邻的存储区域中。这种顺序存储的线性表也被称为顺序表。
顺序表具有以下两个基本特征。
● 线性表中所有数据元素所占的存储空间是连续的。
● 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
在顺序表中，其前件、后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
（1）栈的定义。
栈(stack)是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行，允许插入与删除的一端称为栈顶，不允许插入与删除的一端称为栈底。当栈中没有元素时，称为空栈。
（2）栈的运算。
栈的修改原则是“后进先出”或“先进后出”。
通常用指针top来指示栈顶的位置，用指针bottom来指向栈底。栈顶指针top反映了栈不断变化的状态。
假设栈S=(a 1 ,a 2 ，…,a n )，则称a 1 为栈底元素,a n 为栈顶元素。栈中元素按a 1 ,a 2 ，…,a n 的次序进栈，退栈的第一个元素应为栈顶元素a n 。图2.8所示为栈结构和入栈、退栈示意。
图2.8 栈结构和入栈、退栈示意
栈的基本运算有3种：入栈、退栈及读栈顶元素。
栈和一般线性表的存储方法类似，通常也可以采用顺序存储和链式存储。
（1）队列的定义。
队列(queue)是指允许在一端进行插入，而在另一端进行删除的线性表。允许进行删除运算的一端称为队头(排头)，允许进行插入运算的一端称为队尾。若有队列：
那么,q 1 为队头元素(排头元素),q n 为队尾元素。队列中的元素是按照q 1 ,q 2 ，…,q n 的顺序进入的，退出队列时也只能按照这个次序依次退出。与栈相反，队列又称为“先进先出”或“后进后出”的线性表。
（2）队列的运算。
可以用顺序存储的线性表来表示队列。为了指示当前执行退队运算的队头位置，需要一个队头指针(排头指针)front;为了指示当前执行入队运算的队尾位置，需要一个队尾指针rear。队头指针front总是指向队头元素的前一个位置，而队尾指针rear总是指向队尾元素。队尾指针rear和队头指针front共同反映了队列中元素动态变化的情况。图2.9所示为队列的入队、退队示意。
图2.9 队列的入队、退队示意
（3）循环队列及其运算。
在实际应用中，队列的顺序存储结构一般采用循环队列的形式。
所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置。因此，从队头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。
循环队列的初始状态为空，即front=rear=m,如图2.10所示。
图2.10 循环队列初始状态示意
在循环队列中，当front=rear时，不能确定队列是满还是空。在实际使用循环队列时，通常会增加一个标志s来区分队列是满还是空。当s=0时表示队列空；当s=1且front=rear时表示队列满。
（1）线性链表。
线性链表指线性表的链式存储结构，简称链表。这种链表每个节点只有一个指针域，又称为单链表。
在线性链表中，第一个元素没有前件，因此指向链表中的第一个节点的指针，是一个特殊的指针，称为这个链表的头指针(HEAD)。最后一个元素没有后件，因此，线性链表最后一个节点的指针域为空，用NULL或0表示。
线性链表的存储单元是任意的，即各数据节点的存储序号可以是连续的，也可以是不连续的；各数据节点在存储空间中的位置关系与逻辑关系不一致，前件/后件关系由存储节点的指针来表示。当线性链表指向第一个数据元素的头指针等于NULL或者0时，该表称为空表。
在某些应用中，对线性链表中的每个节点设置两个指针，一个指针域存放前件的地址，称为左指针(Llink)；一个指针域存放后件的地址，称为右指针(Rlink)。这样的线性链表称为双向链表。图2.11所示为双向链表示意。在双向链表中，由于为每个节点设置了两个指针，因此从某一个节点出发，可以很方便地找到其他任意一个节点。
图2.11 双向链表示意
（2）带链的栈。
栈也可以采用链式存储结构表示，可以把栈组织成一个单链表。这种数据结构称为带链的栈。图2.12(a)所示为带链的栈示意。
（3）带链的队列。
与栈类似，队列也可以采用链式存储结构表示。带链的队列就是用一个单链表来表示队列，队列中的每一个元素对应链表中的一个节点。图2.12(b)所示为带链的队列示意。
图2.12 带链的栈和带链的队列示意
（4）顺序表和链表的比较。
顺序表和链表的优缺点如表2.12所示。
表2.12 顺序表和链表的优缺点
在单链表的第一个节点前增加一个表头节点，队头指针指向表头节点，最后一个节点的指针域的值由NULL改为指向表头节点，这样的链表称为循环链表。在循环链表中，所有节点的指针构成了一个环状链。
在循环链表中，只要指出表中任何一个节点的位置，就可以从它出发访问表中其他所有的节点。并且，由于表头节点是循环链表固有的节点，因此，即使在表中没有数据元素的情况下，表中也至少有一个节点存在，从而使空表和非空表的运算统一。
循环链表的逻辑状态如图2.13所示。
图2.13 循环链表的逻辑状态
树(tree)是一种简单的非线性结构。如一个家族中的族谱关系为A有后代B、C;B有后代D、E、F;C有后代G;E有后代H、I,则这个家族的成员及血统关系可用图2.14所示的“倒置的树”来描述。树的相关术语如表2.13所示。
图2.14 树的示例
表2.13 树的相关术语
树中的节点数等于树中所有节点的度之和再加1。
（1）二叉树的定义。
二叉树与树不同，但它与树的结构很相似，图2.15所示为二叉树。
图2.15 二叉树
二叉树的特点如下。
① 二叉树可以为空。空的二叉树没有节点，非空二叉树有且只有一个根节点。
② 每个节点最多有两棵子树，即二叉树中不存在度大于2的节点。
③ 二叉树的子树有左右之分，其次序不能任意颠倒。
（2）二叉树的性质。
二叉树具有以下几个性质。
性质1 :在二叉树的第 k 层上，最多有2 k -1 ( k ≥1)个节点。
性质2 :深度为 m 的二叉树中，最多有2 m -1个节点。
性质3 :对任何一棵二叉树，度为0的节点(即叶子节点)总是比度为2的节点多一个。
性质4 :具有 n 个节点的二叉树，其深度至少为[log 2 n ]+1,其中[log 2 n ]表示取log 2 n 的整数部分。
（3）满二叉树和完全二叉树。
满二叉树是指除最后一层外，每一层上的所有节点都有两个子节点的二叉树。即满二叉树在其第 k 层上有2 k -1 个节点，且深度为 m 的满二叉树共有2 m -1个节点。
图2.16所示为深度是4的满二叉树。
图2.16 满二叉树
完全二叉树是指除最后一层外，每一层上的节点数均达到最大值，在最后一层上只缺少右边的若干节点的二叉树。图2.17所示为深度是4的完全二叉树。
图2.17 完全二叉树
由完全二叉树可知，满二叉树一定是完全二叉树，完全二叉树一般不是满二叉树。完全二叉树具有如下特点：
① 叶子节点只可能在最后两层出现；
② 对于任一节点，若其右子树的深度为 m ，则该节点左子树的深度为 m 或 m +1。
性质5 :具有 n 个节点的完全二叉树的深度为[log 2 n ]+1。
在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中元素的存储节点由数据域和指针域两部分构成。由于每一个元素可以有两个后件，因此用于存储二叉树中元素的存储节点的指针域有两个：一个用于指向该节点的左子节点，即左指针域；另一个用于指向该节点的右子节点，即右指针域。二叉树的存储节点如图2.18所示。
图2.18 二叉树的存储节点
由于二叉树的存储结构中每一个存储节点有两个指针域，因此二叉树的链式存储结构也称为二叉链表。
满二叉树与完全二叉树可以按层次进行顺序存储。
二叉树的遍历是指不重复地访问二叉树中的所有节点。
在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。在先左后右的原则下，根据访问根节点的次序不同，二叉树的遍历可以分为3种：前序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD)。
（1）前序遍历。
首先访问根节点，然后遍历左子树，最后遍历右子树；并且在遍历左子树和右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。对图2.19中的二叉树进行前序遍历的结果(或称为该二叉树的前序遍历序列)为A,B,D,H,E,I,C,F,G。
图2.19 二叉树
（2）中序遍历。
首先遍历左子树，然后访问根节点，最后遍历右子树；并且在遍历左子树和右子树时，仍然首先遍历左子树，然后访问根节点，最后遍历右子树。对图2.19中的二叉树进行中序遍历的结果(或称为该二叉树的中序遍历序列)为H,D,B,E,I,A,C,G,F。
（3）后序遍历。
首先遍历左子树，然后遍历右子树，最后访问根节点；并且在遍历左子树和右子树时，仍然首先遍历左子树，然后遍历右子树，最后访问根节点。对图2.19中的二叉树进行后序遍历的结果(或称为该二叉树的后序遍历序列)为H,D,I,E,B,G,F,C,A。
如果已知一棵二叉树的前序遍历序列和中序遍历序列，可以唯一确定这棵二叉树；已知一棵二叉树的后序遍历序列和中序遍历序列，也可以唯一确定这棵二叉树。但是，已知一棵二叉树的前序遍历序列和后序遍历序列，不能唯一确定这棵二叉树。
基本思想：从线性表的第一个元素开始，逐个将线性表中的元素与被查元素进行比较，若相等，则查找成功，停止查找；若整个线性表扫描完毕，仍未找到与被查元素相等的元素，则表示线性表中没有要查找的元素，查找失败。
● 最好的情况下，第一个元素就是要查找的元素，则比较次数为1。
● 最坏的情况下，最后一个元素才是要找的元素，或者在线性表中，没有要查找的元素，则需要与线性表中所有的元素比较，比较次数为 n 。
● 平均情况下，大约需要比较 n /2次。
在以下两种情况中，顺序查找是唯一的选择。
（1）线性表为无序表(表中的元素是无序的)，则不管采用的是顺序存储结构，还是链式存储结构，都只能用顺序查找。
（2）即使线性表是有序的，如果采用的是链式存储结构，也只能用顺序查找。
能使用二分法查找的线性表必须满足两个条件：①用顺序存储结构；②线性表是有序表。此处的“有序”特指元素按非递减顺序排列，即从小到大排列，但允许相邻元素相等。
对于长度为 n 的有序线性表，利用二分法查找元素X的过程如下。
将X与线性表的中间项比较的过程如下。
● 如果X的值与中间项的值相等，则查找成功，结束查找。
● 如果X的值小于中间项的值，则在线性表的前半部分以二分法继续查找。
● 如果X的值大于中间项的值，则在线性表的后半部分以二分法继续查找。
顺序查找每比较一次，只将查找范围缩小1,而二分法查找每比较一次，可将查找范围缩小为原来的一半，效率大大提高。对于长度为 n 的有序线性表，在最坏情况下，二分法查找只需比较log 2 n 次。
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
交换类排序是借助数据元素的“交换”来进行排序的一种方法。
（1）冒泡排序。
在数据元素的序列中，对于某个元素，如果其后存在一个元素小于它，则称存在一个逆序。冒泡排序的基本思想就是通过两两相邻数据元素之间的比较和交换，不断地消去逆序，直到所有数据元素以非递减顺序排列为止。
在最坏情况下，对长度为 n 的线性表排序，冒泡排序需要比较的次数为 n ( n -1)/2。
（2）快速排序。
基本思想：在待排序的 n 个元素中取一个元素K(通常取第一个元素)，以元素K作为分割标准，把所有小于元素K的数据元素都移到K前面，把所有大于元素K的数据元素都移到K后面。这样，以K为分界线，把线性表分割为两个子表，这称为一趟排序。然后，对K前后的两个子表分别重复上述过程，直到分割的子表的长度为1为止。这时线性表已经排好序。
快速排序在最坏情况下需要进行 n ( n -1)/2次比较，但实际的排序效率要比冒泡排序高得多。
插入类排序是每次将一个待排序元素，按其元素值的大小插入前面已经排好序的子表中的适当位置，直到全部元素插入完成为止。
（1）简单插入排序。
简单插入排序是把 n 个待排序的元素看成一个有序表和一个无序表。开始时，有序表只包含一个元素，而无序表包含另外 n -1个元素。每次取无序表中的第一个元素插入有序表中的正确位置，使之成为增加一个元素的新的有序表。插入元素时，插入位置及其后的记录依次向后移动。最后有序表的长度为 n ，而无序表为空，此时排序完成。
在最坏情况下，简单插入排序需要进行 n ( n -1)/2次比较。
（2）希尔排序。
希尔排序的基本思想是，先取一个整数 d 1 (称为增量， d 1 < n )，把全部数据元素分成 d 1 个组，所有距离为 d 1 倍数的元素放在一组中，组成了一个子序列，对每个子序列分别进行简单插入排序。然后取 d 2 ( d 2 < d 1 )重复上述分组和排序工作，直到 d i =1,即所有记录在一组中为止。
希尔排序的效率与所选取的增量序列有关。在最坏情况下，希尔排序需要比较的次数是 n r (1< r <2)。
选择类排序的基本思想是通过每一次从待排序序列中选出值最小的元素，然后将其顺序放在已排好序的有序子表的后面，直到全部序列满足排序要求为止。
（1）简单选择排序。
基本思想：先从所有 n 个待排序的数据元素中选择最小的元素，将该元素与第1个元素交换，再从剩下的 n -1个元素中选出最小的元素与第2个元素交换。重复操作直到所有的元素有序为止。
简单选择排序在最坏的情况下需要比较 n ( n -1)/2次。
（2）堆排序。
若有 n 个元素的序列(h 1 ,h 2 ，…,h n )，将元素按顺序组成一棵完全二叉树，当且仅当满足下列条件时称为堆。
或者
其中， i =1,2,3,…， n /2。
第一种情况称为大根堆，所有节点的值大于或等于左右子节点的值。第二种情况称为小根堆，所有节点的值小于或等于左右子节点的值。
堆排序在最坏情况下需要比较 n log 2 n 次。