(完整word版)哈希表实现电话号码查询系统

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

2、录的结果存入记录文档。4) 输出形式1) 数据文件“ old.txt ”存放原始电话号码数据。2) 数据文件“ new.txt ”存放有系统随机生成的电话号码文件。3) 数据文件“ out.txt ”存放未查找到的电话信息。4) 查找到相关信息时显示姓名、地址、电话号码。3、初步测试计划1) 从数据文件“ old.txt ”中读入各项记录，或由系统随机产生各记录，并且把记录保存 至ij "new.txt ”中。2) 分别采用伪随机探测再散列法和再哈希法解决冲突。3) 根据姓名查找时显示给定姓名用户的记录。4) 根据电话号码查找时显示给定电话号码的用户记录。5) 将没有查找的结果保存到

3、结果文件Out.txt中。6) 系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进行。三概要设计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,

4、string address)/以电话号码为关键字建立哈希表void Outfile(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)/根据电话号码查找哈希表

5、中的记录xxxx 大学 xxxx 学院 xxxx 专业学号：xxxxxxx 姓名：jenery6152、函数调用图四详细设计2、“伪随机探测再散列处理冲突”伪代码若对应位置上已经存在其他数据，则新的关键字=（原关键字+伪随机数）%合希表长。若新的位置上也存在其他数据，则用伪随机序列的下一个数求新的关键字，直到找到 合适的位置。3、“再哈希法处理冲突”伪代码用“折叠法”将电话号码的 ASCII码值定义为关键字，分别为前四位、中四位、后三 位。再用“除留余数法”求的新的关键字=原关键字%合希表长。4、 ”以姓名为关键字建立哈希表”伪代码用“除留余数法”将姓名的 ASCII码值定义为关键字。若对应位

6、置上存在其他数据，则调用伪随机处理冲突，然后将数据存入哈希表。5、 “以电话号码为关键字建立哈希表”伪代码用“除留余数法”将电话号码的ASCII码值定义为关键字。若对应位置上存在其他数据，则调用再哈希处理冲突。然后将数据存入哈希表。五调试分析1、程序的关键是掌握文件的相关操作、哈希函数的创建和运用、伪随机法处理冲突、 再哈希法处理冲突等。在编程的过程中，出现了很多问题，如文件无法正常打开、程序进 入死循环、无法实现文件的写入操作、忘了添加头文件等错误。修改后程序运行正确。2、创建“ new.txt ”内容用子函数来实现，但是原数据是从“ old.txt ”文件中读取 的，刚开始不知道怎样实现二

7、者之间的选择，在同学和参考书的帮助下终于得到解决。3、关于伪随机和再哈希的相关内容觉得很难懂，看了很久参考书才有所了解六测试结果1、根据姓名查找1）姓名查找成功序，”请输入选择请输入姓名WUSUOipil查找结果jujizhidaawusuopu*黄"C :UsersliuDe5ktoplxD bu5lx.exe,2）姓名查找失败二 | out.txt - 记事本口 回 I文件但制4D 格式9) 查看国)群助Qjffgfgg* I3) 哈希表2、根据电话号码查找1）电话号码输入错误据数能找 功查表 择话希 选由哈 请人示出输显退 12 0XXXXXXXXXXXXXXXXXXXXXXX

8、XXXKXXXKXXXKXXXKXXXXXXXXXXXXXXXXXXX§* uusuopujizhidao威 ' C:UsersliuDesktoplxDebuglx.exe".口 回据数 能找 功查表 择话希 选由哈 请人示出输显退 12 0MMXMMMXMMMXXMMXXMXXXMXXXMXMXMXMXMXMXMXMXMXMXMXMXMXMXMXMXMM §血 ' C:UsersliuDes ktQplxDebuglx.exe"请输入选择:2XNKXXN苴XXN苴苴XN苴苴XK苴苴XK苴苴苴苴苴苴XKN苴XK

