哈希表实现电话号码查询系统

1、?数据结构?课程设计哈希表实现 号码查询系统一目的利用?数据结构?课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C+语言进行程序设计，并标准地完成课程设计报告。通过课程设计，稳固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法包括问题描述、系统分析、设计建模、代码实现、结果分析等；提高利用计算机分析解决综合性实际问题的根本能力。二需求分析1、 程序的功能1) 读取数据 读取原 本存储的 信息。 读取系统随机新建 本存储的 信息。2) 查找信息 根据 号码查询用户信息。 根据查询用户信息。3) 存储信息查询无记录的结果存入记录

2、文档。2、 输出形式1) 数据文件“old.txt存放原始 号码数据。2) 数据文件“new.txt存放有系统随机生成的 号码文件。3) 数据文件“out.txt存放未查找到的 信息。4) 查找到相关信息时显示、地址、 号码。3、 初步测试方案1) 从数据文件“old.txt中读入各项记录，或由系统随机产生各记录，并且把记录保存到“new.txt中 。2) 分别采用伪随机探测再散列法和再哈希法解决冲突。3) 根据查找时显示给定用户的记录。4) 根据 号码查找时显示给定 号码的用户记录。5) 将没有查找的结果保存到结果文件Out.txt中。6) 系统以菜单界面工作，运行界面友好，演示程序以用户和

3、计算机的对话方式进行。三概要设计1、 子函数功能int Collision_Random(int key,int i) /伪随机数探量观测再散列法处理冲突void Init_HashTable_by_name(string name,string phone,string address)/以为关键字建立哈希表int Collision_Rehash(int key,string str) /再哈希法处理冲突void Init_HashTable_by_phone(string name,string phone,string address)/以 号码为关键字建立哈希表void Outfil

4、e(string name,int key) /在没有找到时输出未找到的记录，翻开文件out.txt并将记录储存在文档中void Outhash(int key) /输出哈希表中的记录void Rafile()/随机生成数据，并将数据保存在new.txtvoid Init_HashTable(char*fname,int n)/建立哈希表int Search_by_name(string name)/根据查找哈希表中的记录int Search_by_phone(string phone)/根据 号码查找哈希表中的记录2、 函数调用图四详细设计1、 主函数流程图2、 “伪随机探测再散列处理冲突伪

5、代码假设对应位置上已经存在其他数据，那么新的关键字=原关键字+伪随机数%哈希表长。假设新的位置上也存在其他数据，那么用伪随机序列的下一个数求新的关键字，直到找到适宜的位置。3、 “再哈希法处理冲突伪代码用“折叠法将 号码的ASCII码值定义为关键字，分别为前四位、中四位、后三位。再用“除留余数法求的新的关键字=原关键字%哈希表长。4、 “以为关键字建立哈希表伪代码用“除留余数法将的ASCII码值定义为关键字。假设对应位置上存在其他数据，那么调用伪随机处理冲突，然后将数据存入哈希表。5、 “以 号码为关键字建立哈希表伪代码用“除留余数法将 号码的ASCII码值定义为关键字。假设对应位置上存在其他

6、数据，那么调用再哈希处理冲突。然后将数据存入哈希表。五调试分析1、程序的关键是掌握文件的相关操作、哈希函数的创立和运用、伪随机法处理冲突、再哈希法处理冲突等。在编程的过程中，出现了很多问题，如文件无法正常翻开、程序进入死循环、无法实现文件的写入操作、忘了添加头文件等错误。修改后程序运行正确。2、创立“new.txt内容用子函数来实现，但是原数据是从“old.txt文件中读取的，刚开始不知道怎样实现二者之间的选择，在同学和参考书的帮助下终于得到解决。3、关于伪随机和再哈希的相关内容觉得很难懂，看了很久参考书才有所了解六测试结果1、 根据查找1) 查找成功2) 查找失败3) 哈希表2、 根据 号码

7、查找1) 号码输入错误2) 号码查询成功3) 号码查询失败4) 哈希表七用户使用说明1、 选择数据来源根据提示信息进行操作，选择已存在的“old.txt文件中的数据或系统当前自动生成的“new.txt文件。2、 选择查找方式根据提示信息进行操作，选择“根据查找或“根据 号码查找两种查找方式。 3、 选择功能根据提示信息进行操作，选择输入信息或查看哈希表。4、 显示结果5、 查看文件八课程设计总结1、 收获学会了C+的跟踪。更进一步了解和熟悉了关于哈希表的运用和文件的读取与写入操作。同时锻炼了对话形式的菜单的创立和熟练运用。2、 心得体会在这次数据结构设计中遇到了很多实际性的问题，在实际设计中才

