第1章数据结构与算法 列举法的基本思想是,根据提出的问题,列举所有可能的情况,并用问题中给定的条件检 验哪些是需要的,哪些是不需要的。因此,列举法常用于解决“是否存在”或“有多少种可能” 等类型的问题,例如求解不定方程的问题。 列举法的特点是算法比较简单。但当列举的可能情况较多时,执行列举算法的工作量将会 很大。因此,在用列举法设计算法时,使方案优化,尽量减少运算工作量,是应该重点注意的。 通常,在设计列举算法时,只要对实际问题进行详细的分析,将与问题有关的知识条理化、完 备化、系统化,从中找出规律;或对所有可能的情况进行分类,引出一些有用的信息,是可以 大大减少列举量的 列举原理是计算机应用领域中十分重要的原理。许多实际问题,若采用人工列举是不可想 象的,但由于计算机的运算速度快,擅长重复操作,可以很方便地进行大量列举。列举算法虽 然是一种比较笨拙而原始的方法,其运算量比较大,但在有些实际问题中(如寻找路径、查找 搜索等问题),局部使用列举法却是很有效的,因此,列举算法是计算机算法中的一个基础算法。 (2)归纳法 归纳法的基本思想是,通过列举少量的特殊情况,经过分析,最后找出一般的关系。显然 归纳法要比列举法更能反映问题的本质,并且可以解决列举量为无限的问题。但是,从一个实 际问题中总结归纳出一般的关系,并不是一件容易的事情,尤其是要归纳出一个数学模型更为 困难。从本质上讲,归纳就是通过观察一些简单而特殊的情况,最后总结出一般性的结论 归纳是一种抽象,即从特殊现象中找出一般关系。但由于在归纳的过程中不可能对所有的 凊况进行列举,因此,最后由归纳得到的结论还只是一种猜测,还需要对这种猜测加以必要的 证明。实际上,通过精心观察而得到的猜测得不到证实或最后证明猜测是错的,也是常有的事。 (3)递推 所谓递推,是指从己知的初始条件出发,逐次推出所要求的各中间结果和最后结果。其中 初始条件或是问题本身已经给定,或是通过对问题的分析与化简而确定。递推本质上也属于归 纳法,工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的,因此,递推关 系式往往是归纳的结果。 递推算法在数值计算中是极为常见的。但是,对于数值型的递推算法必须要注意数值计算 的稳定性问题。 (4)递归 人们在解决一些复杂问题时,为了降低问题的复杂程度(如问题的规模等),一般总是将问 题逐层分解,最后归结为一些最简单的问题。这种将问题逐层分解的过程,实际上并没有对问 题进行求解,而只是当解决了最后那些最简单的问题后,再沿着原来分解的逆过程逐步进行综 合,这就是递归的基本思想。由此可以看出,递归的基础也是归纳。在工程实际中,有许多问 题就是用递归来定义的,数学中的许多函数也是用递归来定义的。递归在可计算性理论和算法 设计中占有很重要的地位 递归分为直接递归与间接递归两种。如果一个算法P显式地调用自己则称为直接递归。如 果算法P调用另一个算法Q,而算法Q又调用算法P,则称为间接递归调用。 递归是很重要的算法设计方法之一。实际上,递归过程能将一个复杂的问题归结为若干个 较简单的问题,然后将这些较简单的问题再归结为更简单的问题,这个过程可以一直做下去, 直到最简单的问题为止 有些实际问题,既可以归纳为递推算法,又可以归纳为递归算法。但递推与递归的实现方 是大不一样的。递推是从初始条件出发,逐次推出所需求的结果;而递归则是从算法本身到
第 1 章 数据结构与算法 3 列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检 验哪些是需要的，哪些是不需要的。因此，列举法常用于解决“是否存在”或“有多少种可能” 等类型的问题，例如求解不定方程的问题。 列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会 很大。因此，在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。 通常，在设计列举算法时，只要对实际问题进行详细的分析，将与问题有关的知识条理化、完 备化、系统化，从中找出规律；或对所有可能的情况进行分类，引出一些有用的信息，是可以 大大减少列举量的。 列举原理是计算机应用领域中十分重要的原理。许多实际问题，若采用人工列举是不可想 象的，但由于计算机的运算速度快，擅长重复操作，可以很方便地进行大量列举。列举算法虽 然是一种比较笨拙而原始的方法，其运算量比较大，但在有些实际问题中(如寻找路径、查找、 搜索等问题)，局部使用列举法却是很有效的，因此，列举算法是计算机算法中的一个基础算法。 (2)归纳法 归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。显然， 归纳法要比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。但是，从一个实 际问题中总结归纳出一般的关系，并不是一件容易的事情，尤其是要归纳出一个数学模型更为 困难。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。 归纳是一种抽象，即从特殊现象中找出一般关系。但由于在归纳的过程中不可能对所有的 情况进行列举，因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的 证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。 (3)递推 所谓递推，是指从己知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中 初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归 纳法，工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的，因此，递推关 系式往往是归纳的结果。 递推算法在数值计算中是极为常见的。但是，对于数值型的递推算法必须要注意数值计算 的稳定性问题。 (4)递归 人们在解决一些复杂问题时，为了降低问题的复杂程度(如问题的规模等)，一般总是将问 题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问 题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综 合，这就是递归的基本思想。由此可以看出，递归的基础也是归纳。在工程实际中，有许多问 题就是用递归来定义的，数学中的许多函数也是用递归来定义的。递归在可计算性理论和算法 设计中占有很重要的地位。 递归分为直接递归与间接递归两种。如果一个算法 P 显式地调用自己则称为直接递归。如 果算法 P 调用另一个算法 Q，而算法 Q 又调用算法 P，则称为间接递归调用。 递归是很重要的算法设计方法之一。实际上，递归过程能将一个复杂的问题归结为若干个 较简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去， 直到最简单的问题为止。 有些实际问题，既可以归纳为递推算法，又可以归纳为递归算法。但递推与递归的实现方 法是大不一样的。递推是从初始条件出发，逐次推出所需求的结果；而递归则是从算法本身到
第1章数据结构与算法 达递归边界的。通常,递归算法要比递推算法清晰易读,其结构比较简练。特别是在许多比较 复杂的问题中,很难找到从初始条件推出所需结果的全过程,此时,设计递归算法要比递推算 法容易得多。但递归算法的执行效率比较低。 (5)减半递推技术 实际问题的复杂程度往往与问题的规模有着密切的联系。因此,利用分治法解决这类实际 问题是有效的。所谓分治法,就是对问题分而治之。工程上常用的分治法是减半递推技术 所谓“减半”,是指将问题的规模减半,而问题的性质不变;所谓“递推”,是指重复“减 半”的过程 下面举例说明利用减半递推技术设计算法的基本思想。 例1.1设方程fx=0在区间[a,b]上有实根,且fa)与f(b异号。利用二分法求该方程在区 间[a,b]上的一个实根 用二分法求方程实根的减半递推过程如下 首先取给定区间的中点c=a+b)/2 然后判断f(c)是否为0。若f(c)=0,则说明c即为所求的根,求解过程结束:如果f(c)≠0 则根据以下原则将原区间减半 若f(a)f(c)<0,则取原区间的前半部分 若fb)f(c)<0,则取原区间的后半部分 最后判断减半后的区间长度是否已经很小: 若a-b<ε,则过程结束,取(a+b)2为根的近似值 若a-b|≥ε,则重复上述的减半过程。 (6)回溯法 前面讨论的递推和递归算法本质上是对实际问题进行归纳的结果,而减半递推技术也是归 纳法的一个分支。在工程上,有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤 并且也不能进行无限的列举。对于这类问题,一种有效的方法是“试”。通过对问题的分析,找 出一个解决问题的线索,然后沿着这个线索逐步试探,对于每一步的试探,若试探成功,就得 到问题的解,若试探失败,就逐步回退,换别的路线再进行试探。这种方法称为回溯法。回溯 法在处理复杂数据结构方面有着广泛的应用。 1.12算法复杂度 算法的复杂度主要包括时间复杂度和空间复杂度 1.算法的时间复杂度 所谓算法的时间复杂度,是指执行算法所需要的计算工作量 为了能够比较客观地反映出一个算法的效率,在度量一个算法的工作量时,不仅应该与所 使用的计算机、程序设计语言以及程序编制者无关,而且还应该与算法实现过程中的许多细节 无关。为此,可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。基本运 算反映了算法运算的主要特征,因此,用基本运算的次数来度量算法工作量是客观的也是实际 可行的,有利于比较同一问题的几种算法的优劣。例如,在考虑两个矩阵相乘时,可以将两个 实数之间的乘法运算作为基本运算,而对于所用的加法(或减法)运算忽略不计。又如,当需要 在一个表中进行查找时,可以将两个元素之间的比较作为基本运算 算法所执行的基本运算次数还与问题的规模有关。例如,两个20阶矩阵相乘与两个O阶 阵相乘,所需要的基本运算(即两个实数的乘法)次数显然是不同的,前者需要更多的运算次
第 1 章 数据结构与算法 4 达递归边界的。通常，递归算法要比递推算法清晰易读，其结构比较简练。特别是在许多比较 复杂的问题中，很难找到从初始条件推出所需结果的全过程，此时，设计递归算法要比递推算 法容易得多。但递归算法的执行效率比较低。 (5)减半递推技术 实际问题的复杂程度往往与问题的规模有着密切的联系。因此，利用分治法解决这类实际 问题是有效的。所谓分治法，就是对问题分而治之。工程上常用的分治法是减半递推技术。 所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减 半”的过程。 下面举例说明利用减半递推技术设计算法的基本思想。 例 1.1 设方程 f(x)=0 在区间[a，b]上有实根，且 f(a)与 f(b)异号。利用二分法求该方程在区 间[a，b]上的一个实根。 用二分法求方程实根的减半递推过程如下： 首先取给定区间的中点 c=(a+b)/2。 然后判断 f(c)是否为 0。若 f(c)=0，则说明 c 即为所求的根，求解过程结束；如果 f(c)≠0， 则根据以下原则将原区间减半： 若 f(a)f(c)<0，则取原区间的前半部分； 若 f(b)f(c)<0，则取原区间的后半部分。 最后判断减半后的区间长度是否已经很小： 若|a-b|<ε，则过程结束，取(a+b)/2 为根的近似值； 若|a-b|≥ε，则重复上述的减半过程。 (6)回溯法 前面讨论的递推和递归算法本质上是对实际问题进行归纳的结果，而减半递推技术也是归 纳法的一个分支。在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤， 并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试”。通过对问题的分析，找 出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得 到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。回溯 法在处理复杂数据结构方面有着广泛的应用。 1.1.2 算法复杂度 算法的复杂度主要包括时间复杂度和空间复杂度。 1.算法的时间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所 使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节 无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。基本运 算反映了算法运算的主要特征，因此，用基本运算的次数来度量算法工作量是客观的也是实际 可行的，有利于比较同一问题的几种算法的优劣。例如，在考虑两个矩阵相乘时，可以将两个 实数之间的乘法运算作为基本运算，而对于所用的加法(或减法)运算忽略不计。又如，当需要 在一个表中进行查找时，可以将两个元素之间的比较作为基本运算。 算法所执行的基本运算次数还与问题的规模有关。例如，两个 20 阶矩阵相乘与两个 lO 阶 矩阵相乘，所需要的基本运算(即两个实数的乘法)次数显然是不同的，前者需要更多的运算次
第1章数据结构与算法 数。因此,在分析算法的工作量时,还必须对问题的规模进行度量。 综上所述,算法的工作量用算法所执行的基本运算次数来度量,而算法所执行的基本运算 次数是问题规模的函数,即 算法的工作量:f(n) 其中n是问题的规模。例如,两个n阶矩阵相乘所需要的基本运算(即两个实数的乘法次 数为n3,即计算工作量为n3,也就是时间复杂度为n3。 在具体分析一个算法的工作量时,还会存在这样的问题:对于一个固定的规模,算法所执 行的基本运算次数还可能与特定的输入有关,而实际上又不可能将所有可能情况下算法所执行 的基本运算次数都列举出来。例如,“在长度为n的一维数组中查找值为x的元素”,若采用顺 序搜索法,即从数组的第一个元素开始,逐个与被査值ⅹ进行比较。显然,如果第一个元素恰 为x,则只需要比较1次。但如果x为数组的最后一个元素,或者x不在数组中,则需要比较n 次才能得到结果。因此,在这个问题的算法中,其基本运算(即比较)的次数与具体的被查值ⅹ 有关 在同一个问题规模下,如果算法执行所需的基本运算次数取决于某一特定输入时,可以用 以下两种方法来分析算法的工作量 (1)平均性态( Average behavior) 所谓平均性态分析,是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工 作量。 设x是所有可能输入中的某个特定输入,p(x)是x出现的概率(即输入为x的概率),t(x)是 算法在输入为ⅹ时所执行的基本运算次数,则算法的平均性态定义为 A(n)=∑p(x)(x) 其中D。表示当规模为n时,算法执行时所有可能输入的集合。这个式子中的t(x)可以通 过分析算法来加以确定;而p(x)必须由经验或用算法中有关的一些特定信息来确定,通常是不 能解析地加以计算的。如果确定p(x)比较困难,则会给平均性态的分析带来困难。 (2)最坏情况复杂性( Worst-Case Complexity) 所谓最坏情况分析,是指在规模为n时,算法所执行的基本运算的最大次数。它定义为 w(n)=maxi(x)) 显然,wn)的计算要比A(n)的计算方便得多。由于w(n)实际上是给出了算法工作量的一1 上界,因此,它比A(n)更具有实用价值 下面通过一个例子来说明算法复杂度的平均性态分析与最坏情况分析。 例1.2采用顺序搜索法,在长度为n的一维数组中查找值为x的元素。即从数组的第一个 元素开始,逐个与被查值x进行比较。基本运算为x与数组元素的比较 首先考虑平均性态分析 设被查项x在数组中出现的概率为q。当需要查找的x为数组中第i个元素时,则在查找 过程中需要做i次比较,当需要查找的x不在数组中时(即数组中没有x这个元素),则需要与数 组中所有的元素进行比较。即 i,1≤i≤n n,I=n
第 1 章 数据结构与算法 5 数。因此，在分析算法的工作量时，还必须对问题的规模进行度量。 综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算 次数是问题规模的函数，即 算法的工作量：f(n) 其中 n 是问题的规模。例如，两个 n 阶矩阵相乘所需要的基本运算(即两个实数的乘法)次 数为 n 3，即计算工作量为 n 3，也就是时间复杂度为 n 3。 在具体分析一个算法的工作量时，还会存在这样的问题：对于一个固定的规模，算法所执 行的基本运算次数还可能与特定的输入有关，而实际上又不可能将所有可能情况下算法所执行 的基本运算次数都列举出来。例如，“在长度为 n 的一维数组中查找值为 x 的元素”，若采用顺 序搜索法，即从数组的第一个元素开始，逐个与被查值 x 进行比较。显然，如果第一个元素恰 为 x，则只需要比较 1 次。但如果 x 为数组的最后一个元素，或者 x 不在数组中，则需要比较 n 次才能得到结果。因此，在这个问题的算法中，其基本运算(即比较)的次数与具体的被查值 x 有关。 在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用 以下两种方法来分析算法的工作量。 (1)平均性态(Average Behavior) 所谓平均性态分析，是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工 作量。 设 x 是所有可能输入中的某个特定输入，p(x)是 x 出现的概率(即输入为 x 的概率)，t(x)是 算法在输入为 x 时所执行的基本运算次数，则算法的平均性态定义为 = Dn x A(n) p(x)t(x) 其中 D。表示当规模为 n 时，算法执行时所有可能输入的集合。这个式子中的 t(x)可以通 过分析算法来加以确定；而 p(x)必须由经验或用算法中有关的一些特定信息来确定，通常是不 能解析地加以计算的。如果确定 p(x)比较困难，则会给平均性态的分析带来困难。 (2)最坏情况复杂性(Worst-Case Complexity) 所谓最坏情况分析，是指在规模为 n 时，算法所执行的基本运算的最大次数。它定义为 W (n) max{t(x)} Dn x = 显然，w(n)的计算要比 A(n)的计算方便得多。由于 w(n)实际上是给出了算法工作量的一个 上界，因此，它比 A(n)更具有实用价值。 下面通过一个例子来说明算法复杂度的平均性态分析与最坏情况分析。 例 1.2 采用顺序搜索法，在长度为 n 的一维数组中查找值为 x 的元素。即从数组的第一个 元素开始，逐个与被查值 x 进行比较。基本运算为 x 与数组元素的比较。 首先考虑平均性态分析。 设被查项 x 在数组中出现的概率为 q。当需要查找的 x 为数组中第 i 个元素时，则在查找 过程中需要做 i 次比较，当需要查找的 x 不在数组中时(即数组中没有 x 这个元素)，则需要与数 组中所有的元素进行比较。即 = + = , 1 ,1 n i n i i n t i
第1章数据结构与算法 其中i=n+1表示x不在数组中的情况 如果假设需要查找的x出现在数组中每个位置上的可能性是一样的,则x出现在数组中每 个位置上的概率为qn(因为前面已经假设x在数组中的概率为q),而x不在数组中的概率为 q/nlsi≤n P 1-q=n+1 其中in+l表示x不在数组中的情况。 因此,用顺序搜索法在长度为n的一维数组中查找值为ⅹ的元素,在平均情况下需要做的 比较次数为 A(m)=∑p1=2(q/n)+(1-q)m=(n+1)q/2+(1-q)-n 如果已知需要査找的x一定在数组中,此时ql,则A(n)=(n+1)2。这就是说,在这种情况 下,用顺序搜索法在长度为n的一维数组中查找值为x的元素,在平均情况下需要检查数组中 半的元素 如果已知需要查找的x有一半的机会在数组中,此时q=1/2,则 A(m)=[(n+1)/4]+n/2≈3n/4 这就是说,在这种情况下,用顺序搜索法在长度为n的一维数组中查找值为x的元素,在 平均情况下需要检查数组中314的元素。 再考虑最坏情况分析。 在这个例子中,最坏情况发生在需要杳找的x是数组中的最后一个元素或x不在数细中的 时候。此时显然有 W(m)=max{l1|l≤i≤n+l}=n 在上述例子中,算法执行的工作量是与具体的输入有关的,A(n)只是它的加权平均值,而 实际上对于某个特定的输入,其计算工作量未必是A(n),且A(m)也不一定等于w(n)。但在另外 些情况下,算法的计算工作量与输入无关,即当规模为n时,在所有可能的输入下,算法所 执行的基本运算次数是一定的,此时有A(n)=w(n)。例如,两个n阶的矩阵相乘,都需要做n 次实数乘法,而与输入矩阵的具体元素无关。 2算法的空间复杂度 一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间。 个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以 及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及 某种数据结构所需要的附加存储空间(例如,在链式结构中,除了要存储数据本身外,还需要存 储链接信息)。如果额外空间量相对于问题规模来说是常数,则称该算法是原地( n place)工作的。 在许多实际问题中,为了减少算法所占的存储空间,通常采用压缩存储技术,以便尽量减少不 必要的额外空间 6
第 1 章 数据结构与算法 6 其中 i=n+1 表示 x 不在数组中的情况。 如果假设需要查找的 x 出现在数组中每个位置上的可能性是一样的，则 x 出现在数组中每 一个位置上的概率为 q/n(因为前面已经假设 x 在数组中的概率为 q)，而 x 不在数组中的概率为 1-q。即 − = + = 1 , 1 / ,1 q i n q n i n pi 其中 i=n+l 表示 x 不在数组中的情况。 因此，用顺序搜索法在长度为 n 的一维数组中查找值为 x 的元素，在平均情况下需要做的 比较次数为 + = = = = + − = + + − − 1 1 1 ( ) ( / ) (1 ) ( 1) / 2 (1 ) n i n i A n pi t i q n i q n n q q n 如果已知需要查找的 x 一定在数组中，此时 q=l，则 A(n)=(n+1)/2。这就是说，在这种情况 下，用顺序搜索法在长度为 n 的一维数组中查找值为 x 的元素，在平均情况下需要检查数组中 一半的元素。 如果已知需要查找的 x 有一半的机会在数组中，此时 q=l/2，则 A(n) = [(n +1)/ 4] + n / 2 3n / 4 这就是说，在这种情况下，用顺序搜索法在长度为 n 的一维数组中查找值为 x 的元素，在 平均情况下需要检查数组中 3/4 的元素。 再考虑最坏情况分析。 在这个例子中，最坏情况发生在需要杳找的 x 是数组中的最后一个元素或 x 不在数细中的 时候。此时显然有 W(n) = max{t i |1 i n +1} = n 在上述例子中，算法执行的工作量是与具体的输入有关的，A(n)只是它的加权平均值，而 实际上对于某个特定的输入，其计算工作量未必是 A(n)，且 A(n)也不一定等于 w(n)。但在另外 一些情况下，算法的计算工作量与输入无关，即当规模为 n 时，在所有可能的输入下，算法所 执行的基本运算次数是一定的，此时有 A(n)=w(n)。例如，两个 n 阶的矩阵相乘，都需要做 n。 次实数乘法，而与输入矩阵的具体元素无关。 2.算法的空间复杂度 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以 及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及 某种数据结构所需要的附加存储空间(例如，在链式结构中，除了要存储数据本身外，还需要存 储链接信息)。如果额外空间量相对于问题规模来说是常数，则称该算法是原地(in place)工作的。 在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不 必要的额外空间
第1章数据结枃与算法 12数据结构的基本概念 利用计算机进行数据处理是计算机应用的一个重要领域。在进行数据处理时,实际需要处 理的数据元素一般有很多,而这些大量的数据元素都需要存放在计算机中,因此,大量的数据 元素在计算机中如何组织,以便提高数据处理的效率,并且节省计算机的存储空间,这是进行 数据处理的关键问题。 显然,杂乱无章的数据是不便于处理的。而将大量的数据随意地存放在计算机中,实际上 也是“白找苦吃”,对数据处理更是不利。 数据结构作为计算机的一门学科,主要研究和讨论以下三个方面的问题: ①数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构 ②在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构 ③对各种数据结构进行的运算。 讨论以上问题的主要目的是为了提高数据处理的效率。所谓提高数据处理的效率,主要包 括两个方面:一是提高数据处理的速度,二是尽量节省在数据处理过程中所占用的计算机存储 空间 本章主要讨论工程上常用的一些基本数据结构,它们是软件设计的基础 12.1什么是数据结构 计算机已被广泛用于数据处理。实际问题中的各数据元素之间总是相互关联的。所谓数据 处理,是指对数据集合中的各元素以各种方式进行运算,包括插入、删除、查找、更改等运算, 也包括对数据元素进行分析。在数据处理领域中,建立数学模型有时并不十分重要,事实上 许多实际问题是无法表示成数学模型的。人们最感兴趣的是知道数据集合中各数据元素之间存 在什么关系,应如何组织它们,即如何表示所需要处理的数据元素 下面通过两个实例来说明对同一批数据用不同的表示方法后,对处理效率的影响 例1.3无序表的顺序查找与有序表的对分查找: 图1.1是两个子表。从图中可以看出,在这两个子表中所存放的数据元素是相同的,但它 们在表中存放的顺序是不同的。在图1.1(a所示的表中,数据元素的存放顺序是没有规则的 而在图1.1(b)所示的表中,数据元素是按从小到大的顺序存放的。我们称前者为无序表,后者 为有序表。 下面讨论在这两种表中进行查找的问题。 首先讨论在图1.1(a所示的无序表中进行查找。由于在图1.1(a表中数据元素的存放顺序没 有一定的规则,因此,要在这个表中査找某个数时,只能从第一个元素开始,逐个将表中的元 素与被查数进行比较,直到表中的某个元素与被查数相等(即查找成功)或者表中所有元素与被 查数都进行了比较且都不相等(即査找失败)为止。这种査找方法称为顺序查找。显然,在顺序 查找中,如果被查找数在表的前部,则需要比较的次数就少:但如果被查找数在表的后部,则 需要比较的次数就多。特别是当被查找数刚好是表中的第一个元素时(如被查数为35),只需要 比较一次就查找成功;但当被查数刚好是表中最后一个元素(如被查数为46)或表中根本就没有 被查数时(如被查数为67),则需要与表中所有的元素进行比较,在这种情况下,当表很大时 顺序查找是很费时间的。虽然顺序查找法的效率比较低,但由于图1.(a)为无序表,没有更好 的查找方法,只能用顺序查找 现在再讨论在图1.1(b)所示的有序表中进行查找。由于有序表中的元素是从小到大进行排
第 1 章 数据结构与算法 7 1.2 数据结构的基本概念 利用计算机进行数据处理是计算机应用的一个重要领域。在进行数据处理时，实际需要处 理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据 元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行 数据处理的关键问题。 显然，杂乱无章的数据是不便于处理的。而将大量的数据随意地存放在计算机中，实际上 也是“白找苦吃”，对数据处理更是不利。 数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题： ①数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； ②在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； ③对各种数据结构进行的运算。 讨论以上问题的主要目的是为了提高数据处理的效率。所谓提高数据处理的效率，主要包 括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储 空间。 本章主要讨论工程上常用的一些基本数据结构，它们是软件设计的基础。 1.2.1 什么是数据结构 计算机已被广泛用于数据处理。实际问题中的各数据元素之间总是相互关联的。所谓数据 处理，是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算， 也包括对数据元素进行分析。在数据处理领域中，建立数学模型有时并不十分重要，事实上， 许多实际问题是无法表示成数学模型的。人们最感兴趣的是知道数据集合中各数据元素之间存 在什么关系，应如何组织它们，即如何表示所需要处理的数据元素。 下面通过两个实例来说明对同一批数据用不同的表示方法后，对处理效率的影响。 例 1.3 无序表的顺序查找与有序表的对分查找： 图 1.1 是两个子表。从图中可以看出，在这两个子表中所存放的数据元素是相同的，但它 们在表中存放的顺序是不同的。在图 1.1(a)所示的表中，数据元素的存放顺序是没有规则的； 而在图 1.1(b)所示的表中，数据元素是按从小到大的顺序存放的。我们称前者为无序表，后者 为有序表。 下面讨论在这两种表中进行查找的问题。 首先讨论在图 1.1(a)所示的无序表中进行查找。由于在图 1.1(a)表中数据元素的存放顺序没 有一定的规则，因此，要在这个表中查找某个数时，只能从第一个元素开始，逐个将表中的元 素与被查数进行比较，直到表中的某个元素与被查数相等(即查找成功)或者表中所有元素与被 查数都进行了比较且都不相等(即查找失败)为止。这种查找方法称为顺序查找。显然，在顺序 查找中，如果被查找数在表的前部，则需要比较的次数就少；但如果被查找数在表的后部，则 需要比较的次数就多。特别是当被查找数刚好是表中的第一个元素时(如被查数为 35)，只需要 比较一次就查找成功；但当被查数刚好是表中最后一个元素(如被查数为 46)或表中根本就没有 被查数时(如被查数为 67)，则需要与表中所有的元素进行比较，在这种情况下，当表很大时， 顺序查找是很费时间的。虽然顺序查找法的效率比较低，但由于图 1.1(a)为无序表，没有更好 的查找方法，只能用顺序查找。 现在再讨论在图 1.1(b)所示的有序表中进行查找。由于有序表中的元素是从小到大进行排