云南师范大学信息学院数据结构课件第8章 查找.pptVIP

（2）开放地址法的一般形式 开放定址法的一般形式为： hi=(h(key)+di)％m 1≤i≤m-1? （3）开放地址法堆装填因子的要求 开放定址法要求散列表的装填因子α≤l，实用中取α为0.5到0.9之间的某个值为宜。 （4）形成探测序列的方法 按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。 ①线性探查法(Linear Probing) 该方法的基本思想是： 将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为： ??????? d，d+l，d+2，…，m-1，0，1，…，d-1 即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。 ②二次探查法(Quadratic Probing) ?? 　二次探查法的探查序列是： ???????? hi=(h(key)+i*i)％m 0≤i≤m-1 ，即di=i2 　　 即探查序列为d=h(key)，d+12，d+22，…，等。 ??? 　该方法的缺陷是不易探查到整个散列空间。 ③双重散列法(Double Hashing) ??? 　该方法是开放定址法中最好的方法之一，它的探查序列是： ?????? hi=(h(key)+i*h1(key))％m 0≤i≤m-1，即di=i*h1(key) ??? 　即探查序列为： ?????? d=h(key)，(d+h1(key))％m，(d+2h1(key))％m，…，等。 2、拉链法处理冲突 拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于1，但一般均取α≤1。 　例：已知一组关键字为（26，36，41，38，44，15，68，12，06，51），取表长为13，用拉链法解决冲突构造这组关键字的散列表，如右图所示。 拉链法的优点 (1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短； (2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况； (3)开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间； (4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。 拉链法的缺点 拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。 散列表上的运算  //散列表类型说明： #define NIL -1 #define m 997 typedef struct { ? KeyType key； ? InfoType otherinfo； ?}NodeType； typedef NodeType HashTable[m]； 基于开放地址法的查找算法 散列表的查找过程和建表过程相似。假设给定的值为K，根据建表时设定的散列函数h，计算出散列地址h(K)，若表中该地址单元为空，则查找失败；否则将该地址中的结点与给定值K比较。若相等则查找成功，否则按建表时设定的处理冲突的方法找下一个地址,如此反复进行，直到某个地址单元为空(查找失败)或者关键字比较相等(查找成功)为止。 开放地址法一般形式的函数表示 ?int Hash(KeyType k，int i) ?? {return (h(K)+Increment(i))％m； ?? } ??? 若散列函数用除留余数法构造，并假设使用线性探查的开放定址法处理冲突，则上述函数中的h(K)和Increment(i)可定义为： ?int h(KeyType K) ??? { return K％m； ? } ? { int Increment(int i) ??? { return i; / ?? } 通用的开放定址法的散列表查找算法： int HashSearch(HashTable T，KeyType K，int *pos) ? { ??? int i=0； ??? do{ ???? *pos=Hash(K，i)； ????