哈希查找-数据结构

哈希查找

#define _CRT_SECURE_NO_WARNINGS
#include "iostream"
#include "stdlib.h"
#include "windows.h"
#include "iomanip"
using namespace std;
#define OK 1
#define ERROR 0
#define M 18
#define P 16
typedef int KeyType;

/*开放地址法处理冲突的哈希映射
 H(key)=key%P   P为一个质因子数
 Hi=（H（key）+di）%m    i=1，2，...,k(k<=m),m为表长
*/

typedef struct {
	KeyType key;
}HashTable[M];

int Hash(KeyType key);//开放地址法处理冲突的映射
void CreateHashTable(HashTable ht,int n);//建立哈希表,keys为元素集合，n为元素个数
int SearchHash(HashTable ht, KeyType key); //哈希查找
double ASL(HashTable ht, int n);//求平均查找长度，n为元素个数
void DispHashTable(HashTable ht);
void InitHashTable(HashTable ht);
int NumSearch(HashTable ht,KeyType key);

int main() {
	HashTable ht;
	int n=11;
	CreateHashTable(ht, n);
	DispHashTable(ht);
	cout << "请输入即将查找的值:" << endl;
	int x;
	cin >> x;
	cout << "查找" << x << "的地址为:" << SearchHash(ht, x) << endl << endl;
	cout <<"该表的平均查找长度为:"<<setprecision(3)<< ASL(ht, n) << endl;
	system("pause");
	return 0;
}

//定义哈希函数
int Hash(KeyType key)
{
	return key % P;
}

//用线性探测法处理冲突建立n个元素的哈希表
void CreateHashTable(HashTable ht, int n)
{
	int i, j;
	KeyType x;
	//从键盘输入n个数据元素放入哈希表中
	InitHashTable(ht);
	cout << "请输入" << n << "个数据元素放入哈希表中:" << endl;
	for (i = 0; i < n; i++) {
		cin >> x;
		j = Hash(x);//计算哈希地址
		//当出现冲突时，按线性探测法处理
		while (ht[j].key != 0) {
			j = (j + 1) % M;
		}
		ht[j].key = x;//将x放入表中
	}
}

int SearchHash(HashTable ht, KeyType key)
{
	int ha;
	ha = Hash(key);//计算哈希地址
	while (ht[ha].key != 0) {
		if (ht[ha].key == key)
			return ha;
		else {
			ha = (ha + 1) % M;//按线性探测法处理冲突计算下一个
		}
	}
	return -1;
}

double ASL(HashTable ht, int n)
{
	int i, s = n = 0;
	for (i = 0; i < M; i++) {
		if (ht[i].key != 0) {
			n++;
			s += NumSearch(ht, ht[i].key);
		}
	}
	return (double)s / n;
}

void DispHashTable(HashTable ht)
{
	int i;
	for (i = 0; i < M; i++)
		cout << ht[i].key << " ";
	cout << endl;
}

void InitHashTable(HashTable ht)
{
	for (int i = 0; i < M; i++) {
		ht[i].key = 0;
	}
}

int NumSearch(HashTable ht, KeyType key)
{
	int s = 0, i;
	i = Hash(key);
	while (ht[i].key != 0 && ht[i].key != key) {
		i = (i + 1) % M;
		s++;
	}
	if (ht[i].key == 0)
		return 0;
	else
		return s + 1;
}