数据结构纪颖中国机械工业教育协会组编7单元查找教程.pptVIP

2．链地址法 链地址法就是把发生冲突的关键字用单链表链接起来的方法。在这种方法中哈希表（散列表）中的每个单元（下标位置）不是存储相应的元素，而是存储相应单链表的表头指针。单链表中的每个结点动态产生，同时每个元素被存储在相应的单链表中，在单链表中也可以任意的插入和删除结点。此种方法解决冲突时，首先根据关键字计算出散列地址，接着把给该关键字产生的动态结点插入到下标为该地址的单链表中（可以插入在单链表的任意位置处，但插在表头最方便）。查找过程也与插入类似，首先计算出散列地址，然后从该地址的单链表中查找关键字，若查找成功则返回该元素的存储地址，否则返回空指针。仍以上例用链地址法建立散列表见下图: 0 1 2 3 4 5 6 7 8 9 10 要存储的关键字:47，7，29，11，16，92，3 47 7 29 H(47)=47%11=3 H(7)=7%11=7 H(29)=29%11=7 H(11)=11%11=0 11 H(16)=16%11=5 16 H(92)=92%11=4 92 H(3)=3%11=3 3 ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ 7.4.4 哈希表的查找分析 哈希表的查找过程基本上和建表过程相同。一些关键字可通过哈希函数转换的地址直接找到，另一些关键字在哈希函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的2种处理冲突的方法中，产生冲突后的查找仍然是用给定值与关键字进行比较的过程。因此对哈希表查找效率的量度，可以用平均查找长度来衡量。 从线性探测法和二次探测法处理冲突的例子中看，相同的关键字集合、同样的哈希函数，但在数据元素查找等概率情况下，它们的平均查找长度却不同： 线性探测法的平均查找长度: ASL=(4×1+1×2+1×4)/7=10/7 二次探测法的平均查找长度: ASL=(4×1+1×2+1×3)/7=9/7 填入表中的元素个 α= ───────── 哈希表的长度 α是哈希表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。 哈希表的装填因子定义为： 实际上，哈希表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。 不同解决冲突方法的平均查找长度: 处理冲突 的方法 平 均 查 找 长 度 查找成功时 查找不成功时 线性探测法 二次探测 链地址法 Snl≈(1+1/(1- α))/2 Unl≈(1+1/(1- α)2)/2 Snr≈ln(1-α)/α Unc≈1/(1-α) Snc≈1+α/2 Unc≈α+e-α 作业 1.总结出常用的哈希函数和解决冲突的方法有哪几种。 2.装填因子α是如何定义的? 3.做教材习题中的以下题目。 单项选择题：(2),(8),(10) 填空题：(3),(4) ,(9) 应用题：(3) ,(5) 馋死 PPT研究院 POWERPOINT ACADEMY * * * * * * int deletenode(nodetype **t,keytype key) { nodetype *p=*t,*q,*s,**f; int flag=0; if(searchelem(*t,p,q,key)); { flag=1; /*查找成功，置删除成功标志*/ if(p==q) f=(*t); /*待删结点为根结点时*/ else { f=(p-lc); /*待删结点非根结点时*/ if(keyp-elem)f=(p-rc);} /*f指向待删结点的父结点的相应指针域*/ if(!q-rc)*f=q-lc; /*若待删结点无右子树，以左子树替换待删结点*/ else { if(!q-lc)*f=q-rc; /*若待删结点无左子树，以右子树替换待删结点*/ else { p=q-rc;s=p; /*既有左子树又有右子树*/ while(p-lc)