大学计算机基础-04-算法分析与设课件.ppt

1、第第4 4章章 算法分析与设计算法分析与设计4.1 算法的基本概念算法的基本概念4.2 算法策略算法策略4.3 基本算法基本算法4.1 4.1 算法算法的基本概念的基本概念4.1.1 算法定义与性质算法定义与性质 人们使用计算机，就是要利用计算机处理各种不同的问题，而要做到这一点，人们就必须事先对各类问题进行分析，确定解决问题的具体方法和步骤，再编制好一组让计算机执行的指令，即程序，交给计算机，让计算机按人们指定的步骤有效地工作。 这些让计算机工作的具体方法和步骤，其实就是解决一个问题的算法。算法是一组明确步骤地有序集合，它产生结果并在有限时间内终止。4.1 4.1 算法算法的基本概念的基本概

2、念一个算法必须具备以下性质： 确定性。算法中每一个步骤都必须是确切定义的，不能产生二义性。 可行性。算法必须是由一系列具体步骤组成的，并且每一步都能被计算机所理解和执行。 有穷性。一个算法必须在执行有穷步后结束，每一步必须在有穷的时间内完成。 输入。一个算法可以有零个或多个输入，这取决于算法要实现的功能。 输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。4.1 4.1 算法算法的基本概念的基本概念对算法的学习包括5个方面的内容： 设计算法 表示算法 确认算法 分析算法 验证算法4.1 4.1 算法算法的基本概念的基本概念4.1.2 设计算法原则和过程设

3、计算法原则和过程 对于一个特定问题的算法在大部分情况下都不是唯一的。也就是说，同一个问题，可以有多种解决问题的算法，而对于特定的问题、特定的约束条件，相对好的算法还是存在的。因此，在特定问题、特定的条件下，选择合适的算法，会对解决问题有很大帮助；否则前人的智慧我们不能借鉴，凡事就都得自己从头研究了，这就是所谓的要去“发明轮子（Invent the wheel）”。4.1 4.1 算法算法的基本概念的基本概念在设计算法时，通常应考虑以下原则：（1）正确性 算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。算法的“正确”通常在用法上有很大的

4、差别，大体分为四个层次。算法程序没有语法错误。算法程序能够根据正确的输入的值得到满足要求的输出结果。算法程序能够根据错误的输入的值得到满足规格说明的输出结果。算法程序对于精心设计的、极其刁难的测试数据都能满足要求的输出结果。4.1 4.1 算法算法的基本概念的基本概念 对于这四层含义，第层次要求最低，因为仅仅没有语法错误实在谈不上是好算法。而第层次是最困难的，我们几乎不可能逐一验证所有的输入都得到正确的结果。 因此，算法的正确性在大部分情况下都不可能用程序来证明，而是用数学方法证明的。证明一个复杂算法在所有层次上都是正确的，代价非常昂贵。所以一般情况下，我们把层次作为一个算法是否正确的标准。4

5、.1 4.1 算法算法的基本概念的基本概念（2）可读性 设计算法的目的，一方面是为了让计算机执行，但还有一个重要的目的是为了便于他人阅读，让人理解和交流，自己将来也可能阅读。如果可读性不好，时间长了自己都不知道写了些什么。可读性是评判算法（也包括实现它的程序代码）好坏很重要的标志。可读性不好不仅无助于人们理解算法，晦涩难懂的算法往往隐含错误，不易被发现并且难于调试和修改。4.1 4.1 算法算法的基本概念的基本概念（3）健壮性 当输入的数据非法时，算法应当恰当地做出反应或进行相应处理，而不是产生莫名其妙的输出结果。并且处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以

6、便在更高的抽象层次上进行处理.（4）高效率与低存储量 通常，算法的效率指的是算法的执行时间；算法的存储量指的是算法执行过程中所需的最大存储空间，两者的复杂度都与问题的规模有关。算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性。4.1 4.1 算法算法的基本概念的基本概念4.1.3 算法的基本表达算法的基本表达 算法是对问题求解过程的清晰表述，通常可以采用自然语言、流程图、伪代码等多种不同的方法来描述，目的是要清晰地展示问题求解的基本思想和具体步骤。（1）算法的自然语言描述 自然语言就是人们日常使用的语言，可以使用汉语、英语或其他语言等。用自然语

