哈希查找-資料結構

哈希查找

#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;
}