哈希表实现电话号码查询系统.docx
- 文档编号:11513323
- 上传时间:2023-06-01
- 格式:DOCX
- 页数:35
- 大小:801.87KB
哈希表实现电话号码查询系统.docx
《哈希表实现电话号码查询系统.docx》由会员分享,可在线阅读,更多相关《哈希表实现电话号码查询系统.docx(35页珍藏版)》请在冰点文库上搜索。
哈希表实现电话号码查询系统
哈希表实现电话号码查询系统
一目的
利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目,利用C/C++语言进行程序设计,并规范地完成课程设计报告。
通过课程设计,巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解;掌握现实复杂问题的分析建模和解决方法(包括问题描述、系统分析、设计建模、代码实现、结果分析等);提高利用计算机分析解决综合性实际问题的基本能力。
二需求分析
1、程序的功能
1)读取数据
1读取原电话本存储的电话信息。
2读取系统随机新建电话本存储的电话信息。
2)查找信息
1根据电话号码查询用户信息。
2根据姓名查询用户信息。
3)存储信息
查询无记录的结果存入记录文档。
2、输出形式
1)数据文件“old.txt”存放原始电话号码数据。
2)数据文件“new.txt”存放有系统随机生成的电话号码文件。
3)数据文件“out.txt”存放未查找到的电话信息。
4)查找到相关信息时显示姓名、地址、电话号码。
3、初步测试计划
1)从数据文件“old.txt”中读入各项记录,或由系统随机产生各记录,并且把记录保存到“new.txt”中。
2)分别采用伪随机探测再散列法和再哈希法解决冲突。
3)根据姓名查找时显示给定姓名用户的记录。
4)根据电话号码查找时显示给定电话号码的用户记录。
5)将没有查找的结果保存到结果文件Out.txt中。
6)系统以菜单界面工作,运行界面友好,演示程序以用户和计算机的对话方式进行。
三概要设计
1、子函数功能
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.txt
voidInit_HashTable(char*fname,intn)
//建立哈希表
intSearch_by_name(stringname)
//根据姓名查找哈希表中的记录
intSearch_by_phone(stringphone)
//根据电话号码查找哈希表中的记录
2、函数调用图
四详细设计
1、主函数流程图
2、“伪随机探测再散列处理冲突”伪代码
若对应位置上已经存在其他数据,则新的关键字=(原关键字+伪随机数)%哈希表长。
若新的位置上也存在其他数据,则用伪随机序列的下一个数求新的关键字,直到找到合适的位置。
3、“再哈希法处理冲突”伪代码
用“折叠法”将电话号码的ASCII码值定义为关键字,分别为前四位、中四位、后三位。
再用“除留余数法”求的新的关键字=原关键字%哈希表长。
4、“以姓名为关键字建立哈希表”伪代码
用“除留余数法”将姓名的ASCII码值定义为关键字。
若对应位置上存在其他数据,则调用伪随机处理冲突,然后将数据存入哈希表。
5、“以电话号码为关键字建立哈希表”伪代码
用“除留余数法”将电话号码的ASCII码值定义为关键字。
若对应位置上存在其他数据,则调用再哈希处理冲突。
然后将数据存入哈希表。
五调试分析
1、程序的关键是掌握文件的相关操作、哈希函数的创建和运用、伪随机法处理冲突、再哈希法处理冲突等。
在编程的过程中,出现了很多问题,如文件无法正常打开、程序进入死循环、无法实现文件的写入操作、忘了添加头文件等错误。
修改后程序运行正确。
2、创建“new.txt”内容用子函数来实现,但是原数据是从“old.txt”文件中读取的,刚开始不知道怎样实现二者之间的选择,在同学和参考书的帮助下终于得到解决。
3、关于伪随机和再哈希的相关内容觉得很难懂,看了很久参考书才有所了解
六测试结果
1、根据姓名查找
1)姓名查找成功
2)姓名查找失败
3)哈希表
2、根据电话号码查找
1)电话号码输入错误
2)电话号码查询成功
3)电话号码查询失败
4)哈希表
七用户使用说明
1、选择数据来源
根据提示信息进行操作,选择已存在的“old.txt”文件中的数据或系统当前自动生成的“new.txt”文件。
2、选择查找方式
根据提示信息进行操作,选择“根据姓名查找”或“根据电话号码查找”两种查找方式。
3、选择功能
根据提示信息进行操作,选择输入已知信息或查看哈希表。
4、显示结果
5、查看文件
八课程设计总结
1、收获
学会了C++的跟踪。
更进一步了解和熟悉了关于哈希表的运用和文件的读取与写入操作。
同时锻炼了对话形式的菜单的创建和熟练运用。
2、心得体会
在这次数据结构设计中遇到了很多实际性的问题,在实际设计中才发现,书本上理论性的东西与在实际运用中的还是有一定的出入的,所以有些问题要不断地更正以前的错误思维。
通过这次设计,我懂得了学习的重要性,了解到理论知识与实践相结合的重要意义,学会了坚持、耐心和努力,这将为自己今后的学习和工作做出了最好的榜样。
我觉得作为一名计科专业的学生,这次课程设计是很有意义的。
更重要的是如何把自己平时所学的东西应用到实际中。
虽然自己对于这门课懂的并不多,很多基础的东西都还没有很好的掌握,觉得很难,也没有很有效的办法通过自身去理解,但是靠着学习,渐渐对这门课逐渐产生了些许的兴趣,自己开始主动学习并逐步从基础慢慢开始弄懂它。
附录:
源程序
#include
#include
#include
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"< exit (1); } out_file< out_file.close(); } } voidOuthash(intkey)//输出哈希表中的记录 { unsignedi; if((key==-1)||(sign[key]=='0')) { cout<<"\n"<<"无此记录! ! ! \n"< } else { for(i=0;i cout< for(i=0;i<8;i++) cout<<""; cout< for(i=0;i<8;i++) cout<<""; cout< } } voidRafile()//随机生成数据,并将数据保存在new.txt { inti,j; out_file.open("new.txt"); if(out_file.fail()) { cout<<"\n"<<"文件打开失败! ! ! \n"< exit (1); } for(j=0;j<30;j++) { stringname=""; for(i=0;i<20;i++) name+=rand()%26+'a'; out_file< stringphone=""; for(i=0;i<11;i++) phone+=rand()%10+'0'; out_file< stringaddress=""; for(i=0;i<29;i++) address+=rand()%26+'a'; address+=','; out_file< } 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"< 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 sign[i]='0'; sign[i]='\0'; for(i=0;i { intermediate_data[i].name=""; intermediate_data[i].phone=""; intermediate_data[i].address=""; } cout<<"§**********************************************************§"< cout<<"§**§"< cout<<"§*请选择用于查找的数据来源*§"< cout<<"§**§"< cout<<"§*1.old.TXT*§"< cout<<"§*2.随机生成*§"< cout<<"§*0.退出程序*§"< cout<<"§**********************************************************§"< do { cout<<"\n"<<"请输入选择: \n"; cin>>k; switch(k) { case0: return; case1: Fname="old.txt"; break; case2: Rafile(); Fname="new.txt"; break; default: cout<<"输入序号有误,请重新输入! ! ! \n"< } } while((k! =1)&&(k! =2)&&(k! =0)); //system("cls"); cout<<"§**********************************************************§"< cout<<"§**§"< cout<<"§*请选择查找方式*§"< cout<<"§**§"< cout<<"§*1.根据姓名查找*§"< cout<<"§*2.根据电话号查找*§"< cout<<"§**§"< cout<<"§**********************************************************§"< do { cout<<"\n"<<"请输入选择: \n"; cin>>ch; if(ch! =1&&ch! =2) { cout<<"输入序号有误,请重新输入! ! ! \n"< } } while((ch! =1)&&(ch! =2)); //system("cls"); Init_HashTable(Fname,ch); while(ch==1) { intchoice; cout<<"§**********************************************************§"< cout<<"§**§"< cout<<"§*请选择功能*§"< cout<<"§**§"< cout<<"§*1.输入姓名查找数据*§"< cout<<"§*2.显示哈希表*§"< cout<<"§*0.退出程序! ! ! *§"< cout<<"§**§"< cout<<"§**********************************************************§"< 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"< Outhash(key1); } break; case2: { cout<<"\n"<<"哈希表: \n"< for(i=0;i { if(sign[i]! ='0') { cout<<"*"; Outhash(i); } } cout<<"**"< } break; case0: return; default: cout<<"输入序号有误,请重新输入! ! ! \n"< } } while((choice! =1)&&(choice! =2)&&(choice! =0)); } while(ch==2) { intchoice; cout<<"§**********************************************************§"<
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈希表 实现 电话号码 查询 系统