哈希表c++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<iostream>
using namespace std;
const int maxnum = 15;
int HT[maxnum];		//哈希地址表
int HC[maxnum];		//计算单个地址的比较次数
int m=maxnum;				//线性探测总的步长 = 哈希地址表长，因为要遍历一个周期查看是否有空余位置
//哈希函数
int H(int key)
{
	return key % 13;
}
void init() 
{
	for (int i = 0; i < maxnum; i++)
	{
		HT[i] = -1;
	}
	for (int i = 0; i < maxnum; i++)
	{
		HC[i] = 0;
	}
}
//冲突探测
//（线性探测）
int LineDetect(int H0,int key,int &cnt)	//根据原散列地址H0来计算新的Hi不冲突地址，用cnt计算总比较次数
{
	int Hi;
	for (int i = 1; i < m; i++)			//自身不需要再比较了
	{
		cnt++;
		Hi = (H0 + i) % m;
		if (HT[Hi] == -1)				//使用-1代表地址为存放任何元素
		{
			return Hi;
		}
		else if (HT[Hi] == key)			//查找
		{
			return Hi;
		}
	}
	return -1;							//为未查找到元素而且所有地址都已经放满
}

//(二次探测）
int Seconddetect(int H0, int key, int &cnt)
{
	int Hi;
	for (int i = 0; i < m/2; i++)
	{
		int i1 = i * i;
		int i2 = -i1;
		cnt++;
		Hi = (H0 + i1) % m;
		if (HT[Hi] == -1)
		{
			return Hi;
		}
		else if (HT[Hi] == key)
		{
			return Hi;
		}
		cnt++;
		Hi = (H0 + i2) % m;
		if (Hi < 0)
		{
			Hi += m;
		}
		if (HT[Hi] == -1)
		{
			return Hi;
		}
		else if (HT[Hi] == key)
		{
			return Hi;
		}
	}
	return	-1;
}
bool InsertHash(int key)
{
	int H0 = H(key);
	int Hi = -1, cnt = 1;
	if (HT[H0] == -1)
	{
		HT[H0] = key;
		HC[H0] = 1;
		return 1;
	}
	else 
	{
		Hi = LineDetect(H0, key, cnt);
		if (Hi != -1 && HT[Hi] == -1)
		{
			HC[Hi] = cnt;
			HT[Hi] = key;
			return 1;
		}
	}
	return 0;
}
int SearchHash(int key)
{
	int H0 = H(key),cnt;
	cnt = HC[H0];
	if (HT[H0] == key)
	{
		cout << "查找成功，比较次数为:" << cnt << endl;
		return H0;
	}
	else if(HT[H0]==-1)
	{
		cout << "元素不存在!" << endl;	
		return -1;
	}
	else //元素存在不等于key，需要探测
	{
		int Hi = LineDetect(H0, key, cnt);
		if (HT[Hi] == key)
		{
			cout << "查找成功，比较次数为:" << cnt << endl;
			return Hi;
		}
		else 
		{
			cout <<"元素不存在!"<<endl;
			return -1;
		}
	}
}

int arr[12] = { 14,36,42,38,40,15,19,12,51,65,34,25};
int main() 
{
	init();
	for (int i = 0; i < 12; i++)
	{
		InsertHash(arr[i]);
	}
	int divi = SearchHash(25);
	cout << divi << endl;
	return 0;
}