数据结构查找.ppt
第八章 查找2023年年3月月2日日1 8.1 基本概念与术语基本概念与术语 8.2 静态查找表静态查找表 8.3 动态查找表动态查找表 8.4 哈希表查找哈希表查找 8.5 小结与习题小结与习题第八章 查找本章主要内容本章主要内容 本章主要学习本章主要学习静态查找静态查找和和动态查找动态查找方法。静态查方法。静态查找包括顺序查找、二分查找和分块索引查找等，找包括顺序查找、二分查找和分块索引查找等，动态查找包括二叉排序树、动态查找包括二叉排序树、B树等。作为重点内树等。作为重点内容本章还介绍了哈希查找及相关知识。容本章还介绍了哈希查找及相关知识。 查找是数据结构中的重要操作，好的查找方法会查找是数据结构中的重要操作，好的查找方法会大大提高执行效率。通过本章学习，应掌握以下大大提高执行效率。通过本章学习，应掌握以下内容：内容： 查找的有关概念查找的有关概念； 静态查找；静态查找； 动态查找动态查找； 哈希查找。哈希查找。 2023年年3月月2日日2第八章 查找2023年年3月月2日日38.1 8.1 基本概念与术语基本概念与术语查找查找就是指在给定的一组数据中对某个数值进行就是指在给定的一组数据中对某个数值进行查询的过程。查询的过程。关键字关键字是数据元素（或记录）中某个项或组合项是数据元素（或记录）中某个项或组合项的数值，它可以标识一个数据元素或记录。的数值，它可以标识一个数据元素或记录。主关键字主关键字将能唯一确定一个数据元素（或记录）将能唯一确定一个数据元素（或记录）的的关键字关键字。查找表查找表是由具有相同类型的数据元素（或记录）是由具有相同类型的数据元素（或记录）组成的集合。分为静态查找表和动态查找表两大类。组成的集合。分为静态查找表和动态查找表两大类。如果查找表中能够找到满足条件的记录，称为如果查找表中能够找到满足条件的记录，称为查查找成功找成功，否则称为，否则称为查找不成功查找不成功。第八章 查找2023年年3月月2日日4 静态查找表静态查找表：在对查找表进行操作时，不改变：在对查找表进行操作时，不改变表的结构，只进行查找操作；表的结构，只进行查找操作； 动态查找表动态查找表：在对查找表进行操作时，可以改：在对查找表进行操作时，可以改变该查找表的结构，既可以进行查找操作，又可以变该查找表的结构，既可以进行查找操作，又可以进行插入、删除等操作。进行插入、删除等操作。8.2 8.2 静态查找表静态查找表8.2.1 8.2.1 静态查找表结构静态查找表结构 静态查找表是由数据元素组成的线性表。其存静态查找表是由数据元素组成的线性表。其存储结构分为顺序存储和链式存储两种。可以用储结构分为顺序存储和链式存储两种。可以用顺序顺序表表或或线性链表线性链表来表示静态查找表。来表示静态查找表。第八章 查找2023年年3月月2日日58.2.1 静态查找表结构typedefintKeyType;typedefstructKeyTypekey;ElemType;typedefstructElemTypeelemMAXSIZE+1；intlength；SST； typedefstructNODEElemTypedata；/*结点的数据域结点的数据域*/structNODE*next；/*指针域指针域*/NodeType；静态查找表静态查找表的顺序存储的顺序存储结构定义结构定义静态查找表静态查找表的链式存储的链式存储结构定义结构定义第八章 查找2023年年3月月2日日68.2.2 顺序查找顺序查找顺序查找又称线性查找，它思路简单、容易实又称线性查找，它思路简单、容易实现，是一种最基本的查找方法。现，是一种最基本的查找方法。其查找过程为：从查找表的一端开始，逐个进行关其查找过程为：从查找表的一端开始，逐个进行关键字与查找值的比较，若某个记录的关键字值与给键字与查找值的比较，若某个记录的关键字值与给定值相等，则查找成功，给出数据元素在查找表中定值相等，则查找成功，给出数据元素在查找表中的位置；若将整个表查找完，仍未找到与给定值相的位置；若将整个表查找完，仍未找到与给定值相同的关键字，则查找失败，给出提示信息。同的关键字，则查找失败，给出提示信息。第八章 查找2023年年3月月2日日7【算法算法8.1】顺序查找顺序查找intSearch_Seq(SSTST，KeyTypex)ST.elem0.key=x;/*设置监护哨设置监护哨*/i=ST.length;while(ST.elemi.key!=x)i-;/*返回找到记录的下标或者返回找到记录的下标或者0(查找不成功查找不成功)*/returni;/*Search_Seq*/将查找过程中给定值和关键字将查找过程中给定值和关键字比较的次数称为比较的次数称为查找长度查找长度。通常用。通常用平均查找长度平均查找长度ASL来衡量查找算法来衡量查找算法的优劣。的优劣。算法分析：算法分析：第八章 查找2023年年3月月2日日8 平均查找长度：平均查找长度：在查找成功时，平均查找长度在查找成功时，平均查找长度ASLASL是指为确定数据元素在表中位置所进行关键字比是指为确定数据元素在表中位置所进行关键字比较次数的期望值。对一个含较次数的期望值。对一个含n n个数据元素的表，查找个数据元素的表，查找成功时成功时 ASL=Pi*Ci ni=1Pi为表中第为表中第i个数据元素的查找概率，个数据元素的查找概率，Ci为表中为表中第第i个数据元素的关键字与给定值个数据元素的关键字与给定值x相等时，需要比较相等时，需要比较的次数。的次数。设查找表长度为设查找表长度为n，查找元素，查找元素x和表中第和表中第i个元素个元素关键字相等时，需要比较的次数为关键字相等时，需要比较的次数为n-i+1，则平均查，则平均查找长度为：找长度为：ASL=Pi*（n-i+1）ni=1第八章 查找2023年年3月月2日日9 设查找表中各元素的查找概率相等，即设查找表中各元素的查找概率相等，即Pi=1/n，则上面的式子表示为：则上面的式子表示为： ni =1ASL=（n-i+1）=当查找成功时，顺序查找的时间复杂度就是当查找成功时，顺序查找的时间复杂度就是O(n)。当查找失败时，关键字与给定值的比较次数总是当查找失败时，关键字与给定值的比较次数总是n+1次。次。8.2.3二分查找二分查找 二分查找，也称为二分查找，也称为折半折半查找，是对查找，是对有序表有序表进行的进行的一种高效率的线性查找。有序表是指数据元素按给一种高效率的线性查找。有序表是指数据元素按给定的关键字已经是升序（或者是降序）的查找表。定的关键字已经是升序（或者是降序）的查找表。第八章 查找2023年年3月月2日日10 假设各记录的关键字是由小到大排序的，算法假设各记录的关键字是由小到大排序的，算法的实现过程为：在待查找的有序表中，将的实现过程为：在待查找的有序表中，将中间中间元素元素首先与给定值进行比较，若相等，则表示查找成功；首先与给定值进行比较，若相等，则表示查找成功；若给定值若给定值小于小于中间元素的关键字，则在中间元素的关键字，则在左边左边的区域的区域中继续查找；若给定值中继续查找；若给定值大于大于中间元素的关键字，则中间元素的关键字，则在在右边右边的区域中继续查找。重复上述过程，直到查的区域中继续查找。重复上述过程，直到查找成功或者查找失败，查找的过程随之结束找成功或者查找失败，查找的过程随之结束。例在给定的序列例在给定的序列A=6，13，17，20，24，28，30，36，39，44，48，51，55中查找给定值中查找给定值13和和52这两个数据。这两个数据。查找关键字为查找关键字为13的过程的过程第八章 查找2023年年3月月2日日11 6131720242830363944485155第一次第一次 low=1 mid=7 high=13因因x30 x30，下一步继续在左半区查找，即：，下一步继续在左半区查找，即： 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 7 8 9 10 11 12 13 8 9 10 11 12 13第二次第二次 low=1 mid=3 high=6因因x17x 6x 6 ， 下 一 步 继 续 在 右 半 区 查 找 。 此 时 ， 下 一 步 继 续 在 右 半 区 查 找 。 此 时 ，low=2,high=2low=2,high=2 ,mid=(2+2)/2=2。由于。由于x=13,查找成功，所查找成功，所找到的记录序号为找到的记录序号为2。 查找关键字为查找关键字为5252的过程的过程第一次第一次 low=1 mid=7 high=13因因x30 x30，下一步继续在右半区查找，即：，下一步继续在右半区查找，即： 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 7 8 9 10 11 12 13 8 9 10 11 12 13第二次第二次 low=8 mid=10 high=13 因因x44x44，下一步继续在右半区查找，即：，下一步继续在右半区查找，即： 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 1010 11 12 13 11 12 13 6131720242830363944485155 6131720242830363944485155第八章 查找2023年年3月月2日日13第三次第三次low=11 high=13 mid=12因因x51x51，下一步继续在右半区查找，即：，下一步继续在右半区查找，即： 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 1212 13 13 第四次第四次 low=mid=high=13因因x55xhigh，所以查找失败。，所以查找失败。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 6131720242830363944485155 6131720242830363944485155第八章 查找2023年年3月月2日日14【算法算法8.2】二分查找二分查找intSearch_Bin(SSTST，KeyTypex)low=1；high=ST.length；while(low=high)/*区间条件判断区间条件判断*/*当区间下限不高于上限时，进行比较测试当区间下限不高于上限时，进行比较测试*/mid=(low+high)/2；/*取中点取中点*/if(xST.elemmid.key)low=mid+1；/*查找区间缩小到右边区域查找区间缩小到右边区域*/elsereturnmid;returnERROR;第八章 查找2023年年3月月2日日15算法分析：算法分析：对于有序查找表，可采用建立二叉树的方法：将表对于有序查找表，可采用建立二叉树的方法：将表的的中间元素中间元素作为二叉树的作为二叉树的根结点根结点，比中间值，比中间值小小的所的所有结点全部在二叉树的有结点全部在二叉树的左子树左子树中，比中间值中，比中间值大大的所的所有结点全部在二叉树的有结点全部在二叉树的右子树右子树中。按照这种思路建中。按照这种思路建立的二叉树称为立的二叉树称为判定二叉树判定二叉树。如图所示。如图所示。5139281764455302448361320第八章 查找2023年年3月月2日日16时间复杂度：该算法的时间复杂度取决于该二叉树时间复杂度：该算法的时间复杂度取决于该二叉树中从根结点到该查找元素所在的结点的路径上与中中从根结点到该查找元素所在的结点的路径上与中间结点的比较次数，即该元素结点在树中的所在的间结点的比较次数，即该元素结点在树中的所在的层数。对于层数。对于n n个结点的判定树，树高为个结点的判定树，树高为h h，则有，则有2 2h-1h-1- -1 n 21 n 2h h- 1- 1 ， 即， 即 h - 1 l o gh - 1 key)returnp;/*查找结束查找结束*/elseif(xk
