二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(22)

从而可以有效地减少“堆积”的发生。下面给出双散列函数探查法的算法。算法9.9 散列表的查找和插入⑵ C/C++ 程序：──用双散列函数探查法解决冲突 HashSearch2 hashtable &ht[ ], int K HashSearch2 ht, K int i h1 K ;1. i ← h1 K [ 计算散列地址 ] int c h2 K ;c ← h2 K [ 计算探查间隔 ] while ht[i].key! K && ht[i]! 02. 循环 当ht[i].key≠K且ht[i].key≠0时, 执行 i i + c % m;i ← i +c % m if ht[i].key k3. 若ht[i].key K cout "retrieval" i ht[i] endl;则print "retrieval", i, ht[i] [ 查找成功 ] else否则ht[i].key ← K [ 插入 ] ht[i].key K;4. [ 算法结束 ] ▌ 有多种定义h2 key 的方法。但不论用什么方法定义h2都必须使h2 key 的值与m互素，才能使冲突的同义词均匀地分布在散列表中，否则可能造成同义词地址的循环计算 即陷入死循环 。

另外，用开地址法解决冲突必须注意的一个问题就是不能随便删除散列表里的表目，因为删除了一个表目会影响对其他表目的查找。因此对于经常变动的表，可以采用下面讲述的拉链法中的分离的同义词子表法来解决。⒉ 拉链法拉链法是为散列表中的每个表目建立一个称为同义词子表的单链表。当碰撞发生时，就把要插入的关键字链入到自己同义词子表中。若n个关键字映射到基本区域的m个存储单元上，则最多可以建立m个同义词子表，每个关键字的同义词存放在以这m个单元为首结点链接的子表中。用拉链法处理碰撞时，要求散列表的每个结点增加一个指针字段，用于链接同义词子表。通常每个同义词子表都很短，每个同义词子表的平均长度为n / m。这样用查找平均长度为n / m的同义词子表代替了查找长度为n的线性表，因此查找速度是很快的。同义词子表建立在什么地方呢？可以有两种处理方法：一种方法是在散列表的基本存储区域之外开辟一个溢出区用来存储同义词子表，这种方法称为分离的同义词子表法。另一种方法是不另外建立溢出区，而是将同义词子表就存储在散列表的基本区域中目前还没有被占用的单元里。这种方法称为结合的同义词子表法。下面分别介绍这两种方法。⑴ 分离的同义词子表法由于同义词子表是建立在基本区域外的溢出区，这时基本区域的结点中既存放关键字，同时又是一个链接的同义词子表的表头。

如果某个关键字没有同义词，则其指针域为空；如果某个关键字存在同义词，则它的指针域就指向溢出区的同义词子表。同义词的查找也是沿着这条链进行的。例9.24 对于10个关键字的序列 37, 08, 21, 15, 24, 03, 48, 33, 45, 20 ，仍用除余法构造散列函数，现采用分离的同义词子表法解决冲突，插入次序仍按关键字序列给出的顺序，则可得到图9-37所示的散列表。等概率情况下的平均比较次数为ASL 1+1+1+2+1+2+1+1+3+2 /101.5下面给出算法。const int m 8;typedef struct nodeint key;struct node* next;HTNode;HTNode ht[m], *p, *q;int K, n, i;此算法在散列表中查找关键字值为K结点，若找到，则检索成功；否则把这个关键字插入散列表中。这里仍假设空的结点其内容为0，而关键字值不为0。算法9.10 散列表的查找和插入⑶ ── 用分离的同义词子表法解决冲突 HashSearch3 ht, K 1. i ← h K [ 计算散列地址 ]2.若ht[i].key K 则print "succ ", i [ 一次查找成功 ] 否则 若ht[i].key 0则ht[i].key ← K; [ 插入后为表头结点 ] ht[i].next ← NULL否则 若ht[i].next ≠ NULL则 ⑴ p ← ht[i].next⑵ 循环 当p- key≠K且p- next≠NULL时,执行p ←p- next⑶ 若p- key K则print "retrieval" [ 查找成功 ]否则q ← new HTNode; q- key ← K; q- next ← NULL;p- next ← q [ 插入到子表的尾部 ]否则q ← new HTNode; q- key ← K; q- next ← NULL;ht[i].next ← q [ 插入到子表的前部 ]3. [ 算法结束 ] ▌⑵ 结合的同义词子表法该方法是把同义词子表直接在散列表的基本区域中形成。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-22.html