第5章 数据结构基础PPT讲稿.ppt

第第5 5章章 数据结构基数据结构基础础第1页，共49页，编辑于2022年，星期一5.1 5.1 引言引言J5.1.1 5.1.1 什么是数据结构什么是数据结构J5.1.2 5.1.2 数据的逻辑结构数据的逻辑结构J5.1.3 5.1.3 数据的存储结构数据的存储结构J5.1.4 5.1.4 数据的运算数据的运算第2页，共49页，编辑于2022年，星期一应用举例应用举例学籍档案管理学籍档案管理J学生信息表：学生信息表：C每个学生的信息占一行，结构类型每个学生的信息占一行，结构类型C表中依据学号的大小存在着一种前后关系，即表中依据学号的大小存在着一种前后关系，即线性结构线性结构C操作通常是插入、删除、更新某个学生的信息，操作通常是插入、删除、更新某个学生的信息，和按条件检索某个学生的信息等和按条件检索某个学生的信息等第3页，共49页，编辑于2022年，星期一其它应用举例其它应用举例J计算机和人对奕问题计算机和人对奕问题C对弈的规则和策略对弈的规则和策略-算法算法算法算法C棋盘及棋盘的格局棋盘及棋盘的格局棋盘及棋盘的格局棋盘及棋盘的格局-模型、树模型、树模型、树模型、树J多叉路口交通灯的管理问题多叉路口交通灯的管理问题C路口、通路、交通灯颜色路口、通路、交通灯颜色路口、通路、交通灯颜色路口、通路、交通灯颜色-图图图图第4页，共49页，编辑于2022年，星期一5.1.1 5.1.1 什么是数据结构什么是数据结构J研究数据之间的相互关系研究数据之间的相互关系C逻辑结构逻辑结构C C存储结构（物理结构）存储结构（物理结构）存储结构（物理结构）存储结构（物理结构）C C数据的运算数据的运算数据的运算数据的运算J数据类型数据类型C原子类型原子类型原子类型原子类型 -不可分解不可分解不可分解不可分解C结构类型结构类型结构类型结构类型 -原子类型构造而成原子类型构造而成原子类型构造而成原子类型构造而成第5页，共49页，编辑于2022年，星期一5.1.25.1.2数据的逻辑结构数据的逻辑结构第6页，共49页，编辑于2022年，星期一5.1.3 5.1.3 数据的存储结构数据的存储结构J数据的逻辑结构在计算机存储器中的实现，数据的逻辑结构在计算机存储器中的实现，也称也称物理结构物理结构C顺序映射方式顺序映射方式C链接映射方式链接映射方式C索引映射方式索引映射方式C散列映射方式散列映射方式第7页，共49页，编辑于2022年，星期一1 1、顺序存储顺序存储J用一组连续地址依次存储类型相同、有序用一组连续地址依次存储类型相同、有序的数据元素的集合的数据元素的集合C可以采用索引的方式访问其中的元素可以采用索引的方式访问其中的元素J一维数组描述一维数组描述C数组名称为数组名称为b bC用用b0b0表示第一个元素表示第一个元素表示第一个元素表示第一个元素C C用用用用b1表示第二个元素表示第二个元素表示第二个元素表示第二个元素C CC C 内的数是元素的索引下标内的数是元素的索引下标内的数是元素的索引下标内的数是元素的索引下标可以是常量也可以是变量可以是常量也可以是变量可以是常量也可以是变量可以是常量也可以是变量也可以用循环结构访问数组元素也可以用循环结构访问数组元素也可以用循环结构访问数组元素也可以用循环结构访问数组元素b+b+b+b+b+第8页，共49页，编辑于2022年，星期一插入插入删除删除第9页，共49页，编辑于2022年，星期一2 2、链式存储、链式存储v链表是一个链式存储的线性表链表是一个链式存储的线性表v链表将物理上不连续的结点连接起来链表将物理上不连续的结点连接起来vv链链链链表表表表中中中中的的的的每每每每个个个个元元元元素素素素习习习习惯惯惯惯上上上上被被被被称称称称为为为为结结点点点点，结结点点包包含含两部分：两部分：vv数据数据数据数据vv指针指针指针指针(指针即是存储下一个相同类型元素的地址指针即是存储下一个相同类型元素的地址指针即是存储下一个相同类型元素的地址指针即是存储下一个相同类型元素的地址)v链表包括单链表、双链表、循环链表链表包括单链表、双链表、循环链表，在，在此只讨论单链表此只讨论单链表第10页，共49页，编辑于2022年，星期一单链表单链表J即每个即每个节点节点仅有一个指向后继节点的链仅有一个指向后继节点的链C通常使用一个指针变量指向第一个元素，称为通常使用一个指针变量指向第一个元素，称为通常使用一个指针变量指向第一个元素，称为通常使用一个指针变量指向第一个元素，称为链表的链表的链表的链表的头指针头指针头指针头指针通过头指针可以顺序访问其后的所有节点通过头指针可以顺序访问其后的所有节点通过头指针可以顺序访问其后的所有节点通过头指针可以顺序访问其后的所有节点C链表的最后一个元素包含一个链表的最后一个元素包含一个空指针空指针空指针空指针，标识链，标识链表的结束表的结束第11页，共49页，编辑于2022年，星期一链表的操作链表的操作J对链表的操作很多：对链表的操作很多：C C插入节点插入节点插入节点插入节点C删除节点删除节点C C查找列表查找列表查找列表查找列表C C检索列表检索列表检索列表检索列表C C遍历列表遍历列表遍历列表遍历列表C C注意：注意：注意：注意：（1 1）当向表尾插入、向表头插入、向空）当向表尾插入、向表头插入、向空）当向表尾插入、向表头插入、向空）当向表尾插入、向表头插入、向空表插入节点时，要做特殊处理表插入节点时，要做特殊处理表插入节点时，要做特殊处理表插入节点时，要做特殊处理（2 2）删除第一个节点、只有一个节点时，）删除第一个节点、只有一个节点时，）删除第一个节点、只有一个节点时，）删除第一个节点、只有一个节点时，要做特殊处理要做特殊处理要做特殊处理要做特殊处理第12页，共49页，编辑于2022年，星期一5.1.4 5.1.4 数据的运算数据的运算第13页，共49页，编辑于2022年，星期一5.2 5.2 线性结构线性结构J5.2.1 5.2.1 线性表线性表J5.2.2 5.2.2 栈栈J5.2.3 5.2.3 队列队列第14页，共49页，编辑于2022年，星期一5.2.1 5.2.1 线性表线性表J线性表是一个列表，列表内每个元素都有线性表是一个列表，列表内每个元素都有唯一的前驱和后继元素唯一的前驱和后继元素(除去最开始和末尾除去最开始和末尾的元素的元素)C线性表具有顺序结构线性表具有顺序结构J存储存储C顺序、链表顺序、链表J计算机应用计算机应用C一元多项式，如一元多项式，如7+3x+9x8第15页，共49页，编辑于2022年，星期一5.2.2 5.2.2 栈栈J栈是一种栈是一种线性表线性表，对栈的添加和删除只能对栈的添加和删除只能在在“栈顶栈顶”进行进行C栈顶、栈底栈顶、栈底C“后进先出后进先出”原则原则第16页，共49页，编辑于2022年，星期一栈的栈的“后进先出后进先出”原则原则J1 1、入栈、入栈pushpushC若没有足够的空间，若没有足够的空间，不能添加元素（不能添加元素（溢溢溢溢）C C栈顶添加新的元素栈顶添加新的元素栈顶添加新的元素栈顶添加新的元素C新的元素成为栈顶新的元素成为栈顶J2 2、出栈、出栈poppopCC当栈为空时不能执当栈为空时不能执当栈为空时不能执当栈为空时不能执行出栈操作行出栈操作行出栈操作行出栈操作CC将栈顶元素移走并返将栈顶元素移走并返将栈顶元素移走并返将栈顶元素移走并返回给用户回给用户回给用户回给用户第17页，共49页，编辑于2022年，星期一栈的应用栈的应用J代数表达式中的括号匹配的检验代数表达式中的括号匹配的检验C遇到左括号时入栈，遇到右括号时让左括号出遇到左括号时入栈，遇到右括号时让左括号出栈并删除栈并删除如果栈最后非空，表明左括号多了如果栈最后非空，表明左括号多了如果栈最后非空，表明左括号多了如果栈最后非空，表明左括号多了如果遇到右括号而栈已经空了，表明右括号多了如果遇到右括号而栈已经空了，表明右括号多了如果遇到右括号而栈已经空了，表明右括号多了如果遇到右括号而栈已经空了，表明右括号多了J迷宫求解迷宫求解J表达式求值表达式求值第18页，共49页，编辑于2022年，星期一5.2.3 5.2.3 队列队列J队列也是一种线性表队列也是一种线性表C数据数据只能在称为只能在称为“尾部尾部”的一端插入，只能的一端插入，只能从称为从称为“头部头部”的一端删除的一端删除C“先进先出先进先出”原则原则第19页，共49页，编辑于2022年，星期一5.3 5.3 树形结构树形结构J5.3.1 5.3.1 树及其遍历树及其遍历J5.3.2 5.3.2 二叉树二叉树J5.3.3 5.3.3 遍历二叉树遍历二叉树第20页，共49页，编辑于2022年，星期一5.3.1 5.3.1 树及其遍历树及其遍历J树树包包括括一一组组有有限限的的元元素素，这这些些元元素素称称为为结结点点；同同时时包包括括一一组组有有向向线线段段，用用来来连连接接结结点，称为点，称为分支分支。J一个结点的子树个数称为该结点的一个结点的子树个数称为该结点的度数度数度为0的结点称为叶子父：A子：C、D兄弟：E、F第21页，共49页，编辑于2022年，星期一数的遍历数的遍历J遍历就是按一定的次序系统地访问树的所有遍历就是按一定的次序系统地访问树的所有结点，并且结点，并且只访问一次只访问一次C C树的线性化树的线性化树的线性化树的线性化J遍历方法：遍历方法：C C深度优先深度优先深度优先深度优先先根次序先根次序先根次序先根次序后根次序后根次序后根次序后根次序C广度优先广度优先按层次遍历按层次遍历按层次遍历按层次遍历第22页，共49页，编辑于2022年，星期一5.3.2 5.3.2 二叉树二叉树J二叉树是结点的有限集合，它或为二叉树是结点的有限集合，它或为二叉树是结点的有限集合，它或为二叉树是结点的有限集合，它或为空集空集空集空集，或为由一个，或为由一个，或为由一个，或为由一个根根根根结点结点结点结点和和两两棵互不相交的称为棵互不相交的称为棵互不相交的称为棵互不相交的称为左右左右左右左右的二叉树构成的二叉树构成的二叉树构成的二叉树构成C C树至少有一个结点，而二叉树可以为空树至少有一个结点，而二叉树可以为空树至少有一个结点，而二叉树可以为空树至少有一个结点，而二叉树可以为空C C树的子树不分次序，二叉树的子树有左右之分树的子树不分次序，二叉树的子树有左右之分树的子树不分次序，二叉树的子树有左右之分树的子树不分次序，二叉树的子树有左右之分C C二叉树的任何一个节点只能有二叉树的任何一个节点只能有二叉树的任何一个节点只能有二叉树的任何一个节点只能有0 0、1 1或或或或2 2棵子树棵子树棵子树棵子树C C二叉树的存储：链接方式二叉树的存储：链接方式二叉树的存储：链接方式二叉树的存储：链接方式C C一般先把树或森林转换为一颗二叉树，再进行存储和运算一般先把树或森林转换为一颗二叉树，再进行存储和运算一般先把树或森林转换为一颗二叉树，再进行存储和运算一般先把树或森林转换为一颗二叉树，再进行存储和运算只保留父到第一个子结点的连线，作为左子树只保留父到第一个子结点的连线，作为左子树只保留父到第一个子结点的连线，作为左子树只保留父到第一个子结点的连线，作为左子树子结点的兄弟依次连线，作为右子树子结点的兄弟依次连线，作为右子树子结点的兄弟依次连线，作为右子树子结点的兄弟依次连线，作为右子树左子树结点右子树基本形态第23页，共49页，编辑于2022年，星期一二叉树的性质二叉树的性质J深度：树中结点的最大层次深度：树中结点的最大层次C C深度为深度为深度为深度为k k的二叉树的结点总数最大为的二叉树的结点总数最大为2k-1-1C C第第第第i层的结点数最大为层的结点数最大为层的结点数最大为层的结点数最大为2 2i-1i-1C具有具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为intint（loglog2 2n n）+1+1J任何一个二叉树任何一个二叉树T T，若其叶子为，若其叶子为n0n0个，而度数个，而度数为为2 2的结点数为的结点数为n2n2，则，则n0=n2+1n0=n2+1第24页，共49页，编辑于2022年，星期一特殊的二叉树特殊的二叉树J1.1.1.1.平衡二叉树平衡二叉树平衡二叉树平衡二叉树C C平衡因子：二叉树中任一结点的右子树与平衡因子：二叉树中任一结点的右子树与平衡因子：二叉树中任一结点的右子树与平衡因子：二叉树中任一结点的右子树与左子树的深度之差左子树的深度之差左子树的深度之差左子树的深度之差C C平衡二叉树：所有结点的平衡因子为平衡二叉树：所有结点的平衡因子为平衡二叉树：所有结点的平衡因子为平衡二叉树：所有结点的平衡因子为0,1,-10,1,-1J2.2.2.2.满二叉树满二叉树满二叉树满二叉树C C一个深度为一个深度为一个深度为一个深度为k k的二叉树有的二叉树有的二叉树有的二叉树有2 2k k-1-1个结点个结点个结点个结点JJ3.3.3.3.完全二叉树完全二叉树完全二叉树完全二叉树C Cn n个结点有个结点有个结点有个结点有k+1k+1层，其中层，其中层，其中层，其中2 2k k-1-1个结点在前个结点在前个结点在前个结点在前k k层，剩下的结点从左向右排列在第层，剩下的结点从左向右排列在第层，剩下的结点从左向右排列在第层，剩下的结点从左向右排列在第k+1k+1层层层层第25页，共49页，编辑于2022年，星期一5.3.3 5.3.3 遍历二叉树遍历二叉树J遍历二叉树是按照预定的顺序处理每一个遍历二叉树是按照预定的顺序处理每一个节点且仅处理一次节点且仅处理一次C先根顺序遍历：先根顺序遍历：中左右中左右C中根顺序遍历：中根顺序遍历：左中右左中右C后根顺序遍历：后根顺序遍历：左右中左右中第26页，共49页，编辑于2022年，星期一先根遍历先根遍历(DLR)J首首先先访访问问根根，再再访访问问左左子子树树，最最后后访访问问右右子树。子树。ABCDEF第27页，共49页，编辑于2022年，星期一中序遍历中序遍历(LDR)J首先处理左子树，再访问根，最后访问右子树。首先处理左子树，再访问根，最后访问右子树。CBDAEF第28页，共49页，编辑于2022年，星期一后序遍历后序遍历(LRD)J首先处理左子树，再访问右子树，最后访问根。首先处理左子树，再访问右子树，最后访问根。CDBFEA第29页，共49页，编辑于2022年，星期一练习练习J一棵二叉数共有一棵二叉数共有1010个节点（分别用个节点（分别用A A、B BJ J表示），已知树的中序遍历结果为：表示），已知树的中序遍历结果为：DHBEAFCIGJDHBEAFCIGJ，先序遍历结果为：，先序遍历结果为：ABDHECFGIJABDHECFGIJ。回答下列问题。回答下列问题。C C请画出这棵二叉树。请画出这棵二叉树。请画出这棵二叉树。请画出这棵二叉树。C C写出该树的后序遍历结果。写出该树的后序遍历结果。写出该树的后序遍历结果。写出该树的后序遍历结果。HDEBFIJGCA第30页，共49页，编辑于2022年，星期一*5.4*5.4 图形结构图形结构J5.4.1 5.4.1 图的概念图的概念J5.4.2 5.4.2 图的存储表示法图的存储表示法J5.4.3 5.4.3 图的遍历和生成树图的遍历和生成树第31页，共49页，编辑于2022年，星期一5.4.1 5.4.1 图的概念图的概念JJ图图图图：节点节点节点节点和和和和线段线段线段线段的集合，节点称为的集合，节点称为的集合，节点称为的集合，节点称为顶点顶点顶点顶点，线段称为，线段称为，线段称为，线段称为线线线线，线用于连接一对顶点。线用于连接一对顶点。线用于连接一对顶点。线用于连接一对顶点。JJ有向图有向图有向图有向图：每条线有一个方向：每条线有一个方向：每条线有一个方向：每条线有一个方向(箭头箭头箭头箭头)指向后继节点，有向指向后继节点，有向指向后继节点，有向指向后继节点，有向图中线称为图中线称为图中线称为图中线称为弧弧弧弧，弧的流向只能朝一个指定的方向。，弧的流向只能朝一个指定的方向。，弧的流向只能朝一个指定的方向。，弧的流向只能朝一个指定的方向。JJ无向图无向图无向图无向图：线是没有方向的，线被称为：线是没有方向的，线被称为：线是没有方向的，线被称为：线是没有方向的，线被称为边边边边，顶点间的流向可，顶点间的流向可，顶点间的流向可，顶点间的流向可以是任意方向。以是任意方向。以是任意方向。以是任意方向。第32页，共49页，编辑于2022年，星期一术语术语J结点的结点的结点的结点的度度度度是连接到结点的线的数量。有向图中是连接到结点的线的数量。有向图中出出出出度度度度是离开结点的弧的数量，是离开结点的弧的数量，是离开结点的弧的数量，是离开结点的弧的数量，入度入度是进入结点的弧是进入结点的弧的数量。的数量。J如果两个结点之间有路径相连，则称它们是连通如果两个结点之间有路径相连，则称它们是连通的。如果的。如果所有结点之间都是连通的所有结点之间都是连通的所有结点之间都是连通的所有结点之间都是连通的，不考虑方向，不考虑方向，则该图称为则该图称为连通的连通的连通的连通的。JJ在有向图中，如果每个结点都有通往其它结点的路在有向图中，如果每个结点都有通往其它结点的路在有向图中，如果每个结点都有通往其它结点的路在有向图中，如果每个结点都有通往其它结点的路径，称该图是径，称该图是径，称该图是径，称该图是强连通强连通强连通强连通的。的。的。的。JJ在有向图中，如果至少两个结点是不连通的，则有在有向图中，如果至少两个结点是不连通的，则有在有向图中，如果至少两个结点是不连通的，则有在有向图中，如果至少两个结点是不连通的，则有向图是向图是向图是向图是弱连通弱连通弱连通弱连通的。的。的。的。第33页，共49页，编辑于2022年，星期一5.4.2 5.4.2 图的存储表示法图的存储表示法边上的值表示权，如表示距离、成本等含义第34页，共49页，编辑于2022年，星期一5.4.3 5.4.3 图的遍历和生成树图的遍历和生成树JJ在给定的图中从任一结点出发，系统地访问图中的每一个在给定的图中从任一结点出发，系统地访问图中的每一个在给定的图中从任一结点出发，系统地访问图中的每一个在给定的图中从任一结点出发，系统地访问图中的每一个结点一次，称为结点一次，称为结点一次，称为结点一次，称为图的遍历图的遍历图的遍历图的遍历JJ1 1 1 1、深度优先遍历、深度优先遍历、深度优先遍历、深度优先遍历C C有向图有向图有向图有向图 ，C C无向图无向图无向图无向图 ，JJ2 2 2 2、广度优先遍历、广度优先遍历、广度优先遍历、广度优先遍历C C从结点从结点从结点从结点出度：出度：出度：出度：、C C从结点从结点从结点从结点出度：出度：出度：出度：、第35页，共49页，编辑于2022年，星期一5.5 5.5 内部排序内部排序J5.5.1 5.5.1 简单插入排序简单插入排序J5.5.2 5.5.2 简单选择排序简单选择排序J5.5.3 5.5.3 冒泡排序冒泡排序第36页，共49页，编辑于2022年，星期一5.5.1 5.5.1 简单插入排序简单插入排序J列表被分成两个子列表：列表被分成两个子列表：已排序已排序和和未排序未排序的的J初始时已排序部分为空初始时已排序部分为空J每次扫描过程中：每次扫描过程中：C取出未排序列表中的第一个元素取出未排序列表中的第一个元素C然后转到已排序列表中，将其然后转到已排序列表中，将其插入到合适的插入到合适的位置上位置上C每次扫描后，未排序列表增加每次扫描后，未排序列表增加1个，已排序列个，已排序列表减少表减少1个个J对于对于n n个数据，需要进行个数据，需要进行n-1n-1次扫描次扫描第37页，共49页，编辑于2022年，星期一插入排序示意插入排序示意第38页，共49页，编辑于2022年，星期一5.5.2 5.5.2 简单选择排序简单选择排序JJ列表被分成两个子列表：列表被分成两个子列表：列表被分成两个子列表：列表被分成两个子列表：已排序已排序已排序已排序和和和和未排序未排序未排序未排序的；初始时的；初始时的；初始时的；初始时已排序部分为空。已排序部分为空。已排序部分为空。已排序部分为空。J排序时，排序时，从未排序列表中找到最小元素，与第一个从未排序列表中找到最小元素，与第一个从未排序列表中找到最小元素，与第一个从未排序列表中找到最小元素，与第一个元素交换元素交换元素交换元素交换。C C经过选择和交换后，将未排序列表中的第一个元素划入排经过选择和交换后，将未排序列表中的第一个元素划入排经过选择和交换后，将未排序列表中的第一个元素划入排经过选择和交换后，将未排序列表中的第一个元素划入排序列表中，这一过程称为一次序列表中，这一过程称为一次序列表中，这一过程称为一次序列表中，这一过程称为一次扫描扫描扫描扫描。C C每次扫描后，未排序列表减少一个元素，已排序列表增每次扫描后，未排序列表减少一个元素，已排序列表增每次扫描后，未排序列表减少一个元素，已排序列表增每次扫描后，未排序列表减少一个元素，已排序列表增加一个元素。加一个元素。加一个元素。加一个元素。J对于对于对于对于n n n n个数据，需要进行个数据，需要进行n-1n-1n-1n-1次扫描次扫描次扫描次扫描。第39页，共49页，编辑于2022年，星期一选择排序示意选择排序示意第40页，共49页，编辑于2022年，星期一5.5.3 5.5.3 冒泡排序冒泡排序J列表被分成两个子列表：列表被分成两个子列表：列表被分成两个子列表：列表被分成两个子列表：已排序已排序已排序已排序和和和和未排序未排序未排序未排序的；初始的；初始的；初始的；初始时已排序部分为空。时已排序部分为空。时已排序部分为空。时已排序部分为空。JJ在未排序的子列表中，最小的元素通过在未排序的子列表中，最小的元素通过在未排序的子列表中，最小的元素通过在未排序的子列表中，最小的元素通过冒泡的方法冒泡的方法选选选选出来并移动到已排序子列表中，这一过程称为一次扫出来并移动到已排序子列表中，这一过程称为一次扫出来并移动到已排序子列表中，这一过程称为一次扫出来并移动到已排序子列表中，这一过程称为一次扫描。每次扫描，未排序元素增加描。每次扫描，未排序元素增加描。每次扫描，未排序元素增加描。每次扫描，未排序元素增加1 1 1 1个，已排序元素减少个，已排序元素减少个，已排序元素减少个，已排序元素减少1 1 1 1个。个。JJ冒泡时，进行冒泡时，进行冒泡时，进行冒泡时，进行两两比较两两比较，如果前者较大，则交换数，如果前者较大，则交换数，如果前者较大，则交换数，如果前者较大，则交换数据。据。据。据。J对于对于对于对于n n n n个数据，需要进行个数据，需要进行个数据，需要进行个数据，需要进行n-1n-1n-1n-1次扫描次扫描次扫描次扫描。第41页，共49页，编辑于2022年，星期一冒泡排序示意冒泡排序示意第42页，共49页，编辑于2022年，星期一5.6 5.6 检索（查找）检索（查找）J查找实现在列表中确定目标所在位置。查查找实现在列表中确定目标所在位置。查找通常返回具有要查找目标值的找通常返回具有要查找目标值的第一个元第一个元素素的的位置位置(索引索引)J5.6.1 5.6.1 顺序检索顺序检索J5.6.2 5.6.2 二分法检索二分法检索J5.6.3 5.6.3 分块检索分块检索*J5.6.4 5.6.4 散列表检索散列表检索*第43页，共49页，编辑于2022年，星期一5.6.1 5.6.1 顺序检索（查找）顺序检索（查找）J用于查找无序列表用于查找无序列表，一般用这种方法查找，一般用这种方法查找规模较小的列表。规模较小的列表。J顺序查找顺序查找从表头开始逐个元素查找从表头开始逐个元素查找，当找，当找到目标元素或查找完整个列表时，查找过到目标元素或查找完整个列表时，查找过程结束。程结束。第44页，共49页，编辑于2022年，星期一顺序查找示意顺序查找示意第45页，共49页，编辑于2022年，星期一顺序查找示意顺序查找示意第46页，共49页，编辑于2022年，星期一5.6.2 5.6.2 二分法检索（折半查找）二分法检索（折半查找）J顺序查找很慢顺序查找很慢，尤其当列表中数据非常多时，逐个元，尤其当列表中数据非常多时，逐个元，尤其当列表中数据非常多时，逐个元，尤其当列表中数据非常多时，逐个元素比较非常费时。当素比较非常费时。当素比较非常费时。当素比较非常费时。当列表有序列表有序列表有序列表有序时，可采用效率非常高时，可采用效率非常高时，可采用效率非常高时，可采用效率非常高的的的的折半查找算法折半查找算法折半查找算法折半查找算法。JJ折半查找时，折半查找时，折半查找时，折半查找时，先测试中间元素先测试中间元素先测试中间元素先测试中间元素，可以判断出目标在，可以判断出目标在，可以判断出目标在，可以判断出目标在列表的前半部分还是后半部分。如果在前半部分，列表的前半部分还是后半部分。如果在前半部分，列表的前半部分还是后半部分。如果在前半部分，列表的前半部分还是后半部分。如果在前半部分，则不用比较后半部分数据，排除掉一半数据。则不用比较后半部分数据，排除掉一半数据。则不用比较后半部分数据，排除掉一半数据。则不用比较后半部分数据，排除掉一半数据。JJ重复折半过程，直到找到目标或确定目标不在列表重复折半过程，直到找到目标或确定目标不在列表重复折半过程，直到找到目标或确定目标不在列表重复折半过程，直到找到目标或确定目标不在列表中。中。中。中。第47页，共49页，编辑于2022年，星期一示意示意第48页，共49页，编辑于2022年，星期一小结小结JJ数据结构：数据的逻辑结构、数据的存储结构和数据的运算数据结构：数据的逻辑结构、数据的存储结构和数据的运算数据结构：数据的逻辑结构、数据的存储结构和数据的运算数据结构：数据的逻辑结构、数据的存储结构和数据的运算JJ数据结构通常分为四种基本结构数据结构通常分为四种基本结构数据结构通常分为四种基本结构数据结构通常分为四种基本结构JJ数据的四种基本的存储映射方式数据的四种基本的存储映射方式数据的四种基本的存储映射方式数据的四种基本的存储映射方式JJ线性结构中有关线性表、栈、队列和链表的概念。线性结构中有关线性表、栈、队列和链表的概念。线性结构中有关线性表、栈、队列和链表的概念。线性结构中有关线性表、栈、队列和链表的概念。JJ树型结构中介绍了树、二叉树概念，以及线索化和遍历操作。树型结构中介绍了树、二叉树概念，以及线索化和遍历操作。树型结构中介绍了树、二叉树概念，以及线索化和遍历操作。树型结构中介绍了树、二叉树概念，以及线索化和遍历操作。JJ图型结构中掌握图的基本概念，存储和遍历的方法图型结构中掌握图的基本概念，存储和遍历的方法图型结构中掌握图的基本概念，存储和遍历的方法图型结构中掌握图的基本概念，存储和遍历的方法JJ选择排序、插入排序、冒泡排序选择排序、插入排序、冒泡排序选择排序、插入排序、冒泡排序选择排序、插入排序、冒泡排序JJ顺序查找、折半查找顺序查找、折半查找顺序查找、折半查找顺序查找、折半查找第49页，共49页，编辑于2022年，星期一