数据结构-查找DS-chap.ppt

《数据结构-查找DS-chap.ppt》由会员分享，可在线阅读，更多相关《数据结构-查找DS-chap.ppt（53页珍藏版）》请在三一办公上搜索。

1、第8章 查找,主要内容,第2章至第7章线性或非线性的数据结构本章查找表（实际应用中大量使用）静态查找表及查找算法顺序表有序表静态树表索引顺序表动态查找表及查找算法二叉排序树平衡的二叉排序树B树哈希表及查找算法哈希表,重点与难点,本章的重点静态查找表及查找算法顺序表顺序查找有序表折半查找动态查找表及查找算法二叉排序树查找、建立与删除哈希表及查找算法哈希表建立、查找,重点与难点,本章的难点静态查找表及查找算法静态树表动态查找表及查找算法二叉排序树查找、建立与删除平衡的二叉排序树B树哈希表及查找算法哈希表建立、查找,基本概念,关键字(Key)是数据元素(或记录)中某个数据项的值，用它可以标识(识别)

2、一个数据元素(或记录)。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字(Primary Key)(对不同的记录，其主关键字均不同)。反之，称用以识别若干记录的关键字为次关键字(Secondary Key)。当数据元素只有一个数据项时，其关键字即为该数据元素的值。查找(Searching)根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。,基本概念,查找表(Se

3、arch Table)：由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。对查找表经常进行的操作：查询某个“特定的”数据元素是否在查找表中；检索某个“特定的”数据元素的各种属性；在查找表中插入一个数据元素；从查找表中删去某个数据元素。查找表的分类：静态查找表(Static Search Table)：对查找表只作前两种统称为“查找”的操作。动态查找表(Dynamic Search Table)：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。,8.1 静态查找表,抽象数据类型静态

4、查找表的定义ADT StaticSearchTable数据对象D：具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：Create(&ST，n)；操作结果：构造一个含n个数据元素的静态查找表ST。Destroy(&ST)；初始条件：静态查找表ST存在。操作结果：销毁表ST。,8.1 静态查找表,抽象数据类型静态查找表的定义Search(ST，key)；初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中位置，否则为“空”。T

