《大学计算机基础：第6章 算法与数据结构基础》由会员分享，可在线阅读，更多相关《大学计算机基础：第6章 算法与数据结构基础（87页珍藏版）》请在金锄头文库上搜索。
1、 计算机计算机程序程序主要对主要对数据数据进行进行加工加工和和处处理理。通常程序中要说明数据的。通常程序中要说明数据的组织形式组织形式和和存存储方式储方式，即，即数据结构数据结构；也要给出操作数据的；也要给出操作数据的步骤和方法，即步骤和方法，即算法算法。 数据结构基本概念数据结构基本概念 算法基本概念算法基本概念典型数据结构典型数据结构典型算法典型算法 6 6 学学 时时 6.1 6.1 数据结构基本概念数据结构基本概念 6.1.1 6.1.1 数据结构示例数据结构示例 学号学号姓名姓名性别性别出生出生日期日期班级班级专业专业2004000120040001刘强刘强男男1984/02/131
2、984/02/131400114001机械机械2004000220040002王晓红王晓红女女1986/05/061986/05/061400114001机械机械2004000320040003李明李明男男1984/10/251984/10/251400114001机械机械2004004120040041张宇张宇男男1984/06/141984/06/141400214002机械机械数据数据也称为也称为数据元素数据元素或或结点结点，现实，现实世界中一切客观事物都可以抽象成数据世界中一切客观事物都可以抽象成数据元素。元素。 6.1.2 6.1.2 数据结构的定义数据结构的定义 数数据据结结构构是
3、是指指具具有有相相同同特特征征、相相互互之间有之间有关联关联的的数据集合数据集合。9向量向量22，4343，6868，4545，3232是数据结构是数据结构每个数据每个数据元素元素由由一个数据项一个数据项组成，数组成，数据元素之间有位置上的据元素之间有位置上的前后前后关系关系 每个数据每个数据元素元素由由一个数据项一个数据项组成，组成，数据元素之间有位置上的数据元素之间有位置上的前后前后关系关系 9季度名称组成的集合是数据结构：季度名称组成的集合是数据结构： 春，夏，秋，冬春，夏，秋，冬 9家庭成员家庭成员 祖父、父亲、儿子祖父、父亲、儿子 是数据结构是数据结构每个数据每个数据元素元素由由一个
4、数据项一个数据项组成，数组成，数据元素之间有层次上的据元素之间有层次上的高低高低关系关系 9学生信息学生信息数据结构中，数据结构中，数据元素数据元素由由学号学号、姓名姓名、性别性别、出生日期出生日期、班级班级和和专业专业组成。组成。每个数据每个数据元素元素由由多个数据项多个数据项组成组成 数数据据结结构构是是指指带带有有结结构构特特性性的的数数据据元素集合元素集合，主要研究：，主要研究： 1 1）数数据据集集合合中中数数据据元元素素之之间间所所固固有的关系有的关系，即数据，即数据逻辑结构逻辑结构； 2 2）数数据据处处理理时时数数据据在在计计算算机机中中的的存储关系存储关系，即数据，即数据存储
5、结构存储结构； 3 3）对数据所进行的）对数据所进行的操作操作，即，即算法算法。6.1.3 6.1.3 数据逻辑结构数据逻辑结构 数数据据结结构构中中数数据据元元素素之之间间所所固固有有的的关系关系描述成描述成前后件前后件（前驱与后继前驱与后继）关系。）关系。 数数据据之之间间前前后后件件关关系系是是它它们们之之间间的的逻逻辑辑关关系系，与与它它们们在在计计算算机机中中存存储储位位置置无无关关，因因此此将将这这种种关关系系称称为为数数据据逻逻辑辑结结构构。 一个数据结构可以表示为：一个数据结构可以表示为： S=S=（D D，R R） S S: : 数据结构数据结构 D D: : 数据元素集合数
6、据元素集合 R: R: D D中中数数据据元元素素之之间间前前后后件件关关系系集集合合，即数据即数据逻辑结构逻辑结构 两两个个元元素素之之间间前前后后件件关关系系用用一一个个二二元元组组表示，例：表示，例：( (a a1 1, ,a2a2) ) 季节数据结构可以定义成季节数据结构可以定义成 S=(D,R)S=(D,R) 其中其中: D= : D= 春春, , 秋秋, , 冬冬, , 夏夏 R= ( R= (春春, ,夏夏), (), (夏夏, ,秋秋),(),(秋秋, ,冬冬)向量数据结构可以定义成向量数据结构可以定义成 S=(D,R)S=(D,R) 其中其中: D=2,43,68,45,32
7、 : D=2,43,68,45,32 R=(2,43),(43,68),(68,45),(45,32)R=(2,43),(43,68),(68,45),(45,32)线性结构：线性结构：数据之间有数据之间有集合集合, ,线性线性, ,树形树形和和图图形形 4 4 种基本逻辑结构。种基本逻辑结构。数据元素之间数据元素之间一对一一对一关系关系除第一个除第一个结点无前件外结点无前件外, ,其他结点其他结点都都 只有一个前件只有一个前件除最后一个除最后一个结点无后件外结点无后件外, ,其他结其他结点都点都只有一个后件只有一个后件例如例如: :春春夏夏冬冬秋秋O数据之间数据之间一对多一对多关系关系O一一
8、个个结结点点仅仅有有一一个个前前件件, ,可有可有多个后件多个后件O前、后件之间前、后件之间层次关系层次关系树型结构：9数据元素之间数据元素之间多对多多对多关系关系9一个结点可有一个结点可有多个前多个前件件和多个和多个后件后件图形结构：图形结构：集集合合：是是一一种种松松散散结结构构，数数据据元元素素之之间间的的关关系系是是属属于于一一个个集集合合，可可用用其其他他结结构构表示。表示。集合集合 非线性结构非线性结构: : 有有多个开始结点多个开始结点和和多个多个终端结点终端结点，每个结点可以有，每个结点可以有多个前件多个前件和和多个多个后件后件。 线性结构线性结构: : 有且只有有且只有一个开
9、始结点一个开始结点和和一个终端结点一个终端结点，并且每个结点最多只有，并且每个结点最多只有一个一个前件前件和和一个后件一个后件，线性结构也称为，线性结构也称为线性表线性表。 数据逻辑结构数据逻辑结构分为分为线性结构线性结构和和非线性非线性结构结构。 6.1.4 6.1.4 数据物理结构数据物理结构 数据数据在计算机存储器中的在计算机存储器中的存储方式存储方式称为称为数据数据存储结构存储结构（或数据物理结构）。（或数据物理结构）。 数据结构数据结构中数据元素之间在计算机中的中数据元素之间在计算机中的位置关系位置关系与与逻辑关系逻辑关系不一定相同不一定相同。 在数据在数据存储结构存储结构中，不仅要
10、存放各个数中，不仅要存放各个数据元素据元素信息信息，还要存放数据元素之间，还要存放数据元素之间前后件前后件关系信息关系信息。 数据存储数据存储结构是结构是逻辑结构逻辑结构在计算机存储在计算机存储器中的器中的表示表示。 数据元素在计算机中通常有四种存储方数据元素在计算机中通常有四种存储方式，即式，即顺序顺序、链式链式、索引索引和和散列散列，常用，常用顺序顺序存储结构存储结构和和链式存储结构。链式存储结构。 数据数据地址地址A1A2A3A42000H2001H2002H2003H 顺序存储结构顺序存储结构是在内存中开辟是在内存中开辟一块连续一块连续内存单元用于存放数据，内存单元用于存放数据，逻辑上
11、相邻逻辑上相邻的结点的结点在物理位置上也在物理位置上也邻接邻接，结点之间的，结点之间的逻辑关系逻辑关系是由存储单元是由存储单元相邻关系相邻关系来体现。来体现。 链式存储结构：结点由链式存储结构：结点由两部分两部分组成：组成：数据数据域域和和指针域指针域 数据域数据域用于存放数据元素用于存放数据元素值值 指针域指针域用于存放用于存放前件前件或或后件后件的的存储地址存储地址 链式存储结构是通过链式存储结构是通过指针指针反映数据元素之反映数据元素之间的间的逻辑关系逻辑关系。a13003Ha22506Ha32509Ha42000H2001H3003H3004H2506H2507H2509H2510H
12、6.2 6.2 算法基本概念算法基本概念 6.2.1 6.2.1 算法定义算法定义 算法算法是定义在是定义在逻辑结构逻辑结构上的操作，上的操作，独立于计算机独立于计算机，而算法必须在，而算法必须在计算机上计算机上执行执行，因此算法的实现，因此算法的实现依赖依赖于于数据存储数据存储结构结构。 算法算法是解决问题的是解决问题的具体方法具体方法和和步骤步骤的描述的描述，是一组，是一组有限运算序列有限运算序列。 算法的特征算法的特征Z可行性可行性Z确定性确定性Z有穷性有穷性Z输入输入Z输出输出采取的采取的方法方法和和步骤可行步骤可行，结构另人满意。结构另人满意。算法中每个步骤算法中每个步骤结果结果都必
13、须都必须确确定定，不能产生歧义。，不能产生歧义。执行算法时从外界取得必要的执行算法时从外界取得必要的信息。一个算法可以信息。一个算法可以有零或多有零或多个输入个输入。算法得到的算法得到的结果结果就是输出就是输出, ,没有输没有输出的算法是没有意义的出的算法是没有意义的, ,一个算法一个算法应该应该有一个或多个输出有一个或多个输出。算法必须由算法必须由有限有限步步组成，并能在组成，并能在有效时间有效时间内内完成完成。 用于描述算法的工具很多，通常用于描述算法的工具很多，通常有有流程图流程图、N-SN-S图图、自然语言自然语言和和伪代码伪代码等工等工具。具。自然语言自然语言：带序号的人类语言描述方
14、法。带序号的人类语言描述方法。1.1.将变量将变量s s清清0 0；2.2.将变量将变量n n置置1 1；3.3.把把s+ns+n的值赋给的值赋给s s；4.4.把把n+1n+1的值赋给的值赋给n n；5.5.判断判断 n n 100 100？是否成立？是否成立，若成立，转，若成立，转3 3；否则转否则转6 66. 6. 输出输出s s的值的值; ;S=1+2+3+S=1+2+3+99+100+99+100特点特点: :易懂却不直观易懂却不直观, ,对复杂算法描述很对复杂算法描述很困难困难, ,易产生歧义。易产生歧义。若成立若成立,伪伪代代码码法法：是是一一种种假假的的代代码码不不能能被被计计
15、算算机执行，可由机执行，可由计算机语言计算机语言和和自然语言自然语言构成。构成。0S1nwhilen 100S+nSn+1nprintS 接近接近某种语言编写的某种语言编写的程序程序, , 便于转换便于转换成程成程序。序。流程图法：流程图法：用一些用一些图框图框、线条线条以及以及文字文字说明说明 来形象地、直观地描述算法。来形象地、直观地描述算法。输入输入/ /输出输出处理处理判断判断起止起止连接点连接点流程线流程线符号说明符号说明：开始开始0 S1 nSn Sn1 n输出输出S结束结束T F n 100S=1+2+3+S=1+2+3+99+100+99+100优点优点: :直观形象直观形象缺
16、缺点点: :算算法法复复杂杂时时, ,篇篇幅幅 较较多多, ,费费时时且且不不方方便便修改。修改。N-SN-S图图: : 去去掉掉箭箭头头流流程程线线、算算法法处处理理步步骤骤写写在在大大矩矩形形框框内内, , 框框内内还还可可包包含含一一些些小小矩矩形框形框, , 适于结构化程序设计。适于结构化程序设计。顺序顺序A AB B判断判断条件条件F FT TB BA A当型循环当型循环当条件成立当条件成立A A直到型循环直到型循环直到条件成立直到条件成立A A0 S0 S1 n1 nn n 100 100S Sn Sn Sn n1 n1 n输出输出S S的值的值算法评价算法评价 某某一一任任务务的
17、的算算法法设设计计得得优优与与劣劣, ,将将直直接接影影响响程程序序的的运行效率运行效率、稳定性稳定性和和可维护性可维护性。从。从4 4个方面评价算法：个方面评价算法：U正确性正确性U可读性可读性U健壮性健壮性U执行效率执行效率算法本身没有算法本身没有语法错误语法错误, ,执行时执行时输入输入正确数据能够得到正确正确数据能够得到正确结果结果. .算法要算法要容易理解容易理解和和阅读阅读, ,容易容易实现实现，便于程序维护和完善。便于程序维护和完善。 算法执行的算法执行的时间时间性能和性能和空间性能空间性能 。算法能够对各种输入数据给予适当算法能够对各种输入数据给予适当处理和提示。处理和提示。
18、解解决决同同一一问问题题的的多多个个算算法法，执执行行时时间间短短的的算算法法时时间间效效率率高高; ;占占存存储储空空间间少少的的算算法法空空间间效率高效率高。 计算机资源有计算机资源有时间资源时间资源和和空间资源空间资源，因而，算法复杂度有因而，算法复杂度有时间复杂度时间复杂度和和空间复杂空间复杂度度之分。之分。 一个算法复杂度一个算法复杂度高低高低体现在运行该体现在运行该算法所需要算法所需要资源资源的多少。需要资源越多，算的多少。需要资源越多，算法复杂度越高。法复杂度越高。 6.2.4 6.2.4 算法复杂度算法复杂度 算法复杂度算法复杂度是对算法是对算法效率效率的度量，的度量，是评价算
19、法优劣的重要依据。是评价算法优劣的重要依据。 算法时间复杂度算法时间复杂度 算法时间复杂度算法时间复杂度是指执行算法所需是指执行算法所需时间时间，可以，可以表示为：表示为： 执行时间执行时间= =语句执行时间语句执行时间语句执行次数语句执行次数 “规模规模”一般是指所需处理问题的一般是指所需处理问题的数据量大小数据量大小，数据量数据量越大越大，所花费时间就，所花费时间就越多越多。 通常，通常，语句执行次数语句执行次数表示成以表示成以数据量数据量n n为为自变自变量量的的函数函数，记为，记为f(n)f(n)。算法执行时间算法执行时间可以转换成对可以转换成对f(n)f(n)的分析。的分析。算算法时
20、间复杂度法时间复杂度也变成是也变成是数据量数据量n n的函数的函数，通常记为，通常记为T(n)T(n)。 【 例例6-7 6-7 】 计算下列程序段的时间复杂度：计算下列程序段的时间复杂度： for for （ i = i = 1 1；i i n n；i +i +） for for （j = j = 1 1；j j 1n1时时，其其余余结结点点被被分分成成m m（m0m0）个个互互不不相相交交的的子子集集T1T1，T2T2，.，TmTm，每每个个子子集集又又是一棵树。是一棵树。 用用图形图形表示树时，通常表示成一棵表示树时，通常表示成一棵倒挂倒挂树。树。 A AE EB BC CD DF FG
21、 GH HI IJ JK KL L前件前件后件后件结点的度结点的度：一个结点所拥有后件个数：一个结点所拥有后件个数树的度树的度：树中所有结点的：树中所有结点的最大度最大度 A AE EB BC CD DF FG GH HI IJ JK KL L根根子结点子结点叶结点叶结点 A AE EB BC CD DF FG GH HI IJ JK KL L 结点的结点的层次从根层次从根结点算起结点算起，根根结点结点在在第一层第一层，根的直接后继结点在第二层，同，根的直接后继结点在第二层，同一层上所有结点的后继结点均在下一层。一层上所有结点的后继结点均在下一层。 1 1 2 2 3 3 4 4树中结点的最树
22、中结点的最大层次称为树大层次称为树的的深度深度或或高度高度 6.3.6 6.3.6 二叉树二叉树& 二叉树二叉树是另一种树形结构，是另一种树形结构，每个每个结点结点最多最多只有只有两个两个后件。其特点是：后件。其特点是：& 非空非空二叉树有且只有二叉树有且只有一个一个根结点；根结点；& 每个结点每个结点最多最多有有两棵子树两棵子树，且有，且有左右左右之分之分& 二叉树用五种形态二叉树用五种形态(a) (a) 空二叉树空二叉树 (b) (b) 只有根结点只有根结点(c) (c) 只有左子树只有左子树 (d)(d)有左和右子树有左和右子树(e) (e) 只有右子树只有右子树二叉树基本性质二叉树基本
23、性质 性质一性质一在二叉树的第在二叉树的第i i层上，最多有层上，最多有2 2i-1i-1个结点个结点(i1).(i1).性质二性质二深度为深度为k k的二叉树最多有的二叉树最多有2 2k k-1-1个结点个结点(k1). (k1). 性质三性质三对于任意一棵二叉树，对于任意一棵二叉树，度为度为0 0的结点的结点( (即叶子即叶子结点结点) )总比总比度为度为2 2的结点的结点多多1 1个个. .1-11-1= =A AT TX XC CR RB BP PS SE EG GF FY Y2-12-1=2=23-13-1=4=44-14-1=8=8A AT TX XC CR RB BP PS SE
24、 EG GF FY Y2 24 45 54 4-1=15-1=151212A AT TX XC CR RB BP PS SE EG GF FY Y度为度为0 0结点数结点数6 6, ,度为度为2 2结点数结点数5 5满二叉树满二叉树拥有拥有2 2k k-1-1个结点，个结点，深度深度为为k k的二叉树。的二叉树。每每一一层层的的结结点点数数都都达达到到最最大大值值,叶叶子子结结点点都在都在最下最下面的面的同一层同一层上上完全二叉树完全二叉树 一一棵棵深深度度为为k k的的二二叉叉树树, , 如如果果第第一一层层到到第第k-1k-1层层是是一一棵棵满满二二叉叉树树, , 第第k k层层上上的的结
25、结点点数数可可能能没没达达到到最大值最大值2 2k-1k-1, , 但这些结点都满放在该层但这些结点都满放在该层最左边最左边。 如果某个结点没有左子如果某个结点没有左子树树,则它一定没有右子树则它一定没有右子树A AT TX XC CE EM MB BP P2 2-1-11515个结点的满二叉个结点的满二叉树树S SD DN NF FR RY YQ Q注：注：满满二叉树二叉树是完全是完全二叉树，但二叉树，但完全完全二叉二叉树树不一定不一定是是满满二叉树。二叉树。A AT TX XC CR RB BP PS SE EG GF FY Y2 24-14-1=8=85 5满二叉树满放在最左边满放在最左
26、边完全二叉树性质完全二叉树性质1212个结点的完全二叉树个结点的完全二叉树A AT TX XC CR RB BP PS SE EG GF FY Y性质一性质一具具有有n n个个结结点点的的完完全全二二叉叉树树的的深深度度为为 loglog2 2n n+1+1。其中，。其中， loglog2 2n n表示取表示取loglog2 2n n的整数部分。的整数部分。性质性质二二在在n n个个结结点点的的完完全全二二叉叉树树中中, , 将将结结点点从从上上到到下下, ,从从左左到到右右编编号号1, 1, 2, 2, , , n, n, 对对编编号号为为k k的的结结点点有：有：k=k=1 1为为根根结点
27、。结点。k1k1时时, , 该结点的该结点的父结点父结点编号为编号为int(k/2)int(k/2)。2k=n2k=n时时, , 编号为编号为k k结点的结点的左子结点左子结点编号为编号为2k2k, ,否则否则无左无左子结点。子结点。2k+1=n2k+1=n时时, , 编号为编号为k k结点的结点的右子结点右子结点编号为编号为2k+12k+1, , 否则无右否则无右子结点。子结点。A AT TX XC CR RB BP PS SE EQ QF FY Y1 12 23 34 45 56 67 7101011119 98 81212二叉树的顺序存储二叉树的顺序存储指指用用一一组组连连续续存存储储单
28、单元元存存储储二二叉叉树树中中的的结结点点。结点存储顺序是按着从结点存储顺序是按着从上到下上到下、从、从左到右左到右顺序。顺序。 A AC CB BE EG GD DF FA AB BC CD DE E F FG G 1 1 2 2 3 3 4 4 5 5 6 7 6 7 按按完完全全二二叉叉树树每每个个结结点点编编号号的的顺顺序序存存放放结结点点, ,通通过过结结点点的的编编号号准准确确地地反反映映结结点点之之间间的的逻辑关系。逻辑关系。1 12 23 34 45 56 67 7非完全二叉树顺序存储非完全二叉树顺序存储A AC CB BE EG GF FA AB BC C E E F FG
29、G 1 1 2 2 3 3 4 4 5 5 6 7 6 7 显显然然, ,顺顺序序结结构构适适用用于于完完全全二二叉叉树树，对对于于非非完完全全二二叉叉树树，浪费浪费许多存储许多存储空间空间。1 12 23 34 45 56 67 7二叉树链式存储二叉树链式存储二叉树每个结点由数据域和指针域组成二叉树每个结点由数据域和指针域组成 。两个指针域：两个指针域： o o 一个用于指向一个用于指向左子结点左子结点 o o 一个用于指向一个用于指向右子结点右子结点 常见二叉树结点结构如图：常见二叉树结点结构如图： LChildLChildDataDataRChildRChild数据域数据域 存储左子结点
30、地址存储左子结点地址 存储右子结点地址存储右子结点地址 A AT TX XC CZ ZY YB BP P深度为深度为4 4的二叉树的二叉树二叉树链式存储二叉树链式存储A AT TX XC CZ ZY YB BP P深度为深度为4 4的的二叉树二叉树A AT TX XB BC CP PZ ZY YBTBT&二叉树遍历二叉树遍历 遍历遍历二叉树就是按照某种二叉树就是按照某种顺序顺序访问二叉访问二叉树中树中每个每个结点的过程，每个结点被访问结点的过程，每个结点被访问一次一次且仅一次且仅一次。 非空二叉树可以看成由非空二叉树可以看成由根结点根结点、左子树左子树和和右子树右子树三部分构成。三部分构成。
31、二叉树的遍历分为二叉树的遍历分为先序先序遍历、遍历、中序中序遍历遍历和和后序后序遍历。遍历。先序遍历先序遍历 访问根结点访问根结点 先序遍历左子树先序遍历左子树 先序遍历右子树先序遍历右子树A AT TX XC CZ ZY YB BP P深度为深度为4 4的二叉树的二叉树A A遍历结果：遍历结果：T TB BZ ZX XC CP PY Y因为左子树因为左子树空，故遍历空，故遍历右子树右子树中序中序遍历遍历 中序遍历左子树中序遍历左子树 访问根结点访问根结点 中序遍历右子树中序遍历右子树A AT TX XC CZ ZY YB BP P深度为深度为4 4的二叉树的二叉树A AT TZ ZB BC
32、CX XY YP P因为左子树空因为左子树空遍历结果：遍历结果： 后序遍历左子树后序遍历左子树 后序遍历右子树后序遍历右子树 访问根结点访问根结点后序后序遍历遍历A AT TX XC CZ ZY YB BP P深度为深度为4 4的二叉树的二叉树遍历结果：遍历结果：A AT TX XC CZ ZY YB BP P深度为深度为4 4的二叉树的二叉树A AT TZ ZB BC CX XY YP P因为左子树因为左子树空，故遍历空，故遍历右子树右子树 6.4 6.4 典型算法典型算法 6.4.1 6.4.1 查找算法查找算法 查找查找又称又称检索检索，是数据处理中使用最，是数据处理中使用最频繁的一种操
33、作。频繁的一种操作。 查找查找是指在数据集合中是指在数据集合中查找查找某个数据某个数据元素的过程。元素的过程。 若若存在存在这样数据元素，则查找这样数据元素，则查找成功成功；否则，查找否则，查找失败失败。顺序查找顺序查找 & 顺序查找适用于顺序查找适用于线性表线性表。其基本方法是：。其基本方法是：& 从线性表中从线性表中第一个第一个元素开始，依次将线性元素开始，依次将线性表中元素与表中元素与给定值给定值进行进行比较比较。& 若若相等相等，则查找，则查找成功成功；& 若直到若直到最后最后一个元素，还没找到与给定值一个元素，还没找到与给定值相等的元素，则查找相等的元素，则查找失败失败。例例如如：在
34、在 ( ( 8888, , 1515, , 2323, , 8080, , 6363, , 8 8, , 8686, , 4646, , 7171, , 101101 ) )中中, , 查找查找 值为值为7171的数据元素。的数据元素。从从线线性性表表中中第第一一个个元元素素8888开开始始, , 依依次次将将 线性表中元素与线性表中元素与7171进行比较。进行比较。直到第九个元素为直到第九个元素为71, 71, 查找成功。查找成功。 特点特点：顺序查找算法简单顺序查找算法简单, ,但是执行效率较低但是执行效率较低在下列两种情况下在下列两种情况下, ,只能使用顺序查找法：只能使用顺序查找法：
35、线性表线性表链式存储链式存储。 线性表线性表顺序存储顺序存储，但元素，但元素无序无序排列。排列。 比较了比较了9 9次次 2 2 二分查找二分查找又又称称折折半半查查找找, , 要要求求被被查查找找的的表表用用顺顺序序存存储储结结构构且且数数据据元元素素按按数数据据值值升升序序或或降降序序排排列列, , 即即二分查找法二分查找法只适用于只适用于有序表有序表。 基本思想基本思想 ( (设顺序表升序排列设顺序表升序排列) )P将将给给定定值值与与中中间间元元素素（ (L+R)/2(L+R)/2）比比较较, ,若若相相等等, ,则则找找成功成功；P若给定值若给定值小于小于中间元素值中间元素值, ,则
36、继续对则继续对前半前半再再折半查找折半查找；P若给定值若给定值大于大于中间元素值中间元素值, ,则继续对则继续对后半后半再再折半查找折半查找。 设待查找序列的序号区间为设待查找序列的序号区间为LLRR，则中间序号位置为，则中间序号位置为 mid= mid= (L+R)/2(L+R)/2第一次查找第一次查找 mid= mid= (1+12)/2(1+12)/2=6=6 66 71 66 71 8080 86 88 101 86 88 101 7 8 7 8 9 9 10 11 12 10 11 12第二次查找第二次查找 mid=9 mid=9 6666 71 71 7 7 8 8 【 例例6-1
37、4 6-14 】在有序顺序表（在有序顺序表（8 8，1515，2323，3737，4646，6363，6666，7171，8080，8686，8888，101101）中，用折半查找法查找值为）中，用折半查找法查找值为7171的数据元素。的数据元素。key=71 8 15 23 37 46 key=71 8 15 23 37 46 6363 66 71 80 86 88 101 66 71 80 86 88 101 1 2 3 4 5 1 2 3 4 5 6 6 7 8 9 10 11 12 7 8 9 10 11 12 第三次查找第三次查找 mid=7 mid=7 7171 8 8 第四次查找
38、第四次查找 mid=8 mid=8 查找成功查找成功&排序算法排序算法 排序排序是将一组是将一组无序无序数据按值数据按值递增递增（或（或递减递减）进行重新排列。）进行重新排列。 交交换换排排序序、选选择择排排序序和和插插入入排排序序是是3 3类类基本排序方法。基本排序方法。 待待排排序序数数据据序序列列可可以以是是顺顺序序存存储储或或链链式式存储结构。存储结构。 下下面面排排序序算算法法中中，待待排排序序数数据据序序列列均均采用采用顺序顺序存储结构。存储结构。4 交换排序法交换排序法 & 在排序过程中，通过在排序过程中，通过数据元素数据元素之间不之间不断地进行断地进行比较比较与与交换交换，最终
39、达到，最终达到排序排序目的。目的。冒泡排序法冒泡排序法是典型的交换排序法之一。是典型的交换排序法之一。& 冒泡排序法冒泡排序法的基本思想是：对的基本思想是：对所有所有相相邻邻元素进行元素进行比较比较，若，若逆顺逆顺，则将其，则将其交换交换，最，最终达到终达到有序化有序化。交换排序法原序列：原序列：4242232316164747111145451313494942422323161647471111454513134949第第1 1 遍遍第第2 2遍遍第第3 3遍遍第第4 4遍遍第第5 5遍遍第第6 6遍遍23231616424211114545474713134949161623231111
40、42424545131347474949161623231111424245451313474749491111232316161313454542424747494911111313161623234545424247474949选择排序选择排序4选择排序是指每次从待排序数据序列中，选选择排序是指每次从待排序数据序列中，选择出择出最小最小元素并定位到待（升序）排序序列元素并定位到待（升序）排序序列最最前面前面。简单选择排序法的基本思想是：。简单选择排序法的基本思想是：4 首先扫描整个序列，从中选出首先扫描整个序列，从中选出最小最小元素，元素，将它交换到将它交换到最前面最前面；4 然后再从剩余
41、子序列中，选出然后再从剩余子序列中，选出最小元素最小元素，交换到子序列交换到子序列最前面最前面。4 依次类推，直到子序列依次类推，直到子序列长度为长度为1 1为止。为止。 由由于于每每遍遍扫扫描描只只能能确确定定一一个个元元素素位位置置，所所以以对对于于长长度度为为n n的的序序列列，需需要要扫扫描描n-1n-1遍遍才才能能将将每每个个元元素素位位置置确确定定下来。下来。原序列：原序列：42422323161627271111454513134949选择排序法第第1 1遍选择遍选择424223231616272711114545131349491111232316162727424245451
42、3134949第第2 2遍选择遍选择11111313161627274242454523234949第第3 3遍选择遍选择11111313161627274242454523234949第第4 4遍选择遍选择11111313161623234242454527274949第第5 5遍选择遍选择11111313161623232727454542424949第第6 6遍选择遍选择11111313161623232727424245454949第第7 7遍选择遍选择插入排序插入排序插入排序插入排序是不断地将是不断地将待排序待排序的元素插入的元素插入到前面到前面有序有序序列中，直至所有元素都进入有序
43、列中，直至所有元素都进入有序序列。序序列。 简单插入排序又称简单插入排序又称直接直接插入排序，是插入排序，是典型的典型的插入插入排序法。基本思想是：排序法。基本思想是： 将由将由n n个元素组成的序列分成个元素组成的序列分成前后前后两两个个子序列，子序列，前者前者为为有序有序序列，序列，后者后者为为无序无序序序列。列。 一开始将待排序序列中一开始将待排序序列中第一个第一个元素作为元素作为有序有序序列，将序列，将第二个第二个元素元素插入插入到有序序列到有序序列中，形成由两个元素组成的有序序列。中，形成由两个元素组成的有序序列。 再将再将第三个第三个元素元素插入插入到有序序列中。依到有序序列中。依
44、此类推，直到此类推，直到最后最后一个元素插入到有序序一个元素插入到有序序列中，形成列中，形成n n个元素组成的有序序列个元素组成的有序序列。 插入排序法原序列：原序列：42422323161627271111454513134949第第1 1遍遍23234242161627271111454513134949第第2 2遍遍16162323424227271111454513134949第第3 3遍遍16162323272742421111454513134949第第4 4遍遍11111616232327274242454513134949第第5 5遍遍11111616232327274242454513134949第第6 6遍遍11111616232327274242454549491313第第7 7遍遍13131616232327274242454549491111