8、发现，书本上理论性的东西与在实际运用中的还是有一定的出入的，所以有些问题要不断地更正以前的错误思维。通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的典范。我觉得作为一名计科专业的学生，这次课程设计是很有意义的。更重要的是如何把自己平时所学的东西应用到实际中。虽然自己对于这门课懂的并不多，很多根底的东西都还没有很好的掌握，觉得很难，也没有很有效的方法通过自身去理解，但是靠着学习，渐渐对这门课逐渐产生了些许的兴趣，自己开始主动学习并逐步从根底慢慢开始弄懂它。附录：源程序#include <fstream&

9、gt;#include <iostream>#include <string>using namespace std;ifstream in_file;ofstream out_file;int D10=1,3,5,8,13,15,17,21,27,34;/伪随机数序列int count;/当前数据元素个数int sizeindex;/哈希表的长度char *sign;/冲突的标志struct Datastring name;string phone;string address; Data *intermediate_data;int Collision_Random

10、(int key,int i)/伪随机数探量观测再散列法处理冲突int Re_key;if(signkey='1')Re_key=(key+Di)%sizeindex;return Re_key;/归回新的要害码return -1;void Init_HashTable_by_name(string name,string phone,string address)/以为关键字建立哈希表int i=0;int key;char*p;for(key=0,p=&name0;*p;p+)key=key+*p;key=key%42;while(signkey='1

11、9;)key=Collision_Random(key,i+1);if(key=-1) exit(1);count+;intermediate_=name;/将数据存入哈希表intermediate_datakey.address=address;intermediate_datakey.phone=phone;signkey='1'/设置冲突标志int Collision_Rehash(int key,string str)/再哈希法处理冲突int Re_key;int num1=(str0-'0')*1000+(str1-'0

12、')*100+(str2-'0')*10+(str3-'0');int num2=(str4-'0')*1000+(str5-'0')*100+(str6-'0')*10+(str7-'0');int num3=(str8-'0')*100+(str9-'0')*10+(str10-'0');Re_key=num1+num2+num3;Re_key=(Re_key+key)%sizeindex;return Re_key;void Init_H

13、ashTable_by_phone(string name,string phone,string address)/以 号码为关键字建立哈希表int key;char*p;for(key=0,p=&phone0;*p;p+)key=key+*p;key=key%42;while(signkey='1')key=Collision_Rehash(key,phone);count+;intermediate_=name;intermediate_datakey.address=address;intermediate_datakey.phone=p

14、hone;signkey='1'void Outfile(string name,int key)/在没有找到时输出未找到的记录，翻开文件out.txt并将记录储存在文档中if(key=-1)|(signkey='0')out_file.open("out.txt");if(out_file.fail() cout<<"n"<<"文件翻开失败!n"<<endl;exit(1);out_file<<name<<endl;out_file.clos

15、e();void Outhash(int key)/输出哈希表中的记录unsigned i;if(key=-1)|(signkey='0')cout<<"n"<<"无此记录!n"<<endl;elsefor(i=0;i<strlen(&(intermediate_0);i+)cout<<intermediate_i;for(i=0;i<8;i+)cout<<" "cout<<int

16、ermediate_datakey.phone;for(i=0;i<8;i+)cout<<" "cout<<intermediate_datakey.address<<endl;void Rafile()/随机生成数据，并将数据保存在new.txtint i,j;out_file.open("new.txt");if(out_file.fail()cout<<"n"<<"文件翻开失败!n"<<endl;exit(1);for(j=0;j&

17、lt;30;j+)string name=""for(i=0;i<20;i+)name+=rand()%26+'a'out_file<<name<<" "string phone=""for(i=0;i<11;i+)phone+=rand()%10+'0'out_file<<phone<<" "string address=""for(i=0;i<29;i+)address+=rand()%26+&

18、#39;a'address+=','out_file<<address<<endl; out_file<<"*"out_file.close();void Init_HashTable(char*fname,int n)/建立哈希表string name=""string phone=""string address=""int i,j;in_file.open(fname);if(in_file.fail()cout<<"n&quo

19、t;<<"文件翻开失败!n"<<endl;exit(1);while(!in_file.eof()char* str=new char100;name=""phone=""address=""in_file.getline(str,100,'n');/按行读入数据if(str0='*')/判断数据结束break;i=0;while(stri<=97|stri>=122)i+;for(;stri!=' 'i+)name+=stri;w

20、hile(stri=' ')i+;for(j=0;stri!=' 'j+,i+)phone+=stri;while(stri=' ')i+;for(j=0;stri!=','j+,i+)address+=stri;if(n=1)Init_HashTable_by_name(name,phone,address);/以为关键字else Init_HashTable_by_phone(name,phone,address);/以 号码为关键字delete str;in_file.close();int Search_by_name(s

21、tring name)/根据查找哈希表中的记录int i=0;int j=1;int key;char*p;for(key=0,p=&name0;*p;p+)key=key+*p;key=key%42;while(signkey='1'&&(intermediate_!=name)key=Collision_Random(key,i+1);j+;if(j=count)return -1;return key;int Search_by_phone(string phone)/根据 号码查找哈希表中的记录int key;char*p

22、;for(key=0,p=&phone0;*p;p+)key=key+*p;key=key%42;int j=1;while(signkey='1'&&(intermediate_datakey.phone!=phone)key=Collision_Rehash(key,phone);j+;if(j=count)return-1;return key;void main()count=0;sizeindex=50;int i,k;int ch;char *Fname;sign=new charsizeindex;intermediate_data=new

23、 Datasizeindex;for(i=0;i<sizeindex;i+)signi='0'signi='0'for(i=0;i<sizeindex;i+)intermediate_=""intermediate_datai.phone=""intermediate_datai.address="" cout<<"§*§"<<endl;cout<<"§* *§&qu

24、ot;<<endl;cout<<"§* 请选择用于查找的数据来源 *§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 1 . old.TXT *§"<<endl;cout<<"§* 2 . 随 机 生 成 *§"<<endl;cout<<"§* 0 . 退 出 程 序 *

25、§"<<endl; cout<<"§*§"<<endl; docout<<"n"<< " 请输入选择 : n" cin>>k;switch(k)case 0:return;case 1:Fname="old.txt"break;case 2:Rafile();Fname="new.txt"break; default:cout<<"输入序号有误，请重新输入!n&q

26、uot;<<endl;while(k!=1)&&(k!=2)&&(k!=0); /system("cls"); cout<<"§*§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 请 选 择 查 找 方 式 *§"<<endl;cout<<"§* *§"<&

27、lt;endl;cout<<"§* 1 . 根 据 姓 名 查 找 *§"<<endl;cout<<"§* 2 . 根 据 电 话 号 查 找 *§"<<endl;cout<<"§* *§"<<endl; cout<<"§*§"<<endl;docout<<"n"<< " 请输入选择 :

28、n" cin>>ch;if(ch!=1&&ch!=2)cout<<" 输入序号有误，请重新输入!n"<<endl;while(ch!=1)&&(ch!=2); /system("cls");Init_HashTable(Fname,ch);while(ch=1)int choice;cout<<"§*§"<<endl;cout<<"§* *§"<<en

29、dl;cout<<"§* 请 选 择 功 能 *§"<<endl; cout<<"§* *§"<<endl;cout<<"§* 1 . 输 入 姓 名 查 找 数 据 *§"<<endl;cout<<"§* 2 . 显 示 哈 希 表 *§"<<endl;cout<<"§* 0 . 退 出 程 序! *

30、7;"<<endl;cout<<"§* *§"<<endl; cout<<"§*§"<<endl;docout<<"n"<< " 请输入选择 : n"cin>>choice; switch(choice) case 1:int key1;string name;cout<<"n"<<" 请输入: n"cin&

31、gt;>name;key1=Search_by_name(name);Outfile(name,key1); cout<<"n"<<"查找结果:n"<<endl;Outhash(key1);break;case 2: cout<<"n"<<" 哈希表: n"<<endl;for(i=0;i<sizeindex;i+)if(signi!='0')cout<<"* " Outhash(i)

32、; cout<<"* *"<<endl;break;case 0:return; default:cout<<" 输入序号有误，请重新输入!n"<<endl; while(choice!=1)&&(choice!=2)&&(choice!=0);while(ch=2)int choice;cout<<"§*§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 请 选 择 功 能 *§"<<endl;cout<<"§* 1 . 输 入 电 话 查 找 数 据 *§"<<endl;cout<&l