算法与数据结构二级ACCESS公共基础知识.pptx

《算法与数据结构二级ACCESS公共基础知识.pptx》由会员分享，可在线阅读，更多相关《算法与数据结构二级ACCESS公共基础知识.pptx（72页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第一章 算法与数据结构本章要求算法的基本概念、算法复杂度的概念和意义（时间复杂度与空间复杂度）。数据结构的定义、数据的逻辑结构与存储结构、数据结构的图形表示、线性结构与非线性结构的概念。线性表的定义、线性表的顺序存储结构及其插入与删除运算。栈和队列的定义、栈和队列的顺序存储结构及其基本运算。线性单链表、双向链表与循环链表的结构及其基本运算。树的基本概念，二叉树的定义及其存储结构，二叉树的前序、中序和后序遍历。顺序查找与二分法查找算法、基本排序算法（交换类排序、选择类排序与插入类）。第1页/共72页2第一章 算法与数据结构一、算法二、数据结构三、线性表四、栈五、队列六、线性链表七、树与二叉树八

2、、查找技术九、排序技术第2页/共72页3一、算法1.算法的基本概念算法是指为了解决某类问题而规定的一个有限长度的操作（指令）序列。（1）算法的特点：可行性、确定性、有穷性、拥有足够的情报。（2）算法的两个基本要素：一是对数据对象的运算和操作，具体包括算术运算、逻辑运算、关系运算和数据传输等；二是算法的控制结构，具体包括顺序结构、选择结构和循环结构。第3页/共72页42.算法的复杂度算法的复杂度(代价)是衡量算法好坏的量度，具体可分为两种:时间复杂度和空间复杂度。（1）时间复杂度是指执行算法所需要的计算工作量，即算法执行过程中所需要的基本运算次数。通常记作：常见的时间复杂度有：（2）空间复杂度是

3、指执行该算法所需要的内存空间。具体包括（1）算法程序所占的空间；（2）输入的初始数据所占的存储空间；（3）算法执行过程中的额外空间 第4页/共72页5二、数据结构1.数据结构的基本概念数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。在此概念中:（1）数据是指所有能输入到计算机中并被计算机程序处理的符号的总称;（2）数据元素是指数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理;（3）一个数据元素可以由若干个数据项组成,数据项是数据的最小单位。第5页/共72页6数据结构有三个方面的内容：数据的逻辑结构、数据的存储结构、数据的运算。2.数据的逻辑结构数据的逻辑结构是指数据元素

4、之间的逻辑关系，从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据的逻辑结构的表示方法表示数据的逻辑结构时必须表示清楚两个关键点，一个是数据元素的集合D，另一个是数据元素之间的前后关系R。表示数据结构的方法有两种：二元关系表和图形表示方法。第6页/共72页7A.二元关系表示方法：一个数据结构可以表示为B=（D、R），其中R用二元组来表示(a、b)。a表示前件，b表示后件。例如，一年四季的数据结构可以表示成:B=（D、R）D=春，夏，秋，冬R=（春，夏），（夏，秋），（秋，冬）B.在图形表示方法中，用中间标有元素值的方框来表示数据元素，称为数据结点，简称为结点；用一条有向线段从前件

5、结点指向后件结点（注意：有时可以省略箭头）来表示元素之间的前后关系。第7页/共72页8 例如，同样是一年四季的数据结构，若用图形方法表示则如图所示。数据的逻辑结构一般分为两种:线性结构和非线性结构。线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。如：一年四季。非线性结构：线性以外的数据结构。如：反映家庭成员间辈分关系的数据结构。第8页/共72页9A.线性结构 线性表例:英文字母表 (A,B,C,，X,Y,Z)例:学生成绩表 栈后进先出 队列先进先出8686胡孝臣胡孝臣986110398611039595刘忠赏刘忠赏98611079861107100100张卓张卓986

6、11099861109成绩成绩姓名姓名学号学号第9页/共72页10B.非线性结构 树形结构例:全校学生档案管理的组织方式 例:计算机文件管理系统也是典型的树形结构第10页/共72页11 图形结构结点间的连结是任意的例:数据结构B(D,R)D=1,2,3,4 R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4)例:数据结构C(D,R)D=1,2,3 R=(1,2),(2,3),(3,2),(1,3)1423213第11页/共72页123.数据的存储结构数据的存储结构(又称物理结构):是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储空间中的存放形式。数据