9、N苴XKN苴XKN苴XX&请输入选择：1* 请输入口位的由话号码:343422由话号码输入不正确，请重新输入111* 请输入口位的由话号码;2）电话号码查询成功请输入选择:L* 请输入工工位的由话号码:343422由话号码输入不正确，请重新输入? ?* 请输入工工位的由话号码找结果：3）电话号码查询失败4) 哈希表据数群找 功查表 择话希 选由哈 请人示出输显退 12 0七用户使用说明1、选择数据来源根据提示信息进行操作，选择已存在的“old.txt ”文件中的数据或系统当前自动生成的"new.txt ”文件。2、选择查找方式根据提示信息进行操作，选

10、择“根据姓名查找”或“根据电话号码查找”两种查找方3、选择功能根据提示信息进行操作，选择输入已知信息或查看哈希表。4、显示结果数据结构课程设计xxxx 大学 xxxx 学院 xxxx 专业学号：xxxxxxx 姓名：jenery6195、查看文件ald.txt -记事=文件漏填格式萱看包帮助而|lin Jun jiexinjiapo, liirainminda, zuozhenfengjianshi, lambertAmerican, aisifengchecun.

11、wusuopu suolong baihuzi151714577391388676596013477215986luobingujizhidao, daochang, haizeituan, sahala.xiangjishihaishang, onepieceweizhi, yinhuntucao, lufeihaizeiwang, nameiyurendao, vitasrussia, woailuo 1500

12、7155679 shazh±guoJ luoluohubei, xisuonieren, shujusichuang, jisuanjiaustraliat gaoshuCanada, makes!jape口， xiandaichina, *文件镰婚格式©黄看M整朗业phqghuineaylnlf dxf ire stnrnc y syycqpev ikef fm oejuvpvaboygpoe

13、ylfpb ncbxcoksfzkvatxdknly gzqrcddiuteiojwayyzp izcobzcnfwlqijtvdwvx lotogbgxpeyanfetcuke Ichhbf qmkiniwzobiwybx eeddpszrnavymmtatbdz eqtgjoparmowzdqyoxyt qlrzjpx iogvliexdzuzo Qnjwjmwaxxninsnhhlqqr wkbjzwucwljfrimpmyhc zvfbcgkcfqckcotzgkub iqf1duuveoowqcudhnef toidukuhjzefczzzbfkq tpcclifkeljytihrc

14、qay hfosqvlqfxwwkmfitdyyg nayxqkqoyzwmyubzazcp rarxsvkhtqdihersigbh pknfpfycgfieowqrwwwp cgfmz kg ipdf odkjni jqwi my jf jnhhssqctydteaind 1whypnvrui hoswk ifygt mtpjhaefQzaauldrchjc oqy1obcwqkkzmaus jgmh jomonxrqyjzginrnnzwa xfdmvzcautdcckxaaydz wrxbsjaqrlxvobtwhxgin elsotfIbgsfnpcuzsru/p>

15、 93446066184 77335998182 96510996834 92461821197 97693576658 75812574444 10675004549 40260611173 71916272765 63652810315 96177190341 35526892959 63565839483 51760024336 5389287014849460362458 87816095890 5574734088154442504212 01260546793 0373959丫202 09722829448 09891733076 60129385156

16、61762534075 83112576216 70152290518 21835714768qduxwfnfosvsrtkjprepggxrpnrvy, renzkycxfxtlsgypsfadpooefxzbc, my ehwq n qrqpmx u j j 1 oo vaowux whtn s, ku f nuxx zrz burning qooke tly hnkoau, gubfaaovlzy1ntrkdcpwsrtesjwhd, gbusbmborzt1hesmpxohgmgnkeufd. ekjdqzj enpevqgx iepjsrdzjazuj1, tekmqdcyzjeeu

17、hmsrqcozijipfionr suacbazuxmhecthlegrpunkdmbppfl, rjbxphoohpkwqyuhrqzhnbnfuvqnqf zmzpowkj ilefraamdigpnpuuhgiip, tnzxugldsmzcnockvfajfrmxotho, gfebceyhjugixwtbvtrehbbcpx ifb, free fws jrx j hguz yup zwwe i Qiirp i z, kuiduburiswtbrecuykabfcvkdzea, dhthxdjgkjeIrIpaxamceroswitdp, dyyhn gy c drudmphni

