电话号码查找系统

1、目录问题提出1目的1问题描述 1基本要求 1问题分析 1功能2输出形式2数据结构设计2算法设计2主要函数3伪随机探测再散列处理冲突3再哈希法处理冲突3以姓名为关键字建立哈希表3以电话号码为关键字建立哈希表3测试分析3总结4参考文献4附录4一、 问题提出(一) 目的巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析）；提高利用计算机分析解决综合性实际问题的基本能力。(二) 问题描述设计哈希表实现电话号码查找系统。(三) 基本要求1. 每个记录有下列数据项：电话号码、用户名、地址。2.

2、 从键盘输入各记录，分别以电话号码和用户名为关键字设计哈希表；采用不同的哈希函数，比较冲突率。3. 采用适当的方法解决冲突；在哈希函数确定的前提下，尝试不同类型处理冲突的方法，考察平均查找长度的变化。4. 查找并显示给定号码的记录。5. 查找并显示给定用户名的记录。每个单词仅由大写的英文字符组成长度不超过63个字符。6. 对算法要分析，要说明正确性或近似性能。二、 问题分析利用哈希表记录：电话号码、用户名、地址。通过判断来进行相关的增加记录、查询记录、姓名号码排序、清空、退出等操作。1. 功能：读取数据：读取电话本存储的电话信息；读取系统随机新建电话本存储的电话信息查找信息根据电话号码查询用户

3、信息。根据姓名查询用户信息。存储信息查询无记录的结果存入记录文档。2. 输出形式数据文件“old.txt”存放原始电话号码数据。数据文件“new.txt”存放有系统随机生成的电话号码文件。数据文件“out.txt”存放未查找到的电话信息。查找到相关信息室显示姓名、地址、电话号码。将没有查找的结果保存到结果文件out.txt中。系统以菜单界面工作，运行界面友好。三、 数据结构设计四、 算法设计主要函数：IntCollision_Random(intkey,inti)/伪随机数探量观测再散列法处理冲突Void Inint_HashTable_by_name(string name,string,p

4、hone,stringaddress)/以姓名为关键字建立哈希表intCollision_Rehash(intkey,stringstr)/再哈希法处理冲突void Init_HashTable_by_phone(string name,stringphone,string address)/以电话号码为关键字建立哈希表voidOutfile(string name,int key)/在没有找到时输出未找到的记录，打开文件out.txt并将记录存储在文档中Void Outhash(int key)/输出哈希表中的记录Void Rafile()/随机生成数据，并将数据保存在new.txtVoid

5、 Init_hashTable(char*fname,int n)/根据姓名查找哈希表在的记录伪随机探测再散列处理冲突若对应位置已经存在其他数据，则新的关键字=（原关键字+伪关键字）%哈希表的长若新位置上也存在其他数据，则用伪随序列的下一个数求新的关键字，直到找到合适的位置。再哈希法处理冲突用“折叠法”将电话号码的ASCII码值定义为关键字，分别为前四位、中间四位、后四位。再用“除留余数法”求的新关键字=原关键字%哈希表长。以姓名为关键字建立哈希表用“除留余数法”将姓名的ASCII码值定义为关键字。若对应位置上也存在其他数据，则调用伪随机处理冲突。然后将数据存入哈希表。以电话号码为关键字建立哈

6、希表用“除留余数法”将电话号码的ASCII码值定义为关键字。若对应位置上也存在其他数据，则调用再哈希处理冲突。然后将数据存入哈希表。五、 测试分析1. 程序的关键是掌握文件的相关操作、哈希函数的创建和运用、伪随机法处理冲突、再哈希法处理冲突等。2. 创建“new.txt”用子函数来实现，但是原数据是从“old.txt”文件中读取的。3. 调试出现了很多bug解决他们还是花了大量时间的。姓名查找：哈希表根据电话号码查询哈希表选择数据来源选择查找方式选择功能显示结果六、 总结通过这次的设计自己学到了很多知识，更加熟悉了哈希表的运用和文件的读取。在这个设计的过程中遇到了很多头疼的事情，通过自己的努力

7、解决这些还是很有收获的。在这次设计在我发现理论和实践还是有一定差距的。只要自己认真努力就会解决你遇到的问题。七、 参考文献网络资源、数据结构八、 附录#include <fstream>#include <iostream>#include <string>Using namespace qin;Ifstreamin_file;Ofstreamout_file;Int D10=1,3,5,8,13,15,17,21,27,34;Int count ;/当前数组元素个数Intsizeindex;/哈希表长度Char *sign;/冲突标价StructDataS

8、tring name;stringphone;string address;Data *intermediate_data;IntCollision_Random(intkey,inti)/伪随机探测再散列处理冲突IntRe_key;If(signkey=1)Re_key=(key+Di)%sizeindex;Return Re_key;Return -1;Void Init_HashTable_by_name(string name,stringphone,stringaddress)Inti=0;intkey;char*p;For(key=0,p=&name0;*p;p+)Key=

