[小学教育]第八章查找.ppt

第八章 查找,8.1 基本概念 8.2 静态查找表 8.3 动态查找表 8.4 哈希表,查找也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素 关键字是数据元素中某个数据项的值，它可以标识一个数据元素 查找方法评价 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的,8.2.1 顺序表的查找 查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较,64,监视哨,比较次数=5,比较次数： 查找第n个元素： 1 查找第n-1个元素：2 . 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1,#define MAXSIZE 100 #define KEYTYPE int typedef struct KEYTYPE key; otherdata ; / 记录的其余数据部分 SSELEMENT; typedef struct SSELEMENT rMAXSIZE; int len; SSTABLE;,int seq_search (KEYTYPE k, SSTABLE st) int j; j = st.len; st.r0.key = k; while(st.rj.key != k) j-; return j; ,顺序查找算法：,顺序查找方法的ASL,查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现: 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值 初始时，令low=1,high=n,mid=(low+high)/2 让k与mid指向的记录比较 若k=rmid.key，查找成功 若krmid.key，则low=mid+1 重复上述操作，直至lowhigh时，查找失败,8.2.2 有序表查找（折半查找）,算法描述：,算法评价: 判定树：描述查找过程的二叉树叫 有n个结点的判定树的深度为log2n+1 折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度,折半查找的ASL：,8.2.3 索引顺序表查找（分块查找） 查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 用数组存放待查记录,每个数据元素至少含有关键字域 建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针,1 2 3 4 5 6 7 8 8 10 11 12 13 14 15 16 17 18,22 12 13 8 8 20 33 42 44 38 24 48 60 58 74 57 86 53,索引表,查38,算法描述:,typedef struct int key; int link; SD; typedef struct int key; float info; JD; int blocksrch(JD r ,SD nd ,int b,int k,int n) int i=1,j; while(kndi.key),if(ib) printf(“nNot found“); return(0); j=ndi.link; while(jn) ,8.2 动态查找表,动态查找表的特点：表结构本身是在查找过程中动态生成的，即对给定值key，若表中存在则查找成功，否则插入关键字等于key的记录,定义：二叉排序树或是一棵空树，或 是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值 它的左、右子树也分别为二叉排序树,8.3.1 二叉排序树生成和插入,二叉排序树的插入： 插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子 二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树,插入算法,例 10， 18， 3， 8， 12， 2， 7， 3,10,中序遍历二叉排序树可得到一个关键字的有序序列,数据结点类型：,#define KEYTYPE int; typedef struct node KEYTYPE key; otherdata ; / 结点的其余数据部分struct node *lchild, *rchild; BSTNODE,插入算法：,void insert_btree_onenode(KEYTYPE k, BSTNODE *p) if(p = NULL) / 如果二叉排序树空 p = malloc(sizeof(BSTNODE); p-lchild = NULL; p-rchild = NULL; p-key = k; else if(k p-key) insert_btree_onenode(k,p-rchild else insert_btree_onenode(k,p-lchild ,typedef struct node int data; struct node *lchild,*rchild; JD; JD *insertbst(JD *r,int x) JD *p,*q,*s; s=(JD *)malloc(sizeof(JD); s-data=x; s-lchild=s-rchild=NULL; q=NULL; if(r=NULL) r=s; return(r); p=r;,while(p!=NULL) q=p; if(xdata) p=p-lchild; else p=p-rchild; if(xdata) q-lchild=s; else q-rchild=s; return(r); ,要删除二叉排序树中的p结点，分三种情况： p为叶子结点，只需修改p双亲f的指针 f-lchild=NULL f-rchild=NULL p只有左子树或右子树 p只有左子树，用p的左孩子代替p (1)(2) p只有右子树，用p的右孩子代替p (3)(4) p左、右子树均非空 沿p左子树的根C的右子树分支找到S，S的右子树为空，将S的左子树成为S的双亲Q的右子树，用S取代p (5) 若C无右子树，用C取代p (6),二叉排序树的删除,中序遍历：CL C QL Q SL S P PR F,(5),中序遍历：CL C P PR F,中序遍历：CL C PR F,(6),删除算法,JD *delnode(JD *r,JD *p,JD *f) JD *q,*s; int flag=0; if(p-lchild=NULL) s=p-rchild; else if(p-rchild=NULL) s=p-lchild; else ,删除算法:,q=p; s=p-lchild; while(s-rchild!=NULL) q=s; s=s-rchild; p-data=s-data; if(q=p) q-lchild=s-lchild; else q-rchild=s-lchild; free(s); flag=1;,if(flag=0) if(f=NULL) r=s; else if(f-lchild=p) f-lchild=s; else f-rchild=s; free(p); return(r); ,查找性能的分析： 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值，显然，由值相同的n个关键字构造所得的，不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大,例如：,由关键字序列1，2，3，4，5构造而得的二叉排序树 ASL =（1+2+3+4+5）/ 5 = 3 由关键字序列3，1，2，5，4构造而得的二叉排序树 ASL =（1+2+3+2+3）/ 5 = 2.2 一般情况下，考虑含有n个关键字可能出现的n!种序列出现的可能性相等。,不失一般性，假设某个序列中有k个关键字小于第一个关键字，即有n-k-1个关键字大于第一个关键字，由它构造的二叉排序树的平均查找长度是n和k的函数P(n, k)(0kn-1) 则含n个关键字的二叉排序树的平均查找长度 而在等概率的情况下，,由此 可类似于解差分方程，此递归方程有解： 从查找的角度看，希望由任意序列生成的二叉排序树，其左、右子树的深度近似相等，但实际上有47%的情况生成的二叉排序树非如此。,9.5 平衡二叉树,起因：提高查找速度，避免最坏情况出现。如右图情况的出现。,平衡因子（平衡度）：结点的平衡度是结点的左子树的高度右子树的高度。 平衡二叉树：每个结点的平衡因子都为 1、1、0 的二叉树。或者说每个 结点的左右子树的高度最多差一的二叉树。,平衡二叉排序树的 Adelson 算法的本质特点： 以插入为例： 在左图所示的平衡二叉排序树中插入数据场为2的结点。 插入之后仍应保持平衡二叉排序树的性质不变。,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,平衡树,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度为 0,危机结点,如何用最简单、最有效的办法保持平衡二叉排序树的性质不变？,平衡二叉排序树的 Adelson 算法的本质特点： 以插入为例： 在左图所示的平衡二叉排序树中插入数据场为 2 的结点。 插入之后仍应保持平衡二叉排序树的性质不变。,如何用最简单、最有效的办法保持平衡二叉排序树的性质不变？,解决方案： 不涉及到危机结点的父亲结点，即以危机结点为根的子树的高度应保持不变（左图为 3 ）。 新结点插入后，找到第一个平衡度不为 0 的结点（如左图结点 ）即可。新插入的结点和 第一个平衡度不为 0 的结点（也可能是危机结点）之间的结点，其平衡度皆为 0 在调整中，仅调整那些在平衡度变化的路径上的结点（如： ），其它结点不予调整。 仍应保持二叉树排序树的性质不变。,9,平衡二叉排序树的 Adelson 算法的本质特点： 以插入为例： 在左图所示的平衡树中插入数据场为 2 的结点。 插入之后仍应保持平衡二叉排序树的性质不变。,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度为 0,危机结点,如何用最简单、最有效的办法保持平衡二叉排序树的性质不变？,2,3,5,9,7,12,2,3,5,9,7,12,不可以以结点 为子树的根结点！虽然，对本例来说是可以行得通的。,7,平衡二叉排序树的 Adelson 算法的本质特点： 以插入为例： 在左图所示的平衡二叉排序树中插入数据场为 2 的结点。 插入之后仍应保持平衡二叉排序树的性质不变。,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度为 0,危机结点,关键：将导致出现危机结点的情况全部分析清除，就可以使得平衡二叉排序树的性质保持不变！,14,9,3,2,5,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,12,0,0,左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 1、LL 情况：（LL：表示新插入结点在危机结点的左子树的左子树上）,A,B,+1,h-1,0,+2,+1,h,h-1,h-1,LL 改组,BL,BR,AR,B,A,0,h,0,h-1,h-1,BL,BR,AR,危机结点,改组前：高度为 h + 1 中序序列：,A,B,BL,BR,AR,改组后：高度为 h + 1 中序序列：,A,B,BL,BR,AR,注意：改组后 平衡度为 0,A,B,左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情况A：,A,B,+1,h-1,0,+2,-1,h-1,LR 改组,BL,AR,危机结点,改组前： 高度为 h + 1 中序序列：,注意：改组后 平衡度为 0,0,-1,C,B,C,CL,CR,h-2,h-2,h-1,0,+1,C,B,0,h-1,h-1,BL,AR,A,CR,h-2,CL,h-1,-1,0,A,B,BL,AR,C,CL,CR,改组后： 高度为 h + 1 中序序列：,A,B,BL,AR,C,CL,CR,A,左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情况B：,A,B,+1,h-1,0,+2,-1,h-1,LR 改组,BL,AR,危机结点,改组前： 高度为 h + 1 中序序列：,注意：改组后 平衡度为 +1,0,0,C,B,C,CR,CL,h-1,h-2,h-2,0,-1,C,B,0,h-1,h-1,BL,AR,A,CR,h-1,CL,h-2,+1,0,A,B,BL,AR,C,CR,CL,改组后： 高度为 h + 1 中序序列：,A,A,B,BL,AR,C,CR,CL,左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情况C：,A,B,+1,0,+2,-1,LR 改组,危机结点,改组前： 高度为 2 中序序列：,注意：改组后 平衡度为 0,0,0,C,B,C,0,A,B,C,A,新插入结点,A,B,C,改组后： 高度为 2 中序序列：,C,B,0,A,0,0,四种情况的区分： 如果 的平衡度为1 则为 LL型改组； 否则为 LR型改组：若 的平衡度为1、1 、0 ；则分别为 LRA、LRB、LRC型改组。,B,C,右改组（新插入结点出现在危机结点的右子树上进行的调整）的情况分析： 1、RR 情况：（RR：表示新插入结点在危机结点的右子树的右子树上） 处理图形和 LL 镜象相似 2、RL 情况：（RL：表示新插入结点在危机结点的右子树的左子树上） A、处理图形和 LRA 镜象相似 B、处理图形和 LRB 镜象相似 C、处理图形和 LRC 镜象相似 删除情况：略 程序实现：略,8.6、B_ 树和 B+ 树 1、为什么采用B_ 树和 B+ 树： 大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入内存。因此，要多次 访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。 在 1970 年由 R bayer 和 E macreight 提出用B_ 树作为索引组织文件。提高访问速度、减少时间。,内存,E.G: 用二叉树组织文件，当文件的记录个数为 100，000时，要找到给定关键字的记录，需访问外存17次（log100,000）,太长了！,50,25,10,75,15,35,60,90,20,30,40,55,70,80,95,索引文件,数据文件,文件头，可常驻内存,文件访问示意图：索引文件、数据文件存在盘上,2、B_ 树是一种多分支数，首先介绍 m 阶 B_ 树： 定义： m 阶 B_ 树满足或空，或： A、根结点要么是叶子，要么至少有两个儿子 B、除根结点和叶子结点之外，每个结点的儿子个数为: m/2 K1 且 Kn 的结点的地址（指在该 B_ 树中） 注意：K1 =K2 = . = Kn D、所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。,例如：m = 4 阶 B_ 树。除根结点和叶子结点之外，每个结点的儿子个数 至少为 m/2 = 2 个；结点的关键字个数至少为 1 。该 B_ 树的深度为 4。 叶子结点都在第 4 层上。,1，99,3，47，58，64,1，39,1，27,1，11,2，43，78,1，18,1，35,第 1 层,第 2 层,第 3 层(L层),第 4 层(L1层),B_ 树和 B+ 树 3、B_ 树的查找代价分析： 查找过程，类似于二叉树的查找。如查找关键字为 KEY 的记录。 从根开始查找，如果 Ki = KEY 则查找成功，Ri 为关键字为 KEY 的记录的地址。 若 Ki Kn; 查找 An指向的结点 若 找到叶子，则查找失败。 注意：每次查找将去掉 （s-1）/s 个分支，比二分查找快得多。 设关键字的总数为 N ，求 m阶 B_ 树的最大层次 L。 层次 结点数 关键字的个数（最少） 1 1 1 2 2 2（ m/2 -1） 3 2（ m/2 ） 2（ m/2 ） （ m/2 -1） 4 2（ m/2 ） 2 2（ m/2 ）2 （ m/2 -1） L 2（ m/2 ）L-2 2（ m/2 ）L-2 （ m/2 -1） L+1 2（ m/2 ）L-1 所以，N=1 2（ m/2 -1） +.+ 2（ m/2 ）L-2 （ m/2 -1） = 2 m/2 L-1 -1 故：Llog （N+1）/2）+ 1,B_ 树和 B+ 树 3、B_ 树的查找代价分析： 设关键字的总数为 N ，求 m阶 B_ 树的最大层次 L。 故：Llog m/2 （N+1）/2）+ 1 设 N 1000，000 且 m256 ，则 L = 3；最多 3 次访问外存可找到所有的记录。,4、B_ 树的插入操作 1、确定插入位置，将结点插入到第 L 层（注意：第 L+1 层为叶子结点） 2、找到插入位置，将关键字和其它信息按序插入。 3、若被插入结点的关键字个数 m-1, 则该结点满。必须分裂成两个结点。否则不满结束。 如结点原为： （m-1, A0, (K1, A1), (K2, A2), (Km-1, Am-1)） 插入一个关键字之后变为： （m, A0, (K1, A1), (K2, A2), (Km, Am)） 该结点将进行分裂： . (K m/2 , p ) . （m/2-1, A0, (K1, A1), (K m/2 , A m/2 )） （m- m/2 , A m/2 , (Km, Am)） 生成新结点 p, 将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。,P,P,(K m/2 , p ) 数据项插入上层结点之中,B_ 树和 B+ 树,例如：3 阶 B_ 树的插入操作。m=3, m/2 - 1 = 1; 至少 1 个关键字，二个儿子结点。,3，12,7 24 30,24，30,45，70,53,90,26,100,39,50,61,85,3,45，70,53,90,26,100,39,50,61,85,12,30,3,24 45 70,53,90,26,100,39,50,61,85,12,7,30,3,24,53,90,26,100,39,50,61,85,12,7,45,70,7插入,B_ 树和 B+ 树,5、B_ 树的删除操作 1、查找具有给定键值的关键字 Ki 2、如果 在第 L 层，可直接删除（注意：第 L+1 层为叶子结点），转 4 。 3、否则，则首先生成 “替身”。用 的右子树中的最左面的结点的关键字值，即 处于第 L 层上的最小 关键字值取代 。然后，删除第 L 层上的该关键字。 4、从第 L 层开始进行删除。 A、不动：若删除关键字值的那个结点的关键字的个数仍处于 m/2 -1和 m-1之间。则结束。 B、借：若删除关键字值的那个结点的关键字的个数原为 m/2 -1 。而它们的左或右邻居结 点的关键字的个数 m/2 -1 ; 则借一个关键字过来。处理结束。 C、并：若该结点的左或右邻居结点的关键字的个数为 m/2 -1 ; 则执行合并结点的操作。 如结点原为： （ . (Ki, Ai), (Ki+1, Ai+1), . ） （ A0, (K1, A1 ) ） （ A0, (K1, A1 ) ） K1L ,第 L 层：找到了被删结点的替身。,B_ 树和 B+ 树,例如：3 阶 B_ 树的删除操作。m=3, m/2 - 1 = 1; 至少 1 个关键字，二个儿子结点。,3,24,45,53 90,37,100,50,61，70,被删关键字,3,24,45,61 90,37,100,53,70,借：向被删结点方向旋转,假定再删除该关键字,3,24,45,90,37,100,61，70,假定再删除该关键字,3，24,45,90,100,61，70,3，24,45 90,100,61，70,并,并,并,并：和父结点的一个关键字、及邻居合并。有可能进行到根，使B_ 树的深度降低一层！,9.3 哈希表 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 定义 哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象 哈希函数可写成：addr(ai)=H(ki) ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字,哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫 哈希查找又叫散列查找，利用哈希函数进行查找的过程叫,以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2,以地区别作关键字，取地区 名称第一个拼音字母的在字母表 中序号作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19,从例子可见： 哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可 冲突：key1key2，但H(key1)=H(key2)的现象叫 同义词：具有相同函数值的两个关键字，叫该哈希函数的 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法,9.3.2 哈希函数的构造方法 直接定址法 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=akey+b 特点 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突 实际中能用这种哈希函数的情况很少,数字分析法 构造：对关键字进行分析，取关键字的若干位或若干位组合作哈希地址 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况,例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数,分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机 所以：取任意两位或两位 与另两位的叠加作哈希地址,平方取中法 构造：取关键字平方后中间几位作哈希地址 适于不知道全部关键字情况,折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种类 移位叠加：将分割后的几部分低位对齐相加 间界叠加：从一端沿分割界来回折送，然后对齐相加 适于关键字位数很多，且每一位上数字分布大致均匀情况,例 关键字为 ：0442205864，哈希地址位数为4,除留余数法 构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pm 特点 简单、常用，可与上述几种方法结合使用 p的选取很重要；p选的不好，容易产生同义词 随机数法 构造：取关键字的随机函数值作哈希地址，即H(key)=random(key) 适于关键字长度不等的情况,选取哈希函数，考虑以下因素： 计算哈希函数所需时间 关键字长度 哈希表长度（哈希地址范围） 关键字分布情况 记录的查找频率,9.3.3 处理冲突的方法 开放定址法 方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,k(km-1) 其中：H(key)哈希函数 m哈希表表长 di增量序列,di增量序列(有三种取法) 线性探测再散列：di=1,2,3,m-1 二次探测再散列：di=1,-1,2,-2,3,k(km/2) 伪随机探测再散列：di=伪随机数序列,例 表长为11的哈希表中已填有关键字为17，60，29的记录， H(key)=key MOD 11,现有第4个记录，其关键字为38， 按三种处理冲突的方法，将它填入表中,(1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突,(2) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5 -1) MOD 11=4 不冲突,(3) H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则： H1=(5+9) MOD 11=3 不冲突,再哈希法 方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key) i=1,2,k 其中：Rhi不同的哈希函数 特点：计算时间增加 链地址法 方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针,例 已知一组关键字 (19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79) 哈希函数为：H(key)=key MOD 13, 用链地址法处理冲突,哈希查找过程及分析 哈希查找过程,哈希查找分析 哈希查找过程仍是一个给定值与关键字进行比较的过程 评价哈希查找效率仍要用ASL 哈希查找过程与给定值进行比较的关键字的个数取决于： 哈希函数 处理冲突的方法 哈希表的填满因子=表中填入的记录数/哈希表长度,例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等 (1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m,14,1,68,27,55,19,20,84,79,23,11,10,H(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5,H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，H5=(1+5)MOD16=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=9,ASL=(1*6+2+3*3+4+9)/12=2.5,H(19)=6,H(14)=1,H(23)=10,H(1)=1 冲突，H1=(1+1) MOD16=2,H(68)=3,H(20)=7,H(84)=6 冲突，H1=(6+1)MOD16=7 冲突，H2=(6+2)MOD16=8,H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4,H(11)=11,H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=12,(19,14,23,1,68,20,84,27,55,11,10,79) H(key)=key MOD 13 Hi=(H(key)+di) MOD m,(2) 用链地址法处理冲突,ASL=(1*6+2*4+3+4)/12=1.75,关键字(19,14,23,1,68,20,84,27,55,11,10,79),哈希查找算法实现 用线性探测再散列法处理冲突 实现 查找过程：同前 删除：只能作标记，不能真正删除 插入：遇到空位置或有删除标记的位置就可以插入 算法描述： 用链表处理冲突算法,#define M 100 int h(int k) return(k%97); int slbxxcz(int t,int k) int i,j=0; i=h(k); while(jM) ,int slbxxcr(int t,int k) int i,j=0; i=h(k); while(j0) j+; if(j=M) return(0); i=(i+j)%M; if(ti=0) ti=k; return(1); if(ti=k) return(1); ,int slbxxsc(int t,int k) int i,j=0; i=h(k); while(jM) ,9.4 哈希（HSAE）查找-散列查找 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 定义 哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫 根据关键字的值，利用某个函数直接计算出元素所在的位置。这函数称为“哈希函数”，能用散列技术进行查找的表称为散列表（哈希表）。 哈希表技术的主要目标是提高查找效率，即缩短查表和填表的时间。,以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2,以地区别作关键字，取地区 名称第一个拼音字母的序号 作哈希函数：H(Beijing)=2 H(Shanghai)=18 H(Shenyang)=18,从例子可见： 哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可 冲突：key1key2，但H(key1)=H(key2)的现象叫 同义词：具有相同函数值的两个关键字，叫该哈希函数的 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法 哈希函数的构造方法 直接定址法 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=akey+b 特点 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突 实际中能用这种哈希函数的情况很少,数字分析法 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况,例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数,分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机 所以：取任意两位或两位 与另两位的叠加作哈希地址,平方取中法 构造：取关键字平方后中间几位作哈希地址 适于不知道全部关键字情况 折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种类 移位叠加：将分割后的几部分低位对齐相加 间界叠加：从一端沿分割界来回折送，然后对齐相加 适于关键字位数很多，且每一位上数字分布大致均匀情况,例 关键字为 ：0442205864，哈希地址位数为4,除留余数法 构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pm 特点 简单、常用，可与上述几种方法结合使用 p的选取很重要；p选的不好，容易产生同义词 随机数法 构造：取关键字的随机函数值作哈希地址，即H(key)=random(key) 适于关键字长度不等的情况 选取哈希函数，考虑以下因素： 计算哈希函数所需时间 关键字长度 哈希表长度（哈希地址范围） 关键字分布情况 记录的查找频率,处理冲突的方法 开放定址法 方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,k(km-1) 其中：H(key)哈希函数 m哈希表表长 di增量序列 线性探测再散列：di=1,2,3,m-1 再哈希法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key) i=1,2,k 其中：Rhi不同的哈希函数 特点：计算时间增加,例 表长为11的哈希表中已填有关键字为17，60，28的记录， H(key)=key MOD 11,现有第4个记录，其关键字为38， 按处理冲突的方法，将它填入表中,H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突,38,链地址法(外链法) 方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针,例 已知一组关键字(18,14,23,1,68,20,84,27,55,11,10,78) 哈希函数为：H(key)=key MOD 13, 用链地址法处理冲突,例 已知一组关键字(18,14,23,1,68,20,84,27,55,11,10,78) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等,(1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m,H(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5,H(78)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，H5=(1+5)MOD16=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=8,ASL=(1*6+2+3*3+4+8)/12=2.5,14,1,68,27,55,18,20,84,78,23,11,10,H(18)=6,H(14)=1,H(23)=10,H(1)=1 冲突，H1=(1+1) MOD16=2,H(68)=3,H(20)=7,H(84)=6 冲突，H1=(6+1)MOD16=7 冲突，H2=(6+2)MOD16=8,H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4,H(11)=11,H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=12,(2) 用链地址法处理冲突,ASL=(1*6+2*4+3+4)/12=1.75,关键字(18,14,23,1,68,20,84,27,55,11,10,78),二叉排序 树上的查找,（1）二叉排序 树的查找思想 若二叉排树为空，则查找 失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。,（2）二叉排序树查找的算法实现,Btreenode * find( Btreenode *BST,elentype x) /在以BST为根指针的二叉排队 树中查找值为x的结点 if ( BST= =NULL) return NULL; /查找失败 else if (BST-data= =x) /查找成功 return BST; else if (BST-datax) /进入左子树查找 return find ( BST-left,x); else /进入右子树查找 return find