二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(26)

(3) 伪随机探测再散列：试用H(key)?f(1)，H(key)?f(2)，...

再哈希法

H1(key)冲突，试用H2(key)，H3(key)，...

链地址法

发生冲突的记录链成单链表。

建立公共溢出区

所有冲突记录存入溢出区。

装填因子 ??n n个记录，m个地址空间。

哈希表的平均查找长度与记录个数n不直接相关，而是取决于装填因子和处理冲突的方法。 举例

例：已知一组关键字{19, 14, 23, 1, 68, 20, 85, 9}，采用哈希函数H(key)=key MOD 11，请分别采用以下处理冲突的方法构造哈希表，并求各自的平均查找长度。

1) 采用线性探测再散列；

2) 采用伪随机探测再散列，伪随机函数为f(n) = - n；

3) 采用链地址法。

思路：开始时表为空，依次插入关键字建立哈希表。

1) 线性探测再散列

? 关键字

? H(key) 68 20 85 9 2 9 8 9 key 19 14 23 1 H(key) 8 3 1 1

2 3 9 10

4 10 0

查找长度 1 1 1 2 3 1 3

ASL = (1+1+1+2+3+1+3+3)/8 = 15/8

2) 伪随机探测再散列

? 冲突时计算下一地址 ? 3 ? 每个关键字的查找长度

key 19 14 23 1 68 20

H(key) 8 3 1 1 2 9

查找长度 1 1 1 2 1

ASL = (1+1+1+2+1+1+2+4)/8 = 13/8

3) 链地址法

1

2

3

4

5

6

7

8

9

10 85 9 8 9 7 1 8 7 6 2 4

ASL = (1×5+2×3)/8 = 11/8

注：关键字在链表中的插入位置可以在表头或表尾，也可以在中间以便保持关键字有序。

最后，此哈希表的装填因子是α= 8/11。

内部排序

基础知识和算法

排序的有关概念

排序（按关键字大小顺序排列数据）。

2排序方法：内部排序，外部排序；简单的排序方法O(n)，先进的排序方法O(nlogn)，基数

排序O(dn)；插入排序，交换排序，选择排序，归并排序，计数排序。

排序方法的稳定性：取决于该方法采取的策略，不是由一次具体的排序结果决定的。但是通过列举不稳定的排序实例可以说明该排序算法的不稳定性。

直接插入排序

思路

将待排序记录插入已排好的记录中，不断扩大有序序列

25一句话，“将待排序记录插入有序序列，重复n-1次”。

例：52，49，80，36，14，58，61 进行直接插入排序。

分析

表 错误！文档中没有指定样式的文字。.14 直接插入排序

记录顺序有序时

记录逆序有序时

2比较 n-1 ((n+2)(n-1))/2 2移动 0 ((n+4)(n-1))/2 最好 最坏 平均n/4，算法的时间复杂度O(n)。直接插入排序是稳定的排序算法。

折半插入排序

思路

在直接插入排序中，查找插入位置时采用折半查找的方法。

程序

void BinInsertSort ( T a[], int n )

{

for ( i=1; i<n; i++ ) {

// 在a[0..i-1]中折半查找插入位置使a[high]≤a[i]<a[high+1..i-1]

low = 0; high = i-1;

while ( low<=high ) {

m = ( low+high )/2;

if ( a[i]<a[m] )

high = m-1;

else

low = m+1;

25 不准确的说法，只为便于理解和记忆，不要在正式场合引用。

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