7、言表示通俗易懂，但文字冗长，表示的含义往往不太严格，要根据上下文才能判断其正确含义，容易出现歧义性。 此外，用自然语言来描述包含分支和循环的算法，不很方便，因此除了那些简单的问题以外，一般不用自然语言描述算法。4.1 4.1 算法算法的基本概念的基本概念（2）算法的流程图描述 流程图使用一些图框来表示各种操作。用流程图来描述问题的解题步骤，可使算法十分明确、具体直观、易于理解。美国国家标准化协会ANSI（American National Standard Institute）规定了一些常用的流程图符号。 流程图将解决问题的详细步骤用特定的图形符号表示，中间再画线连接以表示处理的流程，流程图比

8、文字方式更能直观地说明解决问题的步骤，可使人快速准确地理解并解决问题。4.1 4.1 算法算法的基本概念的基本概念 用流程图表示算法直观形象，比较清楚地显示出各个框之间的逻辑关系。但这种流程图占用篇幅较多，尤其当算法比较复杂时，画流程图既费时又不方便。在结构化程序设计方法推广之后，经常采用N-S结构化流程图代替传统的流程图。 N-S流程图是一种适于结构化程序设计的流程图。在N-S流程图中，完全去掉了带箭头的流程线，全部算法写在一个矩形框内，在该框内可以包含其它从属于它的框，或者说，由一些基本的框组成一个大的框。4.1 4.1 算法算法的基本概念的基本概念（3）算法的伪代码描述 用传统的流程图和

9、N-S流程图表示算法直观易懂，但画起来都比较费事。在设计一个算法过程中，因为涉及到需要对算法反复修改，所以用流程图表示算法不是很理想（每修改一次算法，就要重新画流程图）。 为了设计算法时的方便，常用一种称为伪代码的工具。 伪代码是用介于自然语言和程序设计语言之间的文字和符号来描述算法。伪代码不使用图形，在书写上方便，格式紧凑，比较好懂，不仅适宜设计算法过程，也便于向计算机语言算法（即程序）过渡。4.1 4.1 算法算法的基本概念的基本概念（4）用计算机语言表示算法 设计算法的目的是为了实现算法。因为是用计算机解题，也就是要用计算机实现算法，因此在用流程图或伪代码描述一个算法后，还要将它转换成计

10、算机语言编写的程序才能被计算机执行。用计算机语言表示的算法是计算机能够执行的算法。 用计算机语言表示算法必须严格遵循所用的语言的语法规则，这是和伪代码不同的。4.2 4.2 算法策略算法策略 算法策略就是在问题空间中随机搜索所有可能的解决问题的方法，直至选择一种有效的方法解决问题。所有算法策略的中心思想就是用算法的基本工具（循环机制和递归机制）实现算法。按照问题求解策略来分，算法有枚举法、递归法、回溯法、分治法等。4.1 4.1 算法算法的基本概念的基本概念4.2.1 枚举法枚举法 枚举法也叫穷举法、列举法、蛮力法，它既是一个策略，也是一个算法，也是一个分析问题的手段。枚举法算法的实现依赖于循

11、环，通过循环嵌套，枚举问题中各种可能的情况。 枚举法的求解思路很简单，就是对所有可能的解逐一尝试，从而找出问题的真正解。这就要求所求解的问题可能有的解是有限的、固定的、容易枚举的、不会产生组合爆炸的。 枚举法的解题思路常常直接基于问题的描述，所以它是一种简单而直接地问题求解的方法，多用于决策类问题，这类问题都不易进行问题的分解，只能整体来求解。4.1 4.1 算法算法的基本概念的基本概念 枚举法的基本思想是依题目的部分条件确定答案的大致范围，在此范围内对所有可能的情况逐一验证，直到全部情况验证完。若某个情况经过验证符合题目的全部条件，则为本题的一个答案。若全部情况经过验证后都不符合题目的全部条

12、件，则本题无解。 用枚举法解题时，答案所在范围总要求是有限的，关键是怎样才能不重复、一个不漏、一个不增地逐个列举答案所在范围的所有情况。由于计算机的运算速度快，擅长重复操作，很容易完成大量的枚举。 枚举法是计算机算法中的一个基础算法，所设计出来的算法其时间性能往往是最低的。4.1 4.1 算法算法的基本概念的基本概念 枚举法的基本思想是依题目的部分条件确定答案的大致范围，在此范围内对所有可能的情况逐一验证，直到全部情况验证完。若某个情况经过验证符合题目的全部条件，则为本题的一个答案。若全部情况经过验证后都不符合题目的全部条件，则本题无解。 用枚举法解题时，答案所在范围总要求是有限的，关键是怎样