9、key+*p;Key=key%42;While(signkey=1)Key=Collision_Random(key,i+);If(key=-1)Exit(1);Count+;Intermediate_=name;Intermediate_datakey.address=address;Intermediate_datakey.phone=phone;Signkey=1;IntCollision_Rehash(intkey,stringstr)IntRe-key;Intnum1=(str0-0)*1000+(str1-0)*100+(str2-0)*10+(str3-0

10、);Intnum2=(str4-0)*1000+(str5-0)*100+(str6-0)*10+(str7-0);Intnum3= (str9-0)*100+(str10-0)*10+(str1-0);Re_key=(Re_key+key)%sizeindex;Return Re_key;Void Init_HashTable_by_hone(string name,stringphone,string address)Intkey;char*p;key=key%42While(sizekey=1)Key=Collision_Rehash(key,phone);Count+;Intermed

11、iate_=name;Intermediate_datakey.address=address;Intermediate_datakey.phone=phone;Signkey=1;Void Outfile(string name,int key)If(key=-1|(signkey=0)Out_file.open(“out.txt”);If(out_file.fail()Count<<”n”<<”文件打开失败！n”<<endl;Exit(1);Oyt_file<<name<<endl;Out_file.clo

12、se();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<<intermediate_datakey.phone;For(i=0;i<8;i+)Cout<

13、<”;Cout<<intermediate_datakey.address<<endl;Void Rafile()IntI,j;Out_file.open(“new.txt”);If(out_file.fail()Cout<<”n”<<”文件打开失败！n”<<endl;Exit(1);For(j=0;j<30;j+)String name=”;For(i=0;i<20;i+)name+=rand()%26+1Out_file<<name<<”;String phone=”;For(i=0;I&

14、lt;11);i+Phone+rand()%10+0;Out_file<<phone<<”;String address=”;For(i-0;i<29;i+)address+=rand()%26+a;Address+=,;Out_file<<address<<endl;Out_file<<”*”;Out_file.close();Void Int_HashTable(char*fname,int n)String name=”;String phone=”;String address=”;IntI,j;In_file.open

15、(fname);If(in_file.fail()Cout<<”n”<<”文件打开失败！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;While(stri=)i+;For(j=0;stri=,;j+,i+)Address+=str

16、i;If(n=1)Int_HashTable_by_name(name,phone,address);Else Init_HashTable_by_phone(name,phone,address);Delete str;In_file.close();IntSearch_by_name(string name)Inti=0;int j=1;Int key;Char*p;Key=key%42;While(signkey=1&&(intermediate_!=name)Key=Collision_Random(key,i+);J+;If(j=count)r

17、eturn -1;Return key;IntSearch_by_phone(string phone)Intkey;char*p;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;intch;

18、char *Fname;Sign=new charsizeindex;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<<”&*&”<<endl;Cout<<”&请选择用于查找的数据源&”<

19、<endl;Cout<<”&*&”<<endl;Cout<<”&1.old.txt&”<<endl;Cout<<”&2.随机生成&”<<endl;Cout<<”&0.退出程序&”<<endl;Cout<<”&*&”<<endl;DoCount<<”n”<<”请输入选择：n”;cin>>k;switch(k)case 0:return;case 1:Fnam

20、e=”old.txt”;break;case 2:Rafile();Fname=”new.txt”;btrak;default:cout<<”输入序号有误，请重新输入！n”<<endl;While(k!=1)&&(k!=2)&&(k!=0);Cout<<”&*&”<<endl;Cout<<”&*&”<<endl;Cout<<”&请选择查找方式&”<<endl;Cout<<”&*&”<&l

21、t;endl;Cout<<”&1.根据姓名查找&”<<endl;Cout<<”&2.根据电话号码查找&”<<endl;Cout<<”&*&”<<endl;DoCount<<”n”<<”请输入选择：n”;cin>>ch;If(ch!=1&&ch!=2)cout<<”输入序号有误，请重新输入！n”<<endl;While(ch!=1)&&ch!=2);Init_Hash(Fname,ch)

22、;While(ch=1)Int choice;Cout<<”&*&”<<endl;Cout<<”&*&”<<endl;Cout<<”&请选择功能&”<<endl;Cout<<”&1.输入姓名查找数据&”<<endl;Cout<<”&2.显示哈希表&”<<endl;Cout<<”&3.退出查找！&”<<endl;DoCout<<”n”<<

23、;”请选择输入：n”;cin>>choice;Switch(choice)Case 1:Intkey1;string name;Cout<<”n”<<”请输入姓名：n”;cin>>name;key1=Search_by_name(name);Outfile(name,key1);Cout<<”n”<<”查找结果：n”<<endl;outhash(keyl);Break;Case 2:Cout<<”n”<<”哈希表：n”<<endl;For(i=0;i<sizeindex

24、;i+)If(signi!=0)Count<<”*”;Outhash(i);Count<<”*”<<endl;Break;Case 0:return;Defaule;Cout<<”输入序号有误，请重新输入！n”<<endl;While(choice!=1)&&(choice!=2)&&(choice!=0);While(ch=2)Intchoice;Cout<<”&*&”<<endl;Cout<<”&*&”<<endl;Cout<<”&请选择功能&”<<endl;Cout<<”&1.输入