数据结构第九章查找

以你之姓@ 2022-06-08 11:40 365阅读 0赞

**数据结构笔记链接：**

[第一章 绪论][Link 1]

[第二章 线性表][Link 2]

[第三章 栈和队列][Link 3]

[第四章 串][Link 4]

[第五章 数组和广义表][Link 5]

[第六章 树和二叉树][Link 6]

[第七章 图][Link 7]

[第八章 排序][Link 8]

[第九章 查找][Link 9]

--------------------

### 文章目录 ###

*   *   *  9.1 基本概念
         *  9.2 基于线性表的查找
         *   *  9.2.1 顺序表查找法
             *  9.2.2 折半查找法
             *  9.2.3 分块查找法
             *  9.2.4 算法比较
         *  9.3 基于树表的查找
         *   *  9.3.1 二叉排序树
             *   *  9.3.1.1 定义和描述
                 *  9.3.1.2 二叉排序树的创建
                 *  9.3.1.3 二叉排序树的查找
             *  9.3.2 平衡二叉树
             *   *  9.3.2.1 定义和描述
                 *  9.3.2.2 平衡旋转
             *  9.3.3 B树和B+树
             *   *  9.3.3.1 B树的概念
                 *  9.3.3.2 B树的查找
         *  9.4 哈希查找法
         *   *  9.4.1 哈希表的概念
             *  9.4.2 哈希函数的构造方法
             *   *  9.4.2.1 直接定址法
                 *  9.4.2.2 除留余数法
                 *  9.4.2.3 乘余取整法
                 *  9.4.2.4 数字分析法
                 *  9.4.2.5 平方取中法
             *  9.4.3 冲突处理方法
             *   *  9.4.3.1 开放定址法
                 *  9.4.3.2 再哈希法
                 *  9.4.3.3 链地址法
                 *  9.4.3.4 建立公共溢出区
             *  9.4.4 平均查找长度
             *   *  9.4.4.1 查找成功平均查找长度
                 *  9.4.4.2 查找失败平均查找长度
         *  9.5 例题
         *   *  9.5.1 例1
             *  9.5.2 例2
             *  9.5.3 例3
             *  9.5.4 例4

--------------------

### 9.1 基本概念 ###

（1）列表  
由**同一类型**的数据元素（或记录）构成的**集合**，可利用任意数据结构实现。

（2）关键字  
数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。

如果一个关键字可以唯一标识列表中的一个数据元素，则称其为主关键字，否则为次关键字。 当数据元素仅有一个数据项时，数据元素的值就是关键字。

（3）查找  
根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。

若找到相应的数据元素，则称查找是成功的，否则称查找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。

表的查找分为`静态查找`和`动态查找`：

*  静态查找  
    在查找过程中只是对数据元素进行查找
 *  动态查找  
    在实施查找的同时，插入找不到的元素，或从查找表中删除已查到的某个元素，即允许表中元素变化

（4）平均查找长度（ASL）  
为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的`平均查找长度（ASL）`。

对于长度为 n 的列表，查找成功时的 平均查找长度为：

![ASL][]

其中 `Pi`为查找列表中第 i 个数据元素的**概率**，`Ci`为找到列表中第 i 个数据元素时，已经进行过的关键字**比较次数**。

由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来**衡量查找算法的性能**。

### 9.2 基于线性表的查找 ###

#### 9.2.1 顺序表查找法 ####

顺序查找法的特点是，用所给关键字与线性表中各元素的关键字逐个比较，直到成功或 失败。存储结构通常为顺序结构，也可为链式结构。

顺序查找算法简单，但时间效率太低，总计全部比较次数为：`n * (n+1)/2`，若求某一个元素的平均查找次数，还应当除以n(等概率)，即：**ASL＝(n＋1)/2** , 时间效率为`O(n)`（比较成功情况下）。