13、才能不重复、一个不漏、一个不增地逐个列举答案所在范围的所有情况。由于计算机的运算速度快，擅长重复操作，很容易完成大量的枚举。4.1 4.1 算法算法的基本概念的基本概念4.2.2 递归法递归法 直接或间接地调用自身的算法称为递归算法。 递归 法是利用大问题与其子问题间的递归关系来解决问题的。能采用递归描述的算法通常有这样的特征：为了求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解很方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。4.1 4.1

14、算法算法的基本概念的基本概念4.2.3 分治法分治法 分治法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同，求出子问题的解，就可得到原问题的解。在设计上，就是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 当K=2时的分治法又称二分法。4.2.24.2.2 递归法递归法直接或间接地调用自身的算法称为递归算法。递归法是利用大问题与其子问题间的递归关系来解决问题的。能采用递归描述的算法通常有这样的特征：为了求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解很方便地构造出大问题的解，并且这些规模

15、较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。4.1 4.1 算法算法的基本概念的基本概念利用分治法求解的问题，应同时满足以下4个要求：（1）原问题在规模缩小到一定程度时可以很容易地求解（2）原问题可以分解为若干个规模较小的同构子问题（3）各子问题的解可以合并为原问题的解（4）原问题所分解出的各个子问题之间是相互独立的4.2.24.2.2 递归法递归法直接或间接地调用自身的算法称为递归算法。递归法是利用大问题与其子问题间的递归关系来解决问题的。能采用递归描述的算法通常有这样的特征：为了求解规模为N的

16、问题，设法将它分解成规模较小的问题，然后从这些小问题的解很方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。4.1 4.1 算法算法的基本概念的基本概念利用分治法求解问题的算法通常包含以下几个步骤：（1）分解 将原问题分解为若干个相互独立、规模小且与原问题形式相同的一系列子问题，最好使各子问题的规模大致相同。（2）解决 如果子问题规模小到可以直接被解决则直接求解，否则需要递归地求解各个子问题。（3）合并 将各个子问题的结果合并成原问题的解。有些问题的合并方法比较明显，

17、有些问题的合并方法比较复杂，或者存在多种合并方案；也有些问题的合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。4.2.24.2.2 递归法递归法直接或间接地调用自身的算法称为递归算法。递归法是利用大问题与其子问题间的递归关系来解决问题的。能采用递归描述的算法通常有这样的特征：为了求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解很方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。4.1 4.1 算法算法的基本概念的基本概念分

18、治策略的解题思路：if(问题不可分) 直接求解；返回问题的解；Else 对原问题进行分治；递归对每一个分治的部分求解；归并整个问题，得出全问题的解；4.2.24.2.2 递归法递归法直接或间接地调用自身的算法称为递归算法。递归法是利用大问题与其子问题间的递归关系来解决问题的。能采用递归描述的算法通常有这样的特征：为了求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解很方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。4.1 4.1 算法算法的基本概

19、念的基本概念4.2.4 回溯法回溯法 回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 回溯法通过递归尝试走完问题的各个可能解的通路，发现此路不通时回溯到上一步继续尝试别的通路，是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。 算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根

20、的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。直到根结点的所有子树都已被搜索遍才结束。4.2.24.2.2 递归法递归法直接或间接地调用自身的算法称为递归算法。递归法是利用大问题与其子问题间的递归关系来解决问题的。能采用递归描述的算法通常有这样的特征：为了求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解很方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。4.1 4.1 算法算法的基本概念的基本概念用回溯法

21、解题的一般步骤： 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解； 确定易于搜索的解空间结构，使得能用回溯法方便地搜索整个解空间； 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。4.2.24.2.2 递归法递归法直接或间接地调用自身的算法称为递归算法。递归法是利用大问题与其子问题间的递归关系来解决问题的。能采用递归描述的算法通常有这样的特征：为了求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解很方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别

22、地，当规模N=1时，能直接得解。4.1 4.1 算法算法的基本概念的基本概念通过深度优先搜索思想完成回溯的完整过程如下：（1）设置初始化的方案（给变量赋初值，读入已知数据等）；（2）变换方式去试探，若全部试完则转（7）；（3）判断此法是否成功（通过约束函数），不成功则转（2）；（4）试探成功则前进一步再试探；（5）正确方案还未找到则转（2）；（6）已找到一种方案则记录并打印；（7）退回一步（回溯），若未退到头则转（2）；（8）已退到头则结束，或打印无解。4.2.24.2.2 递归法递归法直接或间接地调用自身的算法称为递归算法。递归法是利用大问题与其子问题间的递归关系来解决问题的。能采用递归描述

