哈希表实现电话号码查询系统（c++）

超、凢脫俗 2022-08-05 08:59 299阅读 0赞

问题描述： 设计哈希表实现电话号码查询系统，实现下列功能：  
(1) 假定每个记录有下列数据项：电话号码、用户名、地址。  
(2) 一是从数据文件old.txt(自己现行建好)中读入各项记录，二是由系统随机产生各记录，并且把记录保存到new.txt文件中以及显示到屏幕上，记录条数不要少于30，然后分别 以电话号码和用户名为关键字建立哈希表。  
(3) 分别采用 伪随机探测再散列法和 再哈希法解决冲突。  
(4) 查找并显示给定电话号码的记录；查找并显示给定用户名的记录。  
(5) 将没有查找的结果保存到结果文件Out.txt中，显示查找结果前，要有提示语句。

代码：

**\[cpp\]**  [view plain][] [copy][view plain]

1.  // MyHashTable.cpp : 定义控制台应用程序的入口点。  
2.  设计哈希表实现电话号码查询系统  
3.  //说明：一是从文件old.txt中读取的数据自己在程序运行前建立，  
4.  //      二是由系统随机生成数据，在程序运行由随机数产生器生成，并且将产生的记录保存到 new.txt文件。  
5.    
6.  //存在的问题：使用随机产生的文件，在显示时出现乱码  
7.    
8.    
9.  \#include "stdafx.h"  
10. \#include<fstream>//文件流  
11. \#include<iostream>  
12. \#include <string>  
13. **using** **namespace** std;  
14.   
15. **const** **int** D\[\] = \{3,5,8,11,13,14,19,21\};//预定再随机数  
16. **const** **int** HASH\_MAXSIZE = 50;//哈希表长度  
17.   
18. //记录信息类型  
19. **class** DataInfo  
20. \{  
21. **public**:  
22.     DataInfo();//默认构造函数  
23.     **friend** ostream& operator<<(ostream& out, **const** DataInfo& dataInfo); //重载输出操作符  
24.     //friend class HashTable;  
25.   
26. //private:  
27.     string name;//姓名  
28.     string phone;//电话号码  
29.     string address;//地址   
30.     **char** sign;//冲突的标志位，'1'表示冲突，'0'表示无冲突  
31. \};  
32.   
33. DataInfo::DataInfo():name(""), phone(""), address(""), sign('0')  
34. \{  
35.   
36. \}  
37.   
38. ostream& operator<<(ostream& out, **const** DataInfo& dataInfo) //重载输出操作符  
39. \{  
40.     cout << "姓名：" << dataInfo.name << "   电话：" << dataInfo.phone   
41.          << "    地址：" << dataInfo.address << endl;  
42.     **return** out;  
43. \}  
44.   
45. //存放记录的哈希表类型  
46. **class** HashTable  
47. \{  
48. **public**:  
49.     HashTable();//默认构造函数  
50.     ~HashTable();//析构函数  
51.     **int** Random(**int** key, **int** i);// 伪随机数探测再散列法处理冲突  
52.     **void** Hashname(DataInfo \*dataInfo);//以名字为关键字建立哈希表      
53.     **int** Rehash(**int** key, string str);// 再哈希法处理冲突   注意处理冲突还有链地址法等  
54.     **void** Hashphone(DataInfo \*dataInfo);//以电话为关键字建立哈希表         
55.     **void** Hash(**char** \*fname, **int** n);// 建立哈希表  
56.     //fname 是数据储存的文件的名称，用于输入数据，n是用户选择的查找方式    
57.       
58.     **int** Findname(string name);// 根据姓名查找哈希表中的记录对应的关键码  
59.     **int** Findphone(string phone);// 根据电话查找哈希表中的记录对应的关键码  
60.     **void** Outhash(**int** key);// 输出哈希表中关键字码对应的一条记录  
61.     **void** Outfile(string name, **int** key);// 在没有找到时输出未找到的记录  
62.     **void** Rafile();// 随机生成文件，并将文件保存在 new.txt文档中  
63.     **void** WriteToOldTxt();//在运行前先写入数据      
64.   
65. //private:  
66.         DataInfo \*value\[HASH\_MAXSIZE\];  
67.     **int** length;//哈希表长度  
68. \};  
69.   
70. HashTable::HashTable():length(0)//默认构造函数  
71. \{  
72.     //memset(value, NULL, HASH\_MAXSIZE\*sizeof(DataInfo\*));  
73.     **for** (**int** i=0; i<HASH\_MAXSIZE; i++)  
74.     \{  
75.         value\[i\] = **new** DataInfo();  
76.     \}  
77. \}  
78.   
79. HashTable::~HashTable()//析构函数  
80. \{  
81.     **delete**\[\] \*value;  
82. \}  
83.   
84. **void** HashTable::WriteToOldTxt()  
85. \{  
86.     ofstream openfile("old.txt");  
87.     **if** (openfile.fail())  
88.     \{  
89.         cout << "文件打开错误！" << endl;  
90.         exit(1);  
91.     \}  
92.   
93.     string oldname;  
94.         string oldphone;  
95.     string oldaddress;  
96.   
97.     **for** (**int** i=0; i<30; i++)  
98.     \{  
99.         cout << "请输入第" << i+1 << "条记录:" << endl;          
100.         cin >> oldname ;  
101.         cin >> oldphone;  
102.         cin >> oldaddress;  
103.         openfile << oldname << "  " << oldphone << "  " << oldaddress << "," << endl;  
104.     \}  
105.     openfile.close();  
106. \}  
107.   
108.   
109. **int** HashTable::Random(**int** key, **int** i)// 伪随机数探测再散列法处理冲突  
110. \{ //key是冲突时的哈希表关键码，i是冲突的次数，N是哈希表长度  
111.     //成功处理冲突返回新的关键码，未进行冲突处理则返回-1  
112.     **int** h;  
113.     **if**(value\[key\]->sign == '1')//有冲突  
114.     \{  
115.         h = (key + D\[i\]) % HASH\_MAXSIZE;  
116.         **return** h;  
117.     \}  
118.     **return** -1;  
119. \}  
120.   
121. **void** HashTable::Hashname(DataInfo \*dataInfo)//以名字为关键字建立哈希表  
122. \{ //利用除留取余法建立以名字为关键字建立的哈希函数，在发生冲突时调用Random函数处理冲突  
123.     **int** i = 0;    
124.     **int** key = 0;  
125.   
126.         **for** (**int** t=0; dataInfo->name\[t\]!='\\0'; t++)     
127.     \{         
128.         key = key + dataInfo->name\[t\];  
129.     \}  
130.     key = key % 42;  
131.     **while**(value\[key\]->sign == '1')//有冲突  
132.     \{  
133.         key = Random(key, i++);//处理冲突  
134.     \}  
135.     **if**(key == -1) exit(1);//无冲突  
136.     length++;//当前数据个数加  
137.     value\[key\]->name = dataInfo->name;  
138.     value\[key\]->address = dataInfo->address;  
139.     value\[key\]->phone = dataInfo->phone;  
140.     value\[key\]->sign = '1';//表示该位置有值  
141.     //cout << value\[key\]->name << "  " << value\[key\]->phone << "  "  << value\[key\]->address << endl;  
142. \}  
143.   
144. **int** HashTable::Rehash(**int** key, string str)// 再哈希法处理冲突  
145. \{ //再哈希时使用的是折叠法建立哈希函数      
146.     **int** h;  
147.     **int** num1 = (str\[0\] - '0') \* 1000 + (str\[1\] - '0') \* 100 + (str\[2\] - '0') \* 10 + (str\[3\] - '0');  
148.     **int** num2 = (str\[4\] - '0') \* 1000 + (str\[5\] - '0') \* 100 + (str\[6\] - '0') \* 10 + (str\[7\] - '0');  
149.     **int** num3 = (str\[8\] - '0') \* 100  + (str\[9\] - '0') \* 10  + (str\[10\] - '0');  
150.     h = num1 + num2 + num3;  
151.     h = (h + key) % HASH\_MAXSIZE;  
152.     **return** h;  
153. \}  
154.   
155. **void** HashTable::Hashphone(DataInfo \*dataInfo)//以电话为关键字建立哈希表  
156. \{ //利用除留取余法建立以电话为关键字建立的哈希函数，在发生冲突时调用Rehash函数处理冲突  
157.     **int** key = 0;      
158.     **int** t;  
159.       
160.     **for**(t=0; dataInfo->phone\[t\] != '\\0'; t++)  
161.     \{     
162.         key = key + dataInfo->phone\[t\];  
163.     \}  
164.     key = key % 42;  
165.     **while**(value\[key\]->sign == '1')//有冲突  
166.     \{  
167.         key = Rehash(key, dataInfo->phone);  
168.     \}  
169.     length++;//当前数据个数加  
170.     value\[key\]->name = dataInfo->name;  
171.     value\[key\]->address = dataInfo->address;  
172.     value\[key\]->phone = dataInfo->phone;     
173.     value\[key\]->sign = '1';//表示该位置有值   
174. \}  
175.   
176. **void** HashTable::Outfile(string name, **int** key)//在没有找到时输出未找到的记录  
177. \{  
178.     ofstream fout;  
179.     **if**((key == -1)||(value\[key\]->sign == '0'))//判断哈希表中没有记录  
180.     \{  
181.         fout.open("out.txt",ios::app);//打开文件  
182.   
183.         **if**(fout.fail())  
184.         \{  
185.             cout << "文件打开失败!" << endl;  
186.             exit(1);  
187.         \}  
188.         fout << name << endl;//将名字写入文件,有个问题，每次写入的时候总是将原来的内容替换了  
189.         fout.close();  
190.     \}  
191. \}  
192.   
193. **void** HashTable::Outhash(**int** key)//输出哈希表中关键字码对应的记录  
194. \{    
195.     **if**((key==-1)||(value\[key\]->sign=='0'))  
196.         cout << "没有找到这条记录！" << endl;  
197.     **else**  
198.     \{         
199.         **for**(unsigned **int** i=0; value\[key\]->name\[i\]!='\\0'; i++)  
200.         \{  
201.             cout << value\[key\]->name\[i\];             
202.         \}  
203.   
204.         **for**(unsigned **int** i=0; i<10; i++)  
205.         \{  
206.             cout << " ";  
207.         \}  
208.   
209.         cout << value\[key\]->phone;  
210.   
211.         **for**(**int** i=0; i<10; i++)  
212.         \{  
213.             cout << " ";  
214.         \}  
215.   
216.         cout << value\[key\]->address << endl;  
217.     \}  
218. \}  
219.   
220. **void** HashTable::Rafile()//随机生成文件，并将文件保存在new.txt文档中  
221. \{  
222.     ofstream fout;  
223.     fout.open("new.txt");//打开文件，等待写入  
224.     **if**(fout.fail())  
225.     \{  
226.         cout << "文件打开失败！" << endl;  
227.         exit(1);  
228.     \}  
229.     **for**(**int** j=0; j<30; j++)  
230.     \{         
231.         string name = "";  
232.         **for**(**int** i=0; i<20; i++)//随机生成长个字的名字  
233.         \{  
234.             name += rand() % 26 + 'a';//名字是由个字母组成             
235.         \}  
236.         fout << name << "   ";//将名字写入文件  
237.   
238.         string phone = "";  
239.         **for**(**int** i=0; i<11; i++)//随机生成长位的电话号码  
240.         \{  
241.             phone += rand() % 10 + '0';//电话号码是纯数字  
242.         \}  
243.         fout << phone << "      ";//将电话号码写入文件  
244.   
245.         string address = "";  
246.         **for**(**int** i=0; i<29; i++)//随机生成长个字的名字  
247.         \{  
248.             address += rand() % 26 + 'a';//地址是由个字母组成  
249.         \}  
250.         address += ',';  
251.         fout << address << endl;//将地址写入文件  
252.     \}  
253.     fout.close();  
254. \}  
255.   
256. **void** HashTable::Hash(**char** \*fname, **int** n)//建立哈希表  
257. //fname是数据储存的文件的名称，用于输入数据，n是用户选择的查找方式  
258. //函数输入数据，并根据选择调用Hashname或Hashphone函数进行哈希表的建立  
259. \{  
260.     ifstream fin;         
261.     **int** i;  
262.     fin.open(fname);//读文件流对象  
263.     **if**(fin.fail())  
264.     \{  
265.         cout << "文件打开失败！" << endl;  
266.         exit(1);  
267.     \}  
268.     **while**(!fin.eof())//按行读入数据  
269.     \{  
270.         DataInfo \*dataInfo = **new** DataInfo();  
271.         **char**\* str = **new** **char**\[100\];        
272.         fin.getline(str, 100, '\\n');//读取一行数据  
273.   
274.         **if**(str\[0\] == '\*')//判断数据结束  
275.         \{  
276.             **break**;  
277.         \}  
278.   
279.         i = 0;//记录字符串数组的下标  
280.         //a-z:97-122     A-Z:65-90      
281.         //本程序的姓名和地址都使用小写字母  
282.         **while**((str\[i\] < 97) || (str\[i\] > 122))//读入名字  
283.         \{  
284.             i++;  
285.         \}  
286.   
287.         **for**(; str\[i\]!=' '; i++)  
288.         \{             
289.             dataInfo->name += str\[i\];              
290.         \}  
291.   
292.         **while**(str\[i\] == ' ')  
293.         \{  
294.             i++;  
295.         \}  
296.   
297.         **for**(**int** j=0; str\[i\]!=' '; j++,i++)//读入电话号码  
298.         \{             
299.             dataInfo->phone += str\[i\];  
300.         \}  
301.   
302.         **while**(str\[i\] == ' ')  
303.         \{  
304.             i++;  
305.         \}  
306.   
307.         **for**(**int** j=0; str\[i\]!=','; j++,i++)//读入地址  
308.         \{             
309.             dataInfo->address += str\[i\];  
310.         \}  
311.   
312.         **if**(n == 1)  
313.         \{             
314.             Hashname(dataInfo);  
315.         \}  
316.         **else**  
317.         \{             
318.             Hashphone(dataInfo);//以电话为关键字  
319.         \}  
320.   
321.         **delete** \[\]str;  
322.         **delete** dataInfo;  
323.     \}     
324.     fin.close();  
325. \}  
326.   
327. **int** HashTable::Findname(string name)//根据姓名查找哈希表中的记录对应的关键码  
328. \{  
329.     **int** i = 0;  
330.     **int** j = 1;  
331.     **int** t;  
332.     **int** key = 0;  
333.       
334.     **for**(key=0, t=0; name\[t\] != '\\0'; t++)  
335.     \{  
336.         key = key + name\[t\];  
337.     \}  
338.     key = key % 42;  
339.     **while**((value\[key\]->sign == '1') && (value\[key\]->name != name))  
340.     \{    
341.         key = Random(key, i++);  
342.         j++;  
343.         **if**(j >= length) **return** -1;  
344.     \}  
345.     **return** key;  
346. \}  
347.   
348. **int** HashTable::Findphone(string phone)//根据电话查找哈希表中的记录对应的关键码  
349. \{    
350.     **int** key = 0;  
351.     **int** t;  
352.       
353.     **for**(t=0; phone\[t\] != '\\0' ; t++)  
354.         \{  
355.                 key = key + phone\[t\];  
356.         \}  
357.     key = key % 42;  
358.     **int** j = 1;  
359.     **while**((value\[key\]->sign == '1') && (value\[key\]->phone != phone))  
360.     \{  
361.         key = Rehash(key, phone);  
362.         j++;  
363.         **if**(j >= length)   
364.                 \{  
365.                     **return** -1;  
366.                 \}  
367.         \}  
368.     **return** key;  
369. \}  
370.   
371. **void** main()  
372. \{  
373.     //WriteToOldTxt();    
374.     **int** k;  
375.     **int** ch;   
376.     **char** \*Fname;  
377.     HashTable \*ht = **new** HashTable;  
378.     **while**(1)  
379.     \{  
380.         system("cls");//cls命令清除屏幕上所有的文字  
381.         cout << "欢迎使用本系统！" << endl << endl;  
382.         cout << "请选择数据" << endl;  
383.         cout << "1.使用已有数据文件" << endl;  
384.         cout << "2.随机生成数据文件" << endl;  
385.         cout << "0.结束" << endl;  
386.         cout << "输入相应序号选择功能：";  
387.         cin >> k;  
388.         **switch**(k)  
389.         \{  
390.         **case** 0:  
391.             **return**;  
392.         **case** 1:  
393.             Fname = "old.txt";//从数据文件old.txt(自己现行建好)中读入各项记录  
394.             **break**;  
395.         **case** 2:  
396.             ht->Rafile();  
397.             Fname = "new.txt";//由系统随机产生各记录，并且把记录保存到new.txt文件中  
398.             **break**;  
399.         **default**:  
400.             cout << "输入序号有误，退出程序。" << endl;   
401.             **return**;  
402.         \}  
403.   
404.         **do**  
405.         \{  
406.             system("cls");  
407.             cout << " 请选择查找方式" << endl;  
408.             cout << "1.通过姓名查找" << endl;  
409.             cout << "2.通过电话查找" << endl;  
410.             cout << "输入相应序号选择功能：";  
411.             cin >> ch;  
412.             **if**((ch != 1) && (ch != 2))  
413.                 cout << "输入序号有误！" << endl;  
414.         \}**while**((ch != 1) && (ch != 2));  
415.   
416.         ht->Hash(Fname, ch);  
417.         **while**(ch == 1)  
418.         \{  
419.             **int** choice;  
420.             cout << endl << "请选择功能" << endl;  
421.             cout << "1.输入姓名查找数据" << endl;  
422.             cout << "2.显示哈希表" << endl;  
423.             cout << "0.退出"<<endl;  
424.             cout << "输入相应序号选择功能：";  
425.             cin >> choice;  
426.             **switch**(choice)  
427.             \{  
428.             **case** 1:   
429.                 \{ //注意此处应该加上大括号  
430.                     **int** key1;                     
431.                     string name;                      
432.                     cout << "请输入姓名：";  
433.                     cin >> name;                    
434.                     key1 = ht->Findname(name);  
435.                     ht->Outfile(name, key1);  
436.                     ht->Outhash(key1);     
437.                 \}  
438.                 **break**;  
439.   
440.             **case** 2:   
441.                 \{  
442.                     **for**(**int** i=0; i<HASH\_MAXSIZE; i++)  
443.                     \{  
444.                         **if**(ht->value\[i\]->sign!='0')  
445.                         \{  
446.                             ht->Outhash(i);   
447.                         \}  
448.                     \}     
449.                 \}                             
450.                 **break**;  
451.   
452.   
453.             **default**:  
454.                 cout << endl << "您的输入有误！" << endl;                  
455.             \}  
456.   
457.             **if**(choice == 0)   
458.             \{  
459.                 **return**;  
460.             \}  
461.         \}  
462.   
463.         **while**(ch == 2)  
464.         \{  
465.             **int** choice;  
466.             cout << endl << "请选择功能" << endl;  
467.             cout << "1.输入电话查找数据" << endl;  
468.             cout << "2.显示哈希表"<<endl;  
469.             cout << "0.退出"<<endl;  
470.             cout << "输入相应序号选择功能：";  
471.             cin >> choice;  
472.             **switch**(choice)  
473.             \{  
474.             **case** 1:   
475.                 \{  
476.                     **int** key2;                     
477.                     string phone;                     
478.                     cout << "请输入11位的电话号码：";  
479.                       
480.                     **do**  
481.                     \{  
482.                         cin >> phone;                       
483.                         **if**(phone.length() != 11)                      
484.                         \{  
485.                             cout << "电话号码应为11位！\\n请重新输入：";  
486.                         \}  
487.                               
488.                     \}**while**(phone.length() != 11);  
489.                       
490.                     key2 = ht->Findphone(phone);  
491.                     ht->Outfile(phone, key2);  
492.                     ht->Outhash(key2);  
493.                 \}  
494.                 **break**;  
495.   
496.             **case** 2:   
497.                 \{  
498.                     **for**(**int** i=0; i<HASH\_MAXSIZE; i++)  
499.                     \{  
500.                         **if**(ht->value\[i\]->sign != '0')   
501.                         \{  
502.                             ht->Outhash(i);   
503.                         \}  
504.                     \}  
505.                 \}                 
506.                 **break**;  
507.   
508.             **default**:  
509.                  cout << endl << "您的输入有误！" << endl;                  
510.             \}  
511.   
512.             **if**(choice == 0)   
513.             \{  
514.                 **return**;  
515.             \}  
516.         \}  
517.   
518.         **while**((ch != 1) && (ch != 2))  
519.         \{  
520.             cout << "您的输入有误！请输入相应需要选择功能：";  
521.         \}  
522.     \}  
523.     system("pause");      
524. \}

[view plain]: http://blog.csdn.net/htyurencaotang/article/details/7881427#