7、的存储结构有4种：顺序存储方式、链式存储方式、索引存储方式和散列存储方式。需要注意的是，对于同一个逻辑结构来说，采用不同的存储结构时，其数据处理的效率是不同的。4.数据的运算：检索、排序、插入、删除、修改等。第12页/共72页13三、线性表线性表是最简单的、最常用的一种线性结构。1.线性表的定义:线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2，ai，an ，其中n称作表的长度，当n=0时，称作空表。线性表（非空线性表）必须同时满足以下3个条件：（1）有且只有一个根结点a1，它无前件。（2）有且只有一个终端结点an，它无后件。（3）除根结点与终端结点外，其他所有结点有

8、且只有一个前件，也有且只有一个后件。第13页/共72页14 如下图所示的数据结构就是线性表 注：线性表的概念是从逻辑结构的角度说的，所以，判断是否为线性表时并不考虑其存储结构，线性表可以用四种不同的存储结构来表示。2.线性表的顺序存储结构 特点：（1）线性表中所有元素所占的存储空间是连续的;（2）线性表中各数据元素在存储空间中的存放顺序是按逻辑顺序依次存放的。第14页/共72页15 例：正确表示线性表(A1，A2，A3，A4)的顺序结构是()A)B)C)分析：选C，选项C中线性表各元素的存储空间是连续的，而且元素的存储顺序与逻辑顺序一致。选项A中各元素的物理顺序与逻辑顺序不同。选项B中各元素所

9、占的存储空间并不连续。A1 A2 A3 A4第15页/共72页16顺顺序序存存储储存储地址存储地址存储内容存储内容an.ai.a2a1ADR(a1)ADR(a1)+kADR(a1)+(i-1)kADR(a1)+(n-1)kADR(aADR(ai i)=ADR(a)=ADR(a1 1)+)+（i-1)i-1)k每个元素所占用每个元素所占用的存储单元个数的存储单元个数首地址首地址起始地址起始地址基地址基地址 在线性表的顺序存储结构中可以计算各数据元素（数据起点）的起始地址。第16页/共72页17顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里,具有以下特点:(1)随机存取。(2)作

10、插入或删除操作时，需移动大量元素。(3)长度变化较大时，需按最大空间分配。(4)表的容量难以扩充。通常定义一个一维数组来表示线性表的顺序存储空间。第17页/共72页183.线性表的顺序存储结构的插入运算设顺序表的结构如图所示，其插入运算的步骤如下：(1)判断是否上溢:首先判断为线性表开辟的存储空间是否已满，如果已满则不能插入，如果未满则继续做第二步。(2)空出第i个位置:从最后一个元素开始到插入的位置上的元素，将其中的每个元素均依次往后移动一位。(3)插入:把新元素放入所插入的位置。第18页/共72页19插入位置与需要移动的元素个数之间存在着一定的关系。当线性表很大时，其插入运算的效率是比较低

11、的。具体情况如下所述：(1)最好的情况:如果插入位置在线性表的末尾，即在第n个元素之后插入新元素，则不需要移动线性表中的其他任何元素。(2)最坏的情况:如果插入位置在线性表的第1个元素之前，则需要移动表中的所有元素。(3)如果插入位置在第i（1in）个元素之前，则原来的第i个元素之后(包括第i个元素)的所有元素都必须移动。(4)在平均情况下，要在线性表中插入一个新元素，需要移动线性表中一半的元素。（n/2个）第19页/共72页203.线性表的顺序存储结构的删除运算具体运算步骤如下:如果删除第i（1in）个元素，从第i+1个元素开始直到最后一个元素，将其中的每个元素均依次往前移动一位。此时，线性

12、表的长度变成了n-1。如下图：第20页/共72页21在线性表的顺序存储结构的删除运算中，删除一个数据元素之后，应移动原来的元素，而且删除位置与需要移动的元素个数之间存在着一定的关系。所以当线性表很大时，其删除运算的效率也是比较低的。具体情况如下所述：(1)最好的情况:如果删除位置在线性表的末尾，即删除第n个元素，则不需要移动线性表中的其他任何元素。(2)最坏的情况:如果删除线性表的第1个元素，则需要移动表中的所有元素。(3)在平均情况下，要删除线性表中的一个元素，需要移动表中的(n-1)/2个元素。第21页/共72页22四、栈1.栈的定义：栈是一种特殊的线性表，特殊在其数据操作上，即限定在一端

