自考数据结构02142第六章ppt课件.ppt

《自考数据结构02142第六章ppt课件.ppt》由会员分享，可在线阅读，更多相关《自考数据结构02142第六章ppt课件.ppt（29页珍藏版）》请在三一办公上搜索。

1、第六章 查找,6.1 基本概念6.2 静态查找表6.3 二叉排序树6.4 散列表,6.1 基本概念,查找表由同一类型的数据元素（或记录） 构成的集合。,关键字（键）用来标识数据元素的数据项称 为关键字，简称键；其值称为键值。,主关键字可以惟一标识各个数据元素的关键字,查找根据给定的某个k值，在查找表寻找一个 其键值等于k的数据元素。,静态查找表进行的是引用型运算,动态查找表进行的是加工型运算,6.2 静态查找表的实现,查找表用顺序表表示：（见P163） #define maxsize 20 /静态查找表的表长 typedef struct TableElem etemmaxsize+1 ;/*

2、一维数组，0号单元留空*/ int n ; /*最后一个元素的下标，也即表长*/ SqTable ;,typedef struct keytype key ; /*关键字域 */ /*其它域*/ TableElem ;,6.2.1 顺序表上的查找顺序查找,一、过程 从表中最后一个记录开始顺序进行查找，若当前记录的关键字=给定值，则查找成功；否则，继续查上一记录；若直至第一个记录尚未找到需要的记录，则查找失败。,二、算法,方法一：使用一种设计技巧：设立岗哨 int search_sqtable(sqtable T, keytype K） /*在顺序表R中顺序查找其关键字等于key的元素。 若找到

3、，则函数值为该元素在表中的位置，否则为0*/ T.item0.key=key; i=T.n; while ( T.itemi.key!=key ) i- - ; return i ; ,三、算法分析,成功查找：ASL=ni=1CiPi （设每个记录的查找概率相等） =1/n ni=1（n-i+1） =（n+1)/2不成功查找：ASL=n+1顺序查找优点：简单，对表无要求；顺序查找缺点：比较次数多。,6.2.2 有序表上的查找二分查找,1、二分查找思想：,每次找中项,.中项是，则找到；,.否则，根据此中项的关键字与给 定关键字的关系，决定在表的前 或后半部继续找。,关键点。可使下次查找范围缩小一

4、半。,二分查找基本思想：每次将处于查找区间中间位置上的数据元素与给定值K比较，若不等则缩小查找区间并在新的区间内重复上述过程，直到查找成功或查找区间长度为0（查找不成功）为止。,(2)给定关键字k与中项记录关键字比较 Kitem mid.key，则所查记录落在表的前半部； 继续在前半部找，此时low不变，high=mid-1 Kitem mid.key，则查找成功，中项即是，结束； Kitem mid.key，则所查记录落在表的后半部； 继续在后半部找，此时low=mid+1，high不变,(3)若lowhigh，则转(1)，否则查找不成功。, item1, , itemmid-1, item

5、mid, itemmid+1, , itemn ,3、二分查找算法：,2、二分查找过程：表头指针low=1 表尾指针high=n,因为1835，所以：,15，17，18，22，35，51，60，88，93 low mid high,4、例：（在下列有序顺序表中查找K=18）,1 2 3 4 5 6 7 8 9,因为1817，所以：,因为18=18，所以：查找成功，回送结果为mid=3,5、算法分析：,成功查找时平均查找长度： ASL=ni=1CiPi （设每个记录的查找概率相等） =1/n hj=1（j*2j-1） =（n+1)/n * log2(n+1)-1 log2(n+1)log2n(n

6、+1)/2,注意：对线性表进行二分查找时，要求线性表必： 以顺序方式存储，且结点按关键字有序排序,6.2.3 索引顺序表的查找分块查找,一、查找过程：1.先建立最大（或小）关键字表索引表（有序） 即将每块中最大（或最小）关键字及指示块首记录在表中位置的指针依次存入一张表中，此表称为索引表；2.查找索引表，以确定所查元素所在块号； 将查找关键字k与索引表中每一元素（即各块中最大关键字）进行比较，以确定所查元素所在块号；3.在相应块中按顺序查找关键字为k的记录。,二、例：记录表 22,12,13,9,8,33,42,44,38,24,48,60, 58,74,47 ，查关键字38的元素,表可分三块

7、，块间有序，块中无序,1、先在索引表中（按顺序或折半） 查找：3822而3844 38在第二块中2、在第2块中顺序查找得第9号元素 其关键字为38。,三、算法分析：,分块查找的时间性能高于顺序查找而低于二分查找；分块查找不要求存储结构中数据元素按键值有序。,6.3 动态查找表树表,表结构是在查找过程中动态生成的；对于给定值k，若表中存在其关键字等于k的记录，则查找成功返回，否则在表中插入关键字等于k的记录。,一、二叉排序树什么是二叉排序树？二叉排序树是一种特殊的、增加了限制条件的二叉树，它的存储结构及其类型定义与二叉树相同，它的特殊性表现在结点键值之间的大小关系上，任一结点的键值大于其左孩子(

8、及其子孙)的键值且小于其右孩子(及其子孙)的键值。性质：,中序遍历一棵二叉排序树所得的结点访问序列是键值的递增序列。,2、二叉排序树查找算法见P169,二、二叉排序树上的查找： 1、过程： 当二叉排序树不空时，首先将给定值和根结点的关键字比较,若相等,则查找成功；否则根据给定值与根结点关键字间的大小关系，分别在左子树或右子树上继续进行查找。,注：(1)二叉排序树，对每个结点，均有： 左子树上的所有结点键值都比根的小； 右子树上的所有结点键值都比根的大。(2)构造二叉排序树的同时也对序列排序了；,三、二叉排序树的插入和生成 对序列R=k1，k2，kn， k1 kn均为关键字值，则按下列原则可构造