23、的算法通常有这样的特征：为了求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解很方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。4.3 4.3 基本算法基本算法4.3.1 基础知识基础知识 算法实际上就是用计算机解决某个问题的方法和步骤。对某一类问题的解决，有很多解决的方法，因此，同一个问题的程序设计，针对不同的算法可能编写出不同的程序，本节中介绍的只是对某类问题的通用算法思想。 另外，算法的设计不针对某一个具体的问题，希望大家在学习时，不要仅满

24、足掌握相关例题的程序设计，而要学习算法的基本思想，学会以后遇到类似的问题时能运用该思想来解决问题。4.3 4.3 基本算法基本算法1累加算法累加算法 累加是程序设计中最常遇见的问题，比如求某单位职工的所有工资总和、某门课程的所有学生成绩总和等。 累加算法的一般做法是定义一个变量 s，作为累加器使用，往往初值为0，再定义一个变量用来保存加数。一般在累加算法中的加数都是有规律可循，可结合循环程序来实现。 由前面可知，一个循环程序的算法设计，如果以下三方面确定下来：变量的赋初值、循环体的内容、循环结束条件，那么根据循环语句的格式，就很容易写出相应的循环算法。4.3 4.3 基本算法基本算法1累加算法

25、累加算法 累加是程序设计中最常遇见的问题，比如求某单位职工的所有工资总和、某门课程的所有学生成绩总和等。 累加算法的一般做法是定义一个变量 s，作为累加器使用，往往初值为0，再定义一个变量用来保存加数。一般在累加算法中的加数都是有规律可循，可结合循环程序来实现。 由前面可知，一个循环程序的算法设计，如果以下三方面确定下来：变量的赋初值、循环体的内容、循环结束条件，那么根据循环语句的格式，就很容易写出相应的循环算法。4.3 4.3 基本算法基本算法求解此类问题的基本步骤，可以概括如下： 定义代表和的变量s，定义代表第n项的变量t； 令s=0； 构建循环体，一般情况下为s=s+t； 构建循环条件，

26、根据问题的具体要求，选用相应的循环语句； 输出累加和s的值。说明：上述算法对数值型数据，执行的是累加操作，但如果用于字符串型数据，完成的则是字符串的连接。4.3 4.3 基本算法基本算法求解此类问题的基本步骤，可以概括如下： 定义代表和的变量s，定义代表第n项的变量t； 令s=0； 构建循环体，一般情况下为s=s+t； 构建循环条件，根据问题的具体要求，选用相应的循环语句； 输出累加和s的值。说明：上述算法对数值型数据，执行的是累加操作，但如果用于字符串型数据，完成的则是字符串的连接。 如果需要实现字符串的连接，定义一个字符串型变量s作为字符连接器，一般赋初值为（空串），变量t作为被连接的字符

27、，则在循环体中执行s=s+t时完成的就是字符串的顺序连接。4.3 4.3 基本算法基本算法2连乘算法连乘算法 连乘算法和累加算法的思想类似，只不过一个做乘法，一个做加法。 连乘算法的一般做法是设一个变量p，作为累乘器使用，初值一般为1，设一个变量k用来保存每次需要乘的乘数，在循环体中执行p=p*k的语句即可。4.3 4.3 基本算法基本算法2连乘算法连乘算法 连乘算法和累加算法的思想类似，只不过一个做乘法，一个做加法。 连乘算法的一般做法是设一个变量p，作为累乘器使用，初值一般为1，设一个变量k用来保存每次需要乘的乘数，在循环体中执行p=p*k的语句即可。4.3 4.3 基本算法基本算法3统计

28、算法统计算法 统计问题在程序设计中也是经常遇到的。求解此类问题的基本步骤，概括如下： 定义代表所有统计要求的计数器变量（有几项统计要求，就有几个计数器变量）； 令所有计数器变量的初值为0； 构建循环体，当满足指定的计数要求时，就将相应的计数器的值加1（执行类似于n=n+1的操作）； 构建循环条件，根据问题的具体要求，选用相应的循环语句。 输出所有计数器的值4.3 4.3 基本算法基本算法4求最大值和最小值算法求最大值和最小值算法 求最大值和最小值的问题，属于比较问题，是我们在生活中经常做的事情。比如，找出班上同学中个子最高的同学、年龄最大的同学，若干件商品中价格最低的商品等等，通常采用的方法是

29、两两比较。4.3 4.3 基本算法基本算法求解此类问题的基本步骤，可以概括如下： 定义x代表N个数中的1个数； 定义一个存放最大值的变量max，定义一个存放最小值的变量min； 分别令max=所有数据中的第1个数，min=所有数据中的第1个数； 构建循环体， 将x与max比较，如果x比max大，令max=x； 将x与min比较，如果x比min小，令min=x。 构建循环条件，根据问题的具体要求，选用相应的循环语句； 输出max和min的值。4.3 4.3 基本算法基本算法4.3.2 排序排序 所谓排序，就是将一组相同类型的记录序列调整为按照元素关键字有序（递增或递减）的记录序列。 排序算法就是