13、进行插入与删除的线性表。在栈中，允许插入和删除的一端称为栈顶，而不允许插入和删除的另一端称为栈底。往栈中插入一个元素叫入栈运算（压栈）从栈中删除一个元素称为退栈运算（弹栈）栈的数据操作原则是先进后出FILO（FirstIn Last Out）或后进先出LIFO。栈具有一定的记忆作用。第22页/共72页232.栈的存储结构在程序设计语言中，与普通线性表一样，用一维数组作为栈S(l:m)的顺序存储结构，其中m为栈的最大容量。通常用指针top来指示栈顶的位置，用指针bottom指向栈底。当top=0时为空栈，当top等于数组的最大下标值时则栈满。3.栈的基本运算 有三种:入栈、退栈和读栈顶元素。(1

14、)入栈运算的步骤：首先，判断栈是否为满，如果满则不能入栈(方法top=n)；其次，将栈顶指针进一(即 top加1)；第23页/共72页24 最后，将新元素放入栈顶指针指向的位置中。值得注意的是，在入栈运算中应避免上溢错误的出现。上溢错误是指当栈顶指针己经指向存储空间的最后一个位置时，说明栈的空间己满，不能再进行入栈操作，这种情况称为栈“上溢”错误。(2)退栈运算的步骤：首先，判断栈是否为空(方法top=0);其次，将栈顶元素赋值给一个指定的变量;最后，栈顶指针退一(即top减1)。值得注意的是，退栈运算中应避免下溢错误的出现。第24页/共72页25(3)读栈顶元素的步骤：读栈顶元素是指将栈顶元

15、素赋值给一个指定的变量。读枝顶元素过程中应注意的问题有:第一，读栈顶元素不是删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中，栈顶指针不会改变，这是与入栈运算的区别;第二，当栈顶指针为0时，说明栈为空，读不到栈顶元素。第25页/共72页26五、队列1.队列的基本概念：队列是一种只允许在一端进行插入，而在另一端进行删除的线性表，它也是一种特殊的线性表。允许插入的一端叫队尾(尾指针，Rear，指向队尾元素)，允许删除的一端叫队头(头指针，Front，指向队头元素的前一个位置)。队列的数据操作方法:先进先出FIFO/LILO。第26页/共72页27队列的一个重要应用是在操作系统中的管理用户

16、程序上。即在操作系统中，用队列来组织管理用户程序的排队执行，其原则是:(1)初始时该队列为空;(2)当有用户程序到来时，将该用户程序加入到队列的末尾进行等待;(3)当计算机系统执行完当前的用户程序后，就从队列头部取出一个用户程序执行。与栈一样，程序设计中用一维数组作为队列的顺序存储空间。第27页/共72页282.循环队列在实际应用中，队列的顺序存储结构一般采用循环队列的形式。原理:循环队列是指当队列存储空间的最后一个位置己被使用而仍要进行入队运算，这时只要存储空间的第一个位置空闲，便可以将元素加入到这个位置，即将存储空间的第一个位置作为队尾，如图所示。第28页/共72页29在循环队列中，从头指

17、针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。循环队列的初始状态为空，即：rear=front=m，如图所示。循环队列主要有两种基本运算：入队运算与退队运算。每进行一次入队运算，队尾指针就进一。当队尾指针rear=m+1时，则置rear=1；每进行一次退队运算，排头指针就进一。当排头指针front=m+1时，则置front=1第29页/共72页30例：图（a）是一个容量为8的循环队列存储空间，且其中已有6个元素。图（b）是在图（a）的循环队列中又加入了两个元素后的状态。图（c）是在图（b）的循环队列中退出了1个元素后的状态。Q(1:8)8rear7

18、F6 E5 D4 C3 B2 Afront1 Q(1:8)8 X7 F6 E5 D4 C3 B2 Afrontrear 1 YQ(1:8)8 X7 F6 E5 D4 C3 Bfront 2 rear 1 Y（a）具有6个元素的循环队列 （b）加入X、Y后的循环队列 （c）退出一个元素后的循环队列 从图（b）可以看出，当循环队列满时有front=rear，而当循环队列空时也有front=rear。即在循环队列中，当front=rear时，不能确定是队列满还是队列空。第30页/共72页31为了能区分队列满还是队列空，通常还需增加一个标志s，s值的定义如下：s=0 表示队列空 s=1 表示队列非空由

