1、第第7章章 数据结构与常用算法数据结构与常用算法7.1 数据结构的基本概念数据结构的基本概念7.2 线性表线性表及其存储结构及其存储结构7.3 栈和队列栈和队列7.4 树与二叉树树与二叉树7.5 查找算法查找算法7.6 排序算法排序算法7.1 数据结构的基本概念数据结构的基本概念7.1.1 基本术语基本术语(1)(1)数据数据：能被计算机识别、存储和加工处：能被计算机识别、存储和加工处理的符号的总称。理的符号的总称。计算机中可以操作的对象计算机中可以操作的对象(2)(2)数据元素数据元素：数据的基本单位。：数据的基本单位。在计算机中通常作为整体处理，也称为记录在计算机中通常作为整体处理，也称为
2、记录(3)(3)数据项数据项：数据元素的最小单位。：数据元素的最小单位。一个数据元素由若干个数据项组成一个数据元素由若干个数据项组成(4)(4)数据对象数据对象：相同性质数据元素的集合。：相同性质数据元素的集合。是数据的子集是数据的子集武汉科技大学计算机科学与技术学院7.1.1 基本术语基本术语数据对象、数据元素与数据项数据对象、数据元素与数据项一列整数一列整数2 2，3 3，5 5，-3-3，8 8，1212若干列整数若干列整数一个学生：学号、姓名、性别、入学成绩。一个学生：学号、姓名、性别、入学成绩。一个学生表：若干条学生记录一个学生表：若干条学生记录7.1.2 数据结构数据结构数据数据结
3、构：带结构：带结构结构的数据元素的集合。的数据元素的集合。数据元素之间相互有数据元素之间相互有关联关联例如，例如，3 3214214，65876587，9345 a1 9345 a1，a2a2，a3a3在在a1a1、a2a2和和a3a3之间存在之间存在“次序次序”关系关系、a2a3不等于不等于 6587,6587,3 3214,9345 a2,a1,214,9345 a2,a1,a3 a3 7.1.2 数据结构数据结构数据结构主要研究和讨论数据结构主要研究和讨论3 3个方面的问题：个方面的问题：数据集合中，各种数据元素之间所固有的逻辑数据集合中，各种数据元素之间所固有的逻辑关系，即数据的关系，
4、即数据的逻辑结构逻辑结构；在对数据进行处理时，各数据元素在计算机中在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的的存储关系，即数据的存储结构存储结构；对各种数据结构进行的对各种数据结构进行的运算运算，其中常用的有检，其中常用的有检索、插入、删除、排序等索、插入、删除、排序等7.1.2 数据结构数据结构1.1.数据的逻辑结构数据的逻辑结构指反映数据元素之间逻辑关系的数据结构。指反映数据元素之间逻辑关系的数据结构。两个要素：两个要素：一是数据元素的集合，通常记为一是数据元素的集合，通常记为D D；二是二是D D上的二元关系，它反映了上的二元关系，它反映了D D中各数据元素之间的中各数
5、据元素之间的前驱与后继关系，通常记为前驱与后继关系，通常记为R R。一个数据结构可以表示成一个数据结构可以表示成B=(D,R)B=(D,R)，其中，其中B B表示数据结表示数据结构。构。通常把数据元素之间的这种固有的关系，简单地通常把数据元素之间的这种固有的关系，简单地用前驱与后继关系来描述。用前驱与后继关系来描述。例如家庭成员的数据结构可以表示成例如家庭成员的数据结构可以表示成B=(D,R)B=(D,R)，其中，其中D=D=父亲，儿子，女儿父亲，儿子，女儿，R=R=，。7.1.2 数据结构数据结构1.1.数据的逻辑结构数据的逻辑结构通常有下面通常有下面3 3种基本结构种基本结构：线性结构线性
6、结构：结构中数据元素之：结构中数据元素之间存在间存在一个对一个一个对一个的关系。的关系。树形结构树形结构：结构中数据元素之：结构中数据元素之间存在间存在一个对多个一个对多个的关系。的关系。图形结构或网状结构图形结构或网状结构：结构中：结构中数据元素之间存在数据元素之间存在多个对多个多个对多个的的关系。关系。线性图形树形7.1.2 数据结构数据结构2.2.数据的存储结构数据的存储结构数据的逻辑结构在计算机数据的逻辑结构在计算机存储空间存储空间中的中的存放形式存放形式称为数据的存储结构（也称物理结构）。称为数据的存储结构（也称物理结构）。在数据的存储结构中，不仅要存放数据元素的信在数据的存储结构中
7、，不仅要存放数据元素的信息，还需要存放各数据元素之间的前驱和后继息，还需要存放各数据元素之间的前驱和后继关关系的信息系的信息。4 4种常见的存储结构种常见的存储结构：(1)(1)顺序存储结构顺序存储结构(2)(2)链式存储结构链式存储结构(3)(3)索引存储结构索引存储结构(4)(4)散列存储结构散列存储结构return7.2 线性表及其存储结构线性表及其存储结构7.2.1 线性表的基本概念线性表的基本概念通常，线性表是由通常，线性表是由n n(n n0)0)个数据元素个数据元素 a a1 1,a a2 2,a an n组成的一个有限序列。组成的一个有限序列。存在存在唯一的唯一的一个被称为一个
8、被称为“第一个第一个”的数据元素；的数据元素；存在存在唯一的唯一的一个被称为一个被称为“最后一个最后一个”的数据元的数据元素；素；除了第一个之外，表中的每个数据元素均只有除了第一个之外，表中的每个数据元素均只有一个一个前驱；前驱；除了最后一个之外，表中的每个数据元素均只除了最后一个之外，表中的每个数据元素均只有有一个一个后继。后继。线性表线性表的的数据元素，通常也称为数据元素，通常也称为节点节点。数据元素在线性表中的数据元素在线性表中的位置位置只取决于它们自只取决于它们自己的序号。己的序号。线性表中节点的个数线性表中节点的个数 n n 称为线性表的长度。称为线性表的长度。当当 n n=0=0
9、时，称为空表。时，称为空表。1.1.线性表的顺序存储线性表的顺序存储（顺序表）（顺序表）线性表中的所有元素所占的存储空间是连续的；线性表中的所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。序依次存放的。高级语言中，常用高级语言中，常用“一维数组一维数组”a(1:m)”a(1:m)表示这表示这种存储结构种存储结构武汉科技大学计算机科学与技术学院序号数据元素存储地址1a1ADR（a1）2a2ADR（a1）+kiaiADR（a1）（i1）knanADR（a1）（n1）k7.2.2 线性表的顺序存储及其运算线性表的顺序存储及
10、其运算2.2.顺序表的基本运算顺序表的基本运算(1)(1)顺序表的插入顺序表的插入（aiai 前插入前插入 x x）移动元素：移动元素：从最后一个（即第从最后一个（即第 n n个）元素开始，直到个）元素开始，直到第第 i i 个元素之间共个元素之间共 n-i+1 n-i+1 个元素依次向后移动一个个元素依次向后移动一个位置位置ajaj aj+1(j:aj+1(j:nini )插入新元素：插入新元素：将新元素将新元素 x x 插入到第插入到第 i i 个位置个位置x x aiai更新长度：更新长度：n+1n+1n n当当 n=m n=m 时，不能再插入，否则会时，不能再插入，否则会“上溢上溢”；
11、所以插入前要检查是否会所以插入前要检查是否会“上溢上溢”。序号 数据元素存储地址1a1ADR（a1）2a2ADR（a1）+kiaiADR（a1）（i1）knanADR（a1）（n1）k2.2.顺序表的基本运算顺序表的基本运算(2)(2)顺序表的删除顺序表的删除(删除删除aiai)移动元素：移动元素：从第从第 i+1 i+1 个元素开始，直到第个元素开始，直到第 n n 个元素个元素之间，共有之间，共有 n n i i 个元素依次向前移动一个位置。个元素依次向前移动一个位置。ajaj aj-1(j:aj-1(j:inin)更新长度：更新长度：n-1n-1n n当当 n=0 n=0 时不能再删除，
12、时不能再删除，否则会否则会“下溢下溢”；所以删除前要检查是否所以删除前要检查是否会会“下溢下溢”。序号 数据元素存储地址1a1ADR（a1）2a2ADR（a1）+kiaiADR（a1）（i1）knanADR（a1）（n1）k线性表的顺序存储结构线性表的顺序存储结构的特点的特点具有具有简单、存储密度大、空间利用率高、对表中简单、存储密度大、空间利用率高、对表中任一元素可直接确定其存储地址（随机存取）、任一元素可直接确定其存储地址（随机存取）、效率高等优点；效率高等优点；但是也有明显的不足：但是也有明显的不足：在顺序表中进行插入与删除等操作时，需大量移动数在顺序表中进行插入与删除等操作时，需大量移
13、动数据元素，浪费时间。据元素，浪费时间。因此，对于大的线性表，特别是元素变动频繁的大线因此，对于大的线性表，特别是元素变动频繁的大线性表，不宜采用顺序存储结构，而是采用链式存储结性表，不宜采用顺序存储结构，而是采用链式存储结构。构。1.1.线性表的链式存储线性表的链式存储通过每个节点的指针域将通过每个节点的指针域将n n个节点按其逻辑顺序个节点按其逻辑顺序连接在一起而构成的数据存储结构，称为链式存连接在一起而构成的数据存储结构，称为链式存储结构储结构。对线性链表而言，它不要求逻辑上相邻的元素在对线性链表而言，它不要求逻辑上相邻的元素在物理位置上也相邻，其存储单元既可以是连续的，物理位置上也相邻
14、，其存储单元既可以是连续的，也可以是不连续的，甚至可以零散分布在存储空也可以是不连续的，甚至可以零散分布在存储空间中的任何位置上。间中的任何位置上。数据域 指针域其中指针域 next 用于指向该节点的后继节点datanext7.2.3 线性表的链式存储及其运算线性表的链式存储及其运算1.1.线性表的链式存储线性表的链式存储序号 数据域1a292 3a114 5a406 7 8 9a35指针域3Heada1a2Heada3a43195datanext2.2.单链表的基本运算单链表的基本运算(1)(1)单链表的插入单链表的插入(2)(2)单链表的删除单链表的删除ai1aiXADR(ai-1)ADR
15、(x)ai1aiai1ADR(ai-1)ADR(ai-1).next ADR(x).next ADR(x)ADR(ai-1).next ADR(ai-1).next.next ADR(ai-1).next 释放 ADR(ai-1).nextreturn7.3 栈和队列栈和队列7.3.1 栈及其基本运算栈及其基本运算1.1.什么是栈什么是栈栈是栈是限定在一端限定在一端进行插入和删除进行插入和删除的线性表。的线性表。在栈中，允许插入和删除的一端称在栈中，允许插入和删除的一端称为为栈顶栈顶，用指针，用指针 top top 来表示栈顶的来表示栈顶的位置位置注意，注意，toptop的指向的指向而不允许插
16、入和删除的另一端称为而不允许插入和删除的另一端称为栈底栈底，用用 bottom bottom 指向栈底指向栈底注意，注意，bottombottom的指向的指向a1a2an栈顶 top栈底 bottom入栈退栈1.1.什么是栈什么是栈栈也被称为栈也被称为“先进后出先进后出”表或表或“后进先出后进先出”表。表。因此因此，栈具有记忆作用栈具有记忆作用。例如：例如：货物堆放货物堆放子弹夹子弹夹函数的调用函数的调用a1a2an栈顶 top栈底 bottom入栈退栈武汉科技大学计算机科学与技术学院2.2.栈的顺序存储及其运算栈的顺序存储及其运算在程序设计语言中，用一维数组在程序设计语言中，用一维数组 S
17、S(1:(1:m m)作为栈作为栈的顺序存储空间，其中的顺序存储空间，其中m m为栈的最大容量。为栈的最大容量。初始状态：初始状态：bottom=1bottom=1，top=0top=0S(1:10)S(1:10)S(1:10)A1B2C3D4E5F6X7Y8 9 10topbottom(b)插入X与Y后的栈A1B2C3D4E5F6 7 8 9 10topbottom(a)有6个元素的栈A1B2C3D4E5F6X7 8 9 10topbottom(c)退出一个元素后的栈对栈的定义的进一步理解对栈的定义的进一步理解一个栈的入栈序列是一个栈的入栈序列是a,b,c,d,ea,b,c,d,e，则不，则
18、不可能的出栈序列是（可能的出栈序列是（）。）。A AedcbaedcbaB BdecbadecbaC CdceabdceabD Dabcdeabcde2.2.栈的顺序存储及其运算栈的顺序存储及其运算(1)(1)入栈运算入栈运算1.1.更新更新栈顶栈顶指针：指针：top+1 top+1 top top2.2.插入插入新元素：新元素：x x S Stoptop当当 top=m top=m 时，时，说明栈空间已满，不说明栈空间已满，不能再进行入栈操作。能再进行入栈操作。否则出现否则出现“上溢上溢”错误。错误。所以所以入栈之前入栈之前，要检查是否会，要检查是否会“上溢上溢”top-x2.2.栈的顺序存
19、储及其运算栈的顺序存储及其运算(2)(2)退栈运算退栈运算1.1.读读栈顶栈顶元素元素：S Stoptop x x2.2.更新更新栈顶指针栈顶指针：top-1 top-1 top top当当 top=0 top=0 时，说明栈空，不能时，说明栈空，不能再再进进行退栈运算。行退栈运算。否则会出现否则会出现“下溢下溢”错错误误；所以所以退栈之前退栈之前，要检查是否会，要检查是否会“下溢下溢”top-x2.2.栈的顺序存储及其运算栈的顺序存储及其运算(3)(3)读栈顶元素读栈顶元素读数：读数：S Stoptop x x栈顶指针栈顶指针保持保持不变不变当当 top=0top=0 时，说明栈空，读不到栈
20、顶元素时，说明栈空，读不到栈顶元素；所以所以读数之前读数之前，要检查是否为空栈。，要检查是否为空栈。7.3.2 队列及其基本运算队列及其基本运算武汉科技大学计算机科学与技术学院1.1.什么是队列什么是队列指允许指允许在一端进行插入，而在另一端进行删除在一端进行插入，而在另一端进行删除的的线性表。线性表。允许插入的一端称为允许插入的一端称为队尾队尾，通常用一个称为队尾指针，通常用一个称为队尾指针（rearrear）的指针指向队尾元素的下一个位置）的指针指向队尾元素的下一个位置注意，注意，rear rear 的指向的指向允许删除的一端称为允许删除的一端称为队首队首，通常用一个称为队首指针，通常用一
21、个称为队首指针（frontfront）的指针指向队首元素的位置）的指针指向队首元素的位置注意，注意，front front 的指向的指向ABCDEFG出队入队frontrear1.1.什么是队列什么是队列队列又称为队列又称为“先进先出先进先出”或或“后进后出后进后出”的线的线性表，它体现了性表，它体现了“先来先服务先来先服务”的原则。的原则。例如：例如：排队等候现象排队等候现象ABCDEFG出队入队frontrear武汉科技大学计算机科学与技术学院1.1.什么是队列什么是队列在程序设计语言中，用一维数组在程序设计语言中，用一维数组 S S(1:(1:m m)作为队作为队列的顺序存储空间，其中列
22、的顺序存储空间，其中 m m 为为队列队列的最大容量的最大容量初始状态：初始状态：front=rear=1front=rear=1(b)删除元素A后的队列 BCDrearfront(a)一个队列ABCDrearfront(c)插入元素E后的队列 BCDErearfront1.1.什么是队列什么是队列入队运算入队运算1.1.插入插入新元素：新元素：x x S Srearrear2.2.更新更新队尾指针：队尾指针：rear+1rear+1 rear rear当当 rear=m+1 rear=m+1 时，说明栈时，说明栈队列满队列满，不能不能再入队再入队。否则会出现否则会出现“上上溢溢”错误错误；所
23、以入队之前，要检查是否会所以入队之前，要检查是否会“上上溢溢”观察：此时队首前面可能还有空位观察：此时队首前面可能还有空位置。置。rear-x1.1.什么是队列什么是队列出队运算出队运算1.1.读读队首元素：队首元素：S S frontfront x x2.2.更新更新队首指针：队首指针：front+1front+1 frontfront当当 front=rear front=rear 时，不能时，不能再出队再出队了了。否则会出现否则会出现“下下溢溢”错误错误；所以出队之前，要检查是否会所以出队之前，要检查是否会“下下溢溢”观察：出队后会留下空位置，但已观察：出队后会留下空位置，但已不能继续使
24、用了不能继续使用了空间的浪费！空间的浪费！front-x2.2.循环队列及其运算循环队列及其运算将队列存储空间的最后一个将队列存储空间的最后一个位置绕到第一个位置，形成位置绕到第一个位置，形成逻辑上的环状空间逻辑上的环状空间，供队列，供队列循环使用循环使用。当队尾指针当队尾指针 rear=m+1rear=m+1时，则时，则置置rear=1rear=1。当队首指针当队首指针 front=m+1front=m+1时，则时，则置置 front=1front=1。Q(1:m)1 2 mrearfront2.2.循环队列及其运算循环队列及其运算 1 2C3D4E5F6 7Q(1:7)rearfront(
25、b)退出2个元素后的循环队列A1B2C3D4E5F6 7Q(1:7)rearfront(a)具有6个元素的循环队列Y1 2C3D4E5F6X7Q(1:7)front(c)插入元素X、Y后的循环队列rear武汉科技大学计算机科学与技术学院2.2.循环队列及其运算循环队列及其运算循环队列队满时循环队列队满时，有有 front=rear front=rear；而当循环队而当循环队列空时列空时，也有也有front=rearfront=rear。解决办法：解决办法：增加一个标志增加一个标志 s s循环队列初始状态循环队列初始状态：front=rear=1front=rear=1，且，且 s=0s=0 1
26、 2C3D4E5F6 7Q(1:7)rearfront(b)退出2个元素后的循环队列A1B2C3D4E5F6 7Q(1:7)rearfront(a)具有6个元素的循环队列Y1 2C3D4E5F6X7Q(1:7)front(c)插入元素X、Y后的循环队列rear0,1,s表示队列空表示队列非空2.2.循环队列及其运算循环队列及其运算(1)(1)入队运算入队运算1.1.插入插入新元素新元素：x x S Srearrear2.2.更新更新队尾指针队尾指针和空否标志：和空否标志：rear+1 rear+1 rear rear，当，当 rear=rear=m m+1+1 时置时置rear=1rear=1
27、，且且如果如果此时此时 s s=0=0，则置，则置 s s=1=1，表示队列非空。表示队列非空。防止防止“上溢上溢”：入队之前要检查，是否：入队之前要检查，是否 s s=1=1且且 font=rearfont=rear2.2.循环队列及其运算循环队列及其运算(2)(2)出队运算出队运算1.1.读读队首队首元素：元素：S Sfrontfront x x2.2.更新更新队首指针队首指针和空否标志：和空否标志：front+1 front+1 front front，当，当 front=front=m m+1+1时置时置 front=1 front=1，且且如果如果此时此时 front=rearfro
28、nt=rear，则说明队空，应则说明队空，应置置 s=s=0 0。防止防止“下溢下溢”：出队之前要检查，是否：出队之前要检查，是否 s s=0=0且且 font=rearfont=rear7.4 树与二叉树树与二叉树7.4.1 树的基本概念树的基本概念1.1.树的定义树的定义树是树是n n(n n 0)0)个节点的有限集个节点的有限集T T。当。当n n=0=0时，时，称为空树；当称为空树；当n n 0 0时，该集合满足如下条件：时，该集合满足如下条件：有且仅有一个根节点；有且仅有一个根节点；其余的节点可分为其余的节点可分为m m(m m 0)0)个互不相交的子集个互不相交的子集T T1 1,
29、T T2 2,T Tm m，其中每个子集本身又是一颗树，并称其，其中每个子集本身又是一颗树，并称其为根的子树。为根的子树。ABFKLEGCHDJIM这是一个递归定义，是表达“一对多”的逻辑关系2.2.树的基本术语树的基本术语节点的度节点的度，例如：，例如：节点节点A A的度为的度为3 3，节点，节点C C的度为的度为1 1树的度树的度，例如：，例如：树的度为树的度为3 3叶子叶子，例如：节，例如：节点点E E，G G，H H，J J，K K，L L，M M分支节点分支节点，例如：，例如：节点节点A A，B B，C C，D D，F F，I I双亲和孩子双亲和孩子，例如：，例如：节点节点A A是是
30、B B、C C、D D的双亲的双亲节点的层节点的层，例如：，例如：节点节点E E、F F、G G、H H、I I、J J的层均为的层均为3 3树的深度树的深度，例如：图中，例如：图中树的深度为树的深度为4 4兄弟和堂兄弟兄弟和堂兄弟祖先和子孙祖先和子孙有序树和无序树有序树和无序树森林森林ABFKLEGCHDJIM度的概念的进一步理解度的概念的进一步理解9 9设树设树T T的度为的度为4 4，其中度为，其中度为1,2,3,41,2,3,4的的结点数分别为结点数分别为4,2,1,14,2,1,1。则。则T T中的叶子结中的叶子结点数为（点数为（）。）。A A8 8 B B7 7 C C6 D6 D
31、5 57.4.2 二叉树及其基本性质二叉树及其基本性质1.1.二叉树的定义二叉树的定义二叉树是二叉树是n n(n n 0)0)个节点的有限集，它或者是个节点的有限集，它或者是空集空集(n n=0)=0)，或者是由一个根节点和两颗互不相，或者是由一个根节点和两颗互不相交且分别称为根的左子树和右子树的二叉树组成。交且分别称为根的左子树和右子树的二叉树组成。在二叉树中，每一个节点的度最大为在二叉树中，每一个节点的度最大为2 2。二叉树和度为二叉树和度为2 2的树是的树是两个不同的概念两个不同的概念。AABABCAB（a）空二叉树（b）仅有根结点的二叉树（c）左子树为空的二叉树（d）右子树为空的二叉树
32、（e）左、右子树均非空的二叉树一颗野生的二叉树一颗野生的二叉树2.2.二叉树的基本性质二叉树的基本性质【性质【性质1 1】在二叉树的】在二叉树的第第 i i 层层至多有至多有 2 2i i-1-1 个节个节点点(i i1)1)。【性质【性质2 2】深度深度为为k k的二叉树至多的二叉树至多有有 2 2k k 1 1个节点个节点(k k1)1)。【性质【性质3 3】对任何一颗二叉树】对任何一颗二叉树T T，如果其叶子节点，如果其叶子节点数为数为n n0 0，度为，度为2 2的节点数为的节点数为n n2 2，则，则 n n0 0=n n2 2+1+1。【性质【性质4 4】具有】具有n n(n n1
33、)1)个个节点节点的完全二叉树的的完全二叉树的深深度度为为log log n n+1+1（其中（其中log log n n 表示取表示取log log n n的整的整数部分）。数部分）。2.2.二叉树的基本性质二叉树的基本性质满二叉树满二叉树完全二叉树完全二叉树非完全二叉树非完全二叉树（a）满二叉树（b）完全二叉树（c）非完全二叉树1245361245367124536完全二叉树的深入理解完全二叉树的深入理解1010设一棵完全二叉树共有设一棵完全二叉树共有700700个节点，则个节点，则该二叉树中有该二叉树中有_个叶子节个叶子节点。点。7.4.3 二叉树的存储结构二叉树的存储结构1.1.顺序存
34、储结构顺序存储结构完全二叉树的顺序存储结构完全二叉树的顺序存储结构非完全二叉树的顺序存储结构非完全二叉树的顺序存储结构2.2.链式存储结构链式存储结构lchilddatarchildABCDEFroot7.4.4 二叉树的遍历二叉树的遍历遍历一棵二叉树就是按照某种规则去遍历一棵二叉树就是按照某种规则去访问二叉访问二叉树的每个节点，而且每个节点仅被访问一次树的每个节点，而且每个节点仅被访问一次。在在先左后右先左后右的约定下，根据访问根节点的次序，的约定下，根据访问根节点的次序，二叉树的遍历可以分为二叉树的遍历可以分为:(1)(1)先根遍历先根遍历例如：例如：ABDFCE ABDFCE(2)(2)
35、中根遍历中根遍历例如：例如：BFDACE BFDACE(3)(3)后根遍历后根遍历例如：例如：FDBECA FDBECA武汉科技大学计算机科学与技术学院练习：练习：先根遍历序列：先根遍历序列：+a+a*b b cd/efcd/ef中根遍历序列：中根遍历序列：a+ba+b*c c d d e/fe/f后根遍历序列：后根遍历序列：abcdabcd*+efef/fea*bdc二叉树遍历练习二叉树遍历练习1111设一棵二叉树的中序遍历结果为设一棵二叉树的中序遍历结果为DBEAFCDBEAFC，先序遍历结果为先序遍历结果为ABDECFABDECF，则该二叉树的后序，则该二叉树的后序遍历结果为遍历结果为_
36、。return7.5 查找算法查找算法7.5 查找算法查找算法1 1定义定义查找就是根据给定的值，在一组数据中确定一个查找就是根据给定的值，在一组数据中确定一个其数值等于给定值的数据元素，若存在这样的数其数值等于给定值的数据元素，若存在这样的数据元素说明查找是成功的，否则查找是不成功的。据元素说明查找是成功的，否则查找是不成功的。查找某个数据元素取决于数据中数据元素的组织查找某个数据元素取决于数据中数据元素的组织方式。方式。衡量查找算法好坏的标准是以平均查找比较的次衡量查找算法好坏的标准是以平均查找比较的次数来定。数来定。2 2查找方法查找方法顺序查找顺序查找顺序查找方法的平均查找比较次数为顺
37、序查找方法的平均查找比较次数为(n n+1)/2+1)/2。折半查找折半查找只能用于只能用于顺序存储顺序存储的数据元素且各数据元素按关键字有序的数据元素且各数据元素按关键字有序排列的序列。排列的序列。其基本思想是：假设查找表中的数据元素按关键字递增有其基本思想是：假设查找表中的数据元素按关键字递增有序排列，则首先与序排列，则首先与“中间位置中间位置”的元素比较，若相等则查的元素比较，若相等则查找成功；若给定值大于找成功；若给定值大于“中间位置中间位置”的元素值，则在后半的元素值，则在后半部继续进行折半查找；否则在前半部分进行折半查找。部继续进行折半查找；否则在前半部分进行折半查找。当在长度为当
38、在长度为n n的表中使用折半查找时，最坏情况下的查找长的表中使用折半查找时，最坏情况下的查找长度不超过度不超过loglog2 2 n n+1+12 2查找方法查找方法如果采用顺序查找方法来查找如果采用顺序查找方法来查找2121，需要比较，需要比较4 4次；次；如如果采用折半查找方法来查找果采用折半查找方法来查找2121，需要比较，需要比较3 3次次序号1234567891011数据513192137566475808892return7.6 排序算法排序算法7.6 排序算法排序算法1 1选择排序（从小到大）选择排序（从小到大）原始序列 89 21 56 48 85 16 19 47第1遍 16
39、 21 56 48 85 89 19 47第2遍 16 19 56 48 85 89 21 47第3遍 16 19 21 48 85 89 56 47第4遍 16 19 21 47 85 89 56 48第5遍 16 19 21 47 48 89 56 85第6遍 16 19 21 47 48 56 89 85第7遍 16 19 21 47 48 56 85 89与“固定位固定位”比较，后大则互换，使“最小者最小者”出现在“最前面最前面”。武汉科技大学计算机科学与技术学院2 2交换排序交换排序（冒泡排序，从小到大）（冒泡排序，从小到大）原始序列 89 21 56 48 85 16 19 47第
40、1遍 21 89 56 48 85 16 19 47 21 56 89 48 85 16 19 47 21 56 48 89 85 16 19 47 21 56 48 85 89 16 19 47 21 56 48 85 16 89 19 47 21 56 48 85 16 19 89 47 结果 21 56 48 85 16 19 47 89第2遍 21 56 48 85 16 19 47 89 结果 21 48 56 16 19 47 85 89第3遍 21 48 56 16 19 47 85 89 结果 21 48 16 19 47 56 85 89第4遍 21 48 16 19 47
41、56 85 89 结果 21 16 19 47 48 56 85 89 相邻比较相邻比较两个元素，前大则互换，使“最最大者大者”移动至“最后最后”。武汉科技大学计算机科学与技术学院原始序列 89 21 56 48 85 16 19 47第4遍 21 48 16 19 47 56 85 89 结果 21 16 19 47 48 56 85 89第5遍 21 16 19 47 48 56 85 89 结果 16 19 21 47 48 56 85 89第6遍 16 19 21 47 48 56 85 89 结果 16 19 21 47 48 56 85 89第7遍 16 19 21 47 48 56 85 89 结果 16 19 21 47 48 56 85 893 3插入排序插入排序 原始序列 89 21 56 48 85 16 19 47 第1遍 21 89 56 48 85 16 19 47 第2遍 21 56 89 48 85 16 19 47 第3遍 21 48 56 89 85 16 19 47 第4遍 21 48 56 85 89 16 19 47 第5遍 16 21 48 56 85 89 19 47 第6遍 16 19 21 48 56 85 89 47 第7遍 16 19 21 47 48 56 85 89 return
