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

例如，当发生冲突时，可以在基本区域里从后往前地找空单元，找到空单元就把同义词存进去 并把它链接进同义子表。例9.25设有7个关键字组成的序列 37, 08, 21, 15, 24, 03, 48 ，散列表的长度为8，仍用除余法构造散列函数，现采用结合的同义词子表法解决冲突，并按关键字在序列中的顺序插入，则可得到图9-38所示的散列表。若每个关键字被查找的概率相同，则平均查找长度为1.43从图9-38中可以看到，结合的同义词子表是一种静态链表，这里用 -1来表示子表链表的结束。下面给出算法。const int m 8;typedef structint key;int next;HTNode;HTNode ht[m];int K, n, i, r;这里仍假设空的结点其内容为0，而关键字值不为0。此算法在散列表里查找一个给定的关键字值，设此关键字值进入算法前已存入变量K中，若在散列表中找到这个关键字值则查找成功，否则把这个关键字插入散列表中。算法用散列函数h key 计算表中的相对地址。r是辅助变量，用来帮助在插入时寻找空单元，r的初始值为m，在算法进行过程中，始终有这样的事实存在：散列表中从ht[r] 到ht[m-1]的所有单元都已被占用了。

算法9.11 散列表的查找和插入⑷ ── 用结合的同义词子表法解决冲突 HashSearch4 ht, K 1. i ← h K [ 计算散列地址 ]2. 若ht[i].key 0 则ht[i].key ← K; ht[i].next ← -1 [ 插入后为表首结点 ]print "inserted ", i 否则 ⑴ 循环 当ht[i].key ≠ K且ht[i].next ≠ -1时,执行i ← ht[i].next⑵ 若ht[i].key K则print "succ ", i [ 查找成功 ] 否则 ? 循环执行 当r ≥ 0且ht[r].key ≠ 0时r ← r-1? 若 r 0则print "overflow" [ 无空单元，溢出 ]否则ht[r].key ← K; ht[r].next ← -1;ht[i].next ← r ; [ 插入到子表的尾部 ]print "inserted ", r 3. [ 算法结束 ] ▌算法9.11在执行过程中，当要插入的关键字的位置已被非同义词子表的结点所占用时，便把该关键字链入了这个非同义词子表中。

即出现了堆积现象。为了避免堆积的发生，可采用如下两种处理方法：① 对于静态的表，可以用两遍处理的方法来建立散列表，第一遍只插入作为各同义词子表表头的那些关键字，第二遍再插入其他的关键字；② 上述方法不适用于动态的表，对于动态的表，可以把同义词子表组织成双链表，当发现有插入的关键字的位置已被非同义词子表的结点所占用时，便可将这个非同义词结点移走，使不同的同义词子表分离开来。算法9.11中当散列表的基本区域已占满了时，就会产生溢出，在负载因子α 1时，基本区域是不应该 也不可能 产生溢出的。另外，拉链法的结合的同义词子表法删除表目时，也不能真的删除。其原因请读者思考。9.4.4 散列查找的性能在前面的几个例子中，我们对给出的具体实例，可以直接计算出它的平均查找长度ASL,那是一种定量的性能分析方法。对于定性的分析，我们这里只给出结论，其具体的推导过程感兴趣的读者可参阅Knuth所著的《计算机程序设计技巧》第三卷。表9.2给出了采用四种不同的方法解决冲突时，散列表的平均查找长度。从表9.2可以看出，散列表的平均查找长度是负载因子α的函数，也就是说，散列表的平均查找长度 ASL 不直接依赖于表的结点个数 n ，不是随着结点数目的增多而增加，而是随着负载因子的增大而增加。

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