数据结构第8章剖析.pptVIP

第八章 查找 8.1 概述 3、查找 4、查找表的分类 5、平均查找长度 6、查找的基本方法： 8.2 基于线性表的查找 顺序查找过程示例： 2、顺序查找算法 例： 3、顺序查找的时间复杂度分析 二、折半查找法（二分有哪些信誉好的足球投注网站法） 例如: 2、折半查找算法 3、折半查找时间复杂度分析 三、索引查找 例： 分块查找过程 分块查找时间复杂度分析 线性表的三种查找方法比较 8.3 基于树的查找法 8. 3. 1 二叉排序树（二叉查找树） 一、定义： 例如: 二叉排序树的存储结构 二、查找 例如: 三、插入 二叉排序树的生成算法 例如： 四、删除 （1）被删除的结点是叶子结点 （2）被删除结点只有左子树或只有右子树 （3）被删除的结点既有左子树也有右子树 方法二： 例：方法二 二叉排序树删除算法 五、二叉排序树的查找性能 8.3.2 平衡二叉树 例如： 例如: 2、平衡二叉排序树的构造 例： 例： (2)RR型旋转: (3)LR型旋转: (4)RL型旋转: 8.4 散列 8.4.1 哈希表的定义 上述几例的特点为： 数据类型描述为 #define HASHSIZE 11 typedef struct { int key; otherdata other; }Datatype; typedef struct { Datatype data; int times;}Hashtable [HASHSIZE]； 采用除留余数法构造hash函数 int HashFunc（int key） {return key%HASHSIZE;} 采用线性探测再散列处理冲突 int Collision(int di) {return (di+1)%HASHSIZE; } 哈希表的查找 int HashSearch(Hashtable ht,Datatype x) { int address; address=HashFunc(x.key); while(ht[address].data.key!=NULLht[address].data.key!=x.key) address=Collsion(address); if(ht[address].data.ket==x.key) return address; else return -1; } 哈希表的插入 int HashInsert(Hashtable ht,Datatype x) { int address; address=HashFunc(x.key); if(address=0) return 0; ht[-address].data=x; ht[-address].times=1; return 1; } 哈希表的创建 void Createht(Hashtable ht,Datatype L[], int n) { int i; for(i=0;iMAXSIZE;i++) { ht[i].data.key=NULL; ht[i].times=0; } for(i=0；in;i++) HashInsert(ht,L[i]); } 哈希表的删除 #define DEL -1 int HashDel(Hashtable ht,Datatype x) { int address; address=HashFunc(x.key); if(address=0) {ht[address].data.key=DEL; return 1; }return 0； } {Zi, Qi, Su, Li, Wu, Ci, He, Ye, Du} 又例：对于如下 9 个关键字 设 哈希函数 f(key) = ?(Ord(第一个字母) -Ord(A)+1)/2? Ci Zi Qi Su Li Wu He Ye Du 问题: 若需添加关键字 Zh , 怎么办？ 此类问题称为“冲突”，如何解决？ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 从上述例子可见： 哈希表的构造、使用中有两个问题有待研究： 1、如何根据关键字集合的特点，选择合适的哈希函数，使关键字均匀的散列到表中？ 2、当不同的关键字所得的哈希函数值相同时，即f(k1)=f(k2), 如何有效的处理这类“冲突”现象（碰撞），使建表、查找均能有效地进行？ 根据选定的函数 H(key) 和处理冲突的方法, 将一组关键字映象到一个有限的、连续的地址集 (区间) 上，并以每个关键字在地址集中的 “映象”作为相应