第八章 查找【数据结构】【精致版】

前言

2023-11-7 16:00:47

以下内容源自《【数据结构】【精致版】》

仅供学习交流使用

第8章 查找

8.1 概述

所谓查找,就是根据给定的某个值,在一组记录集合中确定某个特定的数据元素(记录)或 者找到属性值符合特定条件的某些记录。

其中,由同一类型的数据元素(或记录)构成的集合称为“查找表”,也就是查找对象的集合。 关键字是查找表中“特定的"数据元素(或记录)的某个数据项的值,用来识别一个数据元素(或 记录)。若关键字可以唯一地识别一个记录,则称其为“主关键字”;若关键字能识别若干个记录,则称其为“次关键字”

通常,对查找表进行的操作有以下几种。

①查询某个特定的数据元素是否在查找表中

②检索某个特定的数据元素的各种属性，

③在查找表中插入某个数据元素

④从查找表中删除某个数据元素

一般前两项称为“静态查找”,后两项称为“动态查找”

如果在查找表中存在待查记录,则查找成功,并输出该记录的相关信息,或指示该记录在查找表中的位置;否则查找不成功,给出空记录或空指针。

平均查找长度:为确定某元素在查找表中的位置,需要和给定值进行比较的关键字个数的期望值,称为该查找算法查找成功时的“平均查找长度”(average search length,ASL)。

对于长度为n的查找表,查找成功时的平均查找长度为ASL= ∑ⁿ_i=1P_iC_i。其中P_i为查找第i个记录的概率, 且 ∑ⁿ_i=1p=1。C_i为找到该记录时，曾经和给定值比较过的关键字的个数。

8.2 基于线性表的查找

8.2.1顺序查找

顺序查找表的数据类型描述如下。

#define MAXSIZE 1000    //顺序查找表记录数目
typedef int KeyType;    //假设关键字类型为整型
typedef int OtherType; 
typedef struct{
  KeyType key;    //关键字项
  //其他数据项,类型OtherType依赖于具体应用而定义
  OtherType other_data;
}RecordType;//记录类型
typedef struct{
  RecordType r [MAXSIZE+1]; 
  int length;   //序列长度,即实际记录个数
}SeqRList;      //记录序列类型,即顺序表类型

为符合C语言标准,记录序列的下标都从0开始,但下标为0的位置一般作为“监视哨"或

空闲不用,实际的记录序列都从下标为1的记录开始，

例如，一个顺序查找表的记录序列的关键字分别为21,37,88,19,92,5,64,56,80,72,13,待查找记录的关键字为64。

由于整个记录序列是无序的,所以查找时只能从前向后或从后向前进行,从概率的角度来说选择哪种进行都是可以的。

算法8-1为从后向前进行顺序查找的实现。

显然,该算法的时间代价主要消耗在while循环处,即两个循环判断条件的执行。其中,第

个循环条件i>=1是保证循环的结束,即边界条件的判定。事实上,在保证查找成功的情况下，该条件的执行只是白白浪费时间。有实验表明,在查找记录超过1000条时,该条语句的执行时间占到了整个算法执行时间的60%。

