数据结构与算法课程设计报告-利用哈希技术统计C源程序关键字出现频度.docx

国弟孝理N文孽数据结构与算法课程设计报告题目：利用哈希技术统计C源程序关键字出现频度学生姓名：学号：.一班级：指导教师：2012年6月18日利用哈希技术统计c源程序关键字出现频度(D题目内容：利用Hash技术统计某个C源程序中的关键字出现的频度（2）根本要求：扫描一个C源程序，用HaSh表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度。用线性探测法解决HaSh冲突。设HaSh函数为：HaSh（key）（key的第一个字母序号）*100+（key的最后一个字母序号）MOD41一、对题目的分析哈希表是为了便于快速搜索而组织的值组合的集合。HaShTable是一种数组，可以用任意简单变量值来访问其元素，这种数组叫做关联数组，也叫哈希表。值对的集合。理想的情况下是希望不经过任何比拟，一次存储就能得到所查到的记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。根本要求：使用一个下标范围比拟大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值即数组下标，hash值）存在一一对应的关系，于是用这个数组单元来存储这个元素。使用hash表存储关键字时难免会有不同的关键字对应同一关键码的情况，因此必须有个处理冲突的方法。Hash函数：HaSh（key）（key的第一个字母序号）*100+（key的最后一个字母序号）MOD41二、处理冲突的方法处理冲突的方法一线性探测法用线性探法解决冲突时，把有冲突的关键字往后推移直到有空位置的关键码时再插入到hash表中。Q语言关键字.3语言关键字是C语言的保存的一些单词，这些单词都有了固定的意义和用途，不可以作为变量或者自定义类型或类名来使用。其特点是都有小写字母构成。C语言关键字有哪些：doubleintstructbreakelselongswitchcaseenumregistercharexternreturnunionconstfloatshortunsignedcontinueforsignedvoiddefaultgotosizeofvolatiledowhilestaticifautocase定义一个多维数组，数组第一行存放关键字，数组第二行存储hash函数处理后关键字结点地址，用hash函数存储关键字Hash（Key）=（Key第一个字符在1-26个字母中的序号）*100+（Key最后一个字符在1-26个字母中的序号）41如此得至妆口for对应地址3,if对应于地址4,int对应地址18等等。哈希表仪1丫）40州0口41处理冲突为线性探测再散列。三、算法设计及局部函数翻开含关键字的CPP文件：intOpen（char+filename）（charwordMaxLength,ch：inti：FILE*read;指向FILE类的指针*readif(read=fopen(fiIename,*r*)=NULL)只读方式读取文件，如果为空COUt<<endk<”未找到要翻开的文件,请重新输入!；return-1;跳出OPen函数)while(!feof(read)判断文件是否结束，到末尾函数值为“真”即非0(i=0;ch=fgetc(read);读取一个字符whiIe(LetterNot(Ch)=O&&feof(read)=0)ch=fgetc(read);如果不是字母就接着读取,关键字都是由字母组成的while(LetterNot(ch)=l&&feof(read)=0)if(i=MaxLength)(whiIe(LetterNot(ch)=1&&feof(read)=0)(ch=fgetc(read);/超过MXLEN的长度那么一定不为关键字，把余下连一起的字母都读取)i=0;break;)else(WOrdi+=ch;把读取到的字母存入word数组中ch=fgetc(read);)wordi=*0,;if(KeywordsNot(word)(CreatHash(word);)fclose(read);COUt<<endk<”文件中关键字已经存入表中，请继续！"<1血1<1鼠1<1血1;)在Hash表中查找关键字找出关键字位置：intFindHash(char*keyword)在HaSh表中查找关键字intkey,find,FindColl=O;if(!KeywordsNot(keyword)是否关键字return-1;Rey=GetHashValue(keyword);if(strcmp(Testkey.keyword,keyword)=0)returnkey：for(find=key+l;find<LengthofHash;find+)线性探测法FindColl+;/FindColl统计冲突次数if(strcmp(Testfind.keyword,keyword)=0)(Testfind.Coll=FindColl;把冲突次数存入collreturnfind;)for(find=O;find<key;find+)后面的找不到再从前面开始找(FindColl+;if(strcmp(Testfind.keyword,keyword)=0)(Testfind.Coll=FindColl;returnfind;)return-1;)建立HaSh表：intCreatHash(char*keyword)建立HaSh表，keyword是一个数组intkey;if(!KeywordsNot(keyword)判断是否关键字return-1;Rey=GetHashValue(keyword);计算Hash值if(strIen(Testkey.keyword)>0)/Hash表中该位置存在关键字(if(strcmp(Testkey.keyword,keyword)=0)/Hash表中该位置的关键字相同(Testkey.count+;频度加1return1;跳出函数)Rey=FindHash(keyword);不相同，继续查找if(key<O)没有找到相等的keyword(key=Insert(GetHashValue(keyword);if(key<O)/Hash表满或者计算的Hash值有问题returnT;strcpy(Testkey.keyword,keyword);将关键字插入Hash表if(key<O)return-1;Testkey.count+;)else该位置没有关键字(strcpy(Testkey,keyword,keyword);Testkey.count+;)return1;)在HaSh表中插入关键字：intInsert(intkey)在HaSh表中插入关键字intfind,FindColl=O;if(key<Okey>=LengthofHash)return-1;for(find=key+l;find<LengthofHash;find+)分块查找后局部(FindColl+;if(strIen(Testfind.keyword)=0)假设这个地方为空(Testfind.Coll=FindCol1;把冲突的次数存入CoIl中returnfind：)for(find=。;find<key;find+)分块在前局部查找(FindColl+;if(strlen(Testfind.keyword)=0)(Testfind.Coll=FindColl;returnfind;)return-1：HaSh表已满)四、算法的实现a)引用库函数定义变量#include<iostream.h>#include<string>#include<iomanip.h>einclude<conio.h>usingnamespacestd：constintLengthofHash=41;HaSh表长度intkeycount=0;统计HaSh表中的关键字总数constintTotal=38;38个关键字constintMaXLength=20：charKeyWordsTotalMaxLength=列举38个关键字bool,break,case,catch,char,class,const,continue,default,do,double,else,enum,extern,false,float,for,goto,if,int,interrupt,long,new,private,public,register,return,short,signed,szeof,static,struct,switch,typeder,union,unsigned,void,while,;b)类的构造及类的对象classConuntNumpublic:intcoll;COlIiSion冲突次数intcount;出现次数(频度charkeywordMaxLength;；ConuntNumTesttLengthofHash;C)函数的声明局部voidMenu();voidPrintScreen(intkey);intOpen(char+filename)：intLetterNot(charch);intKeywordsNot(char*word);intFindHash(char*keyword);intCreatHash(char*keyword);intInsert(intkey);intGetHashValue(char*keyword);d)在HaSh表中分块查找intFindHash(char*keyword)在HaSh表中查找关键字(intkey,find,FindColl=O;if(!KeywordsNot(keyword)是否关键字return-1;五、源代码#include<iostream,h>#include<string>einclude<iomanip.h>#include<conio.h>usingnamespacestd：constintLengthofHash=41;HaSh表长度intkeycount=0;统计HaSh表中的关键字总数constintTotal=38;38个关键字constintMaxLength=20;charKeyWordsTotalMaxLength=列举38个关键字(bool,break,case,catch,char,class,const,continue,default,do,double,else,enum,extern,false,float,for,goto,if,int,interrupt,long,new,private,public,register,return,short,signed,szeof,static,struct,switch,typedef,union,unsigned,void,while,;classConuntNumpublic:intcoll;COlIiSion冲突次数intcount;出现次数(频度charkeywordMaxLength;；ConuntNumTesttLengthofHash;先声明后使用voidMenu();voidPrintScreen(intkey);intOpen(char+filename)：intLetterNot(charch);intKeywordsNot(char*word);intFindHash(char*keyword);intCreatHash(char*keyword);intInsert(intkey);intGetHashValue(char*keyword);voidmain()charopt;intoption=l,i,count,key,has;charfilename50,wordMaxLength;whiIe(option)Menu();cin>>opt;switch(opt)(case,1,:system(*cls*);COUt<<”请输入文件名：”；cin>>fiIename;Open(fiIename);cout<<endl;continue;break;case'2,:SySteIn("cis");COUt按回车键继续显示！*<<endl;for(i=0;i<LengthofHash;i+)PrintScreen(I);if(i+l)%10=0)getchar();/10行一循环)cout<<*CPP文件中关键字总数为："Gkeycounfendl;cout<<endl<<endl<<endl<<endl<<end1;continue;system(*cls*);break;case'3,:system(*cls*);COUt冲突关键字列表<<endl<<endl;count=0;for(i=0;i<LengthofHash;i+)(if(strlen(Testi.keyword)>0)(Rey=GetHashValue(Testi.keyword);if(key!=i)count+;cout<<*t关键字"<<Test字.keyword：cout<<*tHash表当前位置:“6i;cout<<*t冲突次数：“<×Testi.coll<<endl;)if(count=0)(：011仅<“没有冲突"<<611刖<<611刖<<611<11<<6£1<<6虱1；elsecout<<endl<<*ttt冲突关键字共：“<Xcount<<"个"<<endl;cout<<endl<<endl<<endl<<endl<<end1;continue;SyStein("cis");break;case'4,:system(*cls*);CoUt<<"输入你想要查找的关键字：*<<endl;cin>>word;cout<<endl;PrintScreen(FindHash(word);cout<<endl：continue;system(*cls*);break;case'5,:option=0;break;default:SyStein("cis");)intOpen(char*fiIename)charwordMaxLength,ch;inti;FILE*read;指向FlLE类的指针*readif(read=fopen(fiIename,*r*)=NULL)只读方式读取文件，如果为空(COUt<<endk<”未找到要翻开的文件,请重新输入!；return-1;/跳出OPen函数)while(!feof(read)判断文件是否结束，到末尾函数值为“真”即非O(i=0;ch=fgetc(read);读取一个字符whiIe(LetterNot(ch)=0ftfeof(read)=0)ch=fgetc(read);如果不是字母就接着读取,关键字都是由字母组成的whiIe(LetterNot(ch)=l&&feof(read)=0)(if(I=MaxLength)(whiIe(LetterNot(ch)=l&&feof(read)=0)(ch=fgetc(read);超过MXLEN的长度那么一定不为关键字，把余下连一起的字母都读取)i=0;break;)else(WOrdi+=ch;把读取到的字母存入word数组中ch=fgetc(read);)wordi='0,;if(KeywordsNot(word)(CreatHash(word);)fclose(read);CoUt<<endl<<“文件中关键字已经存入表中，请继续！"<1血1<1M1<1血1;)intLetterNot(charch)判断是否是字母if(ch>=*a'&&ch<='z,)(ch>=*,&&ch<='Z,)return1;elsereturnO;)intFindHash(char*keyword)在HaSh表中查找关键字(intkey,find,FindColl=O;if(!KeywordsNot(keyword)是否关键字return-1;Rey=GetHashValue(keyword);if(strcmp(Testkey.keyword,keyword)=0)returnkey;for(find=key+l;find<LengthofHash;find+)线性探测法FindeO11+;/FindCol1统计冲突次数if(strcmp(Testfind.keyword,keyword)=0)(Testfind.Coll=FindColl;把冲突次数存入collreturnfind;)for(find=O;find<key;find+)后面的找不到再从前面开始找(FindColl+;if(strcmp(Testfind.keyword,keyword)=0)(Testfind.Coll=FindColl;returnfind;)return-1;)intCreatHash(char+keyword)/建立Hash表，keyword是一个数组intkey;if(!KeywordsNot(keyword)判断是否关键字return-1;Rey=GetHashValue(keyword);计算Hash值if(str1en(Testkey.keyword)>0)/Hash表中该位置存在关键字if(strcmp(Testkey.keyword,keyword)=0)/Hash表中该位置的关键字相同Testkey.count+;频度加1return1;跳出函数Rey=FindHash(keyword);不相同，继续查找if(key<O)没有找到相等的keyword(key=Insert(GetHashValue(keyword);if(key<O)/Hash表满或者计算的Hash值有问题return-1;strcpy(Testkey,keyword,keyword);将关键字插入Hash表)if(key<O)return-1;Testkey.count+;)else该位置没有关键字(strcpy(Testkey,keyword,keyword);Testkey.count+;)return1;)intInsert(intkey)在HaSh表中插入关键字(intfind,FindColl=O;if(key<Okey>=LengthofHash)return-1;for(find=key+l;find<LengthofHash;find+)分块查找后局部FindColl+;if(strIen(Testfind.keyword)=0)假设这个地方为空Testfind.Coll=FindCol1;把冲突的次数存入CoIl中returnfind;)for(find=O;find<key;find+)分块在前局部查找FindColl+;if(strlen(Testfind.keyword)=0)(Testfind.colI=FindCol1;returnfind;)return-1;/Hash表已满)intKeywordsNot(char*word)判断是否关键字inti：for(i=0;i<Total;i+)if(strcmp(word,KeyWordsi)=0)return1;returnO;voidPrintScreendntkey)if(key<0key>=LengthofHash)(COUt<<"关键字不存在!*«endl;return：)if(strlen(Testkey.keyword)=0)(COUt<<"Hash表位置："<<key<<”记录是空的！"<<endl;return;)cout<<*Hash表位置：*<<key<<*t*<<*关键字：”<XTestkey.keyword<<"tt"<<”出现次数:*<<Testkey.count<<endl;keycount+;)intGetHashValue(char*keyword)intHashValue;HashValue=(keyword0*100+keywordstrlen(keyword)-1)%41;returnHashValue;)voidMenu()(CoUt<<*tt*<<endl;cout<<*tt*1.读取CPP文件*<<endl;cout<<*tt*2.输出Hash表中的关键字*<<endl;cout<<*tt*3.显布冲突的关键字*<<endl;cout<<*tt*4.在HaSh表中查找关键字*<<endl;cout<<*tt*5.退出*<<endl;cout<<*tt*请选择(15):*<<endl;cout«Artt*/z<<endl;六、程序运行结果截图凿示Ha出择读输显在退选1.2.3.4.5.住用PJs突表Pa中hCH弭S字字一于关的键找牛中关查对武中图1程序运行界面五件中关键字已经存入表中，请继续，字字键链关字关的键找牛中关查:番中5prsb突表一Pa中h1骼而Has出热读输显在退选12345追并图2载入含关键字的CPPHhhhhhhhbbSsssssssssAaaaaaaaaaHhhhhhhhhh位位位位位位位位位位表表表表表表表表表表01234567893333333333关关关关关关关关一defaultpublicreturnelseregisterunsignedwhilestaticintcase出现次数：2出现次数：2出现次数：23出现次数：5出现次数"出现次数：1出现次数：6出现次数二出现次数：32出现次数：6HaSh表位置：40关键字：continueCPP文件族键字羲为=38出现次数:5图3输出HaSh表中的关键字帙关键初表6116789883131933722712数数数数数数数数数数数数数数数数数数数数数FvFvFvvvFvvFvFvFvFvFvFvFvFvFvFvvFvFvFv次次次次次次次次次次次次次次次次次次次次次突突突突突突突突突突突突突突突突突突突突突I口口口口口>Jl>J1VJl¼J1¼J1>J1¼J1>J1>J1>J1¼i1>J1>i1>Ji>i>Jl¼y¼ivJl¼Jl>J11234567913141618192829313235363940位位位位位位位位位位位位位位位位位位位位位.£.tr.-X.m.-X.fr.-Uf,.-JL.dfr.X-f.-X-rr.-X.Hf-JLfTT.-Xfr.-JL.rr.-X.X.fr.-X-fr.X-CTr.I.T._j_t.-Xm.-Uf.当当当当当当当当当当当当当当当当当当当当当表表表表表表表表表表表表表表表表表表表表表IlllllllllllllllllbbbCocetcnOegnetSttn«aZ.11OnO.1iWaCnnn.lrge.1lui<letriiOibtSiSntnolruenaoee9.IlsssfssuufppruwccSxxxxxxxxxxxxiXXXXXXTUBthEI-分匚3Ctl=_?匚r匚3_UPCbF-2C91二HEbE3二WH二3-二fEf-!JfEUBCHw.MuXu;Xu.Xu、1H.MM.UH.1JHQluUHJHw.XlvHw.X5.Hpv卷卷卷卷卷卷卷管管卷卷卷管卷卷卷卷卷卷卷卷冲突关键字共：21个图4显示冲突的关键字输入你想要查找的关键字:forHaSh表位置;23 关键字：£or出现次数：8图5查找关键字在HaSh表中的位置七、课程设计心得体会这次课程设计让我了解到自己在Hash表这一块有着许多的缺乏，在各方面都缺乏最重要的知识。通过这次课程设计,我了解到自己在实践操作方面还有很多缺乏，在实践过程中老师和同学给了我很大的帮助和鼓励，学会了团结精神的重要性，以及做事必须一丝不苟，遇到困难不能半途而废要有不惧困难探求真理，踏踏实实的解决问题。参考文献：李根强编著，数据结构（C+版）（第二版），中国水利水电出版社