typedef struct { 
        ElemType   *elem;           //表基址，0号单元留空。表容量为全部元素
        int       length;          //表长，即表中数据元素个数
    }SSTable;
    
    int Search_Seq( SSTable  ST, KeyType  key ){ 
        ST.elem[0].key =key; 
        for( i=ST.length; ST.elem[ i ].key!=key;  --i)
        	; 
        return i;
    }

#### 9.2.2 折半查找法 ####

（1）先给数据排序(升序)，形成有序表。

（2）将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表。如果中间位置记录的关键字大于查找关键字， 则进一步查找前一子表，否则进一步查找后一子表。

（3）重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时 查找不成功。

int Search_Bin_Recursive(SSTable ST, int key, int low, int high) {  
      	if (low > high) 
      		return 0;	//查找不到时返回0 
      	
      	mid = (low + high) / 2; 
      	
      	if(ST.elem[mid].key == key) 
      		return mid; 
      	else if(ST.elem[mid].key>key) 
        	return Search_Bin_Recursive(ST, key, low, mid-1); 
      	else 
      		return Search_Bin_Recursive(ST, key, mid+1, high); 
    }

![折半查找][20170924183043003]

#### 9.2.3 分块查找法 ####

数据分成若干块，块内数据不必有序，但块间必须有序。

（1）对索引表使用折半查找法(因为索引表是有序表)；

（2）确定了待查关键字所在的子表后，在子表内采用顺序查找法(因为各子表内部是无序表)；

![分块查找][20170924183121007]

#### 9.2.4 算法比较 ####

<table> 
 <thead> 
  <tr> 
   <th align="left">比较</th> 
   <th align="left">顺序查找</th> 
   <th align="left">折半查找</th> 
   <th align="left">分块查找</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">平均查找长度</td> 
   <td align="left">最大</td> 
   <td align="left">最小</td> 
   <td align="left">二者之间</td> 
  </tr> 
  <tr> 
   <td align="left">表结构</td> 
   <td align="left">有序表，无序表</td> 
   <td align="left">有序表</td> 
   <td align="left">分块有序表</td> 
  </tr> 
  <tr> 
   <td align="left">存储结构</td> 
   <td align="left">顺序存储结构，线性链表</td> 
   <td align="left">顺序存储结构</td> 
   <td align="left">顺序存储结构，线性链表</td> 
  </tr> 
 </tbody> 
</table>

### 9.3 基于树表的查找 ###

#### 9.3.1 二叉排序树 ####

##### 9.3.1.1 定义和描述 #####

`二叉排序树`又称为`二叉查找树`，它是一种特殊的二叉树。

其定义为：二叉树排序树或者是一棵空树，或者是具有如下性质的二叉树：  
（1）左子树的所有结点均小于根的值；  
（2）右子树的所有结点均大于根的值；  
（3）它的左右子树也分别为二叉排序树。

这是一个递归定义。注意只要结点之间具有可比性即可，如下图 (a)中的数字值间的比 较，图(b)中是用单词字符的 ASCII 码间的比较。

![二叉排序树][20171115232745554]

二叉排序树的存储结构同二叉树，使用二叉链表作为存储结构。 其结点结构描述说明如下：

typedefstruct node { 
    	KeyType key;	/*关键字的值*/ 
    	struct node *lchild,*rchild;	/*左右指针*/
    }BSTNode,*BSTree;

##### 9.3.1.2 二叉排序树的创建 #####

假若给定一个元素序列，我们可以利用逐个插入结点算法创建一棵二叉排序树。因此， 实现建立二叉排序树包括**创建树**与**插入结点**两个算法。

（1）插入结点：

*  若二叉排序树是空树，则 key 成为二叉排序树的根
 *  若二叉排序树非空，则将 key 与二叉排序树的根进行比较
 *  如果 key 的值等于根结点的值，则停止插入
 *  如果 key 的值小于根结点的值，则将 key 插入左子树
 *  如果 key 的值大于根结点的值，则将 key 插入右子树。