19、此可以得出队列空与队列满的条件如下：队列空的条件为s=0；队列满的条件为s=1且front=rear。循环队列入队与退队的运算注意点当循环队列非空（s=1）且front=rear时，说明循环队列已满，不能入队运算，这种情况称为”上溢“。当循环队列为空（s=0）时，不能进行退队运算，这种情况称为”下溢“。第31页/共72页32六、线性链表1.链式存储结构对于大的线性表或者变动频繁的线性表不宜用顺序存储，应该采用链式存储。链式存储的过程如图所示。每个结点都由两部分组成：每个结点都由两部分组成：数据域数据域和和指指针域针域。数据域数据域存放元素值，存放元素值，指针域指针域存放指针。存放指针。数据元素

20、之间逻辑上的联系由指针来体数据元素之间逻辑上的联系由指针来体现。现。第32页/共72页33注：链式存储方式中的存储结点不一定是连续的；各结点的存储顺序与数据元素之间的逻辑关系可以不一致；链式存储方式可以用于线性结构，也可用于非线性结构。2.线性链表线性链表是指线性表的链式存储结构。为了适应线性链表的链式存储结构，计算机存储空间被划分为一个一个小块，每个小块占若干个字节，通常称这些小块为存储结点。第33页/共72页34在线性链表中，头指针(head)很关键，不得丢失；线性链表的最后一个结点的指针域为空，用NULL或0来表示；空表(线性链表):当head(指向线性表的第一个结点的指针head称为头

21、指针)等于NULL或0时，称为空表;单链表的缺点是只能找到后件，不能找到前件；为了克服单链表的缺点，出现了双向链表的概念。在双向链表中，把每个结点修改为由以下3部分组成:左指针 数据元素 右指针第34页/共72页35双向链表的结点结构如下图所示：双向链表克服了单向链表的只能找到后件不能找到前件的缺陷。3.栈的链式存储结构（带链的栈）第35页/共72页36在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。当计算机系统需要存储结点时，退栈;当计算机系统释放存储结点时，入栈。4.队列的链式存储结构（带链的队列）第36页/共72页37对带链的队列的操作如下

22、图所示：第37页/共72页385.线性链表的基本运算线性链表的基本运算有3种:查找、插入和删除数据元素。（1）在线性链表中查找指定元素在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素值的前一个结点。当找到包含指定元素的前一个结点后，就可以在该结点后插入新结点或删除该结点后的一个结点。在非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法如下：第38页/共72页39 从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。因此，由这种方法找到的结点p有两种可能：当线性链表中存

23、在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号；当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。（2）线性链表中的插入运算为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，以便用于存储该元素的值。新结点可以从可利用栈中取得。然后将存放新元素值的结点链接到线性链表中指定的位置。第39页/共72页40在线性链表中包含x的结点之前插入一个新元素b。其插入过程如下：（1）从可利用栈取得一个结点，设该结点号为p（即取得结点的存储序号存放在变量p中），并置结点p的数据域为插入的元素值b。（2）在线性链表中寻找包含元素x的前一个结点，设该

24、结点的存储序号为q。（3）将结点p插入到结点q之后。为了实现这一步，只要改变两个结点的指针域内容即可：使结点p指向包含元素x的结点（即结点q的后件结点）。使结点q的指针域内容改为指向结点p。第40页/共72页41在线性链表中包含x的结点之前插入一个新元素b。其插入过程如下图：第41页/共72页42（3）线性链表的删除为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。在线性链表中删除包含元素x的结点，其删除过程如下：（1）在线性链表中寻找包含元素x的前一个结点，设该结点序号为q。（2）将结点q后的结点p从线性链表中删除，即让结点q的指针指向包

25、含元素x的结点p的指针指向的结点。（3）将包含元素x的结点p送回可利用栈。第42页/共72页43在线性链表中删除包含元素x的结点，其删除过程如下图所示：第43页/共72页446.循环链表循环链表与单链表的主要区别:(1)在循环链表中增加了表头结点，其数据域为任意或根据需要来设置，指针域为指向线性表的第一个元素的结点；(2)循环链表中的最后一个结点的指针域不为空，而是指向表头结点。第44页/共72页45循环链表的特征如下:(1)循环链表中永远至少有一个结点存在(表头结点)；(2)在对循环链表进行插入和删除的过程中，实现了空表和非空表的运算的统一；(3)在循环链表中，只要指出表中的任何一个结点的位

