数据结构 实验5——散列表的构造和查找

一、实验名称：散列表的构造和查找

二、实验学时：6学时

三、实验目的

1.理解散列表的存储结构；

2.掌握常用散列函数构造方法和处理冲突方法；

3.在散列表上实现查找的算法。

四、实验内容(步骤)

为小于n个关键字设计一个散列表，使得查找成功时平均查找长度<2.0，要求完成相应的散列表建立和查找。假设关键字为整型数据，散列函数用除留余数法，采用开放定址法的线性探测法处理冲突。

1.从键盘输入关键字个数n及关键字数据；

2.根据输入的关键字个数及平均查找长度要求，设计散列函数和计算表长；

3.构造散列表；

4.在散列表中进行查找。

【实验源代码】

#include
#include
#include

#define INFINITY INT_MAX

using namespace std;

typedef int KeyType;

// 顺序表存储结构
typedef struct 
{
	KeyType key; // 关键字（数据项）
	int time; // 探测次数
}ElemType;

typedef struct
{
	ElemType *elem; // 数据元素存储空间基址
	int length; // 查找表的长度 
}HashTable;

void inputData(KeyType KeyData[],int n)
{
	printf("请输入%d个关键字：",n);
	for(int i=0;i2;i--)
	{
		for(j=2;j*j<=i;j++)
		{
			if(i%j==0)
				break;
		}
		if(j*j>i)
		{
			p=i;
			break; // 求得小于m的最大质数 
		}
	}
}

int hashFunc(KeyType key,int p)
{
	int addr=-1;
	addr=key%p;
	return addr;	
}

int linearProbing(HashTable HT,int addr,int m,int &time)
{
	int i,addri;
	for(i=1;i 
【实验运行结果】