例如，设关键字的输入顺序为：45，24 ，53，12，28，90，按上述算法生成的二叉排序树的过程如下图所示：

![二叉排序树的建立][20171115233303788]

可以看出，二叉排序树插入的每一个结点都是作为一个叶子结点，插入时不需要移动元素，不涉及树的整体改动。

二叉排序树的插入算法的时间复杂度为 O(log2n)。

void InsertBstree (bstree *t, KeyType k) { 
    	bstree f = NULL, p;
        p = *t;
        while (p) { 
        	if (k == p->key)
        		return;
            f = p;
            p = (k<p->key) ? p->lchild : p->rchild;
        }
        
        p=(bstree)malloc(sizeof(bsnode));	//生成新结点
        p->key=k;
        p->lchild = p->rchild=NULL;	//为叶子结点
        
        if (*t==NULL)
        	*t=p;	//原树为空
        else if (x<f->key)
        	f->lchild=p;
        else   
         	f->rchild=p;
    }

（2）创建树：

bstree  CreatBstree (void) { 
    	bstree t = NULL;
        KeyType key;  
        printf(“\n请输入一个以-1为结束标记的结点序列:\n”)
        scanf(“%d”,&key);          //输入一个关键字
        while (key!=-1) { 
        	InsertBstree (&t, key); //将key插入到树t中
            scanf(“%d”,&key);
        }   
        return (t);  //返回树的根地址
    }

##### 9.3.1.3 二叉排序树的查找 #####

（1）算法思想

*  若二叉排序树为空，则查找失败，否则，先拿根结点值与待查值进行比较：  
    若相等，则查找成功；若根结点值大于待查值，则进入左子树重复此步骤，否则进入右子树重复此步骤。
 *  若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待查结点，则查找不成功。

（2）代码实现

根据二叉排序树的定义，在二叉排序树结构上查找可以用递归与非递归两种实现算法。