26、置，就可以从它出发访问到表中的其他所有结点，而线性单链表做不到这一点；(4)在循环链表的运算过程中，不必单独考虑对空表和第一结点的处理问题。第45页/共72页46七、树与二叉树1.树树是一种非线性结构，树的数据结构为B=(D,R)，其中，D代表数据对象，是具有相同特性的数据元素的集合；R代表数据关系。若D为空集，则称为空树，否则：（1）在D中存在唯一的称为根的数据元素root；（2）当n1时，其余结点可分为m（m0）个互不相交的有限集T1,T2,T3,其中每一个子集本身又是一颗符合本定义的树，称为根（root）的子树。第46页/共72页47在树结构中，每个结点只有一个前件，称为父结点，没有前件

27、的结点只有一个，称为树的根结点，简称为树的根。如图所示的结点A就是树的根。在树结构中，每个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。如图所示的结点K,L,F,G,M,I,J都是叶子结点。在树结构中，每个结点所拥有的后件个数称为该结点的度。例如图中结点D的度为3。第47页/共72页48在树中所有结点中的最大的度称为树的度。如图示的树的度为3树结构具有明显的层次关系，即树是一种层次结构。在树结构中，一般有如下分层:根结点在第一层，依次类推。树的最大层次称为树的深度。如图所示的树的深度为4。在树中，以某结点的子结点为根构成的树称为该结点的一颗子树。例如在图所示的树中B

28、结点有两颗子树在树中，叶子结点没有子树。树在计算机中通常用多重链表来表示。第48页/共72页492.二叉树（1）二叉树的定义二叉树是一种特殊的树，非空二叉树只有一个根结点。如图所示，每个根结点最多有两棵子树，分别称为该结点的左子树和右子树。第49页/共72页50（2）二叉树的性质：性质1:在二叉树的第k层上，最多有2k-1（k1）个结点。423167891011121314155第三层上第三层上(k=3)(k=3)，有，有2 23-13-1=4=4个节点。个节点。第四层上第四层上(k=4)(k=4)，有，有2 24-14-1=8=8个节点。个节点。第50页/共72页51性质2：深度为m的二叉树

29、最多有2m-1个结点。性质3：在任意一棵二叉树中，度为0的结点(叶子结点)总比度为2的结点多一个。性质4：具有n个结点的二叉树，其深度至少为log2n+1。其中，log2n表示取log2n 的整数部分。第51页/共72页52（3）满二叉树满二叉树是特殊的二叉树。满二叉树是指除最后一层之外，每一层上的所有结点都有两个子结点。性质5：满二叉树上的第k层上有2k-1个结点。结构如图所示：第52页/共72页53（4）完全二叉树完全二叉树也是一种特殊的二叉树。特殊在:除最后一层之外，每一层上的结点数均达到了最大值，在最后一层上只缺少右边的若干个结点。第53页/共72页54性质6:设完全二叉树共有n个结点

30、。如果从根结点开始，按层序(每一层从左到右)用自然数1，2，3n给结点进行编号。对于编号为k(k=1，2，3n)的结点有以下结论：若k=1，则该结点为根结点，它没有父结点;若k1,则编号为k的结点的父结点为k/2。若2kn，则编号为k的结点的左子结点编号为2k，否则该结点无左子结点，当然也没有右子结点。若2k+1n，则编号为k的结点的右子结点编号为2k+1，否则该结点无右子结点。第54页/共72页55例：k=1，是树的根,无父结点;其左子结点为2*k=2,右子结点为2*k+1=3。k=6，其父结点为k/2=3；其左子结点为2*k=12;2*k+1=1312 其无右子结点。k=9，其父结点为k/

31、2=4；2*k=1812，2*k+1=1912 其无左、右子结点112345678910121第55页/共72页56性质7：具有n个结点的完全二叉树的深度为log2n+1。例：n=2 k=2 n=6 k=3 n=7 k=3 n=8 k=4 n=12 k=4112345678910121第56页/共72页57（5）二叉树的存储结构常见的二叉树的存储结构有两种:顺序存储结构和链式存储结构。顺序存储结构：用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左至右的顺序存储。链式存储结构：用链表来表示 一棵二叉树，即用链来指示着元素的逻辑关系。通常采用二叉链表存储形式。链表中每个结

32、点由3个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左子结点和右子结点所在的链结点的存储地址。Lchild data Rchild第57页/共72页58二叉树链式存储结构示意图第58页/共72页59（6）二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历分为三种：前序遍历、中序遍历、后序遍历。（1）前序遍历（根、左、右）访问根结点；前序遍历左子树；前序遍历右子树。（2）中序遍历（左、根、右）中序遍历左子树；访问根结点；中序遍历右子树。（3）后续遍历（左、右、根）后续遍历左子树；后续遍历右子树；访问根结点。第59页/共72页60例：第60页/共72页61（7）表

