哈希表的操作.docx
哈希表操作一目的1 .巩固和深入对哈希表的创建、查找、插入等方法理论学问的理解。2 .把握建立哈希表的方法，本试验是采纳的是除留余数法创建。3 .把握哈希表解决冲突的方法，本试验用的是线性探测再散列的方法。4 .巩固对程序模块化设计的要求。二需求分析1 .对于哈希表的基本操作首先是要创建一个哈希表,哈希表的创建思想是由哈希函数得到,本试验就采纳了除留余数法创建哈希表。2 .创建好哈希表就需要在哈希表中插入元素，本试验是需要插入单词，所以需要调用String函数库，通过每个单词的地址数来进行下一步的查找方案。当插入单词地址已经存在时，就产生了冲突，因此需要采纳线性探测再散列的方式来解决冲突。3 .当哈希表插入单词完成之后便可以显示哈希表的存储状况，因此需要输出整个哈希表。4 .要想计算平均查找长度首先要对哈希表中的元素进行查找，当全部单词查找结束，查找长度也得出。5 .要实现上诉需求，程序需要采纳模块化进行设计。三概要设计1.基本操作：voidInitwordlist(intn)初始化哈希表操作结果：以字符形式插入单词，将字符串的各个字符所对应的ASCH码相加，所得的整数做为哈希表的关键字。voidCreatehashlist(intn)创建哈希表，并插入单词操作结果：(1)用除留余数法构建哈希函数；(2)用线性探测再散列处理冲突。voidfind()查找哈希表中的单词操作结果：在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找胜利的平均查找长度。voidprinthash()显示哈希表操作结果：显示哈希表的存储状况：位置dtt关键字6dtt单词%sn°floataverage()操作结果：计算出平均查找长度。voidmenu()菜单函数设计操作结果：显示格式：1向哈希表中插入单词(<15)；2查找哈希表中的单词；3显示哈希表的存储状况；4计算哈希表的平均查找长度；5退出程序。intmain()主程序设计操作结果：通过调用各个函数操作得到结果。2.程序流程图:四具体设计1.全局变量:defineHASHLEN15/HASH_LEN长度定义为15defineM13/取模质数M为132 .存储结构设计:WORDWOrdIiStHASH_LEN;全局变量typedefstructCharWOrd15;输入的单词intnumber;单词所对应的整数(WORD;typedefstructchar*word;存储输入的单词intnumber;单词所对应的整数intnumofseek;查找的次数HASH;HASHhashlistHASH_LEN;全局变量3 .哈希表初始化voidInitworcllist(intn)(inti,j;char*w;设立一个指针，指向单词的地址for(i=0;i<n;i+)intSUnI=O;存放单词地址Printf(请输入第%d个单词(按回车结束)：，i+l);gets(wordlisti.word);/输入单词w=word1isti.word;取地址for(j=0;*(w+j)!=0;j+)将字符串的各个字符所对应的ASCIl码相加，所得的整数做为哈希表的关键字sum=sm+*(w+j);wordlisti.number=sum;存入每个单词的存放地址，即关键字4 .哈希表的创建voidCreatehashlist(intn)创建哈希表，并插入单词inti;for(i=0;i<HASH_LEN;i+)hashlisti.WOrd=;输入单词hashlisti.number=O;/关键字hashlisti.numofseek=0;查找次数for(i=0;i<n;i+)intaddress,sum=O;address=wordlisti.number%M;除留余数法，将单词插入到哈希表中if(hashlistaddress.numofseek=0)hashlistaddress,word=word1isti.word;hashlistaddress,number=wordlisti.number;hashlistaddress,numofseek=l;elseintd;d为冲突次数d=l;doaddress=(word1isti.number+d)%M;线性探测解决冲突d+;sum+;while(hashlistaddress.numofseek!=0);hashlistaddress,word=wordlisti.word;hashlistaddress,number=word1isti.number;hashlistaddress,numofseek=sum+l;)voidfind()查找哈希表中的单词charseek15,*p;设置查找长度不超过表长intm=0,i=0,j=0,d=l;Printf(请输入你想查找的单词(输入回车结束)：”)；gets(seek);p=seek;for(i;*(p+i)!='0'i+)依次查找j+=*(p+i);得到待查找单词的关键字j=j%M;显示在哈希表中的位置whiIe(!strcmp(hashlistj.word,seek)=0)/用StrCnlP函数来比较字符串j=(j+d)%M;有冲突状况下的地址m+;d+；if(m=HASH_LEN)break;超过表长)ifCm=HASHLEN)Printf("哈希表中没有这个单词n");elsePrintf("单词s存在,他的关键字是%dn”,hashlistj.word,hashlistj.number);)6 .哈希表的显示voidprinthashOinti=0;for(i=0;i<HASH_LEN;i+)Printf(位置%dtt关键字%-6dtt单词%sn”,i,hashlisti.number,hashlisti.word);)7 .菜单界面设计voidmenu()(Printf(“tt*n");printf(,tt*1向哈希表中插入单词(<15)*nz,);printf(/,tt*2查找哈希表中的单词*11;printf(,tt*3显示哈希表的存储状况*nz,);printf(/,tt*4计算哈希表的平均查找长度*11;printf(,tt*5退出程序*nz,);8 .主程序设计intmain()(intn,choose,done;floatave;menu();while(done)Printf("请输入你的选择:")；scanfchoose);switch(choose)case 1:Printf("请输入你想输入的单词数:“)；scanf("%d",&n);getchar();Initworcllist(n);Createhashlist(n);break;case 2:getchar();find()；break;case 3:printhash();break;case 4:ave=average()n;计算平均查找长度Printf("平均查找长度为%fn”,ave);break;case 5:done=0;break;default:break;return0;)五调试分析1 .在编写程序之前首先要确定该程序的功能，是涉及到对哈希表的基本操作，因此首先要了解哈希表的工作原理。2 .哈希表的创建要采纳除留余数法，即取关键地址对不大于表长的数取模，该数的取定要特别留心，通常取质数或者不包含小于2O的质因数的合数，这是除留余数法实现的关键。3 .哈希表的作用是不用比较就能直接查找出想要的数据，因此解决冲突是哈希表的特长。解决冲突的方法有许多种，书上介绍了线性探测法，二次探测法，伪随机探测法，链地址等，因此也需要选用解决冲突的方法，本试验就采纳了线性探测这种最常用的方法来解决冲突。4 .在主程序段采纳了switch语句，便利客户端进行选择性操作。5 .模块的调用要合理，只有模块起到相应的作用才能实现程序的功能。六测试结果1、输出菜单界面向查显基12 3 4 5词词篓 单单鸣 人插中的的 生表表 秦希春 曹哈哈程 曩示算出5>青输入你的选择:XXXWX15长词词曹一单单人的存平播中的的量表表XII哈哈程磨示算出显g12345yinOeab1;:>>>>>>>>>0三SI1S:1结结结结结结结结露词回回回回回回回回回-1J<<<<<<<<<yg>r:同同同同同同同同同h七-d即与与宫与与年与z-:-klrkkkkkl/白木儿1234567891SR第第第第第第第第入入-z.<frji1t7jrfxs三sl住用在4月江4性QE本月清性4月'住用'3查找单词度长<1i词词B-单单v?膏哈哈程不算出向查显宣123455>入的存平播中的K-量表表OtO1IgrlFylnol0>s>3>s>:1结结结结结结结结结一-wH441store词回回回回回回回回回缸词词1<<<XZ<<<<<2第第第第第第第第£入入入入入入入入入入入人入入责江R主月性IiEVnE住皇H住至QE住肩主肩性H住DE洋皇月哈住OE词-的存平¥的的三K三X.箭希需哈哈哈程W示算出23451011Ipr6.1.1h991iW:h>>>>>>>>>0:1结结结结结结结结结锣WHW屿storegirl左结车0回43三×fp今一令一I-二二：二二：二二：二二二：4乌l-kL1J<<<<<<<SZ<fgf>2SJXI2lrB犀疆朝朝朝翻朝朝鬻格选个选查常查在选：的想10的想S想S词回回回回回回回回回I1按按<词词单恢第第第第第第第第你入入入入入入入入入入入人入人文入K入词输'±.11E'R'±月vH'±.H'±.OE'±.nE性月在H''±.411e'±月'i目哈比4