30、如何使得记录按照要求进行排列的方法。当数据不多时，排序比较简单，有时手工可以处理。但若排序对象的数据量庞大，排序就成为一件非常重要且费时的事情。考虑到在各个领域中数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析，在大量数据的处理方面，一个优秀的排序算法可以节省大量的资源。4.3 4.3 基本算法基本算法1选择法排序选择法排序 选择排序是一种简单的容易实现的排序方法。 基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在已排好序的序列的最后（也可以视为待排序序列的起始位置），直到全部待排序的数据元素排完。4.3 4.3 基本算法基本算法2冒泡法排序冒

31、泡法排序 冒泡排序是一种计算机科学领域的较简单的排序算法。 通过序列中相邻元素之间队交换，使较小的元素逐步从序列的后端移到序列的前端，使较大的元素从序列的前端移到后端。它的执行过程有点像在水中气泡的运动，轻的往上浮，重的往下沉，因此人们形象地称这种排序方法为“冒泡排序”。 冒泡排序法主要是比较相邻两个元素的值，如果前面的数比后面的数大，就执行一次交换，这样就可以在每一趟的比较中都产生了本趟的最大值。4.3 4.3 基本算法基本算法3插入排序插入排序 插入排序是一种简单直观的排序算法。适用于少量数据的排序，是一种稳定的排序方法。 基本思想是：将记录分为有序和无序两个序列，假定当插入第k个记录时，

32、前面的R1，R2，Rk-1已经排好序，而后面的Rk，Rk+1，Rn仍然无序，这时用Rk的关键字与Rk-1的关键字进行比较，若Rk小于Rk-1，则将Rk-1向后移动一个单元；再用Rk的关键字与Rk-2的关键字进行比较，若Rk小于Rk-2，则将Rk-2向后移动一个单元；依次比较下去，直到找到插入位置将Rk插入。初始状态认为有序序列为 R1。4.3 4.3 基本算法基本算法插入排序的操作步骤描述如下：对于待排序的一个序列，先把它的第1个记录按顺序排好（实际上是直接取第1个记录作为已经排好的序列，因为一个记录的顺序总是正确的）；取出下一个记录，在已经有序的序列中从后向前扫描；如果有序序列中的记录大于新

33、记录，则将有序序列中的记录移到下一个位置；重复步骤，直到找到有序序列中的记录小于新记录的位置j；将新记录插入到j+1位置上；重复步骤。4.3 4.3 基本算法基本算法4.3.3 查找查找 查找也称为检索，它是在较大的数据集中找出或定位某些数据的过程，即在大量的信息中寻找一个特定的信息元素，在计算机中进行查找的方法是根据表中的记录的组织结构确定的，被用于查找的数据元素的属性一般称为关键字。 查找表即查找集合，是为了进行查找而建立起来的数据结构，集合中元素的存储结构可以是顺序结构，也可以是树状结构或图结构。4.3 4.3 基本算法基本算法 在查找的时候，若随着查找的进行，查找表的长度是固定的，即保

34、持初始元素个数不变，就是静态查找，静态查找的查找表以顺序存储结构为主，这样的查找表称为静态查找表，所对应的查找算法属于静态查找技术。 若随着查找的进行，查找表的内容会动态地扩张或缩小，那就是动态查找，动态查找以树状结构居多，这样的查找表称为动态查找表，所对应的查找算法属于动态查找技术。4.3 4.3 基本算法基本算法下面介绍基于顺序结构的两种常用查找方法。1顺序查找顺序查找 顺序查找也称为线性查找，是一种最简单的查找方法，可用于有序列表，也可用于无序列表。其基本思想是：从查找表（数据结构线性表）的一端开始，顺序扫描线性表，依次将扫描到的结点关键字与给定值key相比较，若当前扫描到的结点关键字与

35、key相等，则表示查找成功；若扫描结束后，没有找到关键字等于key的结点，表示查找失败。4.3 4.3 基本算法基本算法2折半查找折半查找 折半查找又称二分查找，是在一个有序的元素列表中查找特定值的一种方法，该顺序可能是升序，也可能是降序，是一种效率较高的查找方法。 算法思想：假设表中元素是按升序排列的，将表中间位置记录的关键字与要查找的关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录使查找成功，或直到子表不存在为止（即表中不存在这个关键字），此时查找不成功。