5、raverse(ST，visit()；初始条件：静态查找表ST存在，visit是对元素操作的应用函数。操作结果：按某种次序对ST的每个元素调用函数visit()一次且仅一次，一旦visit()失败，则操作失败。ADT StaticSearchTable,8.1 静态查找表,小结顺序表的（简单）查找设置监视哨适用的存储结构：顺序、链式有序表的折半查找有序表的等概率查找适用的存储结构：顺序、链式其他有序表查找方法：斐波那契查找、插值查找静态树表的查找有序表的不等概率查找适用的存储结构：二叉链表索引顺序表的查找顺序表的查找的改进适用的存储结构：顺序、顺序与链式结合,8.2 动态查找表,动态查找表的特

6、点表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于 key的记录，则查找成功并返回位置信息；否则，插入关键字等于key的记录。一种基于树的查找法（树表查找法）将待查表组织成特定树的形式并在树结构上实现查找的方法。,8.2 动态查找表,抽象数据类型动态查找表的定义ADT DynamicSearchTable数据对象D：具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：InitDSTable(&DT)；操作结果：构造个空的动态查找表DT。DestroyDSTable(&DT)；初始条件：

7、动态查找表DT 存在。操作结果：销毁动态查找表DT。SearchDSTable(DT，key)；初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。操作结果：若DT中存在关键字等于key的数据元素，则函数值为该元素值或在表中位置，否则为“空”。,8.2 动态查找表,抽象数据类型动态查找表的定义InsertDSTable(&DT，e)；初始条件：动态查找表DT存在，e为待插入数据元素。操作结果：若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。DeleteDSTable(&DT，key)；初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。操作结果：若DT中

8、存在其关键字等于key的数据元素，则删除。TraverseDSTable(DT，Visit()；初始条件：动态查找表DT存在，Visit是对结点操作的应用函数。操作结果：按某种次序对DT的每个结点调用函数Visit()一次且至多一次。一旦visit()败，则操作失败。ADT DynamicSearchTable,8.2 动态查找表,存储结构二叉链表主要内容二叉排序树二叉排序树的定义二叉排序树的查找过程二叉排序树的插入二叉排序树的建立二叉排序树的删除二叉排序树的查找分析平衡的二叉排序树的定义,8.2 动态查找表二叉排序树,二叉排序树的定义：一种特殊结构的二叉树，或者是一棵空树，或者是具有如下性质

9、的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；它的左右子树也分别为二叉排序树。中序遍历二叉排序树递增有序序列,8.2 动态查找表二叉排序树,二叉排序树的查找与次优二叉树类似当二叉排序树不空时，首先将给定值和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。,35,15,45,50,40,25,10,20,30,搜索45 搜索成功,搜索28搜索失败,8.2 动态查找表二叉排序树,二叉排序树查找的递归算法BiTree SearchBST(BiTr

10、ee T，KeyType key)/在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素/若查找成功，则返回指向该数据元素结点的指针，否则返回空指针 if(!T)|EQ(key，T-data.key)return(T)；/查找结束else if LT(key，T-data.key)return(SearchBST(T-lchild，key)；/在左子树中继续查找 else return(SearchBST(T-rchild，key)；/在右子树中继续查找/SearchBST,8.2 动态查找表二叉排序树,二叉排序树查找的非递归算法BiTree NSearchBST(BiTree T

11、，KeyType key)/在根指针T所指二叉排序树中非递归地查找某关键字等于key的数据元素/若查找成功，则返回指向该数据元素结点的指针，否则返回空指针 p=T;/指针p指向根结点，搜索从根结点开始 while(p!=NULL/NSearchBST,8.2 动态查找表二叉排序树,二叉排序树的插入二叉排序树的查找的特点动态树表查找树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。插入前必须要查找，以确定要插入的位置，因此必须修改二叉排序树的查找

12、算法查找不成功时必须返回插入的位置,8.2 动态查找表二叉排序树,二叉排序树查找的递归算法（查找不成功时返回插入的位置）Status SearchBST(BiTree T，KeyType key，BiTree f，BiTree&p)/在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，/若查找成功，则指针p指向该数据元素结点，并返回TRUE，/否则指针p指向查找路径上访问的最后一个结点并返回FALSE，/指针f指向T的双亲，其初始调用值为NULLif(!T)p=f；return FALSE；/查找不成功else if EQ(key,T-data.key)p=T；return TR

13、UE；/查找成功else if LT(key,T-data.key)SearchBST(T-lchild,key,T,p)；/在左子树中继续查找else SearchBST(T-rchild,key,T,p)；/在右子树中继续查找/SearchBST,8.2 动态查找表二叉排序树,二叉排序树的插入算法Status InsertBST(BiTree/树中已有关键字相同的结点，不再插入/InsertBST,8.2 动态查找表二叉排序树,二叉排序树的建立依次输入数据 53,78,65,17,87,09,81,15，建立二叉排序树,53,53,78,53,78,65,53,78,65,17,53,78

14、,65,87,17,53,78,65,09,17,87,53,78,65,81,17,87,09,53,78,65,15,17,87,09,81,8.2 动态查找表二叉排序树,二叉排序树的建立重复插入中序遍历二叉排序树，得到升序序列建立的过程即为对无序序列进行排序的过程二叉排序树既拥有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示同样n3 个数据，如果输入顺序不同，建立起来的二叉排序树的形态也不同，这直接影响到二叉排序树的查找性能。,8.2 动态查找表二叉排序树,二叉排序树的建立算法void CreateBST(BSTree bst)/*从键盘输入元素的值，创建相

15、应的二叉排序树*/KeyType key;bst=NULL;scanf(%d,8.2 动态查找表二叉排序树,二叉排序树的删除在二叉搜索树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉搜索树的性质不会失去。为保证在删除后树的搜索性能不至于降低，还需要防止重新链接后树的高度增加。分四种情况进行讨论 删除叶结点被删结点缺右子树被删结点缺左子树被删结点左、右子树都存在,单分支结点,双分支结点,8.2 动态查找表二叉排序树,二叉排序树的删除删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。,53,78,65,17,87,09,23,45,删除65,双亲结点指针清零

16、,53,78,17,87,09,23,45,8.2 动态查找表二叉排序树,二叉排序树的删除被删结点缺右子树，可以拿它的左子女结点顶替它的位置，再释放它。,53,78,65,17,87,09,23,45,删除45,缺右子树,用左子女顶替,53,78,65,17,87,09,23,8.2 动态查找表二叉排序树,二叉排序树的删除被删结点缺左子树，可以拿它的右子女结点顶替它的位置，再释放它。,53,78,88,17,94,09,23,删除78,缺左子树,用右子女顶替,53,94,88,17,09,23,8.2 动态查找表二叉排序树,二叉排序树的删除被删结点左、右子树都存在，可以在它的右子树中寻找中序下

17、的第一个结点(关键码最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。,88,53,78,81,17,94,09,45,删除78,在右子树上找中序下第一个结点填补,23,65,53,81,88,17,94,09,45,23,65,8.2 动态查找表二叉排序树,二叉排序树的删除算法Status DeleteBST(BiTree/DeleteBST,8.2 动态查找表二叉排序树,二叉排序树的删除算法Status Delete(BiTree/Delete,8.3 哈希表,什么是哈希表哈希表的构造方法哈希表的冲突处理方法哈希表的查找,8.3.1 什么是哈希表,例1:招1000个新生,将其学

18、号从000编到999，则可以用一个顺序表来存放学生的住处，每个学生的学号正好是他的信息在顺序表的序号 学 号哈希函数学生信息在表中的序号（关键字）（位置）,8.3.1 什么是哈希（hash）表,静态查找表和动态查找表元素的位置和它的关键字之间不存在一个确定关系,查找只能通过关键字的比较操作,查找效率只能取决于和给定值比较的关键字个数。如能在关键字和位置之间建立一种确定的关系f，使每个关键字和唯一的位置对应，则在查找时可以通过这种f快速找到给定值的位置，而不需要进行关键字比较。f称为哈希函数，按这个思想建立的表称为哈希表。,8.3.2 哈希表的构造,构造哈希表的就是在关键字和元素存放位置之间建立

19、映射关系 f(key)=locate(i),f(key）是什么？,(姓氏的首字母的ASCII码值-A的ASCII码值)/2,如果要加入“张”姓怎么办？,8.3.2 哈希表的构造,哈希表的构造冲突是指不同的关键字通过哈希函数的映射后得到了相同的位置冲突不可避免，但应尽量减少冲突构造哈希表的关键是找到合适的哈希函数，既可以从关键字到存储位置的进行映射,又能减少冲突。经典的构造函数都是对数字型关键字而言的，对非数字的关键字要先将其转化为数字型关键字常见的哈希构造函数有直接定址法、数字分析法、平方取中法、折叠法等，每种方法均有其适用条件,8.3.2 哈希表的构造,直接定址法 H(key)=key 或

20、H(key)=a*key+b仅限于地址集合的大小等于关键字集合的大小,如前例中学生学号和学生信息位置的映射,8.3.2 哈希表的构造,数字分析法关键字由多位数字构成，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址例：南航学生的学号构成如下 年份+专业号+班号+流水号限制条件：能够预估全体关键字每一位上各数字出现的频度,8.3.2 哈希表的构造,平方取中法关键字中每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方，通过“平方”扩大差别，同时平方值中的中间几位受到整个关键字各位的影响,8.3.2 哈希表的构造,8.3.2 哈希表的构造,折叠法关键字位数特别多，而且关

21、键字中每一位上数字分布大致均匀，可将其分割为几个部分，取其叠和为哈希地址，有“移伴叠加”和“间界叠加”，如ISBN号0-442-20586-4,8.3.2 哈希表的构造,除留余数法（取模法）H(key)=key mod p;p=m(m为表长)关键问题是如何取P，一般是取不大于m的质数或不含20以下的质因子如对关键字集合（12，39，18，24，33，21），P取9，则使含质因子3的关键字均映射到地址编号为0，3，6的位置上，增加了冲突,8.3.2 哈希表的构造,随机数法f(Key)=random(key)只能是伪随机数哈希表构造法总结具体采用哪种构造方法，取决于关键字集合的特点，对于不同的形态

22、采取不同的方法,8.3.3 哈希表的冲突处理方法,解决冲突即为产生冲突的关键字寻找下一个地址主要的方法有开放定址法链地址法,8.3.3 哈希表的冲突处理方法,开放定址法为产生冲突的关键字寻找一个地址序列h0,h1,h2hs 1=s=m-1,其中 H0=h(key)Hi=(h(key)+di)mod m i=1s对di的不同取法，就产生了三种方法：线性探测再散列、二次探测再散列、随机探测再散列,8.3.3 哈希表的冲突处理方法,线性探测再散列di=c*i二次探测再散列 di=12,-12,22,-22随机探测再散列 di 为一组伪随机数例：对于集合（19，01，23，14，55，68，11，86

23、，37），m=11,8.3.3 哈希表的冲突处理方法,链地址法：所有的相同的哈希地址存放到一个链表中，不会产生二次冲突,8.3.3 哈希表的冲突处理方法,建立一个公共溢出区 设哈希函数产生的哈希地址集为0，m-1，则分配两个表：一个基本表 ElemType base_tblm；每个单元只能存放一个元素；一个溢出表 ElemType over_tblk；只要关键码对应的哈希地址在基本表上产生冲突，则所有这样的元素一律存入该表中。查找时，对给定值kx通过哈希函数计算出哈希地址i，先与基本表的base_tbli单元比较，若相等，查找成功；否则，再到溢出表中进行查找。,8.3.4 哈希表的查找,哈希表

24、的查找查找过程与构造哈希表的过程一致，计算出哈希地址，如该位置上无元素则查找不成功，如有元素，则进行比较，如不相同则按冲突处理办法寻找下一个地址，直到找到或查找不成功查找效率和三个因素相关：哈希函数与冲突冲突办法以及哈希表的饱和度=（表中记录处）/（哈希表的长度）,开放定址冲突处理的哈希表的查找过程,8.3.4 哈希表的查找,各种查找方法的比较,处理冲突的方法,线性探测法,二次探测法与双哈希法,平均查找长度,查找成功时 查找不成功时,链地址法,第8章作业,P289P315以下题目做在书本上：（除例、10.18、10.19外）、10.2.2（除例、10.38、10.41外）以下题目做在习题本上，必须抄题：10.44、10.46、10.47、10.54、10.55、10.57、10.58,8.7 实验九,上机前的预习在实验预习报告上编写好上机题的源程序及运行程序所需的典型数据，并给程序加上适当的注释。程序加上适当的注释。题目编程实现哈希表的造表和查找算法。要求用除留余数法构造哈希函数，用二次探测再散列解决冲突。,The End,Data Structure,