算法8-2为改进后(即加“监视哨")的顺序查找实现。

1-顺序查找.c

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 1000    //顺序查找表记录数目
typedef int KeyType;    //假设关键字类型为整型
typedef int OtherType; 
typedef struct{
  KeyType key;    //关键字项
  //其他数据项,类型OtherType依赖于具体应用而定义
  OtherType other_data;
}RecordType;//记录类型
typedef struct{
  RecordType r [MAXSIZE+1]; 
  int length;   //序列长度,即实际记录个数
}SeqRList;      //记录序列类型,即顺序表类型
//输入  
void input(SeqRList* L){
  printf("输入查找表\n"); 
  int n;
  printf("输入长度:");
  scanf("%d",&n);
  L->length=n;
  int i=1;
  for(i;i<=n;i++){
    printf("%d输入元素:",i);
    scanf("%d",&(L->r[i].key));
  } 
}
//输出 
void output(SeqRList* L){
  printf("输出查找表\n"); 
  printf("输出长度:%d\n",L->length);
  int i;
  for(i=1;i<=L->length;i++){
    printf("%d输出元素：%d\n",i,L->r[i].key);
  }
}
//【算法8-1】顺序查找
int SeqSearch(SeqRList L,KeyType K){
  int i=L.length;
  while (i>=1&&L.r[i].key!=K) i--;
  return(i);
} 
//【算法8-2】加“监视哨”的顺序查找
int SeqSearch2( SeqRList L,KeyType K){
  L.r[0].key=K;//监视哨
  int i=L.length;
  while (L.r[i].key!=K)i--;
  return(i);
}

int main(){
  SeqRList L;
  input(&L);
  int s=SeqSearch(L,64);
  printf("s:%d\n",s);
  int s2=SeqSearch2(L,64); 
  printf("s2:%d\n",s2);
//  output(&L);
  return 0;
}

可以看出,算法利用了0号位管作为“监视哨”,人为地将其关键字设置为待查记录的键字K。这样从后向前进行查找时,省去了边界条件的判断,无论查找成功或失败都能找到

该条记录在查找表中的位置。如果是i>0的位置,则在找成功;如果是i=0的位置,则查找失败。

对顺序表,其平均查找长度为ASL=nP₁+(n-1)P₂+2P_n-1+P_n

在等概率查找的情况下,P_i=1/n,C_i=n-i+1

顺序表查找成功时的平均查找长度为ASL_SUCC-=1/n ∑ⁿ_i=1(n-i+1)= (n+1)/2

也就是说,香找成功时的平均比较次数是表长的一半,那么当表长很大时,查找的效率比较低。但是,顺序查找的优势在于对表的特性没有要求,数据元素可以任意排列,插入元素可以直接加到表尾。

如果查找不成功,则需要讲行n+1次比较才能确定查找失败。假设被查找的关键字记录在线性表中(即查找成功)的概率为p，不在线性表中(即查找失败)的概率为1-p。那么,成功和失败的查找都考虑在内时的平均比较次数为

ASL=p(n+1)/2+(1-p)(n+1)=(n+1)(1-p/2)

可以看出，(n+1)/2<ASL<(n+1)

通常情况下,查找概率无法事先测定,为了加快查找速度,可以建立自组织线性表。自组织 线性表是根据实际的记录访问模式在线性表中修改记录顺序,主要使用启发式规则决定如何重 新排列线性表。一般管理自组织线性表的启发式规则有以下三种。

①最不频繁使用法(least frenquently used,LFU),也叫做“计数法”。。

②最近最少使用法(least recently used,LRU),也叫做“移至前端法”。

③转置(transpose)方法,也叫做“调换方法”。

8.2.2 折半查找

【算法 8-3】折半查找的非递归实现

2-折半查找.c

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 1000    //顺序查找表记录数目
typedef int KeyType;    //假设关键字类型为整型
typedef int OtherType; 
typedef struct{
  KeyType key;    //关键字项
  //其他数据项,类型OtherType依赖于具体应用而定义
  OtherType other_data;
}RecordType;//记录类型
typedef struct{
  RecordType r [MAXSIZE+1]; 
  int length;   //序列长度,即实际记录个数
}SeqRList;      //记录序列类型,即顺序表类型
//输入  
void input(SeqRList* L){
  printf("输入查找表\n"); 
  int n;
  printf("输入长度:");
  scanf("%d",&n);
  L->length=n;
  int i=1;
  for(i;i<=n;i++){
    printf("%d输入元素:",i);
    scanf("%d",&(L->r[i].key));
  } 
}
//输出 
void output(SeqRList* L){
  printf("输出查找表\n"); 
  printf("输出长度:%d\n",L->length);
  int i;
  for(i=1;i<=L->length;i++){
    printf("%d输出元素：%d\n",i,L->r[i].key);
  }
}
//【算法 8-3】折半查找的非递归实现
int BinSrch(SeqRList L,KeyType K){
  int low=1,high=L.length,mid;
  while(low<high){
    mid=(low+high)/2;
    if(K==L.r[mid].key) return mid;
    if(K<L.r[mid].key) high=mid-1;
    else low=mid+1;
  }
  return 0;
}

int main(){
  SeqRList L;
  input(&L);
  printf("查找的索引：\n");
  int s=BinSrch(L,3);
  printf("s:%d\n",s);
  output(&L);
  return 0;
}

运行结果如下：

查找成功时，关键字的比较次数最多不超过⌊log₂n⌋+1

查找失败时，关键字的比较次数最多不超过⌊log₂n⌋+1

折半查找成功时的平均查找长度为

ASL=∑ⁿ_i=1P_iC_i=1/n ∑ⁿ_i=1C_i=1/n ∑^h_j=1 x2^j-1=(n+1)/n log₂(n+1)-1

当n>50时，可得近似结果ASL≈ log₂(n+1)-1

折半查找适用于一些建立就很少改动，而且与需要经常查找的有序查找表

8.2.3 索引查找

略

8.3 基于树的查找

8.3.1 二叉排序树

二叉排序树(binary search tree,BST),又称为“二叉查找树",是一种高效的数据结构。二叉排序树或者是一棵空树,或者是具有如下特性的二叉树。

①若它的左子树不空,则左子树上所有结点的值均小于根结点的值

②若它的右子树不空,则右子树上所有结点的值均大于根结点的值

③它的左、右子树也都分别是二叉排序树

显然,这是一个递归定义,首先要保证结点的值之间具有可比性,另外,关键字之间不允许重复出现。在实际应用中,不能保证被查找记录的关键字互不相同,可将 ①中的“小于"改为“小于等于”,或将②中的“大于"改为“大于等于”,甚至可同时修改这两个性质。

中序遍历二叉排序树便得到递增的有序序列。

二叉排序树可以使用二叉链表作为存储结构,数据类型描述如下。

typedef int KeyType;  //假设的关键字类型
typedef int OtherType;
typedef struct Node{
  KeyType key;
  OtherType other_data;
  struct Node* Lchild,* Rchild;  
}BSTNode,* BSTree;

1.二叉排序树的查找

由于二叉排序树可以看成是一个有序表,所以在二叉排序树上进行查找类似于折半查找,即逐步缩小查找范围的过程。具体如下 。

①若给定值等于根结点的关键字,则查找成功。

②若给定值小于根结点的关键字,则继续在左子树上进行查找。

③若给定值大于根结点的关键字,则继续在右子树上进行查找。

由图8-9可以看出,整个查找过程类似于在折半查找的判定树上进行折半查找。从根结点出发,沿着左子树或右子树逐层向下直至关键字等于给定值的结点——查找成功;从根结点出发,沿着左子树或右子树逐层向下直至指针指向空结点(方块处)为止——查找失败。

基于二叉排序树查找的非递归实现见算法8-4.

显然,根据递归特性,算法也可以用递归实现,见算法8-5。

2.二叉排序树的插入

首先查找待插入的记录是否在树中,如果存在则不允许插入重复关键字；如果直到找到叶子结点仍没有发现重复关键字,则把待插结点作为新的叶子结占插入。具体地,若二叉排序树为空树,则新插入的结点为新的根点:否则,新插入的结点必为一个新的叶子结点,其插入位置由查找不成功的位置确定。

[算法8-6]二叉排序树的插入

3.二叉排序树的建立

二叉排序树的建立是基于插人算法进行的,根据给定的关键字顺序依次插入得到。

可以看出，二叉排序树的形态完全由输入顺序决定,相同的关键字不同的输人顺序会产生不同的二叉排序树

[算法8-7] 二叉排序树的建立

4.二叉排序树的删除

由于二叉排序树要求关键字之间满足一定的大小关系,这就使得从中删除一个结点的算法相对复杂。具体地,首先在二叉排序树中查找待删结点,如果不存在则不做任何操作;否则,分以下三种情况进行讨论。

①待删结点是叶子结点:

②待删结点只有左子树或只有右子树。

③待删结点既有左子树也有右子树。

先看第①种情况

可以看出,此种情况只需将待删结点的父亲结点的相应孩子城置空，

再来看第②种情况

可以看出,此种情况只需将待删结点的父亲结点的相应孩子域置为该孩子对应的左子树可右子树。

最后来看第③种情况,待删结点既有左子树又有右子树。从二义排序树中删除这样一个 点时,要保持剩下结点之间依然满足排序树的特征,就不能在二义排序树中留下一个空位置，因此需要用另一个结点来补充这个位置。那么应该用哪个结点来补充呢?而日为了保证删除的高效性,应该尽量保证其他元素的移动量是最小的。前面已经分析过,二叉排序树的中序遍历结果恰好是一个有序序列,那么可以利用这个结果找到替换待删结点的位置,其实就是待删结点的前驱结点或后继结点。关键是这两个结点在二叉排序树的什么位置。

综合前面提到的三种情况，算法8-8 为二叉排序树的算法实现。

[算法8-8] 二叉排序树的删除

5.二叉排序树的性能分析

二叉排序树查找的最差情况与顺序查找相同,ASL=(n+1)/2;最好情况与折半查找相同,ASL可以达到对数级log₂n。

对于二叉排序树的插入和删除操作来说,只需修改某些结点的指针城,不需要大量移动其他记录,动态查找的效率很高。

3-二叉排序树.c

#include<stdio.h>
#include<stdlib.h>
typedef int KeyType;  //假设的关键字类型
typedef int OtherType;
typedef struct Node{
  KeyType key;
  OtherType other_data;
  struct Node* Lchild,* Rchild;  
}BSTNode,* BSTree;
//访问 
void Visit(KeyType n){
  printf("%d\n",n);
}
//递归 中序
void InOrder(BSTree root){
  //中序遍历二叉树，root为根节点的指针 
  if(root){
    InOrder(root->Lchild);
    Visit(root->key);
    InOrder(root->Rchild);
  } 
} 
//【算法8-4】基于二叉排序树查找的非递归实现
BSTree SearchBST( BSTree bst, KeyType K){ 
  BSTree q;
  q=bst;
  while(q){
    if (q->key==K) return q;
    if (K<q->key) q=q->Lchild;
    else q=q->Rchild;
  }
  return NULL;
}
//【算法8-5】 基于二叉排序树查找的递归实现
BSTree SearchBST2(BSTree bst,KeyType K){
  if(!bst) return NULL;
  else if(bst->key==K) return bst;
  else if(K<bst->key) return SearchBST2(bst->Lchild,K);
  else return SearchBST2(bst->Rchild,K);
}
//【算法8-6】二叉排序树的插入
void InsertBST(BSTree * bst,KeyType K){
  BSTree s;
  if(*bst==NULL){
    s=(BSTree)malloc(sizeof(BSTNode));  
    s->key=K;
    s->Lchild=NULL;
    s->Rchild=NULL;
    *bst=s;
  }
  else if(K<(*bst)->key) InsertBST(&((*bst)->Lchild),K); 
  else if(K>(*bst)->key) InsertBST(&((*bst)->Rchild),K);
}
# define ENDKEY -999
//【算法8-7】  二叉排序树的建立
void CreateBST (BSTree * bst){
  KeyType key;
  *bst=NULL;
  printf("输入关键字："); 
  scanf("%d",&key) ;  
  while(key!=ENDKEY){
    InsertBST(bst,key);
    printf("输入关键字："); 
    scanf("%d",&key); 
  }
}  
//【算法8-8】 二叉排序树的删除
BSTNode * DelBST( BSTree bst,KeyType K){
  BSTNode *p,*f,*s,*q;
  p=bst;
  f=NULL;
  while(p){
    if(p->key==K) break;
    f=p;
    if(p->key>K) p=p->Lchild;  
    else p=p->Rchild;
  }
  if(p==NULL)  return bst;
  if(p->Lchild==NULL){
    if(f==NULL) bst=p->Rchild;
    else if(f->Lchild==p)f->Lchild=p->Rchild;
    else f->Rchild=p->Rchild;
    free(p);
  }else{
    q=p;
    s=p->Lchild;
    while(s->Rchild){
      q=s;
      s=s->Rchild;
    }
    if(q==p) q->Lchild=s->Lchild;  
    else q->Rchild=s->Lchild;  
    p->key=s->key;
    free(s);
  }
  return bst;
}

// 32 21 14 65 58 44 72 80
int main(){
  BSTree bst;
  printf("建立二叉排序树\n"); 
  CreateBST(&bst);
  printf("中序遍历二叉排序树\n"); 
  InOrder(bst);
  KeyType K=21;
  BSTree s=SearchBST(bst,K);
  printf("SearchBST\n");
  if(s){
    Visit(s->key);
  }
  BSTree s2=SearchBST2(bst,K);
  printf("SearchBST2\n");
  if(s2){
    Visit(s2->key);
  }
  printf("中序遍历删除K=%d后的二叉排序树\n",K); 
  BSTree bst2=DelBST(bst,K); 
  InOrder(bst2);
}

代码运行结果如下

8.3.2 平衡二叉树

略

8.3.3 B树和B+树

略

8.3.4伸展树

略

8.3.5红黑树

略

8.4 散列

散列方法是一种计算式查找方法，又叫“hash（哈希。杂凑）法”或“关键字地址计算”等。

它的基本思想是,首先在记录的关键字key和记录的存储位置p之间建立一个对应关系H,使得p=H(key),H称为“哈希函数”,p称为“散列地址”。当创建哈希表时,把关键字为key的记录 建存人地址为H(key)的地址单元中;以后当在找关键字为key的记录时,再利用哈希函数n: H(k)计算出该记录的散列地址p,从而达到直接存取记录的目的。因此,散列方法的核心就是由哈希函数决定关键字值与散列地址之间的对应关系,通过这种关系来组织存储并进行查找等操作。

由于哈希函数是一个压缩映像,因此在实际应用中很少存在不产生冲突的哈希函数,因而在采用散列方法进行查找时必须解决以下两个问题。

①如何构造恰当的哈希函数,使得结点分布均匀,尽量少产生冲突。
②一旦发生冲突,如何处理冲突。

8.4.1哈希函数的构造方法

本节将介组几种哈希函数的构造方法。在这些方法中,假设处理的关键字值为整型,这样就 可以建立一种关键字与整数之间的对应关系,从而把关键字的查找转换为对应的整数的查找。哈希函数的构造原则为简单和均匀,具体如下。

①哈希函数本身运算尽量简单,便于计算:

②哈希函数值必须在散列地址范围内,且分布均匀,地址冲突尽可能少。

下面介绍几种常用的哈希函数构造方法。

(1)除留余数法

该方法是最为简单常用的一种方法。假设表长为m,p为小于等于表长m的最大素数,则哈希函数为H(key)=key%p

对于p的选取问题,p应为不大于m的质数或者是不含20以下的质因子 。

（2）数字分析法

（3）平方取中法

（4）分段叠加法

（5）基数转换法

在实际应用中,还是应该根据实际情况选择采用恰当的散列方法,并用实际数据测试它的性能,以便做出正确判定。

一般应考虑以下因素。

①计算哈希函数所需的时间,

②关键字的长度

③散列表的大小

④关键字分布的情况

⑤记录查找的频率

8.4.2处理冲突的方法

尽管构造性能良好的哈希函数可以减少冲突,但实际上冲突是不可避免的。事实上,处理冲突的实际含义就是为产生冲突的地址寻找下一个散列地址。接下来介绍几种处理冲突的方法

1.开放定址法

开放定址法也被称为“再散列法”。其基本思想是,当关键字key的初始散列地址h₀=H(key)出现冲突时,以h₀为基础查找下一个地址h₁,如果h₁仍然冲突,再以h₀为基础,产生另一个散列地址h₂…直到找出一个不冲突的地址h_i,将相应元素存入其中。这种方法有一个通用的再散列函数形式:

h_i=(H(key)+d_i)%m i=1,2,…,n

其中,H(key)为哈希函数,h,=H(key),m为表长,d_i为增量序列。增量序列的取值方式不同,对应有不同的再散列方式,主要有以下三种。

(1)线性探测再散列

d_i=cxi 最简单的情况c=1

这种方法的特点是,冲突发生时,顺序查看表中下一个单元,直到找到一个空单元或查遍全表。值得注意的是,由于这里使用的是%运算,因而整个表成为一个首尾连接的循环表,在查找时类似于循环队列,表尾的后边是表头,表头的前边是表尾。

(2)二次探测再散列

d_i=1²,-1²,2²,-2²,…k²,-k²(k≤m/2)

这种方法的特点是,冲突发生时分别在表的右、左进行跳跃式探测,较为灵话,不易产生聚集，但缺点是不能探查到整个散列地址空间。

(3)随机探测再散列

d_i=伪随机数

这种方法需要建立一个随机数发生器,并给定一个随机数作为起始点。

2.链地址法

链地址法解决冲突的基本思想是,把所有具有地址冲突的关键字链在同一个单链表中: 若哈希表的长度为m,则可将哈希表定义为一个由m个头指针组成的指针数组。散列地址为i的记录均插入以指针数组第i个单元为头指针的单链表。

8.4.3哈希表查找

根据不同的处理冲突的方法,哈希表的查找操作也有所不同。这里以开放定址法处理冲突为例,介绍相关的操作。

数据类型描述如下。

#define HASHSIZE 11
typedef int otherdata; 
typedef struct{
  int key;
  otherdata other;
}Datatype;
typedef struct{
  Datatype data;
  int times;//比较次数
}Hashtable[HASHSIZE];

如果构造哈希函数采用除留余数法,即H(key)=key%m,则获得散列地址的算法描述如下。

[算法8-10]采用除留余数法构造哈希函数

// 【算法8-10】采用除留余数法构造哈希函数
int HashFunc(int key){
  return key%HASHSIZE;
}

如果采用线性探测再散列处理冲突,处理冲突的算法描述如下。

[算法8-11]采用线性探测再散列处理冲突

//【算法8-11】采用线性探测再散列处理冲突
int Collision(int di){
  return(di+1)%HASHSIZE;
}

1.哈希表的查找

哈希表的查找过程与构建哈希表的过程类似。查找过程如下。

①根据待查找记录的关键字和建表时的哈希函数计算散列地址

②若该地址所对应的地址单元为空,则在找失败;若不为空,则将该单元中的关键字与待查记录的关键字进行比较,如果相等则查找成功,否则按建表时设定的处理冲突的方法找下一个地址。

③重复上述步骤②,直至某个单元为空,则查找失败或与待查记录的关键字相等,查找

成功

哈希表的查找算法如下。

[算法8-12]哈希表的查找

//【算法8-12】哈希表的查找
int HashSearch(Hashtable ht, Datatype x){
  int address;
  address= HashFunc(x.key);//计算散列地址
  while(ht[address].data.key!=INIT&&ht[address].data.key!=x.key)
    address=Collision(address);//没找到,处理冲突
  if(ht[address].data.key==x.key) return address;//查找成功
  else return -1;//查找失败
}

2.哈希表的插入

哈希表的插入步疆为,首先通过查找算法找到待插记染在表中的位置、若在表中找到待查记录,则不必插入;著没有找到,此时查找算法给出一个单元的散列地址,将待插记录插入该地址单元

哈希表的插入算法如下。

[算法8-13] 哈希表的插入

//【算法8-13】  哈希表的插入
int HashInsert( Hashtable ht,Datatype x)  {
  int address;
  address=HashSearch(ht,x);  
  if(address>=0)return 0;
  int times=1;
  address= HashFunc(x.key);//计算散列地址
  while(ht[address].data.key!=INIT){
    address=Collision(address);//没找到,处理冲突
    times++;
  }
  ht[address].data=x;
  ht[address].times=times;
  return 1;
}

3.哈需表的创建

和前面讲过的内容相似,哈希克的创建算法是基于插入算法的。首先将表中各结点的关键字置空,使其地址为开放的,然后调用插入算法将给定的记录的关键字序列依次插入哈希表。

哈希表的创建算法如下

[算法8-14]哈希表的创建

//【算法8-14】哈希表的创建
void Createht(Hashtable ht, Datatype L[],int n){
  int i;
  for(i=0;i<HASHSIZE;i++){
    ht[i].data.key=INIT;
    ht[i].times=0;
  }
  for(i=0;i<n;i++)
    HashInsert(ht,L[i]);
}

4.哈希表的删除

基于开放定址法的哈希表不能实现真正的删除操作、只能给被删除结点设置删除标志,以 在删除后找不到比它晚插入且与它发生过冲突的记录。也就是说,如果执行真正的删除操作, 中断查找路径。如果必须对哈希表做真正的删除操作，则最好采用链地址法处理冲突的哈希表。

哈希表的删除算法如下

[算法8-15] 哈希表的删除

#define DEL -1
//【算法8-15】  哈希表的删除
int HashDel(Hashtable ht, Datatype x){
  int address;
  address = HashFunc(x.key);  
  if(address>=0){ //找到      
    ht[address].data.key=DEL;//置删除标志
    return 1;
  }
  return 0;
}

根据以上介绍的内容,产生冲突的问题是无法避免的,因而ASL=0还是理想中的情况,基于散列的方法仍然需要与关键字进行比较。因此,基于散列的查找方法的性能评价仍然需要用平均查找长度来衡量，影响关键字比较次数的因素有三个:哈希函数、处理冲突的方法以及哈希表的装填因子。

哈希表的装填因子:

α=哈希表中已存入的元素个数 / 哈希表的长度

它表示哈希表的装满程度。显然,α越小,冲突的可能性就越小,但存储空间的利用率就低；α越大,冲突的可能性就越大,但存储空间的利用率就越高。为了兼顾两者，一般选α在0.6 ~0.9的范围内

表8-2所示为几种不同外理冲突方法下的哈希表的ASL。

从表8-2中可以看出,哈希表的平均查找长度与装填因子α相关,而与待散列记录的数目 n无关。因此,无论记录数目n有多大,关键还是通过调整装填因子α控制平均查找长度使其在合理范围之内。

4-哈希表查找.c

#include<stdio.h>
#include<stdlib.h>
#define HASHSIZE 11
#define INIT -1
typedef int otherdata; 
typedef struct{
  int key;
  otherdata other;
}Datatype;
typedef struct{
  Datatype data;
  int times;//比较次数
}Hashtable[HASHSIZE];
// 【算法8-10】采用除留余数法构造哈希函数
int HashFunc(int key){
  return key%HASHSIZE;
}
//【算法8-11】采用线性探测再散列处理冲突
int Collision(int di){
  return(di+1)%HASHSIZE;
}
//【算法8-12】哈希表的查找
int HashSearch(Hashtable ht, Datatype x){
  int address;
  address= HashFunc(x.key);//计算散列地址
  while(ht[address].data.key!=INIT&&ht[address].data.key!=x.key)
    address=Collision(address);//没找到,处理冲突
  if(ht[address].data.key==x.key) return address;//查找成功
  else return -1;//查找失败
}
//【算法8-13】  哈希表的插入
int HashInsert( Hashtable ht,Datatype x)  {
  int address;
  address=HashSearch(ht,x);  
  if(address>=0)return 0;
  int times=1;
  address= HashFunc(x.key);//计算散列地址
  while(ht[address].data.key!=INIT){
    address=Collision(address);//没找到,处理冲突
    times++;
  }
  ht[address].data=x;
  ht[address].times=times;
  return 1;
}
//【算法8-14】哈希表的创建
void Createht(Hashtable ht, Datatype L[],int n){
  int i;
  for(i=0;i<HASHSIZE;i++){
    ht[i].data.key=INIT;
    ht[i].times=0;
  }
  for(i=0;i<n;i++)
    HashInsert(ht,L[i]);
}
#define DEL -1
//【算法8-15】  哈希表的删除
int HashDel(Hashtable ht, Datatype x){
  int address;
  address = HashFunc(x.key);  
  if(address>=0){ //找到      
    ht[address].data.key=DEL;//置删除标志
    return 1;
  }
  return 0;
}
//输出
void output(Hashtable ht){
  printf("输出散列表\n") ; 
  int i;
  printf("散列地址 关键字值 比较次数\n"); 
  for(i=0;i<HASHSIZE;i++){
    printf("%8d %8d %8d\n",i,ht[i].data.key,ht[i].times);
  }
} 
void CreateData(Datatype L[],int data[],int n){
  int i;
  for(i=0;i<n;i++){
    L[i].key=data[i];
  }
} 
void printData(Datatype L[],int n){
  int i;
  for(i=0;i<n;i++){
    printf("%d ",L[i].key);
  }
}

// 19,01,23,14,55,68,11,82,36
int main(){
  Hashtable ht;
  Datatype L[9]={0};
  int data[9]={19,1,23,14,55,68,11,82,36};
  CreateData(L,data,9);
//  printData(L,9); 
  Createht(ht,L,9);
  output(ht);
  return 0;
}

代码运行结果如下

8.5 算法总结

查找是一种使用最频繁的基本操作,无论是编译中的符号表,还是数据库系统的信息检索，都涉及查找操作。因此,查找操作的实现效率十分重要,衡量查找效率的主要性能指标就是平均查找长度(ASL)。本章介绍了三种类型的查找表。

(1)基于线性的查找表

主要分顺序查找、折半查找以及索引查找。

顺序查找对查找表没有特别要求,但是查找效率不高,几乎是表长的一半。现在有很多技术可以改进这种查找方法

折半查找要求查找表必须采用顺序结构而且按照关键字有序排列。整个折半查找过程借助于折半判定树加以描述,判定树中每一个结点对应表中一个记录的位置序号。它的查找速度快， 平均性能较好,但是插人和删除操作较困难。它在等概率的情况下,查找成功的平均查找长度与 折半判定树的深度相关:

ASL≈log₂(n+1)-1

索引查找是一种性能介于顺序查找和折半查找之间的查找办法,平均查找长度等于两个阶 段各自查找的长度之和。它有较快的查找速度,又可以动态更新变化。在插入或删除一个结点时,找到该结点所属的块,然后在块内进行插人和删除运算。由于块内结点的存放是任意的,因此插人或删除比较容易,不需要移动大量的结点。插人可直接在块尾进行,如果待删的记录不是块中最后一个记录,可以将本块内最后一个记录移入被删记录的位置。

(2)基于树形的查找表

针对大型数据库的数据查找工作,要求支持高效的动态查找能力。由于数据库中包含了大量的记录,前面讲到的基于线性表的查找本身会因为记录太大而无法存储到主存中。另外,对于 记录的插人和删除操作来说,都需要移动大量的元素。事实上,对于大型数据库的组织结构一般都采用树形结构的查找表:

①二叉排序树。基于二叉排序树的查找过程与折半查找过程类似,在二叉排序树中查找一 个记录的比较次数不超过树的深度,平均查找长度仍然是O(log₂n)。但是它的插入、删除操作 无须移动大量结点,经常需要变化的动态表宜采用二叉排序树结构。

②平衡二叉树。由于二叉排序树在建立时受输人序列影响,有可能退化为最差的查找情 况,这也可能是由于在树中插人或删除结点而造成的。平衡一又树不受输人序列或插入结点等 的影响,始终保持平衡状态,从而达到很好的检索效率。它的查找、插入和删除效率都是O(log₂n)，而且都是从根到叶子结点单路径进行的局部运算

③伸展树。伸展树的吸引力在于查找和更新方法的简洁性。它是一种自调整形式的二叉查找树,每次查找、插入或删除之后,通过仔细设计旋转序列,将被访问的结占向上移动到根。这 钟简单“移动到顶”的启发式策略有利于所进行的各种操作。它会沿着从某个结占到树根之间 的路径,通过一系列旋转把这个结点搬移到树根去。事实上,伸展树只是改进了一叉排序树性能的一组规则,可以在O(log₂n)内完成插入、查找和删除等操作,控制了查找、插人和删除等操作 对排序树的修改,从而避免二叉排序树在最差情况下的线性时间代价。

④红黑树。红黑树是一种自平衡二叉查找树,它的操作有着良好的最坏情况运行时间,并 且在实践中是高效的,它可以在0(log,n)时间进行查找、插人和删除等操作。其中每个结点被 “染成”红色或黑色。它利用对树中结点红黑着色的要求达到局部平衡。

(3)散列

散列方法是一种计算式查找方法,其核心就是由哈希函数决定关键字值与散列地址之间的 对应关系,通过这种关系来组织存储并进行查找等操作。该方法面临的主要问题是哈希函数的 选取以及处理冲突的方法。而影响整个哈希查找的主要因素就是哈希函数、处理冲突的方法以 及哈希表的装填因子。如果假设哈希函数是均匀的,并且按处理冲突的方法分别考虑,则影响平均查找长度的因素就只有装填因子了。

总之,查找技术很多,具体采用哪一种应根据实际的应用环境和需求进行选取。

习题8

1 单项选择题 1~5 8 9

(1)在关键字随机分布的情况下,用二叉排序树的方法进行查找,其查找长度与B数量级相当

A.顺序查找

B.折半查找

C.分块查找

D.哈希香找

(2)分别以下列序列构造二叉排序树,与用其他三个序列所构造的结果不同的是C

A.(100,80,90,60,120,110,130)

B.(100,120,110,130,80.60,90)

C.(100,60,80,90,120,110,130)

D.(100,80,60,90,120,130,110)

(3)顺序查找适合于存储结构为D的线性表。

A.散列存储

B.压缩存储

C.索引存储

D.顺序或链式存储

(4)如果要求用线性表既能较快地查找,又能适应动态变化的要求,则可采用A查找方法

A.分块查找

B.顺序查找

C.折半查找

D.基于属性

(5)已知一个有如下10个记录的表，其关键字序列为（2，15，19，25，30,34,44，55

，58,80）用折半查找关键字为55的记录,比较次数是B

A.1次

B.2次

C.3次

D.4次

(8)哈希表的地址区间为0~17,哈希函数为H(K)=K MOD 17。采用线性探测法处理冲突,并将关键字序列26,25,72,38,8,18,59依次存储到哈希表中,则元素59存放在哈希表中的地址为D

A.8

B.9

C.10

D.11

(9)设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79}用链地址法构造

散列表。散列函数为H(key)=key MOD 13,散列地址为1的链中有D个记录。

A.1

B.2

C.3

D.4

3 完成题 1~4

(1)已知一个有7个数据元素的有序顺序表,其关键字为13,18,25,37,69,87,

38，99},请给出用折半查找方法查找关键字值18的查找过程。

(2)已知关键字序列为{53,17,19,61,98,75,79,63,46,40,请给出利用这些关键字构造的二叉排序树。

(3)根据如图8-62所示的二叉排序树,给出刚联老键字88后的二叉排序树。

(4)已知一组关键字序列为{5，88,12,56,79,28，33，43，93，17}，哈希表长为13,哈希函数为H(key)=key%13,请用线性探测再散列、二次线性探测再散列以及链地址法解决冲突构造这组关键字的哈希表,并计算查找成功时的平均查找长度。

4 算法设计题

（6）编写算法,输出给定二叉排序树中数据域值最大的结点。

略

最后

2023-11-7 16:19:19

我们都有光明的未来

不必感谢我，也不必记得我

祝大家考研上岸

祝大家工作顺利

祝大家得偿所愿

祝大家如愿以偿

点赞收藏关注哦