一、实验目的
1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。
2、掌握线性表中顺序查找和折半查找的方法。
3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。
二、实验预习
说明以下概念
1、顺序查找：
顺序查找又叫线性查找，是最基本的查找方法。
查找思路：从查找表的第一个（或最后一个）数据元素开始，逐个将数据元素的关键字和给定的关键字进行比较，如果存在某个数据元素的关键字和给定关键字相等，则查找成功，返回该数据元素相关信息；如果直到最后一个（或第一个）数据元素，还未找到和给定关键字相等的数据元素，则查找失败，表中没有所查的数据。
2、折半查找：
折半查找也叫二分查找、对分查找。折半查找的前提是查找表中所有数据元素的关键字按照递增或递减有序排列。
查找思路：假设查找表中数据元素关键字按照递增有序排列，设置一个指针 low 指向查找表中关键字最小的位置，设置一个指针 high 指向查找表中关键字最大的位置，再设置一个指针 mid 指向查找表中间位置。
① mid=(low+high)/2。
② 将给定的关键字 k 与 mid 位置的关键字 m 比较：
若k=m，查找成功，返回相关数据元素信息。
若k<m，则high=mid-1，重复以上操作（从①开始）
若k>m，则low=mid+1，重复以上操作（从①开始）
③ 如果直至 low>high 还未查找成功，则查找失败。
3、哈希函数：
哈希函数又叫散列函数、杂凑函数，是散列方法中使用的转换函数。
在使用散列方法存储查找表中的数据元素时，选取一个函数，依照该函数和关键字计算数据元素的存储位置，并按此位置存放，这个函数就是哈希函数。
同样的，在查找时，由同一个哈希函数对给定的关键字 k 进行计算得到地址，再将 k 与该地址中数据元素的关键字进行比较，确认是否查找成功。
哈希函数就是记录的存储位置与关键字之间的对应关系：Loc(element.i)=Hash(key.i)
4、冲突及处理：
冲突就是在散列表中使用哈希函数，根据关键字计算存储地址时，不同的关键码映射到了同一个散列地址，这些具有相同函数值的多个关键字叫做同义词。
处理方法：开放地址法、链地址法、再散列法、建立一个公共溢出区……
（1）开放地址法（开地址法）
基本思想：发生冲突时就寻找下一个空的散列地址(即地址加上某个增量)，若找到空地址，则将数据存入。
例如：除留余数法 Hi=( Hash(key)+di )mod m ，di为增量序列（m为查找表中元素个数）
开放地址法寻找空地址常用方法：
① 线性探测法：di为1，2，3，……，m-1 的线性序列。
② 二次探测法：di为1*1，- 1*1，2*2，- 2*2，……，q*q 的二次序列。
③伪随机探测法：di为伪随机数序列。
（2）链地址法（拉链法）
基本思想：相同散列地址（同义词）的数据元素链成一个单链表，m个散列地址就设置m个单链表，然后用一个数组存储m个单链表的表头指针，形成一个动态的结构。
根据数据元素的关键字计算散列函数值（即地址），若该地址对应的链表为空，则该地址直接存储该数据元素结点；若该地址对应的链表非空，则将该元素插入此链表（前插法/后插法）。
三、实验内容和要求
1. 静态查找表技术
依据顺序查找算法和折半查找算法的特点，对下面的两个查找表选择一个合适的算法，设计出完整的C源程序，并完成问题：
查找表1：{ 8，15，19，26，33，41，47，52，64，90 }，查找key = 41
查找表2：{12，76，29，15，62，35，33，89，48，20 }，查找key = 35
查找 key=41 的算法： 折半查找法 比较次数： 3
查找 key=35 的算法： 顺序查找法 比较次数： 5
选择依据：可以看出查找表1中的数据是按递增有序排列的，所以可以选择折半查找法；而查找表2中的数据是无序的，看不出什么规律，所以选择顺序查找法。
- 顺序查找算法实现代码
#include <stdio.h>
#define MAX_NUM 50 //查找表中数据元素最大数量
typedef struct{
int key; //关键字域
}ElemType; //定义数据元素类型
typedef struct{
ElemType elem[MAX_NUM]; //从下标为1的分量开始存储(0位置设置监视哨)
int length; //表长
}SST; //Sequence Search Table-顺序查找表
/*顺序查找算法,ST为目标查找表,key为给定的关键字*/
int Seq_Search(SST ST,int key)
{
ST.elem[0].key = key; //设置监视哨
int i;
for(i=ST.length;ST.elem[i].key != key;i--)
{
; //for循环内为空语句
}
return i; //返回0:查找失败;返回值>0:查找成功
}
int main()
{
int i,n,key;
printf("请输入查找表中记录个数n：\n");
scanf("%d",&n);
SST ST;
ST.length = n;
printf("\n请输入查找表中数据记录：\n");
for(i=1;i<ST.length+1;i++)
scanf("%d",&(ST.elem[i].key));
printf("\n请输入查找的关键字key：\n");
scanf("%d",&key);
/*顺序查找*/
int m = Seq_Search(ST,key);
if( m )
printf("\n查找成功！该记录的位置为：%d",m);
else
printf("\n查找失败！查找表中没有该记录");
return 0;
}- 运行结果：
- 折半查找算法实现代码
#include <stdio.h>
#define MAX_NUM 50 //查找表中数据元素最大数量
typedef struct{
int key; //关键字域
}ElemType; //定义数据元素类型
typedef struct{
ElemType elem[MAX_NUM]; //从下标为1的分量开始存储(0位置设置监视哨)
int length; //表长
}SST; //Sequence Search Table-顺序查找表
/*折半查找算法,ST为目标查找表,key为给定的关键字*/
int Bin_Search(SST ST,int key)
{
int low = 1;
int high = ST.length;
int mid;
while(low <= high)
{
mid = (low+high)/2;
if(key == ST.elem[mid].key)
return mid;
if(key < ST.elem[mid].key)
high = mid - 1;
if(key > ST.elem[mid].key)
low = mid + 1;
}
return 0; //返回0:查找失败;返回值>0:查找成功
}
/*折半查找的递归算法*/
//ST为目标查找表,key为给定的关键字,low为查找区间的开始下标,high为查找区间的结束下标,*/
int Bin_Search_R(SST ST,int key,int low,int high)
{
if(low > high)
return 0; //查找失败
int mid;
mid = (low+high)/2;
if(key == ST.elem[mid].key)
return mid;
if(key < ST.elem[mid].key)
Bin_Search_R(ST,key,low,high-1);
if(key > ST.elem[mid].key)
Bin_Search_R(ST,key,low+1,high);
}
int main()
{
int i,n,key;
printf("请输入查找表中记录个数n：\n");
scanf("%d",&n);
SST ST;
ST.length = n;
printf("\n请输入查找表中数据记录：\n");
for(i=1;i<ST.length+1;i++)
scanf("%d",&(ST.elem[i].key));
printf("\n请输入查找的关键字key：\n");
scanf("%d",&key);
/*折半查找*/
int m = Bin_Search(ST,key);
if( m )
printf("\n折半查找：\n查找成功！该记录的位置为：%d",m);
else
printf("\n折半查找：\n查找失败！查找表中没有该记录");
/*折半查找-递归版*/
int k = Bin_Search_R(ST,key,1,ST.length);
if( k )
printf("\n折半查找(递归算法)：\n查找成功！该记录的位置为：%d",k);
else
printf("\n折半查找(递归算法)：\n查找失败！查找表中没有该记录");
return 0;
}- 运行结果：
2. 哈希表的构造与查找。
【注】
以下代码中SearchHash函数中while循环的条件，和老师给的代码略有不同，包括网上有些代码也是有一点问题的，构造哈希表时可能会出错。
/*采用开放地址法构造哈希表*/
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 25 //哈希表中元素最大数目
#define P 13 //除留余数法的除数
#define OK 1
#define ERROR 0
#define DUPLICATE -1
#define TRUE 1
#define FALSE 0
typedef struct{
int key; /*关键字值*/
int flag; /*是否存放元素*/
}ElemType; /*哈希表元素结构*/
typedef struct{
ElemType data[MAXSIZE];
int count; /*元素个数*/
int sizeindex; /*当前哈希表容量*/
}HashTable; /*哈希表*/
int d1[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}; /*线性探测序列*/
int d2[15]={0,1,-1,2*2,-2*2,3*3,-3*3,4*4,-4*4,5*5,-5*5,6*6,-6*6,7*7,-7*7}; /*二次探测序列*/
void dataset(int ds[],int *len); /*输入查找表*/
int InsertHash(HashTable *H,int e,int d[]); /*计算哈希地址，插入哈希表*/
int CreateHash(HashTable *H,int ds[],int len,int d[]); /*构造哈希表*/
int SearchHash(HashTable *H, int e,int d[]); /*在哈希表中查找*/
void menu(); /*演示菜单*/
/*输入查找表*/
void dataset(int ds[],int *len){ //查找表关键字通过ds数组返回,查找表长度通过指针len返回
int n,m;
n = 0;
printf("\n查找表输入(输入一个非整数结束)：");
//scanf()返回值表示正确输入参数的个数
while(scanf("%d",&m) == 1) /*以输入一个非整数作为结束*/
{
ds[n]=m; //ds数组存放查找表关键字
n++; //n记录个数
}
*len=n;
}
/*计算哈希地址，插入哈希表*/
int InsertHash(HashTable *H,int e,int d[]){ //H为目标哈希表,e为插入的关键字,d数组指向线性或二次探测序列
int k,i=1;
k = e%P; //除留余数法计算地址
while(H->data[k].flag==TRUE || k<0) //发生冲突or计算得到的位置<0
{
k = (e%P+d[i])%MAXSIZE;
i++;
if(i>=15)
return ERROR; //探测序列所有值都尝试后仍未找到合适地址,则插入失败,返回0
}
//成功找到空地址
H->data[k].key = e;
H->data[k].flag = TRUE;
H->count++; //插入成功,哈希表长度+1
return OK; //返回1
}
/*构造哈希表*/
int CreateHash(HashTable *H,int ds[],int len,int d[]){ //ds数组存放查找表的关键字,len为记录个数,d数组指向线性或二次探测序列
int i;
for(i=0;i<len;i++)
{
if(SearchHash(H,ds[i],d) != -1)
return DUPLICATE; //查找成功,说哈希表中已存在该关键字,故创建失败,返回-1
//查找失败,说明不存在重复关键字,可以插入
InsertHash(H,ds[i],d);
if(H->count >= MAXSIZE)
return ERROR; //记录个数超过MAXSIZE,返回0
}
return OK; //创建成功,返回1
}
/*初始化哈希表*/
void InitHash(HashTable *H){
int i;
for(i=0;i<MAXSIZE;i++)
{
H->data[i].key = 0;
H->data[i].flag = FALSE;
}
}
/*在哈希表中查找*/
int SearchHash(HashTable *H,int e,int d[]){ //e为查找的关键字,d数组指向线性或二次探测序列(查找和插入应使用同一个探测序列)
int k,i=1;
k = e%P;
while(H->data[k].key!=e || k<0)
{
k = (e%P+d[i])%MAXSIZE;
i++;
if(i>=15)
return -1; //探测序列中所有值都尝试过仍未找到关键字e,说明哈希表中不存在该关键字,查找失败,返回-1
}
return k; //查找成功,返回该关键字在哈希表中的位置
}
/*演示菜单*/
void menu(){
int choice;
int *p;
HashTable h;
h.count=0;
h.sizeindex = MAXSIZE;
int a[MAXSIZE]={0};
int i,n,e;
dataset(a,&n); /*建立查找表*/
getchar(); //消耗回车键
printf("\n");
do{
printf("\n----哈希查找演示----\n");
printf("\n1.线性探测构造哈希表\n");
printf("\n2.二分探测构造哈希表\n");
printf("\n3.退出\n");
printf("\n输入选择：");
scanf("%d",&choice);
if(choice == 1)
p = d1; //p指向线性探测序列
else if(choice == 2)
p = d2; //p指向二次探测序列
else
return;
InitHash(&h); /*初始化哈希表*/
i = CreateHash(&h,a,n,p); /*构造哈希表*/
if( !i )
printf("\n哈希表构造失败！\n");
else if(i == DUPLICATE)
printf("\n哈希表具有重复关键字！\n");
else
{
printf("\n哈希表：\n");
for(i=0;i<h.sizeindex;i++)
printf("%3d",h.data[i].key);
printf("\n\n哈希查找\n输入要查找的key值：");
getchar(); //消耗回车键
scanf("%d",&e);
if((i=SearchHash(&h,e,p)) == -1)
printf("\n%d未找到\n",e);
else
printf("\n%d在哈希表中下标为%d\n",e,i);
}
getchar();
}while(1);
}
int main()
{
menu();
return 0;
}
输入查找表为：19 14 23 1 68 20 84 27 55 11 10 79（注意以输入一个非整数结束）。
- 运行结果
1）线性探测散列
哈希表形态：
84在哈希表中的位置： 8
2）二次探测散列
哈希表形态：
84在哈希表中的位置： 5
我开始是直接运行老师给的代码，输入选择2，通过二分探测法构造哈希表，却得到以下结果：
哈希表具有重复关键字！
但是通过线性探测法构造却是正常的，也很容易看出输入的数据是没有重复的。那为什么会显示有重复的关键字呢？
先来到打印 “哈希表具有重复关键字！”语句的代码：
i = CreateHash(&h,a,n,p); /*构造哈希表*/
……
else if(i == DUPLICATE) //DUPLICATE=-1
printf("\n哈希表具有重复关键字！\n");说明CreateHash函数返回了-1，而CreateHash函数返回-1则是因为SearchHash函数返回了一个不等于-1的数。
所以我在原来的SearchHash函数里添加了一行代码，如果查找成功、就输出重复关键字的信息：
int SearchHash(HashTable *H,int e,int d[]){
……
while(H->data[k].key!=e)
{
……
}
printf(“重复关键字：%d，在哈希表中下标为：%d”,H->data[k].key,k); //添加代码
return k; //查找成功,返回该关键字在哈希表中的位置
}
运行后得到以下结果：
容易看出 68 在查找表中是没有重复的，但是却显示重复，而且下标还是个负数，哈希表的下标范围应该是 0 ~ MAXSIZE-1，所以负数下标指示的关键字不属于哈希表。
那为什么会查找到哈希表以外的数据呢？因为在插入关键字和查找关键字时哈希地址的计算没有统一。
InsertHash函数中，对地址 k 是有限制的：当计算出的地址 k<0 时，需要重新计算地址。
k=e%P;
while(H->data[k].flag==TRUE || k<0){
k=(e%P+d[i])%MAXSIZE;i++;
if(i>=15)
return ERROR;
}
原SearchHash函数中，却没有对地址 k 进行限制，没有判断地址 k 的值是否超过哈希表范围。而二次探测序列中存在负数，且增量跨度较大，地址很可能会超出范围。
k = e%P;
while(H->data[k].key!=e){
k=(e%P+d[i])%MAXSIZE;i++;
if(i>=15)
return -1;
}
- 解决方法：
在插入关键字和查找关键字计算地址时时，不仅使用的哈希函数要相同，其它限制条件也要相同。
所以这里直接在查找时增加一个和插入操作相同的条件即可，即地址k<0时，重新计算地址。
int SearchHash(HashTable *H,int e,int d[]){
……
k = e%P;
while(H->data[k].key!=e || k<0)
{
k = (e%P+d[i])%MAXSIZE;
i++;
if(i>=15)
return -1;
}
return k; //查找成功,返回该关键字在哈希表中的位置
}
文章出处登录后可见！
