录 第1章数据结构与算法 1算法 1.1.1算法的基本概念 1.1.2算法复杂度 1.2数据结构的基本概念 .2.1什么是数据结构 22数据结构的图形表示 123线性结构与非线性结构 1.3线性表及其顺序存储结构 1.3.1线性表的基本概念 1.3.2线性表的顺序存储结构 13.3顺序表的插入运算 34顺序表的删除运算 14栈和队列 栈及其基本运算 42队列及其基本运算 5679902 1.5线性链表 1.5.1线性链表的基本概念 1.5,2线性链表的基本运算 1.5.3循环链表及其基本运算 1.6树与二叉树 61树的基本概念 162二叉树及其基本性质 163二叉树的存储结构 164二叉树的遍历 1.7查找技术 1.7.1顺序查找 1.7.2二分法查找 18排序技术 81交换类排序法 EL 82插入类排序法 83选择类排序法 习题1 第2章程序设计基础 2.1程序设计方法与风格 2.2结构化程序设针 22.1结构化程序设计的原则 222结构化程序设计的基本结构和特点
目 录 第1章 数据结构与算法........................................................................................................ 1 1.1 算 法................................................................................................................. 1 1.1.1算法的基本概念................................................................................................. 1 1.1.2 算法复杂度...................................................................................................... 4 1.2 数据结构的基本概念................................................................................................ 7 1.2.1什么是数据结构................................................................................................. 7 1.2.2数据结构的图形表示.........................................................................................12 1.2.3线性结构与非线性结构.....................................................................................13 1.3线性表及其顺序存储结构 ...........................................................................................14 1.3.1线性表的基本概念............................................................................................14 1.3.2线性表的顺序存储结构.....................................................................................15 1.3.3顺序表的插入运算............................................................................................16 1.3.4顺序表的删除运算............................................................................................17 1.4 栈和队列................................................................................................................19 1.4.1栈及其基本运算................................................................................................19 1.4.2队列及其基本运算............................................................................................20 1.5 线性链表................................................................................................................22 1.5.1线性链表的基本概念.........................................................................................22 1.5.2线性链表的基本运算.........................................................................................26 1.5.3循环链表及其基本运算.....................................................................................28 1.6 树与二叉树.............................................................................................................29 1.6.1树的基本概念...................................................................................................29 1.6.2二叉树及其基本性质.........................................................................................32 1.6.3二叉树的存储结构............................................................................................34 1.6.4二叉树的遍历...................................................................................................35 1.7 查找技术................................................................................................................36 1.7.1顺序查找..........................................................................................................37 1.7.2二分法查找.......................................................................................................37 1.8 排序技术................................................................................................................37 1.8.1交换类排序法...................................................................................................38 1.8.2插入类排序法...................................................................................................39 1.8.3选择类排序法...................................................................................................41 习 题 1.......................................................................................................................43 第2章 程序设计基础............................................................................................................45 2.1 程序设计方法与风格...............................................................................................45 2.2 结构化程序设针......................................................................................................46 2.2.1结构化程序设计的原则.....................................................................................46 2.2.2结构化程序设计的基本结构和特点....................................................................47
223结构化程序设计原则和方法的应用 23面向对象的程序设计 231关于面向对象方法 232面向对象方法的基本概念 习题2 第3章软件工程基础 3.1软件工程基本概念 3.1.1软件定义与软件特点 666 3.1.2软件危机与软件工程 3.1.3软件工程过程与软件生命周期 3.14软件工程的目标与原则 3.1.5软件开发工具与软件开发环境 3.2结构化分析方法 3.2.1需求分析与需求分析方法 3.22结构化分析方法 3.2.3软件需求规格说明书 3.3结构化设计方法 3.3.1软件设计的基本概念 3.32概要设计 3.33详细设计 34软件测试 341软件测试的目的 342软件测试的准则 48999 34.3软件测试技术与方法综述 344软件测试的实施 3.5程序的调试 3.51基本概念 3.52软件调试方法 习题3 第4章数据库设计基础 4.1数据厍系统的基本概念 4.1.1数据、数据库、数据库管理系统 4.1.2数据库系统的发展 41.3数据库系统的基本特点 41.4数据库系统的内部结构体系 4.2数据模型 42.1数据模型的基本概念 100 42.2E-R模型 101 42.3层次模型 105 4网状模型 105 42.5关系模型 106
2.2.3结构化程序设计原则和方法的应用....................................................................48 2.3面向对象的程序设计 ..................................................................................................48 2.3.1关于面向对象方法............................................................................................48 2.3.2面向对象方法的基本概念..................................................................................51 习 题 2.......................................................................................................................54 第3章 软件工程基础............................................................................................................56 3.1 软件工程基本概念..................................................................................................56 3.1.1软件定义与软件特点.........................................................................................56 3.1.2软件危机与软件工程.........................................................................................57 3.1.3软件工程过程与软件生命周期...........................................................................58 3.1.4软件工程的目标与原则.....................................................................................59 3.1.5软件开发工具与软件开发环境...........................................................................60 3.2 结构化分析方法......................................................................................................61 3.2.1 需求分析与需求分析方法................................................................................61 3.2.2结构化分析方法................................................................................................62 3.2.3软件需求规格说明书.........................................................................................66 3.3 结构化设计方法......................................................................................................67 3.3.1软件设计的基本概念.........................................................................................67 3.3.2概要设计..........................................................................................................70 3.3.3详细设计..........................................................................................................74 3.4 软件测试................................................................................................................78 3.4.1软件测试的目的................................................................................................79 3.4.2软件测试的准则................................................................................................79 3.4.3软件测试技术与方法综述..................................................................................79 3.4.4软件测试的实施................................................................................................86 3.5程序的调试 ................................................................................................................89 3.5.1基本概念..........................................................................................................89 3.5.2软件调试方法...................................................................................................90 习 题 3.......................................................................................................................92 第4章 数据库设计基础.........................................................................................................93 4.1 数据厍系统的基本概念...........................................................................................93 4.1.1数据、数据库、数据库管理系统.......................................................................93 4.1.2数据库系统的发展............................................................................................96 4.1.3数据库系统的基本特点.....................................................................................98 4.1.4数据库系统的内部结构体系..............................................................................99 4.2 数据模型..............................................................................................................100 4.2.1数据模型的基本概念.......................................................................................100 4.2.2E-R模型..........................................................................................................101 4.2.3层次模型........................................................................................................105 4.2.4网状模型........................................................................................................105 4.2.5关系模型........................................................................................................106
4.3关系代数 109 44数据厍设计与管理 44.1数据库设计概述 442数据库设计的需求分析 116 44.3数据库概念设计 l17 444数据库的逻辑设计 44.5数据库的物理设计 44.6数据库管理 122 习题 习题参考答案 习题1参考答案 习题2参考答案 125 习题3参考答案. 习题4参考答案
4.3 关系代数..............................................................................................................109 4.4 数据厍设计与管理................................................................................................ 115 4.4.1数据库设计概述.............................................................................................. 115 4.4.2数据库设计的需求分析................................................................................... 116 4.4.3数据库概念设计.............................................................................................. 117 4.4.4数据库的逻辑设计..........................................................................................120 4.4.5数据库的物理设计..........................................................................................122 4.4.6数据库管理.....................................................................................................122 习 题 4.....................................................................................................................123 习题参考答案 ......................................................................................................................125 习题1参考答案..............................................................................................................125 习题2参考答案..............................................................................................................125 习题3参考答案..............................................................................................................125 习题4参考答案..............................................................................................................125
第1章数据结构与算法 第1章数据结构与算法 1.1算法 11.1算法的基本概念 所谓算法是指解题方案的准确而完整的描述。 对于一个问题,如果可以通过一个计算机程序,在有限的存储空间内运行有限长的时间而 得到正确的结果,则称这个问题是算法可解的。但算法不等于程序,也不等于计算方法。当然, 程序也可以作为算法的一种描述,但程序通常还需考虑很多与方法和分析无关的细节问题,这 是因为在编写程序时要受到计算机系统运行环境的限制。通常,程序的编制不可能优于算法的 设计。 1算法的基本特征 作为一个算法,一般应具有以下几个基本特征 (1)可行性( effectiveness) 针对实际问题设计的算法,人们总是希望能够得到满意的结果。但一个算法又总是在某个 特定的计算工具上执行的,因此,算法在执行过程中往往要受到计算工具的限制,使执行结果 产生偏差。例如,在进行数值计算时,如果某计算工具具有7位有效数字(如程序设计语言中的 单精度运算),则在计算下列三个量 A=1012,B=1,C=-10 的和时,如果采用不同的运算顺序,就会得到不同的结果,即 A+B+C=1012+1+(-1012)=0 A+C+B=1012+(-1012)+1=1 而在数学上,A+B+C与A+C+B是完全等价的。因此,算法与计算公式是有差别的。在设 计一个算法时,必须要考虑它的可行性,否则是不会得到满意结果的 2)确定性( definiteness 算法的确定性,是指算法中的每一个步骤都必须是有明确定义的,不允许有模棱两可的解 释,也不允许有多义性。这一性质也反映了算法与数学公式的明显差别。在解决实际问题时, 可能会出现这样的情况:针对某种特殊问题,数学公式是正确的,但按此数学公式设计的计算 过程可能会使计算机系统无所适从。这是因为根据数学公式设计的计算过程只考虑了正常使用 的情况,而当出现异常情况时,此计算过程就不能适应了 (3)有穷性( finiteness 算法的有穷性,是指算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之 后终止。数学中的无穷级数,在实际计算时只能取有限项,即计算无穷级数值的过程只能是有 穷的。因此,一个数的无穷级数表示只是一个计算公式,而根据精度要求确定的计算过程才是 有穷的算法。 算法的有穷性还应包括合理的执行时间的含义。因为,如果一个算法需要执行千万年,显 然失去了实用价值 (4)拥有足够的情报 个算法是否有效,还取决于为算法所提供的情报是否足够。通常,算法中的各种运算总
第 1 章 数据结构与算法 1 第 1 章 数据结构与算法 1.1 算 法 1.1.1 算法的基本概念 所谓算法是指解题方案的准确而完整的描述。 对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而 得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。当然， 程序也可以作为算法的一种描述，但程序通常还需考虑很多与方法和分析无关的细节问题，这 是因为在编写程序时要受到计算机系统运行环境的限制。通常，程序的编制不可能优于算法的 设计。 1.算法的基本特征 作为一个算法，一般应具有以下几个基本特征。 (1)可行性(effectiveness) 针对实际问题设计的算法，人们总是希望能够得到满意的结果。但一个算法又总是在某个 特定的计算工具上执行的，因此，算法在执行过程中往往要受到计算工具的限制，使执行结果 产生偏差。例如，在进行数值计算时，如果某计算工具具有 7 位有效数字(如程序设计语言中的 单精度运算)，则在计算下列三个量 A=1012，B=1，C=-1012 的和时，如果采用不同的运算顺序，就会得到不同的结果，即 A+B+C=1012+1+(-1012)=0 A+C+B=1012+(-1012)+1=1 而在数学上，A+B+C 与 A+C+B 是完全等价的。因此，算法与计算公式是有差别的。在设 计一个算法时，必须要考虑它的可行性，否则是不会得到满意结果的。 (2)确定性(definiteness) 算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解 释，也不允许有多义性。这一性质也反映了算法与数学公式的明显差别。在解决实际问题时， 可能会出现这样的情况：针对某种特殊问题，数学公式是正确的，但按此数学公式设计的计算 过程可能会使计算机系统无所适从。这是因为根据数学公式设计的计算过程只考虑了正常使用 的情况，而当出现异常情况时，此计算过程就不能适应了。 (3)有穷性(finiteness) 算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之 后终止。数学中的无穷级数，在实际计算时只能取有限项，即计算无穷级数值的过程只能是有 穷的。因此，一个数的无穷级数表示只是一个计算公式，而根据精度要求确定的计算过程才是 有穷的算法。 算法的有穷性还应包括合理的执行时间的含义。因为，如果一个算法需要执行千万年，显 然失去了实用价值。 (4)拥有足够的情报 一个算法是否有效，还取决于为算法所提供的情报是否足够。通常，算法中的各种运算总
第1章数据结构与算法 是要施加到各个运算对象上,而这些运算对象又可能具有某种初始状态,这是算法执行的起点 或是依据。因此,一个算法执行的结果总是与输入的初始数据有关,不同的输入将会有不同的 结果输出。当输入不够或输入错误时,算法本身也就无法执行或导致执行有错。一般来说,当 算法拥有足够的情报时,此算法才是有效的,而当提供的情报不够时,算法可能无效。 综上所述,所谓算法,是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的 且是明确的,此顺序将在有限的次数下终止 2算法的基本要素 一个算法通常由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构 (1)算法中对数据的运算和操作 每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指 令序列。因此,计算机算法就是计算机能处理的操作所组成的指令序列 通常,计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有 指令的集合,称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中 选择合适的指令所组成的指令序列。在一般的计算机系统中,基本的运算和操作有以下四类 ①算术运算:主要包括加、减、乘、除等运算 ②逻辑运算:主要包括“与”、“或”、“非”等运算 ③关系运算:主要包括“大于”、“小于”、“等于”、“不等于”等运算 ④数据传输:主要包括赋值、输入、输出等操作。 前面提到,计算机程序也可以作为算法的…种描述,但由于在编制计算机程序时通常要考 虑很多与方法和分析无关的细节问题(如语法规则,因此,在设计算法的一开始,通常并不直 接用计算机程序来描述算法,而是用别的描述工具(如流程图,专门的算法描述语言,甚至用自 然语言)来描述算法。但不管用哪种工具来描述算法,算法的设计一般都应从上述四种基本操作 考虑,按解题要求从这些基本操作中选择合适的操作组成解题的操作序列。算法的主要特征着 重于算法的动态执行,它区别于传统的着重于静态描述或按演绎方式求解问题的过程。传统的 演绎数学是以公理系统为基础的,问题的求解过程是通过有限次推演来完成的,每次推演都将 对问题作进一步的描述,如此不断推演,直到直接将解描述出来为止。而计算机算法则是使用 些最基本的操作,通过对已知条件一步一步的加工和变换,从而实现解题目标。这两种方法 的解题思路是不同的 (2)算法的控制结构 一个算法的功能不仅取决于所选用的操作,而且还与各操作之间的执行顺序有关。算法中 各操作之间的执行顺序称为算法的控制结构 算法的控制结构给出了算法的基本框架,它不仅决定了算法中各操作的执行顺序,而且也 直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化 程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而 3算法设计基本方法 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。计算机算法不同 于人工处理的方法 本节介绍工程上常用的几种算法设计方法,在实际应用时,各种方法之间往往存在着一定 的联系。 (1)列举法
第 1 章 数据结构与算法 2 是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这是算法执行的起点 或是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的 结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。一般来说，当 算法拥有足够的情报时，此算法才是有效的，而当提供的情报不够时，算法可能无效。 综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的， 且是明确的，此顺序将在有限的次数下终止。 2.算法的基本要素 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。 (1)算法中对数据的运算和操作 每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指 令序列。因此，计算机算法就是计算机能处理的操作所组成的指令序列。 通常，计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有 指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中 选择合适的指令所组成的指令序列。在一般的计算机系统中，基本的运算和操作有以下四类： ①算术运算：主要包括加、减、乘、除等运算。 ②逻辑运算：主要包括“与”、“或”、“非”等运算。 ③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。 ④数据传输：主要包括赋值、输入、输出等操作。 前面提到，计算机程序也可以作为算法的…种描述，但由于在编制计算机程序时通常要考 虑很多与方法和分析无关的细节问题(如语法规则)，因此，在设计算法的一开始，通常并不直 接用计算机程序来描述算法，而是用别的描述工具(如流程图，专门的算法描述语言，甚至用自 然语言)来描述算法。但不管用哪种工具来描述算法，算法的设计一般都应从上述四种基本操作 考虑，按解题要求从这些基本操作中选择合适的操作组成解题的操作序列。算法的主要特征着 重于算法的动态执行，它区别于传统的着重于静态描述或按演绎方式求解问题的过程。传统的 演绎数学是以公理系统为基础的，问题的求解过程是通过有限次推演来完成的，每次推演都将 对问题作进一步的描述，如此不断推演，直到直接将解描述出来为止。而计算机算法则是使用 一些最基本的操作，通过对已知条件一步一步的加工和变换，从而实现解题目标。这两种方法 的解题思路是不同的。 (2)算法的控制结构 一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中 各操作之间的执行顺序称为算法的控制结构。 算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也 直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S 结构化 流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而 成。 3.算法设计基本方法 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。计算机算法不同 于人工处理的方法。 本节介绍工程上常用的几种算法设计方法，在实际应用时，各种方法之间往往存在着一定 的联系。 (1)列举法
第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)所示的有序表中进行查找。由于有序表中的元素是从小到大进行排