课程设计报告-利用哈希技术统计C源程序关键字出现频度.doc

数据结构与算法课程设计报告 题目：利用哈希技术统计c源程序关键字出现频度 学生姓名： 学 号： _ 班 级： _ 指导教师： _ 2012年 6 月 18 日利用哈希技术统计c源程序关键字出现频度(1)题目内容：利用hash技术统计某个c源程序中的关键字出现的频度(2)基本要求：扫描一个c源程序，用hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度。用线性探测法解决hash冲突。设hash函数为：hash(key)(key的第一个字母序号)*100+(key的最后一个字母序号) mod 41 一、对题目的分析哈希表是为了便于快速搜索而组织的值组合的集合。hash table是一种数组，可以用任意简单变量值来访问其元素，这种数组叫做关联数组，也叫哈希表。值对的集合。理想的情况下是希望不经过任何比较，一次存储就能得到所查到的记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。基本要求：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）存在一一对应的关系，于是用这个数组单元来存储这个元素。使用hash表存储关键字时难免会有不同的关键字对应同一关键码的情况，因此必须有个处理冲突的办法。hash函数：hash(key)(key的第一个字母序号)*100+(key的最后一个字母序号) mod 41 二、处理冲突的方法处理冲突的办法线性探测法用线性探法解决冲突时，把有冲突的关键字往后推移直到有空位置的关键码时再插入到hash表中。c语言关键字: c语言关键字是c语言的保留的一些单词，这些单词都有了固定的意义和用途，不可以作为变量或者自定义类型或类名来使用。其特点是都有小写字母构成。c语言关键字有哪些：double int structbreakelselongswitch caseenumregistercharextern returnunionconstfloatshortunsignedcontinuefor signedvoiddefaultgotosizeofvolatiledowhilestaticifautocase定义一个多维数组，数组第一行存放关键字，数组第二行存储hash函数处理后关键字结点地址，用hash函数存储关键字hash(key)=(key第一个字符在1-26个字母中的序号)*100+(key最后一个字符在1-26个字母中的序号)%41如此得到如for对应地址3，if对应于地址4，int对应地址18等等。哈希表 h(key)=keymod41 处理冲突为线性探测再散列。 三、算法设计及部分函数打开含关键字的cpp文件：int open(char *filename)char wordmaxlength,ch;int i;file *read; /指向file类的指针*read if(read=fopen(filename,r)=null) /只读方式读取文件，如果为空coutendl未找到要打开的文件,请重新输入!;return -1; /跳出open函数while(!feof(read) /判断文件是否结束，到末尾函数值为“真”即非0i=0;ch=fgetc(read); /读取一个字符while(letternot(ch)=0&feof(read)=0)ch=fgetc(read); /如果不是字母就接着读取,关键字都是由字母组成的while(letternot(ch)=1&feof(read)=0)if(i=maxlength)while(letternot(ch)=1&feof(read)=0)ch=fgetc(read); /超过maxlen的长度则一定不为关键字，把余下连一起的字母都读取i=0;break;elsewordi+=ch; /把读取到的字母存入word数组中ch=fgetc(read);wordi=0;if(keywordsnot(word)creathash(word);fclose(read);coutendl文件中关键字已经存入表中，请继续!endlendlendl;在hash表中查找关键字找出关键字位置：int findhash(char *keyword) /在hash表中查找关键字int key,find,findcoll=0;if(!keywordsnot(keyword) /是否关键字return -1;key=gethashvalue(keyword);if(strcmp(testkey.keyword,keyword)=0)return key;for(find=key+1;findlengthofhash;find+) /线性探测法findcoll+; /findcoll统计冲突次数if(strcmp(testfind.keyword,keyword)=0)testfind.coll=findcoll; /把冲突次数存入collreturn find;for(find=0;find0) /hash表中该位置存在关键字 if(strcmp(testkey.keyword,keyword)=0) /hash表中该位置的关键字相同 testkey.count+; /频度加1return 1; /跳出函数key=findhash(keyword); /不相同，继续查找if(key0) /没有找到相等的keywordkey=insert(gethashvalue(keyword);if(key0) /hash表满或者计算的hash值有问题return -1;strcpy(testkey.keyword,keyword); /将关键字插入hash表if(key0)return -1;testkey.count+;else /该位置没有关键字strcpy(testkey.keyword,keyword);testkey.count+;return 1;在hash表中插入关键字：int insert(int key) /在hash表中插入关键字int find,findcoll=0;if(key=lengthofhash) return -1;for(find=key+1;findlengthofhash;find+) /分块查找后部分findcoll+;if(strlen(testfind.keyword)=0) /若这个地方为空 testfind.coll=findcoll; /把冲突的次数存入coll中 return find; for(find=0;findkey;find+) /分块在前部分查找findcoll+;if(strlen(testfind.keyword)=0)testfind.coll=findcoll;return find;return -1; /hash表已满四、算法的实现a)引用库函数定义变量#include #include #include #include using namespace std;const int lengthofhash=41; /hash表长度int keycount=0; /统计hash表中的关键字总数const int total=38; /38个关键字const int maxlength=20; char keywordstotalmaxlength= /列举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,sizeof,static,struct,switch,typedef,union,unsigned,void,while,;b)类的构造及类的对象class conuntnum public:int coll; /collision冲突次数int count; /出现次数（频度）char keywordmaxlength; conuntnum testlengthofhash;c)函数的声明部分void menu();void printscreen(int key);int open(char *filename); int letternot(char ch);int keywordsnot(char *word);int findhash(char *keyword);int creathash(char *keyword);int insert(int key);int gethashvalue(char *keyword);d)在hash表中分块查找int findhash(char *keyword) /在hash表中查找关键字int key,find,findcoll=0;if(!keywordsnot(keyword) /是否关键字return -1;五、源代码#include #include #include #include using namespace std;const int lengthofhash=41; /hash表长度int keycount=0; /统计hash表中的关键字总数const int total=38; /38个关键字const int maxlength=20; char keywordstotalmaxlength= /列举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,sizeof,static,struct,switch,typedef,union,unsigned,void,while,;class conuntnum public:int coll; /collision冲突次数int count; /出现次数（频度）char keywordmaxlength; conuntnum testlengthofhash;/先声明后使用void menu();void printscreen(int key);int open(char *filename); int letternot(char ch);int keywordsnot(char *word);int findhash(char *keyword);int creathash(char *keyword);int insert(int key);int gethashvalue(char *keyword);void main() char opt; int option=1,i,count,key,has;char filename50,wordmaxlength; while(option) menu(); cinopt;switch(opt) case 1:system(cls); coutfilename;open(filename); coutendl; continue;break; case 2: system(cls);cout按回车键继续显示！endl;for(i=0;ilengthofhash;i+) printscreen(i); if(i+1)%10=0)getchar(); /10行一循环 coutcpp文件中关键字总数为:keycountendl;coutendlendlendlendlendl;continue; system(cls); break;case 3:system(cls); cout冲突关键字列表:endlendl; count=0; for(i=0;i0) key=gethashvalue(testi.keyword); if(key!=i) count+; coutt关键字testi.keyword; coutthash表当前位置:i; coutt冲突次数:testi.collendl; if(count=0) cout没有冲突endlendlendlendlendl; else coutendlttt冲突关键字共:count个endl;coutendlendlendlendlendl;continue; system(cls); break; case 4:system(cls);cout输入你想要查找的关键字： word; coutendl; printscreen(findhash(word);coutendl;continue; system(cls); break; case 5:option=0;break;default: system(cls);int open(char *filename)char wordmaxlength,ch;int i;file *read; /指向file类的指针*read if(read=fopen(filename,r)=null) /只读方式读取文件，如果为空coutendl未找到要打开的文件,请重新输入!;return -1; /跳出open函数while(!feof(read) /判断文件是否结束，到末尾函数值为“真”即非0i=0;ch=fgetc(read); /读取一个字符while(letternot(ch)=0&feof(read)=0)ch=fgetc(read); /如果不是字母就接着读取,关键字都是由字母组成的while(letternot(ch)=1&feof(read)=0)if(i=maxlength)while(letternot(ch)=1&feof(read)=0)ch=fgetc(read); /超过maxlen的长度则一定不为关键字，把余下连一起的字母都读取i=0;break;elsewordi+=ch; /把读取到的字母存入word数组中ch=fgetc(read);wordi=0;if(keywordsnot(word)creathash(word);fclose(read);coutendl文件中关键字已经存入表中，请继续!endlendl=a&ch=a&ch=z)return 1; elsereturn 0; int findhash(char *keyword) /在hash表中查找关键字int key,find,findcoll=0;if(!keywordsnot(keyword) /是否关键字return -1;key=gethashvalue(keyword);if(strcmp(testkey.keyword,keyword)=0)return key;for(find=key+1;findlengthofhash;find+) /线性探测法findcoll+; /findcoll统计冲突次数if(strcmp(testfind.keyword,keyword)=0)testfind.coll=findcoll; /把冲突次数存入collreturn find;for(find=0;find0) /hash表中该位置存在关键字 if(strcmp(testkey.keyword,keyword)=0) /hash表中该位置的关键字相同 testkey.count+; /频度加1return 1; /跳出函数key=findhash(keyword); /不相同，继续查找if(key0) /没有找到相等的keywordkey=insert(gethashvalue(keyword);if(key0) /hash表满或者计算的hash值有问题return -1;strcpy(testkey.keyword,keyword); /将关键字插入hash表if(key0)return -1;testkey.count+;else /该位置没有关键字strcpy(testkey.keyword,keyword);testkey.count+;return 1;int insert(int key) /在hash表中插入关键字int find,findcoll=0;if(key=lengthofhash) return -1;for(find=key+1;findlengthofhash;find+) /分块查找后部分findcoll+;if(strlen(testfind.keyword)=0) /若这个地方为空 testfind.coll=findcoll; /把冲突的次数存入coll中 return find; for(find=0;findkey;find+) /分块在前部分查找findcoll+;if(strlen(testfind.keyword)=0)testfind.coll=findcoll;return find;return -1; /hash表已满int keywordsnot(char *word) /判断是否关键字int i;for(i=0;itotal;i+)if(strcmp(word,keywordsi)=0)ret