数据结构与算法教程 朱明方 吴及 第6章 查找

《数据结构与算法教程 朱明方 吴及 第6章 查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章查找6.1顺序表查找一、顺序查找二、对分查找6.2索引查找一、索引存储结构二、分块查找三、索引文件6.3散列查找一、散列的概念二、Hash函数的构造三、冲突处理方法第六章查找6.4树表查找一.二叉搜索树查找二.B‾树6.5字符串匹配一.字符串匹配的简单算法二.字符串匹配的KMP算法6.1顺序表查找查找———在不同的表结构中查找指定元素;查找到指定元素———返回该元素在表中的位置;若找不到满足条件的元素———查找失败，返回特定值;不同的表结构采用不同的查找方法;元素(记录)的关键字———可以标识一个元素(记录)的数据项；一.

2、顺序查找(SequentailSearch)适用情况：对无序表查找。查找方法：——蛮力法从表首开始，把表中元素的关键字逐个与给定值k比较,若某个元素的关键字值与k相等则查找成功；否则，查找失败。6.1顺序表查找若表的数据元素结构定义为:typedefstruct{KeyTypekey;//元素关键字项…//元素其他项}ElemType;顺序表类型定义为:typedefstruct{ElemTypeelem;//存放数据元素的数组intlen;//顺序表长度}SeqTable;6.1顺序表查找顺序表查找算法描述：intSeqSea

3、rch(SeqTableST,KeyTypex){inti;for(i=0;i

4、据比较结果确定下一步的比较项；算法描述：可用递归和非递归描述.参考教材空间复杂度：inplace时间复杂度：查找一个元素最多比较次数为：⌊log2n⌋+1其复杂度为O(log2n)优点：查找速度快于顺序查找；适用：表中元素相对稳定的有序顺序表；6.1顺序表查找分析查找过程知：对分查找→判定过程→判定树(平衡二叉树)假设对分查找的有序表为：序号i：0123456789关键字k：12182235506072809298对分查找树：50221880126092729835由对分查找树可直观地看出其最坏情况时间复杂度：O(log2n)6

5、.2索引查找一.索引存储结构1.索引存储的概念基本思想：•将有n个结点的线性表划分为m个子表，分别存储各子表；•另设一个有m个结点(索引项)的索引表，每个结点存子表第一个结点的地址及相关信息；线性表划分原则：①具有某种性质Pi的结点归并到子表li中；②m个子表的结点结合在一起，正好构成原线性表L的全部结点；关键：找出满足上述原则的划分条件(函数关系)——索引函数；设元素的关键字为k，若根据Pi有：i=g(k)g—索引函数(i—子表序号，Pi—子表i的性质)；6.2索引查找例1，为了节省存储空间，要将二级字库的汉字(大表)按笔划多

6、少分组(子表)，以便分组存放。分组(子表)原则：以笔划差在两划以内的汉字作为一组，并以笔划从少到多，顺序编号。根据子表划分原则，可以确定划分函数(索引函数)g，并由g计算出某个汉字所在的子表序号i：i=汉字笔划数/3=k/3由此可知：子表序号i：1234…汉字笔划数k：1—34—67—910—12…6.2索引查找例2，要将标称值为200Ω，实际值为190~210Ω的电阻按实际测量值分为以下7组：l1——190~192Ω根据要求取索引函数：l2——193~195Ωl3——196~198Ω假设测得10个电阻值为：l4——19

7、9~201ΩR1:193ΩR2:197ΩR3:191ΩR4:201Ωl5——202~204ΩR5:207ΩR6:199ΩR7:204ΩR8:194Ωl6——205~207ΩR9:208ΩR10:202Ωl7——208~210Ω划分结果：l1l2l3l4l5l6l7R3R1,R8R2R4,R6R7,R10R5R96.2索引查找2.索引存储方式索引表——顺序表或链表子表——顺序表或链表可以有四种不同的索引存储方式：①“顺序索引—顺序存储”——索引表顺序表，子表顺序表；②“顺序索引—链接存储”——索引表顺序表，子表链表；③“链接索引—

8、顺序存储”——索引表链表，子表顺序表；④“链接索引—链接存储”——索引表链表，子表链表；索引表特点：表不大，表中元素不常变动；适合用顺序表来表示索引表；6.2索引查找(1)顺序索引——顺序存储方式索引表——顺序表结点结构：子表——顺序表，独立存放，子表之间无存储