【基本要求】
（1）设每个记录有下列数据项：电话号码、用户名、地址；
（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；
（3）采用一定的方法解决冲突；
（4）查找并显示给定电话号码的记录；
（5）查找并显示给定用户名的记录。
【选做内容】
（1）系统功能的完善；
（2）设计不同的散列函数，比较冲突率；
（3）在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。
用的C++开发，基本实现了3种哈希函数+3种解决冲突的方法。因为要求同时有姓名散列与按号码散列，所以用了
flag标记每次的散列类型 ，针对不同的要求对散列函数做了个别优化。
哈希表类的结构如下
1 class HashTable{
2 public:
3 HashTable(int size = MAXSIZE-1);
4 ~HashTable(){ delete[]E; delete[]tag; delete[]E2; delete[]tag2; }
5 int hash1(string name, int flag);//哈希函数1 除数求余法
6 int hash2(string tel);//哈希函数2 折叠法
7 int hash3(string tel);//哈希函数3 数字分析法
8 int solve1(int hashVal, int flag);//线性探测法解决冲突
9 int solve2(int hashVal, int flag);//二次探测法解决冲突
10 Node* solve3(int hashVal, int flag);//拉链法解决冲突
11 User input();//往电话薄中添加用户
12 void creat(int flag); //创建散列表
13 void show(int flag); //列出电话薄所有元素
14 void search(int flag,string at); //搜索指定用户
15 void searchByNode(int flag, string at); //拉链法搜索指定用户
16 void insert(int flag, User newUser); //插入
17 void del(int flag, string by);//删除
18 void save(int flag);//将电话薄保存至本地文件
19 int length; //要创建的电话本长度
20 Node** ht;
21 private:
22 User* E; //用户数组 按姓名散列
23 User* E2; //用户数组2 按电话号码散列
24 int* tag; //标记散列表1每个桶的存储状态 0为空 1为实
25 int* tag2;//标记散列表2每个桶的存储状态
26 int flag; //1表示是按姓名 2表示按电话号码 新建的哈希表
27 int maxSize; //哈希表最大长度
28 int f;//比例因子 主要用于折叠法
29 };
View Code
User类的结构
class User{
public:
string name;
string tel;
string address;
bool operator==(const User&target)
{
if (this->name == target.name&&this->address == target.address&&this->tel == target.tel)
return true;
else
return false;
}
};
哈希函数1
int HashTable::hash1(string name,int flag) //除留求余法
{
int hashValue; long a = 0;
switch (flag)
{
case 1:
for (int i = 0; i < name.length(); i++)
a += int(name[i]);
hashValue = a%maxSize;
break;
case 2:
int temp = atof(name.c_str());
hashValue = temp%maxSize;
break;
}
return hashValue;
};
哈希函数2
int HashTable::hash2(string tel) //折叠法--移位法
{
int hashValue;
int temp; //移位法求和
temp = atof(tel.substr(0, 3).c_str()) + atof(tel.substr(3, 3).c_str())
+ atof(tel.substr(6, 3).c_str()) + atof(tel.substr(9, 2).c_str());
//取计算之后的数的最后三位
if (temp >= 999)
{
char p[10];
sprintf(p, "%d", temp);
string lastThree = p;
lastThree = lastThree.substr(lastThree.length() - 3, 3);
hashValue = atof(lastThree.c_str());
return hashValue;
}
hashValue = temp;
return hashValue;
};
哈希函数3
int HashTable::hash3(string tel)//数字分析法做哈希函数
{
int hashValue;
hashValue = atof(tel.substr(8, 3).c_str()); //因为电话号码一般后4位不同
return hashValue;
};
解决冲突的方法
1.线性探测法
int HashTable::solve1(int hashVal,int flag) //线性探查法处理冲突
{
int output = hashVal;
switch (flag)
{
case 1:
for (int j = 1; j < MAXSIZE; j++)
{
output = (hashVal + j) % MAXSIZE;
if (tag[output] == 0)
{
tag[output] = 1;
return output;
}
}
return -1;
break;
case 2:
for (int j = 1; j < MAXSIZE; j++)
{
output = (hashVal + j) % MAXSIZE;
if (tag2[output] == 0)
{
tag2[output] = 1;
return output;
}
}
return -1;
default:
break;
}
};
2.二次探查法
int HashTable::solve2(int hashVal, int flag) //二次探查法解决冲突
{
int i = hashVal; //i为初始桶号
int k = 0; //k为探查次数
int odd = 0; //odd为控制加减的标志
int save; //缓存上一次的桶号
switch (flag)
{
case 1:
while (tag[i]==1)
{
if (odd == 0)
{
k++; save = i;
i = (i + 2 * k-1) % MAXSIZE;
odd = 1;
}
else
{
i = (save - 2 * k+1) % MAXSIZE;
odd = 0;
if (i<0)
{
i = i + MAXSIZE;
}
}
}
return i;
break;
case 2:
while (tag2[i] == 1)
{
if (odd == 0)
{
k++; save = i;
i = (i + 2 * k - 1) % MAXSIZE;
odd = 1;
}
else
{
k++;
i = (save - 2 * k + 1) % MAXSIZE;
odd = 0;
if (i<0)
{
i = i + MAXSIZE;
}
}
}
return i;
break;
default:
break;
}
};
3.拉链法
Node* HashTable::solve3(int hashVal, int flag)//拉链法解决冲突
{
int i = hashVal; //第i条链
Node*p = ht[i]; //该链上的头指针
while (p!=NULL)
p = p->next;//往后遍历直到找到一个空节点用于存放user
return p;
};
所有代码如下
1 #include <iostream>
2 #include <string>
3 #include <fstream>
4
5 using namespace std;
6
7 const int MAXSIZE = 12;//默认最大表长
8
9
10
11
12 //存储项
13 class User{
14 public:
15 string name;
16 string tel;
17 string address;
18 bool operator==(const User&target)
19 {
20 if (this->name == target.name&&this->address == target.address&&this->tel == target.tel)
21 return true;
22 else
23 return false;
24 }
25 };
26
27 //用于拉链法
28 struct Node{
29 User user;
30 Node* next;
31 };
32 class HashTable{
33 public:
34 HashTable(int size = MAXSIZE-1);
35 ~HashTable(){ delete[]E; delete[]tag; delete[]E2; delete[]tag2; }
36 int hash1(string name, int flag);//哈希函数1 除数求余法
37 int hash2(string tel);//哈希函数2 折叠法
38 int hash3(string tel);//哈希函数3 数字分析法
39 int solve1(int hashVal, int flag);//线性探测法解决冲突
40 int solve2(int hashVal, int flag);//二次探测法解决冲突
41 Node* solve3(int hashVal, int flag);//拉链法解决冲突
42 User input();//往电话薄中添加用户
43 void creat(int flag); //创建散列表
44 void show(int flag); //列出电话薄所有元素
45 void search(int flag,string at); //搜索指定用户
46 void searchByNode(int flag, string at); //拉链法搜索指定用户
47 void insert(int flag, User newUser); //插入
48 void del(int flag, string by);//删除
49 void save(int flag);//将电话薄保存至本地文件
50 int length; //要创建的电话本长度
51 Node** ht;
52 private:
53 User* E; //用户数组 按姓名散列
54 User* E2; //用户数组2 按电话号码散列
55 int* tag; //标记散列表1每个桶的存储状态 0为空 1为实
56 int* tag2;//标记散列表2每个桶的存储状态
57 int flag; //1表示是按姓名 2表示按电话号码 新建的哈希表
58 int maxSize; //哈希表最大长度
59 int f;//比例因子 主要用于折叠法
60 };
61
62 HashTable::HashTable(int size)
63 {
64 maxSize = size; //用作除数
65 E = new User[MAXSIZE];
66 E2 = new User[MAXSIZE];
67 tag = new int[MAXSIZE];
68 tag2 = new int[MAXSIZE];
69 for (int i = 0; i < MAXSIZE; i++)
70 {
71 tag[i] = 0;
72 tag2[i] = 0;
73 }
74 f = maxSize / 512; //用于折叠法产生的哈希值过大 保留3位数的地址范围为0~511
75 ht = new Node*[maxSize]; //存放节点的一维数组 拉链法
76 };
77
78 int HashTable::hash1(string name,int flag) //除数求余法
79 {
80 int hashValue; long a = 0;
81 switch (flag)
82 {
83 case 1:
84 for (int i = 0; i < name.length(); i++)
85 a += int(name[i]);
86 hashValue = a%maxSize;
87 break;
88 case 2:
89 int temp = atof(name.c_str());
90 hashValue = temp%maxSize;
91 break;
92
93 }
94 return hashValue;
95 };
96
97 int HashTable::hash2(string tel) //折叠法--移位法
98 {
99 int hashValue;
100 int temp; //移位法求和
101 temp = atof(tel.substr(0, 3).c_str()) + atof(tel.substr(3, 3).c_str())
102 + atof(tel.substr(6, 3).c_str()) + atof(tel.substr(9, 2).c_str());
103 //取计算之后的数的最后三位
104 if (temp >= 999)
105 {
106 char p[10];
107 sprintf(p, "%d", temp);
108 string lastThree = p;
109 lastThree = lastThree.substr(lastThree.length() - 3, 3);
110 hashValue = atof(lastThree.c_str());
111 return hashValue;
112 }
113 hashValue = temp;
114 return hashValue;
115 };
116
117 int HashTable::hash3(string tel)//数字分析法做哈希函数
118 {
119 int hashValue;
120 hashValue = atof(tel.substr(8, 3).c_str()); //因为电话号码一般后4位不同
121 return hashValue;
122 };
123
124 int HashTable::solve1(int hashVal,int flag) //线性探查法处理冲突
125 {
126 int output = hashVal;
127 switch (flag)
128 {
129 case 1:
130 for (int j = 1; j < MAXSIZE; j++)
131 {
132 output = (hashVal + j) % MAXSIZE;
133 if (tag[output] == 0)
134 {
135 tag[output] = 1;
136 return output;
137 }
138 }
139 return -1;
140 break;
141 case 2:
142 for (int j = 1; j < MAXSIZE; j++)
143 {
144 output = (hashVal + j) % MAXSIZE;
145 if (tag2[output] == 0)
146 {
147 tag2[output] = 1;
148 return output;
149 }
150 }
151 return -1;
152 default:
153 break;
154 }
155
156 };
157
158 int HashTable::solve2(int hashVal, int flag) //二次探查法解决冲突
159 {
160 int i = hashVal; //i为初始桶号
161 int k = 0; //k为探查次数
162 int odd = 0; //odd为控制加减的标志
163 int save; //缓存上一次的桶号
164 switch (flag)
165 {
166 case 1:
167 while (tag[i]==1)
168 {
169 if (odd == 0)
170 {
171 k++; save = i;
172 i = (i + 2 * k-1) % MAXSIZE;
173 odd = 1;
174 }
175 else
176 {
177 i = (save - 2 * k+1) % MAXSIZE;
178 odd = 0;
179 if (i<0)
180 {
181 i = i + MAXSIZE;
182 }
183 }
184 }
185 return i;
186 break;
187 case 2:
188 while (tag2[i] == 1)
189 {
190 if (odd == 0)
191 {
192 k++; save = i;
193 i = (i + 2 * k - 1) % MAXSIZE;
194 odd = 1;
195 }
196 else
197 {
198 k++;
199 i = (save - 2 * k + 1) % MAXSIZE;
200 odd = 0;
201 if (i<0)
202 {
203 i = i + MAXSIZE;
204 }
205 }
206 }
207 return i;
208 break;
209 default:
210 break;
211 }
212
213 };
214
215 /*
216 Node* HashTable::solve3(int hashVal, int flag)//拉链法解决冲突
217
218 {
219 int i = hashVal; //第i条链
220
221 Node*p = ht[i]; //该链上的头指针
222 while (p!=NULL)
223 p = p->next;//往后遍历直到找到一个空节点用于存放user
224 return p;
225 };
226
227 void HashTable::searchByNode(int flag, string at)//调用拉链法搜索
228 {
229 int i = hash1(at,1);
230 Node** ht = new Node*[maxSize]; //存放节点的一维数组
231 Node*p = ht[i]; //该链上的头指针
232 while (p!=NULL&&p->user.name!=at)
233 {
234 p = p->next;
235 }
236 };
237 */
238 User HashTable::input()
239 {
240 User user;
241 cout << "请输入姓名：" << endl;
242 cin >> user.name;
243 cout << "请输入电话号码：" << endl;
244 cin >> user.tel;
245 cout << "请输入地址：" << endl;
246 cin >> user.address;
247 return user;
248 };
249
250 void HashTable::creat(int flag)
251 {
252 switch (flag)
253 {
254 case 1: //按姓名哈希创建哈希表
255 for (int i = 0; i < length; i++)
256 {
257 User newUser = input();
258 int val = hash1(newUser.name,1);
259 if (tag[val] == 1)
260 val = solve1(val,1);//线性探测法解决冲突
261 E[val] = newUser;
262 tag[val] = 1;
263 }
264 break;
265 case 2: //按电话号码哈希创建哈希表
266 for (int i = 0; i < length; i++)
267 {
268 User newUser = input();
269 int val = hash1(newUser.tel,2);
270 if(tag2[val] == 1)
271 val = solve1(val,2);//线性探测法解决冲突
272 E2[val] = newUser;
273 tag2[val] = 1;
274 }
275 break;
276 }
277 };
278 void HashTable::show(int flag)
279 {
280 switch (flag)
281 {
282 case 1:
283 for (int i = 0; i < MAXSIZE; i++)
284 {
285 if (tag[i] == 1)
286 cout << E[i].name << " " << E[i].tel << " " << E[i].address << " 位于： " << i << endl;
287 }
288 break;
289 case 2:
290 for (int i = 0; i < MAXSIZE; i++)
291 {
292 if (tag2[i] == 1)
293 cout << E2[i].name << " " << E2[i].tel << " " << E2[i].address << " 位于： " << i << endl;
294 }
295 break;
296 }
297
298 };
299
300 void HashTable::search(int flag,string at) //at表示索引内容
301 {
302 int i = 0;
303 switch (flag)
304 {
305 case 1: //调用线性探测法查找姓名
306 i = hash1(at,1);
307 if (tag[i] == 1 && E[i].name != at)
308 i = solve1(i, 2);
309 if (i < 0 || tag2[i] == 0)
310 {
311 cout << "查无此人！" << endl;
312 return;
313 }
314 if (tag[i] == 1 && E[i].name == at)
315 cout << E2[i].name << " " << E2[i].tel << " " << E2[i].address << endl;
316 break;
317 case 2: //调用二次探测法查找电话号码
318 i = hash2(at);
319 if (tag2[i] == 1&&E2[i].tel!=at)
320 i = solve2(i,2);
321 if (i < 0||tag2[i]==0)
322 {
323 cout << "查无此人！" << endl;
324 return;
325 }
326 if (tag2[i] == 1 && E2[i].tel==at)
327 cout << E2[i].name << " " << E2[i].tel << " " << E2[i].address << endl;
328 break;
329 }
330 };
331
332 void HashTable::insert(int flag, User newUser){
333 int i = -1;
334 switch (flag)
335 {
336 case 1:
337 i = hash1(newUser.name,1);
338 if (tag[i] == 1||E[i]==newUser)
339 i = solve1(i, 1);
340 if (i < 0)
341 {
342 cout << "表满！插入失败！" << endl;
343 return;
344 }
345 if (tag[i] == 0)
346 {
347 E[i] = newUser;
348 tag[i] = 1;
349 length++;
350 cout << "插入成功" << endl;
351 }
352 case 2:
353 i = hash1(newUser.tel,2);
354 if (tag2[i] == 1 || E2[i] == newUser)
355 i = solve1(i, 2);
356 if (i < 0)
357 {
358 cout << "表满！插入失败！" << endl;
359 return;
360 }
361 if (tag2[i] == 0)
362 {
363 E2[i] = newUser;
364 tag2[i] = 1;
365 length++;
366 cout << "插入成功" << endl;
367 }
368 default:
369 break;
370 }
371 };
372
373 void HashTable::del(int flag, string by) //by表示按照何种标签进行删除
374 {
375 int i = -1;
376 int select;//选择是否删除
377 switch (flag)
378 {
379 case 1: //调用线性探测法查找姓名
380 i = hash1(by,1);
381 if (tag[i] == 1 && E[i].name != by)
382 i = solve1(i, 2);
383 if (i < 0 || tag2[i] == 0)
384 {
385 cout << "查无此人！" << endl;
386 return;
387 }
388 if (tag[i] == 1 && E[i].name == by)
389 {
390 cout << E2[i].name << " " << E2[i].tel << " " << E2[i].address << endl;
391 cout << "是否删除 0.删了 1.算了" << endl;
392 cin >> select;
393 if (select == 0)
394 tag[i] = 0;//伪删除
395 }
396 break;
397 case 2: //调用二次探测法查找电话号码
398 i = hash2(by);
399 if (tag2[i] == 1 && E2[i].tel != by)
400 i = solve2(i, 2);
401 if (i < 0 || tag2[i] == 0)
402 {
403 cout << "查无此人！" << endl;
404 return;
405 }
406 if (tag2[i] == 1 && E2[i].tel == by)
407 {
408 cout << E2[i].name << " " << E2[i].tel << " " << E2[i].address << endl;
409 cout << "是否删除 0.删了 1.算了" << endl;
410 cin >> select;
411 if (select == 0)
412 tag2[i] = 0;//伪删除
413 }
414 break;
415 }
416 };
417
418 void HashTable::save(int flag)
419 {
420 fstream out1("电话薄（姓名散列）.txt", ios::out);
421 fstream out2("电话薄（号码散列）.txt", ios::out);
422 switch (flag)
423 {
424 case 1:
425 for (int i = 0; i < maxSize; i++)
426 {
427 if (tag[i] == 1)
428 out1 << E[i].name << " " << E[i].tel << " " << E[i].address << endl;
429 }
430 cout << "已存至电话薄（姓名散列）.txt" << endl;
431 return;
432 break;
433 case 2:
434 for (int i = 0; i < maxSize; i++)
435 {
436 if (tag2[i] == 1)
437 out2 << E2[i].name << " " << E2[i].tel << " " << E2[i].address << endl;
438 }
439 cout << "已存至电话薄（号码散列）.txt" << endl;
440 return;
441 break;
442 default:
443 break;
444 }
445
446 };
hashtable.h
1 #include <iostream>
2 #include <string>
3 #include <fstream>
4 #include "hashtable.h"
5 using namespace std;
6
7 //菜单
8 void menu()
9 {
10 cout << " ****************************" << endl;
11 cout << "|| 0.建表 ||" << endl;
12 cout << "|| 1.查看 ||" << endl;
13 cout << "|| 2.搜索 ||" << endl;
14 cout << "|| 3.添加 ||" << endl;
15 cout << "|| 4.删除 ||" << endl;
16 cout << "|| 5.保存 ||" << endl;
17 cout << "|| 6.退出 ||" << endl;
18 cout << " ****************************" << endl;
19
20 }
21
22 int main()
23 {
24 User user;
25 int size;//第一次创建的数据量大小
26 int select;//主菜单选项
27 int select_;//子菜单选项
28 cout << "欢迎使用电话簿" << endl;
29 HashTable ht;
30 while (1)
31 {
32 menu();
33 cin >> select;
34 switch (select)
35 {
36 case 0:
37 cout << "第一次使用，请输入要新建的电话本大小：" << endl;
38 cin >> size;
39 ht.length = size;
40 cout << "1.姓名散列 2.电话号码散列" << endl;
41 cin >> select_;
42 ht.creat(select_);
43 break;
44 case 1:
45 cout << "1.姓名散列 2.电话号码散列" << endl;
46 cin >> select_;
47 ht.show(select_);
48 break;
49 case 2:
50 cout << "1.按姓名查找 2.按电话号码查找" << endl;
51 cin >> select_;
52 if (select_==1)
53 {
54 cout << "输入姓名" << endl;
55 string name;
56 cin >> name;
57 ht.search(1, name);
58 }
59 else if (select_ == 2)
60 {
61 cout << "输入号码" << endl;
62 string tel;
63 cin >> tel;
64 ht.search(2, tel);
65 }
66 else
67 cout << "不合法操作！！！" << endl;
68 break;
69 case 3:
70 user = ht.input();
71 cout << "1.插入到姓名散列表 2.插入到电话号码散列" << endl;
72 cin >> select_;
73 ht.insert(select_,user);
74 break;
75 case 4:
76 cout << "1.根据姓名删除 2.根据电话号码删除" << endl;
77 cin >> select_;
78 if (select_ == 1)
79 {
80 cout << "输入姓名" << endl;
81 string name;
82 cin >> name;
83 ht.del(1, name);
84 }
85 else if (select_ == 2)
86 {
87 cout << "输入号码" << endl;
88 string tel;
89 cin >> tel;
90 ht.del(2, tel);
91 }
92 else
93 cout << "不合法操作！！！" << endl;
94 break;
95 case 5:
96 cout << "1.保存姓名散列表到本地 2.保存电话号码散列表到本地" << endl;
97 cin >> select_;
98 ht.save(select_);
99 case 6:
100 return 0;
101 }
102 }
103 }
main.cpp
通过这次课程设计,总结如下
1.C++技艺不精，语法不熟悉，比如模版类与运算符重载，指针更是不大熟练。要掌握C++还需要漫长的修炼。
2. 算法停留在理解阶段感觉远远不够，实现起来远没有当初想的那么简单。
3. 数据结构与算法很重要，很重要，很重要。同样的功能，一个优秀的算法节约了大量的时间，创造出巨大的经济效益！
我知道我还很菜，加油！
原文链接: https://www.cnblogs.com/morningsky/p/5090467.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/226675
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