33、达式树表示表达式的树叫表达式树。用树来表示算术表达式的原则如下：（1）表达式中的每个运算符在树中对应一个结点，称为运算符结点；（2）运算符的每一个运算对象在树中为该运算符结点的子树，在树中的顺序为从左到右；（3）运算对象中的单变量均为叶子结点；（4）表达式树的表示方法必须按照特定的遍历方法 第61页/共72页62例如，假设表达式为a(b+c/d)+ef-g，则其中序遍历的表达式树如图所示。第62页/共72页63八、查找技术查找是指在一个给定的数据结构中查找某个指定的元素。通常，根据不同的数据结构，应采用不同的查找方法。常见的查找方法有两种：顺序查找、二分法查找。查找是数据处理中的重要环节，一般

34、认为查找的效率将直接影响到数据处理的效率。（1）顺序查找顺序查找是指从线性表的一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示查找成功；若找不到相等的元素则查找失败。第63页/共72页64顺序查找的最好的查询次数是指所查找的元素是线性表的第一个元素时的查询次数。最差的查询次数是指所查找的元素是线性表的最后一位元素或者在线性表中根本不存在这个元素时的查询次数。顺序查找的平均查询次数为大约需要与线性表中一半的元素进行比较的次数。对于庞大的线性表来说，顺序查找的效率是很低的。但是在下列两种情况下只能采用顺序查找：（1）线性表是无序表，即表中的元素的排列是无序的，则不管是顺序结构还是

35、链式结构，都只能用顺序查找；（2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。第64页/共72页65（2）二分法查找二分法查找只适用于顺序存储的有序表。其中，“有序表”是指已对顺序存储结构排序，但允许相邻元素值相等。设有序列表的长度为n，被查找的元素为x，则二分法查找的方法如下：将x与线性表中的中间项进行比较：若中间项的值等于x，则说明查到，查找结束；若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。上述过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元

36、素)为止。第65页/共72页66二分法查找的优点主要有两个:（1）二分法查找的效率比顺序查找高得多；（2）对于长度为n的有序线性表，在最坏的情况下，二分法查找只需要比较log2n次,而顺序查找需要比较n次。第66页/共72页67九、排序技术排序是指将一个无序的列表整理成按值递减（或递增）顺序排列的有序序列。常见的排序方法有:交换类排序、插入类排序和选择类排序。（1）交换式排序交换类排序法是指借助数据元素之间的相互交换进行排序的一种方法。典型交换类排序法实例有两种：冒泡排序和快速排序。第67页/共72页68冒泡排序:通过相邻数据元素交换逐步将线性表变换成有序的。快速排序:将原问题分解成若干个小规

37、模的同结构的问题，递归解决每个子问题。（2）插入类排序 插入类排序方法是指将无序列表中的各元素依次插入到已经有序的线性表中。插入类排序的典型实例有：简单插入排序法和希尔排序法（Shell sort）。第68页/共72页69简单插入排序法：将无序列表中的各元素依次插入到已有序的线性表中。希尔排序法:这是对简单插入排序法的改进，先选取第一个增量，把距离为第一个增量的倍数的记录放在同一组中，在组内进行直接插入排序，再取小于第一个增量的第二个增量，重复上述操作。（3）选择类排序选择类排序法的典型实例有:简单选择排序方法和堆排序方法。简单选择排序:扫描整个线性表，从中选出最小的元素，将它交换到表的最上面

38、。然后对剩下的子表采取相同的方法，直到子表空为止。第69页/共72页70（4）各种排序方法的性能 不同排序方法的时间复杂度、空间复杂度可能是不同的。如下表所示：第70页/共72页71假设线性表长度为n,在最坏的情况下，各种排序方法的比较次数如下：（1）冒泡排序需要经过n/2遍的从前往后的扫描和n/2次的从后往前的扫描，需要的比较次数为n(n-1)/2（2）快速排序方法的比较次数为O(n2)=n(n-1)/2（3）简单插入排序需要的比较次数为n(n-1)/2;（4）希尔排序的比较次数为O(n1.5)；（5）简单选择排序的比较次数为n(n-1)/2；（6）堆排序的比较次数为O(nlog2n)=nlog2n+nC(1)，其中C(1)表示对长度为1的区间进行快速排序所需的比较次数。第71页/共72页感谢您的观看！第72页/共72页