4477.哈希表实现电话号码查询系统数据结构课程设计报告

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

2、原始 号码数据。数据文件“new.txt”存放有系统随机生成的 号码文件。数据文件“out.txt”存放未查找到的 信息。查找到相关信息时显示姓名、地址、 号码。初步测试计划从数据文件“t”中读入各项记录，或由系统随机产生各记录，并且把记录保存到“new.txt”中 。分别采用伪随机探测再散列法和再哈希法解决冲突。根据姓名查找时显示给定姓名用户的记录。根据 号码查找时显示给定 号码的用户记录。将没有查找的结果保存到结果文件Out.txt中。系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进行。三 概要设计子函数功能int Collision_Random(int key,in

3、t 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 Outfile(string name,int key)void Outhash(int key) /输出哈希表中的记

4、录void Rafile()void Init_HashTable(char*fname,int n)/建立哈希表int Search_by_name(string name)/根据姓名查找哈希表中的记录int Search_by_phone(string phone)/根据 号码查找哈希表中的记录函数调用图四 详细设计主函数流程图 “伪随机探测再散列处理冲突”伪代码若对应位置上已经存在其他数据，则新的关键字=（原关键字+伪随机数）% 哈希表长。若新的位置上也存在其他数据，则用伪随机序列的下一个数求新的关键字，直到找到合适的位置。“再哈希法处理冲突”伪代码用“折叠法”将 号码的ASCII码值定

5、义为关键字，分别为前四位、中四位、后三位。再用“除留余数法”求的新的关键字=原关键字%哈希表长。“以姓名为关键字建立哈希表”伪代码用“除留余数法”将姓名的ASCII码值定义为关键字。若对应位置上存在其他数据，则调用伪随机处理冲突，然后将数据存入哈希表。“以 号码为关键字建立哈希表”伪代码用“除留余数法”将 号码的ASCII码值定义为关键字。若对应位置上存在其他数据，则调用再哈希处理冲突。然后将数据存入哈希表。五 调试分析1、程序的关键是掌握文件的相关操作、哈希函数的创建和运用、伪随机法处理冲突、再哈希法处理冲突等。在编程的过程中，出现了很多问题，如文件无法正常打开、程序进入死循环、无法实现文件

6、的写入操作、忘了添加头文件等错误。修改后程序运行正确。2、创建“new.txt”内容用子函数来实现，但是原数据是从“old.txt”文件中读取的，刚开始不知道怎样实现二者之间的选择，在同学和参考书的帮助下终于得到解决。3、关于伪随机和再哈希的相关内容觉得很难懂，看了很久参考书才有所了解六 测试结果根据姓名查找姓名查找成功姓名查找失败哈希表根据 号码查找 号码输入错误 号码查询成功 号码查询失败哈希表七 用户使用说明选择数据来源根据提示信息进行操作，”文件。选择查找方式根据提示信息进行操作，选择“根据姓名查找”或“根据 号码查找”两种查找方式。 选择功能根据提示信息进行操作，选择输入已知信息或查

7、看哈希表。显示结果查看文件八 课程设计总结收获学会了C+的跟踪。更进一步了解和熟悉了关于哈希表的运用和文件的读取与写入操作。同时锻炼了对话形式的菜单的创建和熟练运用。心得体会在这次数据结构设计中遇到了很多实际性的问题，在实际设计中才发现，书本上理论性的东西与在实际运用中的还是有一定的出入的，所以有些问题要不断地更正以前的错误思维。通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的榜样。我觉得作为一名计科专业的学生，这次课程设计是很有意义的。更重要的是如何把自己平时所学的东西应用到实际中。虽然自己对于这门课懂的

8、并不多，很多基础的东西都还没有很好的掌握，觉得很难，也没有很有效的办法通过自身去理解，但是靠着学习，渐渐对这门课逐渐产生了些许的兴趣，自己开始主动学习并逐步从基础慢慢开始弄懂它。附录：源程序#include #include #include 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;st

9、ring phone;string address; Data *intermediate_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

10、=&name0;*p;p+)key=key+*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 n

11、um1=(str0-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)%sizeindex;return Re_key;void Init_HashTable_by_phone(string name,string phone,string address)/以 号码为关键字建立哈

12、希表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=phone;signkey=1;if(key=-1)|(signkey=0)out_file.open(out.txt);if(out_file.fail() coutn

13、文件打开失败!nendl;exit(1);out_filenameendl;out_file.close();void Outhash(int key)/输出哈希表中的记录unsigned i;if(key=-1)|(signkey=0)coutn无此记录!nendl;elsefor(i=0;istrlen(&(intermediate_0);i+)coutintermediate_i;for(i=0;i8;i+)cout ;coutintermediate_datakey.phone;for(i=0;i8;i+)cout ;coutinterm

14、ediate_datakey.addressendl;int i,j;out_file.open(new.txt);if(out_file.fail()coutn文件打开失败!nendl;exit(1);for(j=0;j30;j+)string name=;for(i=0;i20;i+)name+=rand()%26+a;out_filename ;string phone=;for(i=0;i11;i+)phone+=rand()%10+0;out_filephone ;string address=;for(i=0;i29;i+)address+=rand()%26+a;address+

15、=,;out_fileaddressendl; 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()coutn文件打开失败!nendl;exit(1);while(!in_file.eof()char* str=new char100;name=;phone=;address=;in_file.getline(str,100,n);/

16、按行读入数据if(str0=*)/判断数据结束break;i=0;while(stri=122)i+;for(;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);/以 号码为关键字del

17、ete 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_by_phone(string phone)/根据 号码

18、查找哈希表中的记录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 *Fname;sign=new charsizeindex;intermediate_data=new

19、 Datasizeindex;for(i=0;isizeindex;i+)signi=0;signi=0;for(i=0;isizeindex;i+)intermediate_=;intermediate_datai.phone=;intermediate_datai.address=; cout*endl;cout* *endl;cout* 请选择用于查找的数据来源 *endl;cout* *endl;cout* 1 . old.TXT *endl;cout* 2 . 随 机 生 成 *endl;cout* 0 . 退 出 程 序 *endl; cout*endl; do

20、coutnk;switch(k)case 0:return;case 1:Fname=old.txt;break;case 2:Rafile();Fname=new.txt;break; default:cout输入序号有误，请重新输入!nendl;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; cou

21、t*endl;docoutnch;if(ch!=1&ch!=2)cout 输入序号有误，请重新输入!nendl;while(ch!=1)&(ch!=2); /system(cls);Init_HashTable(Fname,ch);while(ch=1)int choice;cout*endl;cout* *endl;cout* 请 选 择 功 能 *endl; cout* *endl;cout* 1 . 输 入 姓 名 查 找 数 据 *endl;cout* 2 . 显 示 哈 希 表 *endl;cout* 0 . 退 出 程 序! *endl;cout* *endl; cout*endl;docoutnchoice; switch(choice) case 1:int key1;string name;coutnname;key1=Search_by_name(name);Outfile(name,key1); coutn查找结果:nendl;Outhash(key1);break;case 2: coutn 哈希表: nendl;for(i=0;isizeindex;i+)if(signi!=0)cout* ; Out