9、二叉排序树： (1)令k1为根； (2)若k1k2 ，则令k2为k1的右孩，否则为左孩； (3) k3，k4，kn递归重复(2),散列函数（哈希函数）设记录表A，长为n，ai（1in）为表中某一元素，ki为其关键字，则关键字ki和元素ai在表中的地址之间有一函数关系，即： Addr（ai） = H（ki）,ai在表中地址,散列函数：关键字与元素地址的函数,6.4 散列表（哈希表）,散列地址由散列函数决定数据元素的存储 位置，该位置称为散列地址。,散列查找：,给定关键字,在表中的地址,散列函数转换,查看此位置上有无欲查元素,有,无,输出信息,将它填到此位置上,散列表通过散列法建立的表称为散列表。

10、,散列法主要工作,.选择一个好的散列函数.解决冲突,.函数计算简便，运算速度快.随机性好，地址尽可能均匀分布.冲突小,冲突：,k1 k2 但 H（k1）=H（k2）的现象称为冲突。即：不同的关键字映射到同一存储单元。并称k1和 k2是同义词。,2、除留余数法,散列函数：取关键字被某个不大于散列表长n的数p除 后所得余数作为散列地址。 即： H(key)= key mod p ， （pn ）,例： 一组关键字从000,001 859,999 散列地址为：0 5999 即 n=6000 取 p=5999 余数r在05999范围内 H=k mod 5999 设：k=172,148 则：H=k mod

11、 p = 172148 mod 5999 = 4176,6.4.1 散列函数的构造,1、数字分析法（见P173）,3、平方取中法（见P174）,4、基数转换法（见P174）,即用“链地址法”处理冲突,思想：将散列地址相同记录存储在同一单 链表中（称同义词表），同时按散列 地址设立一个表头指针向量。,例：已知一组关键字为（13，41，15，44，06， 68，25，12，38，64，19，49），按散列 函数H(key)=key mod 13 和链地址法处理冲 突构造散列表。,6.4.2 散列表的实现,Key:（13,41,15,44,06,68,25,12,38, 64, 19,49）,0,

12、2, 2, 5, 6, 3, 12,12,12, 12, 6, 10,散列 地址：,过程：设有散列表HT（向量），对给定记录R， 其关键字k，对应哈希地址H(k)=j,HT表,思想：计算出的散列地址已被占用，则按顺序找 “下一个”空位。,用“线性探测法”处理冲突构造散列表,散列表：,0 1 2 3 4 5 6 7 8 9 10 11 12,例：已知一组关键字为（13，41，15，44，06， 68，25，12，38，64，19，49），按散列 函数H(key)=key mod 13 和线性探测法处 理冲突构造散列表。,Key:（13,41,15,44,06,68,25,12,38, 64, 1

13、9,49）,0, 2, 2, 5, 6, 3, 12,12,12, 12, 6, 10,散列 地址：,散列法的优缺点： 优点：直接由关键字通过哈希函数计算出哈 希地址，查找效率高； 缺点：常发生冲突，影响查找效率。,第六章 查找小结,熟练掌握顺序表和有序表的查找方法和算法；掌握二叉排序树的定义、构建方法和查找方法； 知道二叉排序树的定义及维护平衡四个旋转规则； 掌握B_树的定义和建树过程，查找方法；什么是散列方法、什么是冲突？熟练掌握散列表的构造和查找及冲突的处理；按定义计算各种查找方法在等概率情况下查找成功的平均查找长度。,1二分查找算法要求被查找的表是（ ） A. 键值有序的链表 B. 键

14、值不一定有序的链表 C. 键值有序的顺序表 D. 键值不一定有序的顺序表2静态查找表与动态查找表的根本差别在于（ ） A. 逻辑结构不同 B.存储实现不同 C. 施加的操作不同 D. 数据元素的类型不同3在二叉排序树中，对于任意结点a，其左子树中所有结点 的键值均（ ） A. 小于结点a的键值 B. 小于等于结点a的键值 C. 大于结点a的键值 D. 大于等于结点a的键值4. 在二叉排序树中，对于任意结点a，其右子树中所有结点 的键值均（ ） A. 小于结点a的键值 B. 小于等于结点a的键值 C. 大于结点a的键值 D. 大于等于结点a的键值,练 习,5二分查找法适用于这样的线性表，即按关键字排好 序且存储结构为（ ） A. 顺序存储 B. 链式存储 C. 散列存储 D. 顺序存储或链式存储6在散列函数H(k)=k MOD m中，一般来讲，m应取 （ ） A奇数 B.偶数 C. 质数 D.充分大的数7二分查找法要求查找表中各元素的键值必须是（ ） A递增排列 B递减排列 C无序排列 D递增或递减排列,