typedef int KeyType;
    typedef struct node { 
        KeyType key; 
        struct node *lchild; *rchild;
    } bsnode;
    
    typedef bsnode *bstree;
    
    /* Recursive Algorithm */
    bstree bssearch(bstree t, KeyType k) { 
    	if(t==NULL || t->KeyType==k)
    		return(t);
        
        if( k<( t->KeyType )
        	return(search(t->lchild, k));
        else
    		return(search(t->lchild, k));
    }
    
    /* Dis Recursive algorithm */
    bstree bssearch1(bstree t, KeyType k, bstree *f,bstree *p) { 
    	// *p返回k在二叉树中的地址，*f 返回k的父结点地址
    	*f=NULL;
    	*p=t;
    	
    	while (*p) { 
      		if (k==(*p)->key)
      			return;
        	*f=*p; 
        	*p=(k<(*p)->key) ? (*p)->lchild : (*p)->rchild;
    	}
       
       return;
    }

（3）ASL分析

对于同一个关键字集合，关键字插入的先后次序不同，所构成的二叉排序树的形态和深度也不同。而二叉排序树的平均查找长度ASL与二叉排序树的形态有关，二叉排序树的**各分支越均衡**，树的深度浅，其**平均查找长度 ASL 越小**。

例如，下图为两棵二叉排序树，它们对应同一元素集合，但排列顺序不同：

![二叉排序树的不同形态][20171116095210063]

由此可见，在二叉排序树上进行查找时的平均查找长度和二叉排序树的形态有关。

在最坏情况下，二叉排序树是通过把一个有序表的n个结点一次插入生成的，由此得到二叉排序树蜕化为一棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，也是（n+1）/ 2。

在最好情况下，二叉排序树在生成过程中，树的形态比较均匀，最终得到的是一棵形态 与折半查找的判定树相似的二叉排序树，此时它的平均查找长度大约是 log2n 。

若考虑把n个结点，按各种可能的次序插入到二叉排序树中，则有n棵二叉排序树（其中有的形态相同），可以证明，对这些二叉排序树的查找长度进行平均，得到的平均查找长度仍然是 O(log2n)。

就平均性能而言，二叉排序树上的查找和折半查找相差不大，并且二叉排序树  
上的插入和删除结点十分方便，无需移动大量结点。因此，对于需要经常做插入、删除、查 找运算的表，宜采用二叉排序树结构。人们也常常将二叉排序树称为`二叉查找树`。

#### 9.3.2 平衡二叉树 ####

##### 9.3.2.1 定义和描述 #####

`平衡二叉排序树`又称为`AVL树`。

一棵平衡二叉排序树或者是空树，或者是具有下列性质的二叉排序树：

*  左子树与右子树的高度之差的**绝对值小于等于1**
 *  左子树和右子树**也是**平衡二叉排序树。

引入平衡二叉排序树的目的，是为了**提高查找效率**，其平均查找长度为O(log2n)。

引入`平衡因子（balancefactor）`这一概念，其定义为：结点的左子树深度与右子树**深度之差**。

显然，对一棵平衡二叉排序树而言，其所有结点的平衡因子只能是`-1`、`0`、或`1`。当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现平衡因子绝对值大于`1`。

![平衡和失衡二叉排序树][20171116103339366]

##### 9.3.2.2 平衡旋转 #####

如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为`平衡旋转`。

平衡旋转可以归纳为四类：

*  LL型平衡旋转
 *  RR型平衡旋转
 *  LR型平衡旋转
 *  RL型平衡旋转

（1）LL型平衡旋转

一棵平衡二叉排序树如下图（a）所示。在 A 的左子树的左子树上插入 15 后，导致失 衡，如下图（b）所示。为恢复平衡并保持二叉排序树特性，可将 A 改为 B 的右子，B 原来 的右子，改为 A 的左子，如下图（c）所示。这相当于以 B 为轴，对 A 做了一次顺时针旋转。

![LL][]

（2）RR型平衡旋转

已知一棵平衡二叉排序树如下图（a）所示。在 A 的右子树 B 的右子树上插入 70 后， 导致失衡，如下图（b）所示。为恢复平衡并保持二叉排序树特性，可将 A 改为 B 的左子， B 原来的左子，改为 A 的右子，如下图（c）所示。这相当于以 B 为轴，对 A 做了一次逆时 针旋转。

![RR][]

（3）LR型平衡旋转

已知一棵平衡二叉排序树如下图（a）所示。在 A 的右子树的左子树上插入 55 后，导 致失衡，如下图（b）所示。为恢复平衡并保持二叉排序树特性，可首先将 B 改为 C 的右子， 而 C 原来的右子，改为 B 的左子；然后将 A 改为 C 的左子， C 原来的左子，改为 A 的右子， 如下图（c）所示。这相当于对 B 做了一次顺时针旋转，对 A 做了一次逆时针旋转。

![LR1][]

![LR2][]

（4）RL型平衡旋转

已知一棵平衡二叉排序树如下图（a）所示。在 A 的左子树 B 的右子树上插入 45 后， 导致失衡，如下图（b）所示。为恢复平衡并保持二叉排序树特性，可首先将 B 改为 C 的左 子，而 C 原来的左子，改为 B 的右子；然后将 A 改为 C 的右子， C 原来的右子，改为 A 的 左子，如下图（c）所示。这相当于对 B 做了一次逆时针旋转，对 A 做了一次顺时针旋转。

![RL1][]

![RL2][]

一般情况下，只有**新插入结点**的**祖先结点**的平衡因子受影响，即以这些祖先结点为根的子树有可能失衡。

下层的祖先结点恢复平衡，将使上层的祖先结点恢复平衡，因此应该调整最下面的失衡子树。因为平衡因子为0的祖先不可能失衡，所以从新插入结点开始向上，遇到的**第一个**其平衡因子**不等于0**的**祖先结点**为**第一个可能失衡的结点**，如果失衡，则应**调整以该结点为根的子树**。

练习：输入关键字序列\{16, 3, 7, 11, 9, 26, 18, 14, 15\}，给出构造一棵AVL树的步骤：

![AUL\_TEST1][AUL_TEST1]

![AUL\_TEST2][AUL_TEST2]

#### 9.3.3 B树和B+树 ####

前面所讨论的查找算法都是在内存中进行的，它们适用于较小的文件，对较大的、存放在外存上的文件就不合适了。

1970年R.Bayer和E.McCreight提出了一种称为`B树`的`多路平衡查找树`，它适合在磁盘等直接存取设备上组织动态的索引表，在系统运行过程中插入或删除记录时，索引结构本身也可能发生变化，以保持较好的查询性能。

B树是一种组织和维护外存文件系统非常有效的数据结构，并得到广泛的应用。

B树中所有结点的**孩子结点最大值**称为B树的`阶`，通常用m表示。从查找效率考虑，要求m≥3。

m阶B+树 可看作是 m阶B树 的变形。

##### 9.3.3.1 B树的概念 #####

一棵m阶的B树，或为空树，或为满足下列特性的m叉树：

（1）树中每个结点至多有`m`棵子树，即每个结点至多有`m-1`个关键字。

（2）除根之外的所有非叶子结点至少有`m/2`棵子树，即至少有`m/2-1`个关键字。

（3）若根结点不是叶子结点，则至少有两棵子树，即B树是所有结点的平衡因子**均等于0**的多路查找树。

（4）所有叶子结点在同一个层次上，且不含有任何信息。

（5）所有非叶子结点中包含下列信息：

![B树结构][B]

其中：

*  ki(1≤i≤n)为关键字，且满足**ki < ki+1**
 *  pi(0≤i≤n)为该结点的孩子结点指针且满足:  
    ki+1< pi(0≤i≤n-1)结点上的关键字 ≤ki  
    pn结点上的关键字 > kn
 *  n为该结点中关键字个数，除根结点外，其他结点：m/2-1≤n≤m-1。( n+1为子树个数 )

![4阶B树][4_B]

##### 9.3.3.2 B树的查找 #####

在B树上进行查找的过程与二叉排序树的查找类似。

根据给定的键值k，先在**根结点**的键值的集合中采用顺序(当m较小时)或二分(当m较大时)查找方法进行查找。

若有**k=ki**，则查找成功，根据相应的指针即可取得记录；否则，若k在ki和ki+1之间，取指针**pi所指的结点**，重复这个查找过程，直到在某结点中查找成功，或在某结点处出现pi为空，查找失败 。

### 9.4 哈希查找法 ###

#### 9.4.1 哈希表的概念 ####

（1）`哈希表`：即散列存储结构。

散列法存储的基本思想：**建立关键码字与其存储位置的对应关系**，或者说，由关键码的值决定数据的存储地址。查找速度极快(**O(1)**)，查找效率与元素个数n无关！

例1：若将学生信息按如下方式存入计算机，如：  
将2001011810201的所有信息存入V\[01\]单元；  
将2001011810202的所有信息存入V\[02\]单元；  
……  
将2001011810231的所有信息存入V\[31\]单元。

> 欲查找学号为2001011810216的信息，便可直接访问V\[16\]单元

（2）`哈希方法`：选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；**查找时，由同一个函数**对给定值k计算地址，将k与地址单元中元素关键码进行比较，确定查找是否成功。

（3）`哈希函数`：哈希方法中使用的转换函数称为哈希函数(`杂凑函数`)。

例2：有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址 H(k)＝k，请画出存储结构图。

![散列例2][2]

（4）`哈希表`：按上述思想构造的表称为哈希表(杂凑表)。

（5）`冲突`：通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将**不同的关键码映射到同一个哈希地址上**，这种现象称为冲突。

例3：有6个元素的关键码分别为：(14, 23, 39, 9, 25, 11)。选取关键码与元素位置间的函数为：`H(k)=k mod 7`：

![散列例3][3]

在哈希查找方法中，**冲突是不可能避免的**，只能尽可能减少。

所以，哈希方法必须解决以下两个问题：

*  构造好的哈希函数  
    所选函数尽可能简单，以便提高转换速度；所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。
 *  制定一个好的解决冲突的方案  
    查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。

#### 9.4.2 哈希函数的构造方法 ####

构造哈希函数的原则是：

*  函数本身**便于计算**。
 *  计算出来的**地址分布均匀**，即对任一关键字 k，H(k) 对应不同地址的概率相等，目的是尽可能减少冲突。

##### 9.4.2.1 直接定址法 #####

`Hash(key) = a•key + b` (a、b为常数)

**优点**：以关键码key的某个线性函数值为哈希地址，不会产生冲突。  
**缺点**：要占用连续地址空间，空间效率低。

例如：关键码集合为 \{ 100, 300, 500, 700, 800, 900 \}，选取哈希函数为Hash(key)=key/100，则存储结构(哈希表)如下：

##### 9.4.2.2 除留余数法 #####

`Hash(key) = key mod p` (p是一个整数)

**特点**：以关键码除以p的余数作为哈希地址。

**关键**：如何选取合适的p

**技巧**：若设计的哈希表长为m，则一般取 p≤m 且为质数（也可以是不包含小于20质因子的合数）。

##### 9.4.2.3 乘余取整法 #####

`Hash(key) = B * (A * key mod 1)` (A、B均为常数，且0<A<1，B为整数)

**特点**：以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希地址。

##### 9.4.2.4 数字分析法 #####

如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以 从关键字中选出分布较均匀的若干位，构成哈希地址。

例如，有 80 个记录，关键字为 8 位十进制整数 d1d2d3…d7d8，如哈希表长度取为 100，则哈希表的地址空间为：0~99。

假设经过分析，各关键字中d4和d7的取值分布较均匀，则哈希函数为：`H(key)=H(d1d2d3…d7d8)=d4d7`。例如，H(81346532)=43，H(81301367)=06。

相反，假设经过分析，各关键字中d1和d8的取 值分布极不均匀， d1都等于5，d8都等于2，此时，如果哈希函数为：`H (key)= H (d1d2d3…d7d8)=d1d8`，则所有关键字的地址码都是52，显然不可取。

##### 9.4.2.5 平方取中法 #####

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的**平方值**，然后按需要取平方值的中间几位作为哈希地址。

这是因为平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。

例：2589的平方值为6702921，可以取中间的029为地址。

#### 9.4.3 冲突处理方法 ####

##### 9.4.3.1 开放定址法 #####

**基本思想**：又称为`再散列法`，当关键字 key 的初始哈希地址 h0=H（key） 出现冲突时，以 h0为基础，产生另一个地址 h1，如果 h1仍然冲突，再以 h0为基础，产生另一个哈希地址 h2，…，直到找出一个不冲突的地址 hi ，将相应元素存入其中。

这种方法有 一个通用的再散列函数形式：

`i=（H（key）+di）%m i=1，2，…，n` 或 `i=（h0 +di）%m i=1，2，…，n`

其中 H（key）为哈希函数，m 为表长，di称为增量序列。

增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：

*  线性探测法
 *  二次探测法
 *  伪随机探测法

以`线性探测法`为例：`i=(Hash(key)+di) mod m ( 1≤i < m )`

其中：

*  Hash(key) 为哈希函数
 *  m 哈希表长度
 *  di 为增量序列 1，2，…m-1，且di=i

**含义**：一旦冲突，就找附近（下一个）空地址存入。

例：关键码集为\{47, 7, 29, 11, 16, 92, 22, 8, 3\}。设：哈希表表长为m=11；哈希函数为Hash(key)=key mod 11，拟用线性探测法处理冲突。建哈希表如下：

![线性探测法例][20171116191245783]

**解释**：  
47、7(以及11、16、92)均是由哈希函数得到的没有冲突的哈希地址；

`Hash(29)=7`，哈希地址有冲突，需寻找下一个空的哈希地址：由H1=(Hash(29)+1) mod 11=8，哈希地址8为空，因此将29存入。另外，22、8、3同样在哈希地址上有冲突，也是由H1找到空的哈希地址的。

**优点**：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；

**缺点**：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“**堆积**”起来，大大**降低了查找效率**。

##### 9.4.3.2 再哈希法 #####

这种方法是同时构造多个不同的哈希函数：`Hi=RHi（key） i=1，2，…，k`

当哈希地址`H1=RH1（key）`发生冲突时，再计算 `H2=RH2（key）……`，直到冲突不再产 生。这种方法不易产生聚集，但增加了计算时间。

##### 9.4.3.3 链地址法 #####

这种方法的基本思想是将所有哈希地址为 i 的元素构成一个称为**同义词链**的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在同义词链中进行。

链地址法适用于经常进行插入和删除的情况。

例：已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表 长度为 13，哈希函数为：H（key）=key%13，给出用链地址法处理冲突的结果，计算平均查找长度。如下图所示：

![链地址法][20171116191607719]

> 平均查找长度ASL=(1 \* 7 + 2 \* 4 + 3 \* 1) / 12 = 1.5

##### 9.4.3.4 建立公共溢出区 #####

基本思想是：将哈希表分为**基本表**和**溢出表**两部分，凡是和基本表发生冲突的元素一律填入溢出表。

#### 9.4.4 平均查找长度 ####

对于哈希表的平均查找长度（ASL），通过一个例子就能够学会计算。

假设存在关键字序列：`（15，22，36，40，63）`，哈希函数为：`H（K）＝K MOD 7`。K为关键字，用线性探测法再散列法处理冲突。

##### 9.4.4.1 查找成功平均查找长度 #####

**查找成功平均长度=总查找成功次数 / 关键字个数**。

如上表所示，成功查找关键字63、36、40仅需要1次即可，对于关键字15需要2次，对于关键字22需要3次。

> ASL = (1×3 + 2 + 3)/5 = 1.6

##### 9.4.4.2 查找失败平均查找长度 #####

**查找失败平均长度=每个下标到最近的空位置的长度和 / MOD的值。**

对于下标0，距离最近的空位置长度为5；对于下标1，距离最近的空位置长度为4；依次计算出如下表：

> ASL = (5 + 4 + 3 + 2 + 1 + 2 + 1) / 7 ≈ 2.57

【注】表述并不严谨，只是为了方便理解。

### 9.5 例题 ###

#### 9.5.1 例1 ####

折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素【 】比较大小。

> 28，6，12，20

#### 9.5.2 例2 ####

假设在有序线性表a\[20\]上进行折半查找，则比较一次查找成功的结点数为【 】；比较两次查找成功的结点数为【 】；比较四次查找成功的结点数为 【 】；平均查找长度为【 】。

> 1 ; 2 ; 8 ; 3.7

注：全部元素的`查找次数为＝(1＋2×2＋4×3＋8×4＋5×5)＝74`； `ASL＝74/20=3.7`。

#### 9.5.3 例3 ####

从供选择的答案中，选出应填入下面叙述【 】内的最确切的解答，把相应编号写在答卷的对应栏内。

数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的插入和删除 B 。通常查找线性表数据元素的方法有 C 和 D 两种方法，其中 C 是一种只适合于顺序存储结构但 E 的方法；而 D 是一种对顺序和链式存储结构均适用的方法。

供选择的答案：  
A： ①顺序存储线性表 ②非顺序存储非线性表 ③顺序存储非线性表 ④非顺序存储线性表

B： ①不需要移动结点，不需改变结点指针 ②不需要移动结点，只需改变结点指针 ③只需移动结点，不需改变结点指针 ④既需移动结点，又需改变结点指针

C： ①顺序查找 ②循环查找 ③条件查找 ④二分法查找

D： ①顺序查找 ②随机查找 ③二分法查找 ④分块查找

E： ①效率较低的线性查找 ②效率较低的非线性查找 ③效率较高的非线性查找 ④效率较高的线性查找

> ④ ； ② ； ④ ； ① ； ③

#### 9.5.4 例4 ####

设哈希（Hash）表的地址范围为0～17，哈希函数为：`H（K）＝K MOD 16`。  
K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：  
`（10，24，32，17，31，30，46，47，40，63，49）`  
造出Hash表，试回答下列问题：  
（1）画出哈希表的示意图；  
（2）若查找关键字63，需要依次与哪些关键字进行比较？  
（3）若查找关键字60，需要依次与哪些关键字比较？  
（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

解：  
（1）画表如下：

（2） 查找63,首先要与`H(63)=63%16=15`号单元内容比较，即`63 vs 31 ,no;`  
然后顺移，与`46,47,32,17,63`相比，一共比较了6次！

（3）查找60,首先要与`H(60)=60%16=12`号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

（4） 对于没有移位的数据元素，各比较1次；共6次；对移位的元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，  
所以`ASL=1/11（1×6+6＋2＋3+3+3）＝23/11≈2.09`。

--------------------

[Link 1]: http://blog.csdn.net/yuanlaijike/article/details/69442950
[Link 2]: http://blog.csdn.net/yuanlaijike/article/details/69451381
[Link 3]: http://blog.csdn.net/yuanlaijike/article/details/69472125
[Link 4]: http://blog.csdn.net/yuanlaijike/article/details/69480358
[Link 5]: http://blog.csdn.net/yuanlaijike/article/details/69486729
[Link 6]: http://blog.csdn.net/yuanlaijike/article/details/78070403
[Link 7]: http://blog.csdn.net/yuanlaijike/article/details/78074765
[Link 8]: http://blog.csdn.net/yuanlaijike/article/details/78078434
[Link 9]: http://blog.csdn.net/yuanlaijike/article/details/78078788
[ASL]: /images/20220608/7bdf8e5d46cc40778233df51115ca8e1.png
[20170924183043003]: /images/20220608/01b2910ec0894cc89b4dd3c211d2148b.png
[20170924183121007]: /images/20220608/17008775d33d438191aa284c0d82be66.png
[20171115232745554]: /images/20220608/3a39052de76743c0b0128c1f298e7026.png
[20171115233303788]: /images/20220608/eacd43ccde7c4b61a598b1caa7836b32.png
[20171116095210063]: /images/20220608/f20e77a33cbf4428bfd728a853830d7f.png
[20171116103339366]: /images/20220608/ded892a5704649708710441f212eb401.png
[LL]: /images/20220608/3ad3823c326446a7ac0615620d04f0e6.png
[RR]: /images/20220608/9df31f2e7646473abd62077d3f8b7c5f.png
[LR1]: /images/20220608/22912582238247598d0ef8ae9e7e815f.png
[LR2]: /images/20220608/baf9f38ae498455c9176e56ca1951ec2.png
[RL1]: /images/20220608/468d6200721d41c8a4d8dd2053b56ff6.png
[RL2]: /images/20220608/d427f653b300492eae9859d733da24f3.png
[AUL_TEST1]: /images/20220608/473e42b6d0bc497c965f6e5560961476.png
[AUL_TEST2]: /images/20220608/659d90759a674f40925443ad860b866f.png
[B]: /images/20220608/b5fa37b676214d4894c1138beb237eba.png
[4_B]: /images/20220608/fb19d80998004eca9cbf6261242f2846.png
[2]: /images/20220608/1f28058bd1ef41c6b8f5cd61c4120252.png
[3]: /images/20220608/785b3483abe14b438074a5211ee0b8ab.png
[20171116191245783]: /images/20220608/700eefd3eeaf429e945b93a4b0fd25e8.png
[20171116191607719]: /images/20220608/0fbfa0ccd8654dfb9ceb827abe773f5a.png