数据结构与算法课程设计报告-利用哈希技术统计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