C++实现哈希表创建、查找、显示、计算ALS（详细）（数据结构）

问题引入

        针对某个数值序列，设计一个哈希表，完成相应的建表和查表顺序。哈希函数用除留余数法构造，用线性探测再散列的方法处理哈希地址冲突。

        针对给定的数列：{23,5,17,12,26,31,13,4,6}，完成哈希表的构造。具体哈希函数采用除留余数法，并用线性探测再散列的方法处理哈希地址冲突。具体为：表长为13，哈希函数为：H(key)= key MOD 13，要求：

        1）能根据给定值进行查询，判断该值在哈希表中是否存在？如果存在，输出相应的地址；否则，输出不存在。

        2）能输出哈希表中的全部内容，相应地址存储的元素为空，则不输出。

        3）能输出该表的平均查找长度ASL（假定每个元素被查找的概率都是相等的）。

代码实现

#include<iostream>
#include<malloc.h>
#define HashLength 13 //定义哈希表表长 
#define NULLKEY 0  //空哈希表元素值为0 
using namespace std; 


//定义哈希表属性、结构 
typedef struct{
	int key;            //元素的值
	int compareTimes;   //查找到该元素需要比较的次数
	int flag;           //用来标识该位置是否已经存有别的数据
}Elem;
typedef struct{
	Elem *base; //表示生成的空间的首地址 
	int count; //元素个数 
	int length; //表长 
}HashList;

//除留余数法 
int Hash(int data){
	return data%HashLength;
} 

//初始化哈希表 
void InitHash(HashList &H) {
	int i;
	H.base= (Elem *)malloc(HashLength*sizeof(Elem)); //分配存储空间 
	H.length=HashLength; //表长 
	for (i=0;i<HashLength; i++) {
		H.base[i].key=NULLKEY; //赋初始值，构建空哈希表 
	}
}

//哈希表的插入函数，可用于构造哈希表
void Insert(HashList &H,int data) {
	int hashAddress=Hash(data); //求哈希地址
	//发生冲突
	while(H.base[hashAddress].key!=NULLKEY) {
		//将已经存有别的数据的位置进行标记
		H.base[hashAddress].flag=-1; 
		//利用开放定址法解决冲突
		hashAddress=(++hashAddress)%HashLength;
	}
	H.base[hashAddress].key=data; //存入数据 
}

//建立哈希表
void CreateHashList(HashList &H){
	int i,key;
	cout<<"哈希表长度为：13"<<endl;
	cout<<"输入哈希表元素个数:";
	cin>>H.count;
	for(i=0;i<H.count;i++){
		cout<<"输入元素:";
		cin>>key;
		Insert(H,key);
	}
}

//显示哈希表中内容 
void PrintHashList(HashList H){
	cout<<"根据实验要求，哈希表中的全部非空元素为："<<endl;
	int i;
	for(i=0;i<H.length;i++){  //循环输出哈希表中的非空元素 
		if(H.base[i].key!=0){ //判断对应下标存储的元素是否非空 
			cout<<H.base[i].key<<' ';
		}
	}
	cout<<endl; //换行 
}


//查找元素在哈希表中的位置
int SearchHashList(HashList H,int key){
	int hashAddress=Hash(key); //求元素在哈希表中的地址
	int number=1; //查找1次就找到 
	while(H.base[hashAddress].key!=key){
		number++; //查找次数累加 
		hashAddress=(++hashAddress)%HashLength; //下一地址 
		if(H.base[hashAddress].key==NULLKEY || hashAddress==Hash(key)){
			return -1; //查找失败，返回-1 
		}
	}
	return hashAddress; //查找成功，返回元素位置 
}

//获取整个哈希表中每个非空元素的查找次数 
int SearchNumber(HashList H,int key){
	int hashAddress=Hash(key); //求元素在哈希表中的地址
	int number=1; //查找1次就找到 
	while(H.base[hashAddress].key!=key){
		number++; //查找次数累加 
		hashAddress=(++hashAddress)%HashLength; //下一地址 
		if(H.base[hashAddress].key==NULLKEY || hashAddress==Hash(key)){
			return -1; //查找失败，返回-1
		}
	}
	//输出对应元素查找多少次，便于查看 
	cout<<H.base[hashAddress].key<<"查找了"<<number<<"次"<<endl; 
	return number; //返回查找次数 
}

//计算平均查找长度ASL
void CalcuASL(HashList H){
	int i,once,sum=0; //辅助变量 
	double als; //平均查找长度 
	//循环查找哈希表中的非空元素
	for(i=0;i<H.length;i++){
		if(H.base[i].key!=0){
			once=SearchNumber(H,H.base[i].key); //接收元素的查找次数 
			if(once!=-1){
				sum=sum+once;  //累加哈希表中各元素查找次数 
			}
			
		}
	}
	als=(double)sum/H.count; //计算ALS 
	cout<<"哈希表的平均查找长度ALS为："<<als<<endl;
}

//显示界面信息 
void Information(){
	
	cout<<endl<<"目录："<<endl<<endl
	<<"（1）例如：{23,5,17,12,26,31,13,4,6}，"<<
	"哈希表表长为13。"<<endl<<endl<<"（2）只输出哈希"<<
	"表中的全部内容，存储的元素为空时不输出，"<<endl<<"     "<<"因"<<
	"此显示的哈希表内容是不包含元素为空的下标值对应的全部元素，显示"
	<<endl<<"     "<<"的数据位置并不是对应不上，而是跳过了元素为空"<<
	"的下标值，实际上全部输出时位置是一一对应的。"<<endl;
	
	cout<<"============================================"<<endl;
	cout<<"   1.创建哈希表"<<endl;
	cout<<"   2.显示创建的哈希表内容"<<endl;
	cout<<"   3.查找元素在哈希表中的位置（下标位置+1）"<<endl;
	cout<<"   4.计算哈希表的平均查找长度ALS"<<endl;
	cout<<"   5.退出"<<endl;
	cout<<"============================================"<<endl;
	
}


//主函数：
int main(){
	int n,key,choose;
	HashList H;
	InitHash(H);
	
	Information();
	cout<<"请根据选项选择您的操作：\n";
	cin>>choose;
	while(choose!=5){
		switch(choose){
			case 1:{
			CreateHashList(H);
			break;
			}
			case 2:{
				PrintHashList(H);
				break;
			}
			case 3:{
				cout<<"输入要查找的元素值:";
				cin>>key;
				n=SearchHashList(H,key);
				if(n==-1){
					cout<<"查询不到";
				}else{
					cout<<key<<"在哈希表中的下标位置是："<<n+1;
					cout<<endl;
				}
				break;
			}
			case 4:{
				CalcuASL(H);
				break;
			}
			default:{
				cout<<"选择不正确，请重新输入！\n";
				break;
			}
		}
		cout<<"\n请根据选项选择您的操作：";
		cin>>choose;
	}
}

运行结果