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

...wd......wd......wd...哈希表实现号码查询系统一目的利用?数据构造?课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进展程序设计，并标准地完成课程设计报告。通过课程设计，稳固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法〔包括问题描述、系统分析、设计建模、代码实现、结果分析等〕；提高利用计算机分析解决综合性实际问题的基本能力。二需求分析程序的功能读取数据读取原本存储的信息。读取系统随机新建本存储的信息。查找信息根据号码查询用户信息。根据姓名查询用户信息。存储信息查询无记录的结果存入记录文档。输出形式数据文件“old.txt〞存放原始号码数据。数据文件“new.txt〞存放有系统随机生成的号码文件。数据文件“out.txt〞存放未查找到的信息。查找到相关信息时显示姓名、地址、号码。初步测试方案从数据文件“old.txt〞中读入各项记录，或由系统随机产生各记录，并且把记录保存到“new.txt〞中。分别采用伪随机探测再散列法和再哈希法解决冲突。根据姓名查找时显示给定姓名用户的记录。根据号码查找时显示给定号码的用户记录。将没有查找的结果保存到结果文件Out.txt中。系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进展。三概要设计子函数功能intCollision_Random(intkey,inti)//伪随机数探量观测再散列法处理冲突voidInit_HashTable_by_name(stringname,stringphone,stringaddress)//以姓名为关键字建设哈希表intCollision_Rehash(intkey,stringstr)//再哈希法处理冲突voidInit_HashTable_by_phone(stringname,stringphone,stringaddress)//以号码为关键字建设哈希表voidOutfile(stringname,intkey)//在没有找到时输出未找到的记录，翻开文件out.txt并将记录储存在文档中voidOuthash(intkey)//输出哈希表中的记录voidRafile()//随机生成数据，并将数据保存在new.txtvoidInit_HashTable(char*fname,intn)//建设哈希表intSearch_by_name(stringname)//根据姓名查找哈希表中的记录intSearch_by_phone(stringphone)//根据号码查找哈希表中的记录函数调用图四详细设计主函数流程图“伪随机探测再散列处理冲突〞伪代码假设对应位置上已经存在其他数据，那么新的关键字=〔原关键字+伪随机数〕%哈希表长。假设新的位置上也存在其他数据，那么用伪随机序列的下一个数求新的关键字，直到找到适宜的位置。“再哈希法处理冲突〞伪代码用“折叠法〞将号码的ASCII码值定义为关键字，分别为前四位、中四位、后三位。再用“除留余数法〞求的新的关键字=原关键字%哈希表长。“以姓名为关键字建设哈希表〞伪代码用“除留余数法〞将姓名的ASCII码值定义为关键字。假设对应位置上存在其他数据，那么调用伪随机处理冲突，然后将数据存入哈希表。“以号码为关键字建设哈希表〞伪代码用“除留余数法〞将号码的ASCII码值定义为关键字。假设对应位置上存在其他数据，那么调用再哈希处理冲突。然后将数据存入哈希表。五调试分析1、程序的关键是掌握文件的相关操作、哈希函数的创立和运用、伪随机法处理冲突、再哈希法处理冲突等。在编程的过程中，出现了很多问题，如文件无法正常翻开、程序进入死循环、无法实现文件的写入操作、忘了添加头文件等错误。修改后程序运行正确。2、创立“new.txt〞内容用子函数来实现，但是原数据是从“old.txt〞文件中读取的，刚开场不知道怎样实现二者之间的选择，在同学和参考书的帮助下终于得到解决。3、关于伪随机和再哈希的相关内容觉得很难懂，看了很久参考书才有所了解六测试结果根据姓名查找姓名查找成功姓名查找失败哈希表根据号码查找号码输入错误号码查询成功号码查询失败哈希表七用户使用说明选择数据来源根据提示信息进展操作，选择已存在的“old.txt〞文件中的数据或系统当前自动生成的“new.txt〞文件。选择查找方式根据提示信息进展操作，选择“根据姓名查找〞或“根据号码查找〞两种查找方式。选择功能根据提示信息进展操作，选择输入信息或查看哈希表。显示结果查看文件八课程设计总结收获学会了C++的跟踪。更进一步了解和熟悉了关于哈希表的运用和文件的读取与写入操作。同时锻炼了对话形式的菜单的创立和熟练运用。心得体会在这次数据构造设计中遇到了很多实际性的问题，在实际设计中才发现，书本上理论性的东西与在实际运用中的还是有一定的出入的，所以有些问题要不断地更正以前的错误思维。通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的典范。我觉得作为一名计科专业的学生，这次课程设计是很有意义的。更重要的是如何把自己平时所学的东西应用到实际中。虽然自己对于这门课懂的并不多，很多根基的东西都还没有很好的掌握，觉得很难，也没有很有效的方法通过自身去理解，但是靠着学习，渐渐对这门课逐渐产生了些许的兴趣，自己开场主动学习并逐步从根基慢慢开场弄懂它。附录：源程序#include<fstream>#include<iostream>#include<string>usingnamespacestd;ifstreamin_file;ofstreamout_file;intD[10]={1,3,5,8,13,15,17,21,27,34};//伪随机数序列intcount;//当前数据元素个数intsizeindex;//哈希表的长度char*sign;//冲突的标志structData{ stringname; stringphone; stringaddress;};Data*intermediate_data;intCollision_Random(intkey,inti)//伪随机数探量观测再散列法处理冲突{ intRe_key; if(sign[key]=='1') { Re_key=(key+D[i])%sizeindex; returnRe_key;//归回新的要害码 } return-1;}voidInit_HashTable_by_name(stringname,stringphone,stringaddress)//以姓名为关键字建设哈希表{ inti=0; intkey; char*p; for(key=0,p=&name[0];*p;p++) key=key+*p; key=key%42; while(sign[key]=='1') { key=Collision_Random(key,i+1); } if(key==-1) exit(1); count++; intermediate_data[key].name=name;//将数据存入哈希表 intermediate_data[key].address=address; intermediate_data[key].phone=phone; sign[key]='1';//设置冲突标志}intCollision_Rehash(intkey,stringstr)//再哈希法处理冲突{ intRe_key; intnum1=(str[0]-'0')*1000+(str[1]-'0')*100+(str[2]-'0')*10+(str[3]-'0'); intnum2=(str[4]-'0')*1000+(str[5]-'0')*100+(str[6]-'0')*10+(str[7]-'0'); intnum3=(str[8]-'0')*100+(str[9]-'0')*10+(str[10]-'0'); Re_key=num1+num2+num3; Re_key=(Re_key+key)%sizeindex; returnRe_key;}voidInit_HashTable_by_phone(stringname,stringphone,stringaddress)//以号码为关键字建设哈希表{ intkey; char*p; for(key=0,p=&phone[0];*p;p++) key=key+*p; key=key%42; while(sign[key]=='1') { key=Collision_Rehash(key,phone); } count++; intermediate_data[key].name=name; intermediate_data[key].address=address; intermediate_data[key].phone=phone; sign[key]='1';}voidOutfile(stringname,intkey)//在没有找到时输出未找到的记录，翻开文件out.txt并将记录储存在文档中{ if((key==-1)||(sign[key]=='0')) { out_file.open("out.txt"); if(out_file.fail()) { cout<<"\n"<<"文件翻开失败!!!\n"<<endl; exit(1); } out_file<<name<<endl; out_file.close(); }}voidOuthash(intkey)//输出哈希表中的记录{ unsignedi; if((key==-1)||(sign[key]=='0')) { cout<<"\n"<<"无此记录!!!\n"<<endl; } else { for(i=0;i<strlen(&(intermediate_data[key].name[0]));i++) cout<<intermediate_data[key].name[i]; for(i=0;i<8;i++) cout<<""; cout<<intermediate_data[key].phone; for(i=0;i<8;i++) cout<<""; cout<<intermediate_data[key].address<<endl; }}voidRafile()//随机生成数据，并将数据保存在new.txt{ inti,j; out_file.open("new.txt"); if(out_file.fail()) { cout<<"\n"<<"文件翻开失败!!!\n"<<endl; exit(1); } for(j=0;j<30;j++) { stringname=""; for(i=0;i<20;i++) name+=rand()%26+'a'; out_file<<name<<""; stringphone=""; for(i=0;i<11;i++) phone+=rand()%10+'0'; out_file<<phone<<""; stringaddress=""; for(i=0;i<29;i++) address+=rand()%26+'a'; address+=','; out_file<<address<<endl; }out_file<<"*"; out_file.close();}voidInit_HashTable(char*fname,intn)//建设哈希表{ stringname=""; stringphone=""; stringaddress=""; inti,j; in_file.open(fname); if(in_file.fail()) { cout<<"\n"<<"文件翻开失败!!!\n"<<endl; exit(1); } while(!in_file.eof()) { char*str=newchar[100]; name=""; phone=""; address=""; in_file.getline(str,100,'\n');//按行读入数据 if(str[0]=='*')//判断数据完毕 break; i=0; while(str[i]<=97||str[i]>=122) i++; for(;str[i]!='';i++) name+=str[i]; while(str[i]=='') i++; for(j=0;str[i]!='';j++,i++) phone+=str[i]; while(str[i]=='') i++; for(j=0;str[i]!=',';j++,i++) address+=str[i]; if(n==1) Init_HashTable_by_name(name,phone,address);//以姓名为关键字 elseInit_HashTable_by_phone(name,phone,address);//以号码为关键字 deletestr; } in_file.close();}intSearch_by_name(stringname)//根据姓名查找哈希表中的记录{ inti=0;intj=1; intkey; char*p; for(key=0,p=&name[0];*p;p++) key=key+*p; key=key%42; while(sign[key]=='1'&&(intermediate_data[key].name!=name)) { key=Collision_Random(key,i+1); j++; if(j=count) return-1; } returnkey;}intSearch_by_phone(stringphone)//根据号码查找哈希表中的记录{ intkey; char*p; for(key=0,p=&phone[0];*p;p++) key=key+*p; key=key%42; intj=1; while(sign[key]=='1'&&(intermediate_data[key].phone!=phone)) { key=Collision_Rehash(key,phone); j++; if(j=count) return-1; } returnkey;}voidmain(){ count=0; sizeindex=50; inti,k; intch; char*Fname; sign=newchar[sizeindex]; intermediate_data=newData[sizeindex]; for(i=0;i<sizeindex;i++) sign[i]='0'; sign[i]='\0'; for(i=0;i<sizeindex;i++) { intermediate_data[i].name=""; intermediate_data[i].phone=""; intermediate_data[i].address=""; } cout<<"§**********************************************************§"<<endl; cout<<"§**§"<<endl; cout<<"§*请选择用于查找的数据来源*§"<<endl; cout<<"§**§"<<endl; cout<<"§*1.old.TXT*§"<<endl; cout<<"§*2.随机生成*§"<<endl; cout<<"§*0.退出程序*§"<<endl;cout<<"§**********************************************************§"<<endl;do { cout<<"\n"<<"请输入选择:\n"; cin>>k; switch(k) { case0: return; case1: Fname="old.txt"; break; case2: Rafile(); Fname="new.txt"; break;default: cout<<"输入序号有误，请重新输入!!!\n"<<endl; } } while((k!=1)&&(k!=2)&&(k!=0));//system("cls"); cout<<"§**********************************************************§"<<endl; cout<<"§**§"<<endl; cout<<"§*请选择查找方式*§"<<endl; cout<<"§**§"<<endl; cout<<"§*1.根据姓名查找*§"<<endl; cout<<"§*2.根据电话号查找*§"<<endl; cout<<"§**§"<<endl;cout<<"§**********************************************************§"<<endl; do { cout<<"\n"<<"请输入选择:\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) { intchoice; cout<<"§**********************************************************§"<<endl; cout<<"§**§"<<endl; cout<<"§*请选择功能*§"<<endl;cout<<"§**§"<<endl; cout<<"§*1.输入姓名查找数据*§"<<endl; cout<<"§*2.显示哈希表*§"<<endl; cout<<"§*0.退出程序!!!*§"<<endl; cout<<"§**§"<<endl;cout<<"§**********************************************************§"<<endl; do { cout<<"\n"<<"请输入选择:\n"; cin>>choice; switch(choice) { case1: { intkey1; stringname; cout<<"\n"<<"请输入姓名:\n"; cin>>name; key1=Search_by_name(name); Outfile(name,key1);cout<<"\n"<<"查找结果:\n"<<endl; Outhash(key1); } break; case2: {cout<<"\n"<<"哈希表:\n"<<endl; for(i=0;i<sizeindex;i++) { if(sign[i]!='0') { cout<<"*"; Outhash(i); } } cout<<"**"<<endl; } break; case0: return; default: cout<<"输入序号有误，请重新输入!!!\n"<<endl; } } while((choice!=1)&&(choice!=2)&&(choice!=0)); } while(ch==2) { intchoice; cout<<"§**********************************************************§"<<endl; cout<<"§**§"<<endl; cout<<"§*请选择功能*§"<<endl; cout<<"§*1.输入电话查找数据*§"<<endl; cout<<"§*2.显示哈希表*§"<<endl; cout<<"§*0.退出*§"<<endl; cout<<"§*