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

数据结构课程设计报告题目：利用哈希技术统计C源程序关键字出现频度学生姓名：於金娥学号：1021113230班级：10211132指导教师：高永平2012年6月16日1目录一、需求分析..................................2二、总体设计..................................3三、详细设计..................................4五、程序测试.................................12六、总结.....................................151.问题：......................................152.收获：......................................152利用哈希技术统计C源程序关键字出现频度一、需求分析1.题目内容：利用Hash技术统计某个C源程序中的关键字出现的频度。2.基本要求：扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度。用线性探测法解决Hash冲突。设Hash函数为：Hash(key)[(key的第一个字母序号)*100+(key的最后一个字母序号)]MOD413.需求：（1）首先要用一个二维数组存储C源程序中的32个关键字。（2）建立Hash表。（3）在Hash表中找到相应的位置存放关键字。（4）读取某个C文件，并统计出现的每个关键字在Hash表中存放的位置及在文件中出现的次数。（5）输入文件中出现的任意一个关键字，显示在Hash表中存放的位置及在文件中出现的次数。（6）显示C源程序中所有关键字在Hash表中的位置。（7）显示所有冲突关键字列表。3二、总体设计4三、详细设计1.创建一个哈希表类HashTable和一个类模板HASH：HashTable:{charkeyword[MAXLEN];intcount;intnum;}HASH:{voidShow(intkey);intCreatHX(char*keyword);intGetFreePos(intkey);voidResetHX();intGetKey(char*keyword);intisKeyWords(char*word);intRead(char*filename);intisLetter(charch);intFindHX(char*keyword)intkey;char*keyword;char*word;charch;}2.构造二维数组存储32个关键字：KeyWords[TOTAL][MAXLEN]={char,double,enum,float,int,long,short,signed,struct,union,unsigned,void,break,case,continue,default,do,else,for,goto,if,return,switch,while,auto,extern,register,static,const,sizeof,typedef,volatile}3.各个数据成员及成员函数的功能：数据成员：keyword[MAXLEN]存放关键字；count关键字出现次数；num冲突次数；key关键字在哈希表中的下标；*keyword指向关键字的首字母指针；*word指向文件中单词的指针；ch关键字的每一个字母；成员函数：Show(intkey)输出关键字：若输入正确，输出关键字在哈希表中的存储位置及其在指定的文件中出现的次数；否则，提示出错（关键字不存在）。CreatHX(char*keyword)建立哈希表：先计算哈希值，再判断关键字表中该位置是否存在关键字，如果存在，再判断哈希表中该位置的关键字是否相同，若相同，count加一；若不相同，继续查找，直到将关键字插入哈希表；如果该位置为空，直接将关键字插入该位置中。GetFreePos(intkey)在哈希表中给关键字找个位置插进去：先找后面的5位置，从下标为key+1的位置开始查找，若该位置为空，则将关键字放到此位置（即没有冲突），否则（发生冲突，用线性探测法解决冲突），依次往后查找，直到有空位，如果到哈希表的表尾仍无空位，则重新从哈希表的第一个位置依次往后查找，直到将关键字插入到哈希表中。ResetHX()重置哈希表。GetKey(char*keyword)哈希函数：Hash(Key)=[(Key的首字母序号)*100+(Key的尾字母序号)]Mod41。isKeyWords(char*word)判断是否关键字：是关键字就返回1，否则返回0值。Read(char*filename)读取文件：若打开文件不成功，提示错误；否则，读取文件前先清空哈希表，利用文件结束检测函数feof(),如果没有结束,返回值是0,结束了是1。一个一个字符依次读取，如果不是字母的话接着读取，如果是字符，超过关键字长度将跳过当前识别区域,读取后一单词，若没有超过关键字长度，将连续读取的字母存在数组里，组成一个单词，直到字符数组的结束，提示文件读取成功。isLetter(charch)判断是否是字母：关键字是英文单词，由字母组成，是字母就返回1，否则返回0值。FindHX(char*keyword)查找哈希表：先利用哈希函数GetKey(keyword)计算出关键字在哈希表中应存放的位置，看看是否是该关键字，若是（即不存在冲突），返回此哈希表的位置，否则（存在冲突），依次往后查找，直到找到相应的关键字，如果到哈希表的表尾仍未找到该关键字，则重新从哈希表的第一个位置依次往后查找，直到找到为止。四、实现部分#includeiostream.h#includefstream.h#includestring#includeiomanip.husingnamespacestd;constintTOTAL=32;constintMAXLEN=10;constintHASHLEN=41;intcont=0;classHashTable{public:6charkeyword[MAXLEN];intcount;intnum;};HashTableHS[HASHLEN];charKeyWords[TOTAL][MAXLEN]={char,double,enum,float,int,long,short,signed,struct,union,unsigned,void,break,case,continue,default,do,else,for,goto,if,return,switch,while,auto,extern,register,static,const,sizeof,typedef,volatile};templateclassTclassHASH{public:voidShow(intkey);intCreatHX(char*keyword);intGetFreePos(intkey);voidResetHX();intGetKey(char*keyword);intisKeyWords(char*word);intRead(char*filename);intisLetter(charch);intFindHX(char*keyword);private:intkey;char*keyword;char*word;charch;};templateclassTvoidHASHT::Show(intkey){if(key0||key=HASHLEN){cout关键字不存在!endl;return;}if(strlen(HS[key].keyword)==0){cout哈希表位置：key记录是空的endl;7return;}cout哈希表位置:key关键字:HS[key].keyword出现次数HS[key].countendl;cont++;}templateclassTintHASHT::CreatHX(char*keyword){intkey;if(!isKeyWords(keyword))return-1;key=GetKey(keyword);if(strlen(HS[key].keyword)0){if(strcmp(HS[key].keyword,keyword)==0){HS[key].count++;return1;}key=FindHX(keyword);if(key0){key=GetFreePos(GetKey(keyword));if(key0)return-1;strcpy(HS[key].keyword,keyword);}if(key0)return-1;HS[key].count++;}else{strcpy(HS[key].keyword,keyword);HS[key].count++;}return1;}templateclassTintHASHT::GetFreePos(intkey){intfind,tem=0;if(key0||key=HASHLEN)return-1;8for(find=key+1;findHASHLEN;find++){tem++;if(strlen(HS[find].keyword)==0){HS[find].num=tem;returnfind;}}for(find=0;findkey;find++){tem++;if(strlen(HS[find].keyword)==0){HS[find].num=tem;returnfind;}}return-1;}templateclassTvoidHASHT::ResetHX(){inti;for(i=0;iHASHLEN;i++){strcpy(HS[i].keyword,);HS[i].count=0;HS[i].num=0;}}templateclassTintHASHT::GetKey(char*keyword){return(keyword[0]*100+keyword[strlen(keyword)-1])%41;}templateclassTintHASHT::isKeyWords(char*word){inti;for(i=0;iTOTAL;i++)if(strcmp(word,KeyWords[i])==0)return1;return0;}9templateclassTintHASHT::isLetter(charch){if((ch='a'&&ch='z')||(ch='A'&&ch='Z'))return1;elsereturn0;}templateclassTintHASHT::FindHX(char*keyword){intkey,find,tem=0;if(!isKeyWords(keyword))return-1;key=GetKey(keyword);if(strcmp(HS[key].keyword,keyword)==0)returnkey;for(find=key+1;findHASHLEN;find++){tem++;if(strcmp(HS[find].keyword,keyword)==0){HS[find].num=tem;returnfind;}}for(find=0;findkey;find++){tem++;if(strcmp(HS[find].keyword,keyword)==0){HS[find].num=tem;returnfind;}}return-1;}templateclassTintHASHT::Read(char*filename){charword[MAXLEN],ch