18、e c kot rwospof gf odk jghcwnibnDtrniliu.yfyQgajqk.cklz, uypurfmbisgekyrgzvxdhpoamvafyf nar aewkeg jcc vhhr j vb jtsqdj exit g, pxnvjiupalyynmkiiinuvklhsecdwra, uzwyvi jgful Ik jduhs jafbtlkinfqr, i?ragc jwlgrsmeaearw'tvjs jbaoio j, wzmtgonz11 j hgau hn ihreqgj fwkjs, yeegfivdrcygurqdredakubnfgu

19、pr, kamhurktrffacIvgrzkkldacllteo, zrfusew j tbox vy nf hkstcenaiunndd, vvpjgojog1mkxgbfcpypckqchbddz, jugwwbsqfcihubs jollmsqsEhincphj griwniqxdfjpwpxfblkpnpee1fjmt.八课程设计总结1、收获学会了 C+的跟踪。更进一步了解和熟悉了关于哈希表的运用和文件的读取与写入操 作。同时锻炼了对话形式的菜单的创建和熟练运用。2、心得体会在这次数据结构设计中遇到了很多实际性的问题，在实际设计中才发现，书本上理论 性的东西与在实际运用中的还是有一定

20、的出入的，所以有些问题要不断地更正以前的错误 思维。通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意 义，学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的榜样。我觉得 作为一名计科专业的学生，这次课程设计是很有意义的。更重要的是如何把自己平时所学 的东西应用到实际中。虽然自己对于这门课懂的并不多，很多基础的东西都还没有很好的 掌握，觉得很难，也没有很有效的办法通过自身去理解，但是靠着学习，渐渐对这门课逐 渐产生了些许的兴趣，自己开始主动学习并逐步从基础慢慢开始弄懂它。数据结构课程设计xxxx 大学 xxxx 学院 xxxx 专业学号：xxxxxxx 姓名：j

21、enery637附录：源程序#include <fstream>#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 *int

22、ermediate_data;int Collision_Random(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+*

23、p;key=key%42;while(signkey='1') 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-

24、'0')*1000+(str1-'0')*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)%sizei

25、ndex;return Re_key;以电void Init_HashTable_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=addre

26、ss;intermediate_datakey.phone=phone;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<<nam

27、e<<endl;out_file.close();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<<

28、""cout<<intermediate_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"<

29、<endl;exit(1);for(j=0;j<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+=randO%10+'0'out_file<<phone<<""string address=""for(i=0;i<29

30、;i+)address+=rand()%26+'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()c

31、out<<"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(;

32、stri!=' 'i+) name+=stri; while(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);/以电话号码为关键字de

33、lete str;in_file.close();int Search_by_name(string 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_

34、by_phone(string phone)/根据电话号码查找哈希表中的记录int key;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;int ch;char

35、 *Fname;sign=new charsizeindex;intermediate_data=new 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<<"*§ "<

36、;<endl;cout<<" § * § "<<endl;* § "<<endl;* § "<<endl;* § "<<endl;* § "<<endl;cout<<" § *cout<<" § *cout<<" § *cout<<" § *cout<<&quo

37、t; § *请选择用于查找的数据来源1 . old.TXT2 .随机生成0 .退出程序* § "<<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;def

38、ault:!n"<<endl;cout<<"输入序号有误，请重新输入while(k!=1)&&(k!=2)&&(k!=0);/system("cls");cout<<"* tS "<<endl;cout<<":§*一§ "<<endl;cout<<"§*请选择* tS "<<endl;cout<<":§*一&

39、#167; "<<endl;cout<<"§*1 .根据一§ "<<endl;cout<<"§*2 .根据*§ "<<endl;找方式名查找话号查找cout<<" § * § "<<endl;cout<<"*§ "<<endl;docout<<"n"<< "请输入选择：n&qu

40、ot;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 <<" § * § "<<endl;cout

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

42、ut<<":§*cout<<"*§ "<<endl;* § "<<endl;docout<<"n"<< "请输入选择：n"cin>>choice;switch(choice)case 1:int keyl;string name;cout<<"n"<<"请输入姓名：n”;cin>>name;key1=Search_by_name(name);Oufile(name,key1); cout<<"n"<<"查找结果：n"<<endl;Outhash(keyl);break;case 2:cout<<"n"<<"哈希表：n"<<endl;for(i=0;i<sizeindex;i+)if(signi!='0') cout<<"* "