《大学计算机基础(第四版)-5.pptx》由会员分享，可在线阅读，更多相关《大学计算机基础(第四版)-5.pptx（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编者：何振林联系方式：Tel：13908045104目录 教师在讲解时，可重点介绍第 1、2、3、4、6、7和8章，第5、9章部分内容自学。第2章 Windows 7操作系统的使用第3章 计算机网络与应用第4章 信息的编码与存储第5章 算法与实现第7章 电子表格软件Excel 2010第9章 Access数据库技术基础第6章 文字处理软件Word 2010第1章 计算机基础知识第8章 演示文稿软件PowerPoint 2010第5章 算法与实现 算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一
2、定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。本章将学习算法的一些基本概念和实现算法的Raptor流程图程序设计工具。5.1 算法5.2 程序设计概述5.3 结构化程序设计本本章章目目录录5.4 面向对象程序设计5.5 Raptor流程图编程基础5.1 算法 算法（Algorithm）是对解决某一特定问题的操作步骤的具体描述。简单地说就是解决一个问题而采取的方法和步骤。例如上网探索信息，首先选择一家ISP运营商，如电信。
3、交纳一定的上网费，领取一个“猫”，这就是我们通常使用的ASDL上网方式。接下来工作人员会给建立一个上网连接方式（需要账户和密码），再点击IE浏览器，就可以上网了。这些步骤都按一定的次序，缺一不可，次序错了也不行。算法是描述计算机解决给定问题的有明确意义操作步骤（指令）有有限集合。计算机算法一般可分为数值计算算法和非数值计算算法。数值计算算法就是对所给的问题求数值解，如求函数的极限、求方程的根等；非数值计算算法主要是指对数据的处理，如对数据的排序、分类、查找及文字处理、图形图像处理等。算法不等于程序，也不等计算机方法，程序的不可能优于算法的设计。5.1.1 算法的基本概念 5.1.2 算法的基本
4、特征 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。一个算法应该具有以下5个重要的特征：5.1.3 算法的表示 （1）有穷性：一个算法必须保证执行有限步之后结束。在执行有限步之后，计算必须终止，并得到解答。也就是说一个算法的实现应该在有限的时间内完成。（2）确定性：算法的每一步骤必须有确定的定义。算法中对每个步骤的解释是唯一的。（3）零个或多个输入：输入指在执行算法时需要从外界取得的必要的信息。一个算法有零个或多个输入，以刻画运算对象的初始情况。一个算法可以没有输入。（4）一个或多个输出：输出是算法的执行结果。一个算法有一个或多个输
5、出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。（5）可行性。算法中的每一个步骤能够精确地运行，并得到确定的结果。而且人们用笔和纸做有限次运算后即可完成。算法的描述应直观、清晰、易懂、便于维护和修改。描述算法的方法有多种常用的表示方法有自然语言、传统流程图、N-S图、PAD图、伪代码和计算机语言等。其中最常用的是传统流程图和N-S图。1自然语言 自然语言（Natural language）就是人们日常使用的语言，因此，用自然语言表示一个算法便于人们理解。【例5-1】用自然语言描述求业主交物业费。住房面积90平方米以内的部分（含90平方米），每平方米收费1.8元；住房面积超90平方
6、米的部分，每平方米收费2元。输入住房面积，输出应付的物业费。用S表示住房面积，以M表示应交的物业费，其算法如下：输入S的值；如果S90，则MS1.8；否则，MS1.8（S90）2；输出M的值。用自然语言表示算法，容易表达，也易于理解，但文字冗长且模糊，表示复杂算法时不直观，容易产生“二义性”，叙述不直观。因此，除了很简单的问题以外，一般不用自然语言表示算法。2传统流程图 流程图是用一些图形符号、箭头和简要的文字说明来表示算法的框图，它能清晰明确地表示程序的运行过程。用流程图表示算法的优点是直观形象、易于理解，能将设计者的思路清楚地表达出来，便于以后检查修改和编程。程序流程图表示程序中的操作顺序
7、。传统流程图包括：指明实际处理操作的处理符号，它包括根据逻辑条件确定要执行的路径的符号；指明控制流的流线符号；便于读、写程序流程图的特殊符号。表5-1是用传统流程图描述算法时常用的符号。通常在各种图符中加上简要的文字说明，以进一步表明该步骤所要完成的操作。表5-1 流程图常用符号 用流程图描述算法时，流程图的描述可粗可细，总的原则是：根据实际问题的复杂性，流程图达到的最终效果应该是，依据此图就能用某种程序设计语言实现相应的算法（即完成编程）。起止框：表示流程开始中结束。表示流程开始或结束。输入/输出框：表示输入或输出。处理框：表示对基本处理功能的描述。判断框：根据条件是否满足，在几个可以选择的
8、路径中，选择某一路径。流向线：表示流程的路径和方向。连接点：用于将画在不同地方的流程连接起来。【例5-2】求一元二次方程 的根。算法分析：首先，定义三个变量a、b、c，将三个数依次输入到a、b、c中，另外，再准备一个delta表示要求出的差别式，r和s分别表示-b/2a 和sqrt(abs(delta)/2a的大小。算法分析的流程图，如图5-1所示。（1）开始，并输入系数a的值。（2）判断系数a的值是否为0，是则重新输入。（3）并输入系数b和c的值。（4）求判别式 （5）判断delta是否大于或等于0。如果delta0，则执行步骤6，否则执行步骤7。（6）如果delta0，求出r=-b/2a，
9、s=sqrt(delta)/2a，输出r+s和r-s。（7）如果delta0，求出r=-b/2a，s=sqrt(-delta)/2a，输出r+si和r-si。（8）结束。图5-1 求一元二次方程 的根的传统流程图3N-S图 传统流程图直观，对流程线的使用没有限制，使流程转来转去，破坏了程序结构，给阅读和维护带来困难。随着结构化程序设计方法的出现，美国学者I.Nassi和B.Shneiderman于1973年提出了一种新的流程图，其主要特点是不带流程线，算法的每一步都用一个矩形框来描述，把一个个矩形框按执行的次序连接起来就是一个完整的算法描述。这种流程图以两位学者名字的第一个字母来命名，称为N-
10、S流程图。N-S图的优点如下：（1）强制设计人员按SP方法（SP方法即结构化程序设计方法）进行思考并描述设计方案，因为除了表示几种标准结构的符号之处，它不再提供其他描述手段，保证了设计的质量；（2）N-S图形象直观，具有良好的可见度。例如循环的范围、条件语句的范围都是一目了然的，所以容易理解设计意图，为编程、复查、选择测试用例、维护都带来了方便；（3）NS图简单、易学易用，可用于软件教育和其他方面。N-S图的缺点：手工修改比较麻烦，这是有些人不用它的主要原因。图5-2 三种程序结构的N-S图 【例5-3】输入三个数，然后输出其中最大的数。首先，定义三个变量a、b、c，将三个数依次输入到a、b、
11、c中，另外，再准备一个max表示要求出的最大数。由于计算机一次只能比较两个数，我们首先把a与b比，大的数放入max中，再把max与c比，又把大的数放入max中。最后，把max输出，此时max中装的就是a、b、c三数中最大的一个数。算法可以表示如下：输入a、b、c。若ab，则maxa；否则maxb。若cmax，则maxc。输出max，max即为最大数。求解三个数中最大数的N-S图，如图5-3所示。图5-3 求解三个数中最大数的N-S图4PAD图 PAD（Problem Analysis Diagram）自1974年由日本的二村良彦等人提出，用结构化程序设计思想表现程序逻辑结构的图形工具。），是近
12、年来在软件开发中被广泛使用的一种算法的图形表示法。PAD图的优点：流程图、N-S图都是自上而下的顺序描述，而PAD图除了自上而下以外，还有自左向右的展开。所以，PAD图能展现算法的层次结构，直观易懂。下面是PAD的几种基本形态：图5-4顺序结构的PAD图图5-5 选择结构的PAD图图5-6 循环结构的PAD图 PAD图的图形元素，如表5-2所示。【例5-4】画出例5-3的PAD图。例5-4的PAD图，如图5-7所示。表5-2 PAD表示的控件结构图5-7 例5-3的PAD图 【例5-5】某序列的第一项为0，第二项为1，以后的奇数项为其前两项之和；偶数项为其前两项之差。画出求解该序列的前50项的
13、PAD图。分析：设序列的第一项用S1表示，且S1=0；第二项用S2表示，且S2=1。然后生成序列的第三项S3、第四项S4等，生成一项输出一项。在生成序列一项时要考虑该项是偶数项还是奇数项。该序列项（用W表示）生成的规律如下：图5-8 输出序列的PAD求解图 本例求解过程的PAD图，如图5-8所示。伪代码（Pseudocode）是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言实现，如Pascal、C、Java等。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。介于自然语言与编程语言之间。用伪代码写出的算法很容易修改。但是用伪代码写的算法不如流程
14、图直观，可能会出现逻辑上的错误。在伪代码中，每一条指令占一行（elseif，例外）。指令后不跟任何符号（Pascal和C中语句要以分号结尾）。伪代码只是像流程图一样用在程序设计的初期，帮助写出程序流程。比如：ElseIf 9点到17点 then 工作；Else 下班；Endif 这样不但可以达到文档的效果，同时可以节约时间。更重要的是，使结构比较清晰，表达方式更加直观。用伪代码写算法并无固定的、严格的语法规则，只要把意思表达清楚，并且书写的格式要写成清晰易读的形式。5伪代码 【例5-6】使用伪代码描述n！的算法。使用伪代码描述n！的算法过程如下。BEGIN /*算法开始*/输入 n 的值；i
15、1；/*为变量 i 赋初值*/f 1；/*为变量 f 赋初值*/while i=n /*当变量 i=n 时，执行下面的循环体语句*/f f*i；i i+1；输出 sum 的值；END /*算法结束*/6计算机语言 可以利用某种计算机语言对算法进行描述，计算机程序就是算法的一种表示方式。【例5-7】用Visual Basic语言描述例5-5的求解过程。5.1.4 算法设计中的基本方法 常用的算法设计基本方法如下：1列举法 列举法（Enumeration Method，或穷举法）是根据其要解决的问题，逐一列举各种可能的情况，并判断每种情况是否满足题设条件。这种方法的好处是最大限度考虑了各种情况，为
16、求出最优解创造条件，但工作量很大。【例5-8】百钱百鸡问题。中国古代数学家张丘建在他的算经中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何（每种鸡至少买回一只）?问题分析与算法设计：这是一个典型的数值型问题，我们要首先建立这个问题的数学模型，数学模型也就是我们平时说的数学方程。假设：我们要买x只公鸡，y只母鸡，z只小鸡，根据题目的意思可以得到两个方程：根据题目，可以确定x、y、z的取值范围：1x、y、z100。采用列举法进行求解。对于变量x,y,z的不同组合，看它们是否满足上面的两个方程，如果满足了，就是问题的一个解。否则就不是问题的
17、解。我们可以采用三重嵌套的循环对变量x，y，z进行组合，如下面的VB程序。（略）2归纳法 归纳法（Induction）是一种由个别到一般的论证方法。它通过许多个别的事例或分论点，然后归纳出它们所共有的特性，从而得出一个一般性的结论。通过观察一些简单而特殊的情况，总结出一般性的结论，需要证明。例如、求前n个奇数的和。分析：如用S(n)表示前n个奇数的和，则 S(1)=1=12 S(2)=1+3=4=22 S(3)=1+3+5=9=32 S(4)=1+3+5+7=16=42 S(5)=1+3+5+7+9=25=52 可以看出，当n取1，2，3，4，5时，S(n)=n2。因此可以归纳出求前n个奇数的
18、和的一般规律，即S(n)=n2。上面的归纳法是不完全归纳法，因为由它得到的结论不一定对任意的n都成立，如果结论对任意的n 都成立，这需要证明。证明过程如下：（略）3递推法 递推法（Recursive Method）是指从已知的初始条件出发，逐次推出所要求的各种中间结果和最后结果，其中初始条件或问题本身已经给定，或是通过对问题的分析与化简而确定，递推本质上也属性归纳法。【例5-9】裴波那契（Fibonacci）数列1，1，2，3，5，8，13，21，就是采用递推的方法解决问题的。假设用F(n)表示裴波那契数列的第n项，则该数列有如下规律：即知道了数列的第1项和第2项数值后，则利用公式 就可计算出
19、第三项等后面的各项值。递推分倒推法和顺推法两种形式。一般分析思路:（1）倒推法。就是在不知初始值的情况下，经某种递推关系而获知问题的解或目标，再倒过来，推知它的初始条件。因为这类问题的运算过程是一一映射的，故可分析得其递推公式。然后再从这个解或目标出发，采用倒推手段，一步步地倒推到这个问题的初始陈述。（2）顺推法。倒推法的逆过程，即由边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值，依次递推，直至从问题初始陈述向前推进到这个问题的解为止。4迭代法 迭代法（Iteration method）也称辗转法，是一种不断用变量的旧值去递推新值的过程。迭代算法是用计算机解决问题的
20、一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。【例5-10】用VB语言编写一个函数jsValue()，它的功能是：求Fibonacci数列中大于一个指定的数t的最小的一个数（项），结果由函数返回。例如，当t=1000时，函数值为：1597。Function jsValue(t&)Dim a As Long,b As Long,m As Long a=1 Fibonacci数列第1项 b=1 Fibonacci数列第2项 Do While(b=3时 这是一个典型的递归
21、算法。6回溯法 回溯法（Back method）是一种试探求解的方法：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若成功，则得到解；若失败了，则逐步回退，换其他路线再往前试探。【例5-12】从1到X这X个数字中选出N个，排成一列，相邻两数不能相同，求所有可能的排法。每个数可以选用零次、一次或多次。例如，当N=3、X=3时，排法有12种：121、123、131、132、212、213、231、232、312、313、321、323。算法分析：以N=3，X=3为例，这个问题的每个解可分为三个部分：第一位，第二位，第三位。先写第一位，第一位可选1、2或3，根据从小到大的顺序，
22、我们选1；那么，为了保证相邻两数不同，第二位就只能选2或3了，我们选2；最后，第三位可以选1或3，我们选1；这样就得到了第一个解121。然后，将第三位变为3，就得到了第二个解123。此时，第三位已经不能再取其他值了，于是返回第二位，看第二位还能变为什么值。第二位可以变为3，于是可以在13的基础上再给第三位赋予不同的值1和2，得到第三个解131和132。此时第二位也已经不能再取其他值了，于是返回第一位，将它变为下一个可取的值2，然后按顺序变换第二位和第三位，得到212、213、231232。这样，直到第一位已经取过了所有可能的值，并且将每种情况下的第二位和第三位都按上述思路取过一遍，此时就已经得
23、到了该问题的全部解。由以上过程可以看出，回溯法的思路是：问题的每个解都包含N部分，先给出第一部分，再给出第二部分，直到给出第N部分，这样就得到了一个解。若尝试到某一步时发现已经无法继续，就返回到前一步，修改已经求出的上一部分，然后再继续向后求解。这样，直到回溯到第一步，并且已经将第一步的所有可能情况都尝试过之后，即可得出问题的全部解。7使用逐步求精的思想设计算法 复杂的问题，不可能一下就得到程序，正确的可行方法是：先将问题中简单的部分明确出来，再逐步对复杂部分进行细化，然后一步一步推出完整程序。这样一种逐步向前推进的思想就是逐步求精法。【例5-13】从键盘输入n值，输出h行用*号组成等腰三角形
24、。例：输入 n=4，输出的图形如下：*算法分析：根据图形的要求，我们可以分析出下列结论：（1）图形按行输出，共输出 n 行。（2）整个图形的每一行中，前面先输出空格，后面再输出*。所以程序的关键是：要找出每一行（第k行）中，输出的空格的数量和*的数量。（3）对于图形中的第 k 行(1=k=n)：则要输出 n-k 个 空格 和 2k-1 个*。根据此算法编写的VB程序，略。5.1.5 算法复杂度 算法的复杂度包括时间复杂度和空间复杂度。1算法的时间复杂度 算法的时间复杂度（Time Complexity）是指执行算法所需要的计算工作量。算法所执行的基本运算次数与计算机硬件、软件因素无关。算法所执
25、行的基本运算次数与问题的规模有关。对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。（1）时间频度 一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。（2）时间复杂度 在时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于
26、零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)，称O(f(n)为算法的渐进时间复杂度，简称时间复杂度。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1)，另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。下面举例来说明计算算法时间复杂度的方法。【例5-13】分析以下程序的时间复杂度。y=0 Do While y x y=y+1 Loop 分析：这是一重循环的程序，while循环的循环次数为n，所以，该程序段中语句的频度是n，则程序段的时间复杂度
27、是T(n)=O(n)。【例5-14】分析以下程序的时间复杂度。For i=1 To n For j=1 To n t=i*j Next Next 解：这是二重循环的程序，外层for循环的循环次数是n，内层for循环的循环次数为n，所以，该程序段中语句的频度为n*n，则程序段的时间复杂度为T(n)=O(n2)。在有些情况下，算法中的基本操作重复执行的次数还依据问题的输入数据集的不同而不同。例如在选择升序排序的算法中，当要排序的一组数初始序列为自小至大有序时，基本操作的执行次数为0；当初始序列为自大至小有序时，基本操作的执行次数为n(n1)/2。对这类算法的分析，可以采用以下两种方法来分析。（1）
28、平均性态(Average Behavior)所谓平均性态是指在各种特定输入下，用基本运算次数的加权平均值来度量算法的工作量。设x是所有可能输入中的某个特定输入，p(x)是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为：其中Dn表示当规模为n时，算法执行的所有可能输入的集合。(2)最坏情况复杂性(Worst-case Complexity)所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。显然，W(n)比A(n)计算容易，W(n)更有实际意义。2算法的空间复杂度 一个算法的空间复杂度（Space Complexity），
29、一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占用的空间输入的初始数据所占用的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间（例如，在链式结构中，除了要存储数据本身外，还需要存储链接信息）。如果额外空间量相对于问题规模来说是常数，则称该算法是原地in place工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。类似于时间复杂度的讨论，一个算法的空间复杂度作为算法所需存储空间的量度，记作：S(n)=O(f(n)。其中n为问题的规模(或
30、大小)，空间复杂度也是问题规模n的函数。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(log2n)；当一个算法的空窠复杂度与n成线性比例关系时，可表示为O(n)。5.1.6 算法的评价 算法的好坏，关系到整个问题解决得好与不好，一般可从以下几个方面对一个算法进行评价。1正确性 算法的正确性是最起码的，也是最重要的。一个正确的算法（或程序）应当对所有合法的输入数据都能得到应该得到的结果。要保证算法的正确性，通常要用数学归纳法去证明。2运行时间 运行时间是指将一个算法转换成程序并在计算机上运
31、行所花费的时间，采用“时间复杂”度来衡量，一般不必精确计算出算法的时间复杂度，只需要大致计算出相应的数量级，算法运行所花费的时间主要从4个方面来考虑，即硬件的速度，用来编写程序的语言、编译程序所生成的目标代码质量、问题的规模。3占用空间 占用空间是指执行这个算法所需要的内存空间，一般以数量级形式给出，一个算法所占用的存储空间包括程序所占用的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。4可理解性一个算法应该思路清晰、层次分明、简单明了、易读易懂。5.1.7 查找 以下介绍基于线性表的数据的几种常用查找和排序方法。查找是根据给定的条件，在线性表中，确定一个与给定条件相匹配
32、的数据元素。若找到相应的数据元素，则称查找成功，否则称查找失败。在最坏情况下，顺序查找的时间复杂度为O(n)。1顺序查找 顺序查找（Sequential search）又称顺序搜索。一般是指在线性表中查找指定的元素，方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。【例5-15】在线性表（32，12，76，83，41，27，31，46，64，19，52，96）中查找元素31和68。查找31时，逐个将表中的元素与31进行比较，第7次比较时，两
33、数相等查找成功；查找68时，逐个将表中的元素与68进行比较，表中所有元素与68都进行了比较且都不相等，即查找失败，共比较12次 顺序查找的效率很低，在平均情况下，利用顺序查找法在长度为n的线性表查找一个元素，大约要与线性表中一半的元素进行比较，即平均查找次数为n/2。以下两种情况只能采用顺序查找：（1）如果线性表无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。（2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。2二分法查找 二分法查找（Dichotomy search，或折半查找）只适用于存储的有序数据结构。设有序线性表的长度为n，被查元
34、素为x，则对分查找的方法如下：（1）将x与线性表的中间项进行比较，若中间项的值等于x，则说明查到，查找结束。（2）若x小于（大于）中间项的值，则在线性表的前（后）半部分以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。【例5-16】在线性表（23、31、35、38、45、50、56、68、79、85、96）中查找元素33和85，查找过程如图5-9所示。图5-9 二分法查找过程示意图 查找33的过程（3次比较后查找失败）查找85的过程（3次比较后查找成功）显然，二分法查找不需要与表中所有的元素进行比较。在最坏情况下，二分查找只需要比较log2n次。3
35、分块查找 分块查找（Block search）又称索引顺序查找，是介于顺序查找和二分查找之间的一种查找方法。它的基本方法如下：（1）将所有数据元素分成若干块，块内元素按关键字是无序的，但块间按关键字是有序的，即第一块中所有元素大于（或小于）第二块中所有元素，第二块中所有元素均大于（或小于）第三块中所有元素，依次类推。（2）建立一个块的最大（或最小）索引关键字表，该表是有序的。索引表中的一项对应线性表中的一块，索引项由存放相应块的最大关键字，并指向本块第一个结点的指针。索引表按关键字值递增顺序排列。图5-10 分块查找 【例5-17】在数据11、9、30、14、35、50、65、55、86、70
36、、78、67中查找50。算法分析：如图5-10所，按分块查找的思想是如下：（1）将数据分成三块；（2）建立一个最大顺序的索引关键字表；（3）根据待查的关键字进行查找。由于待查的关键字为50，则从索引关键字表中查找到该50应在第二块中，因3050Ri+1则交换Ri和Ri+1的位置。第一趟全部比较完毕后Rn是序列最大的数据元素，如图所示。冒泡排序：第一次排序结果 再从R1开始两两比较Ri和Ri+1（i=1,2,n-2）的排序码的大小，若RiRi+1则交换Ri和Ri+1的位置。第二趟全部比较完毕后Rn-1是序列最大的数据元素。如此反复，进行n-1趟冒泡排序后所有待排序的n个元素序列按排序码有序。冒泡
37、排序间复杂度为O(n2)。【例5-20】待排序数据序列是（63，95，73，12，31，46，52），写出冒泡排序每一趟执行后的序列状态（升序），如右图所示。冒泡排序5.2 程序设计概述 程序是人们事先使用某种程序设计语言编制好的语句序列，程序以文件的形式保存在指定的磁盘中称为程序文件。程序文件中未编译的按照一定的程序设计语言规范书写的文本文件称为源代码（也称源程序）。计算机按照一定顺序执行这些语句，逐步完成整个工作。5.2.1 程序设计的基本过程 程序设计的基本过程一般由分析所求解的问题、抽象数据模型、选择合适算法、编写程序、调试通过直到得到正确结果等几个阶段，如图5-12所示。图5-12
38、程序设计的基本过程 其设计步骤如下：确定要解决的问题，对任务进行调查分析，明确要实现的功能。对要解决的问题进行分析，找出它们的运算和变化规律，建立数学模型。当一个问题有多个解决方案时，选择适合计算机解决问题的最佳方案。依据解决问题的方案确定数据结构和算法，绘制流程图。依据流程图描述算法，选择一种用合适的计算机语言编写程序。通过反复执行所编写的程序，找出程序中的错误，直到程序的执行效果达到预期的目标。对解决问题整个过程的有关资料进行整理，编写程序使用说明书。5.2.2 程序设计方法与风格 强调“清晰第一、效率第二”论点已成为当今程序设计的主导风格。要形成良好的程序设计风格，应注重考虑下列因素：1
39、源程序文档化 源程序文档化主要包括选择标识符的名称、程序注释和程序的视觉组织。符号名的命名。符号名的命名应具有一定的实际含义，以便于对程序功能的理解。程序注释。正确的注释能够帮助读者理解程序。注释分为序言性注释和功能性注释。序言性注释通常位于每个程序的开头部分，它给出程序的整体说明，包括：程序标题、程序功能说明、主要算法、接口说明、开发简历等。功能性注释嵌在源程序体之中，主要描述其后的语句或程序做什么。视觉组织。为了使程序的结构一目了然，在程序中利用空格、空行、缩进等技巧可使程序逻辑结构清晰，层次分明。2数据说明 在编写程序时，需要注意数据说明的风格，以便程序中的数据说明更易于理解和维护。应注
40、意如下几点：数据说明的次序规范化。鉴于理解、阅读和维护的需要，数据说明先后次序固定，可以使数据的属性容易查找，也有利于程序的测试、调试和维护。说明语句中变量安排有序化。汉使用一个说明语句说明多个就是时，变量最好按照字母顺序排列。使用注释，说明复杂数据的结构。3语句的结构 语句构造力求简单直接，不为提高效率而使语句复杂化。一般应注意：在一行内只写一条语句，并采用适当的缩进格式，使程序的逻辑和功能变得明确。程序编写应优先考虑清晰性。除非对效率有特殊要求，否则程序编写要做到清晰第一，效率第二。首先要保证程序正确，然后才要求提高速度。数据结构要有利于程序的简化，程序设计要模块化，使模块功能尽量单一。尽
41、可能使用库函数 避免使用临时变量而使程序的可读性降低 避免使用无条件转移语句和采用复杂的条件语句。避免过多的循环嵌套和条件嵌套。利用信息隐藏，确保每一个模块的独立性。4输入和输出 输入、输出方式和格式，往往是用户对应用程序是否满意的一个因素，应尽可能方便用户的使用，在设计和编程时都应考虑如下原则：对所有的输入数据都要检验数据的合法性。检查输入项的各种重要组合的合理性。输入格式要简单，输入的步骤和操作尽可能简洁。输入数据时，应允许使用自由格式。应允许缺省值。输入一批数据时，最好使用输入结束标志。在以交互输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中和输入结
42、束时，在屏幕上给出状态信息。当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性。给所有的输出加注释，并设计输出报表格式。5.2.3 程序设计的一般步骤 一般程序设计可按照下面给出的5步进行求解：（1）明确问题的性质，分析题意 不同类型的问题可以有针对性地采用不同的方法进行处理。（2）建立问题的描述模型 （3）设计或确定算法 （4）编程调试 （5）分析运行结果5.3 结构化程序设计 20世纪60年代末，著名学者E.W.Dijkstra（迪克斯特拉）首先提出了“结构化程序设计”（Structured Programming）的思想和方法，方法中引入了工程思想和结构化思想，使大型
43、软件的开发和编程都得到了极大的改善。5.3.1 结构化程序设计的基本结构图5-13 三种控制结构示意图 程序类似于作文，是有一定的结构，即有“启、承、转、合”等部分。每一部分由一或几个自然段组成，我们说程序是有结构的，结构的顺序可以不同。为了描述语句的执行过程，高级语言均提供了一套控制机制，它的作用是控制语句的执行过程（顺序），这种机制称为“控制结构”。把“控制结构”所用的语句或命令称为结构控制语句。1966年，Boehm和Jacopini证明了任何单入口单出口且没有“死循环”的程序都能利用顺序、选择和循环3种基本的控制结构构造出来。顺序、选择和循环3种程序结构（流程图），如图5-13所示。1
44、顺序结构 顺序结构是按照程序语句行的自然顺序依次执行程序，如图5-13(a)所示。2选择结构 选择结构又称为分支结构，这种结构可以根据设定的条件，判断应该选择哪一条分支来执行相应的语句序列，如图5-13(b)所示。3循环结构 循环结构是根据给定的条件，判断是否需要重复执行某一程序段，如图5-13(c)所示。采用结构化的程序设计，可使程序结构清晰、易读、易理解、易维护。5.3.2 结构化程序设计的基本思想 结构化程序设计方法的基本思想可以概括为自顶向下、逐步求精、模块化和限制使用goto语句。具体如下：（1）在程序设计中，采用自顶向下、逐步求精的设计方法 应用程序设计过程应自顶向下分成若干层次或
45、模块，逐步加以解决。程序的控制结构仅由三种基本的控制结构：顺序结构、选择结构和循环结构组成。（2）一个入口，一个出口 对每一部分结构来说，都应该有一条从入口到出口的路径通过。结构内没有死循环。（3）使用图形、表格和语言详细描述处理过程 图形有程序流程图、N-S图、PAD图等 （4）限制使用goto语句5.4 面向对象程序设计 面向对象的语言（Object-Oriented Language）是上个世纪80年代中期提出的新思想，是一种以对象作为基本程序结构单位的程序设计语言，指用于描述的设计是以对象为核心，而对象是程序运行时刻的基本成分。程序设计语言中提供了类、继承、封闭和多态等成分，如Visu
46、al Basi、C、C+、Java、C#、Object Pascal（Delphi）等。面向对象程序设计（Object Oriented Programming，简称OOP）是一种模仿人们建立世界模型的程序设计方式，是对程序设计的一种全新的认识。面向对象语言刻画客观系统较为自然，便于软件扩充与复用。有4个主要特点：（1）识认性，系统中的基本构件是一组可识别的离散对象；（2）类别性，系统具有相同数据结构与行为的所有对象可组成一类；（3）多态性，对象具有惟一的静态类型和多个可能的动态类型；（4）继承性，在基本层次关系的不同类中共享数据和操作。其中，前三者为基础，继承是特色。四者结合使用，体现出面向
47、对象语言的表达能力。1对象（Object）对象就是现实生活中客观存在的一个实体，如一个人、一台电脑等都可看作一个对象。对象是具有某些特征的具体事物的抽象。每个对象都具有能描述其特征的属性。一个人有性别、年龄、体重等，又有脾气、习惯等行为。在自然界中，对象是以类（Class）划分的，如人类、家畜、汽车、电视等。对计算机内部而言，对象既包含数据又包含对数据操作的方法和能响应的事件。对象是将数据、方法和事件封装起来的一个逻辑实体。对象有如下一些基本特点：（1）标识唯一性。指对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分。（2）分类性。指可以将具有相同属性和操作的对象抽象成类。（3）
48、多态性。指同一个操作可以是不同对象的行为。（4）封装性。从外界看只能看到对象的外部特性。2属性（Properties）任何一个对象都具某些外观或内在的特征、性质和状态，我们说对象具有属性（数据）。对象有共同的特征也有不同的特征。5.4.1 面向对象程序设计的基本概念3事件（Event）在现实生活中，常有事情发生，发生的事情和对象又有联系。如马是一个对象，骑士鞭打跑动的马是一个事件。同样在在程序设计语言中，如VB，C#等，也有许多对象的事件，如单击（Click）事件，加载（Load）表单事件等。事件（Event）就是对象上所发生的事情。事件只能发生在程序运行时，而不会发生在设计阶段。对于不同的对
49、象，可以触发许多不同的事件。4方法（Method）方法（Method）就是对象所具有的能力、可执行的动作，如人的吃饭、思维、走、跑等。在在程序设计语言中，如VB、C#等，方法与事件过程类似，是一种特殊的过程和函数。它用于完成某种特定功能而不能响应某个事件，如Print（打印对象）、Show（显示窗体）、Move（移动）方法等。每个方法完成某个功能，用户无法看到其实现的步骤和细节，更不能修改，用户能做的工作只是按照约定直接调用它们。综上所述，我们可以把属性看成是对象的特征，把事件看成是对象的响应，把方法看成是对象的行为，属性、事件和方法构成了对象的三要素。5类（Class）类是一组具有共同特征对
50、象的集合或抽象。对象是类的一个实例。如：“汽车”就是一个类，它抽取了各种汽车的共同特性，而每一部具体的汽车就是一个对象，是类“汽车”的一个实例。类具有继承性、封装性和多态性等三大特征。5.4.2 面向对象程序设计的思想 （1）继承性（Inheritance）：子类具有延用父类的能力。如父类特征发生改变，则子类将继承这些新特征。（2）封装性（Encapsulation）：指明包含和隐藏对象信息的能力。封装性将操作对象的内部复杂性与应用程序的其他部分隔离开来。如对一个命令按钮设计标题属性时，用户不必了解标题字符串是如何存储的。（3）多态性（Polymorphism）：多态性使得相同的操作可以作用于