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

：利用哈希技术统计C源程序关键字出现频度 目录一 需求分析说明3二 总体设计3三 详细设计4四 实现部分5五 程序测试10六 总结11一、需求分析说明1.课程设计目的本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。2.题目要求1)题目内容：利用Hash技术统计某个C源程序中的关键字出现的频度2)基本要求：扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度。用线性探测法解决Hash冲突。设Hash函数为：Hash(key)(key的第一个字母序号)*100+(key的最后一个字母序号) MOD 41二、总体设计一 算法思想描述首先读取关键字文件以建立二叉排序树以供后续查询，每个树节点保存一个关键字字符串及指向左右子树的指针。同时创建一Hash表，每个节点除应保存关键字字符串外，还应保存关键字频数及该存储单元冲突次数。然后扫描一个C源程序，每次扫描一行，从中循环分离出每个单词，每次均查找其是否为关键字，若是，则按计算公式计算其KEY值并在Hash表中进行相应操作，若该节点为空则插入否者比较其是否与现有关键字相同，若相同则增加其频数，否则增加其冲突次数并继续线性探测下一个存储单元，完了继续操作下一个分离出来的单词，如此循环运行直至扫描结束。编写本程序时，使用了二叉树创建、二叉树查找、Hash表的建立和操作及文件操作等基本算法。二 三、详细设计 (程序结构/Hash表存储结构typedef struct node /定义 char s20; int num,time; /num为频数，time为冲突次数node;/二叉排序树结构定义typedef struct nod /定义 char s20;struct nod *left,*right;nod; int max; /max为Hash表长度函数说明：nod *creat()：读关键字文件，按照关键字中字符字母先后顺序建立二叉排序树，每个节点中保存一个关键字；void init(node *head)：初始化Hash表各节点数据域；void deal(node *head,nod *parent,char filename)：扫描源文件，分离出每个单词，检验是否为关键字；并根据检验结果来决定是否调用strdeal函数，以对Hash做适当更改；void strcp(node *head,char s,int k)：将新查找到的关键字复制到Hash表中第k个节点存储单元；void strdeal(node *head,char s,int k)：判断Hash表中第k个单元中有无关键字，若无则将当前关键字存入该单元，返回；否则比较两关键字是否相等，相等则将该单元频数加一，返回；不相等则将该单元冲突数加一并循环线性探测下一个存储单元；int strcmp(char t,char s)：字符串比较；void prin(nod *head)：以左根右的顺序将二叉排序树打印在屏幕上； 四、实现部分 #include #include #include using namespace std; const int TOTAL=39; /39个关键字const int MAXLEN=10; /关键字长度const int HASHLEN=41; /哈希表长度int cont=0; /统计哈希表中的关键字个数void jiemian();void Show(int key);void Select(int choice);int Read(char *filename);int Input(); int isLetter(char ch);int isKeyWords(char *word);int FindHX(char *keyword);int CreatHX(char *keyword);int GetFreePos(int key);void ResetHX();int GetKey(char *keyword);char KeyWordsTOTALMAXLEN= /构造二维数组存储39个关键字asm,auto,break,case,cdecl,char,const,continue,default,do,double,else,enum,extern,far,float,for,goto,huge,if,int,interrupt,long,near,pascal,register,return,short,signed,sizeof,static,struct,switch,typedef,union,unsigned,void,volatile,while,;/*typedef struct HASHchar keywordMAXLEN;int count; /出现次数（频度）int con; /冲突次数HASH HSHASHLEN;/*/class HASH /哈希表类public:char keywordMAXLEN;int count; /出现次数（频度）int con; /冲突次数; HASH HSHASHLEN; int main()ResetHX(); /先清空哈希表coutt=endl;coutt* 欢迎使用该软件，请按提示操作 *endl;coutt* 该程序功能是统计一个文件中C语言关键字的频度 *endl;coutt* 统计开始前请先读取一个文件 *endl;coutt* *endl;coutt* by 黄耀广 *endl;coutt=endlendl;jiemian();Select(Input();return(0); void jiemian()/主菜单函数coutendl;couttt1.读取一个文件endl;couttt2.输出Hash表(关键字总数，冲突次数)endl;couttt3.查询某关键字在Hash表中的情况endl;couttt4.显示Hash表中的冲突关键字endl;couttt5.显示C语言关键字的Hash函数值(作为对照)endl;couttt6.回主菜单endl;couttt7.退出endl;int Input()coutendl;coutchoice)if(choice7) cout输入范围不正确，请重新输入endl; elsecout输入错误，请重新输入endl;cin.clear();while(!isspace(cin.get() /功能：判断字符是否为空白符 /说明：当字符为空白符时，返回非零值，否则返回零。 /空白符指空格、水平制表、垂直制表、换页、回车和换行符。 continue;coutendl;return choice;void Show(int key)/显示出某关键字的频度if(key=HASHLEN)cout关键字不存在!endl;return;if(strlen(HSkey.keyword)=0)cout哈希表位置：key 记录是空的endl;return ;cout哈希表位置: key 关键字: HSkey.keyword 出现次数 HSkey.countendl;cont+;void Select(int choice)char filename128,wordMAXLEN;int i,key,count;switch(choice)case 1:coutfilename;coutendl;Read(filename);/read函数从一个文件读字节到一个指定的存储器区域,由长度参数确定要读的字节数Select(Input();break;case 2:cout每次显示5行，请按回车键继续！endlendl;for(i=0;iHASHLEN;i+)Show(i); if(i+1)%5=0) getchar(); /为了清晰，每次显示5行cout关键字总数为：contendl;Select(Input();break;case 3:coutword;coutendl;Show(FindHX(word);Select(Input();break;case 4:coutt冲突关键字列表endlendl;count=0;for(i=0;i0)key=GetKey(HSi.keyword);if(key!=i)count+;coutt关键字: HSi.keywordendl;coutt哈希表当前位置: iendl;coutt冲突次数: HSi.conendlendl;if(count=0) cout没有冲突endl;elsecoutt冲突关键字共:count个endl;Select(Input();break;case 5:cout C语言中的关键字和其在哈希表的位置:endl;for(i=0;iTOTAL;i+)coutsetiosflags(ios:left)setw(2)GetKey(KeyWordsi)setiosflags(ios:left)setw(11)KeyWordsi;if(i+1)%5=0) coutendl;coutendl;Select(Input();break;case 6:jiemian();Select(Input();case 7:break;/退出default:Select(Input();return;int Read(char *filename) /读取文件char wordMAXLEN,ch;int i;FILE *read;if( (read=fopen(filename,r)=NULL ) /只读方式打开一个文本文件,只允许读数据cout文件不存在,请确认好再输入!endl;return -1;ResetHX(); /读取文件前先清空哈希表while(!feof(read) /feof()是文件结束检测函数,如果没有结束,返回值是0,结束了是1i=0;ch=fgetc(read); /读取一个字符while(isLetter(ch)=0 & feof(read)=0 ) ch=fgetc(read);/如果不是字母的话接着读取while(isLetter(ch)=1 & feof(read)=0 )if(i=MAXLEN)while(isLetter(ch)=1& feof(read)=0)ch=fgetc(read);i=0;break;/超过关键字长度将跳过当前识别区域,读取后一单词else /将连续读取的字母存在数组里，组成一个单词wordi+=ch;ch=fgetc(read);wordi=0; /字符数组的结束标志if(isKeyWords(word)CreatHX(word);fclose(read);cout读取成功，文件中关键字已经存入hash表，请继续操作=a&ch=A&ch=Z) ) return 1;else return 0;/是字母就返回1，否则返回0值 int FindHX(char *keyword) /查找哈希表，分块查找int key,find,tem=0;if(!isKeyWords(keyword) return -1;key=GetKey(keyword); if(strcmp(HSkey.keyword,keyword)=0) return key;for(find=key+1;findHASHLEN;find+)/线性探查法顺序查找哈希表中是否已存在关键字tem+; /统计冲突次数if(strcmp(HSfind.keyword,keyword)=0)HSfind.con=tem;return find; for(find=0;find0) /判断关键字表中该位置是否存在关键字 /已经存在有关键字if(strcmp(HSkey.keyword,keyword)=0) /再判断哈希表中该位置的关键字是否相同HSkey.count+;return 1;key=FindHX(keyword); /不相同，继续查找if(key0)key=GetFreePos(GetKey(keyword);if(key0) return -1;strcpy(HSkey.keyword,keyword); /将关键字插入哈希表if(key0) return -1;HSkey.count+;else /该位置为空，直接将关键字插入该位置中strcpy(HSkey.keyword,keyword);HSkey.count+;return 1;int GetFreePos(int key) /在哈希表中给关键字找个位置插进去int find,tem=0;if(key=HASHLEN) return -1;for(find=key+1;findHASHLEN;find+) /先找后面的位置tem+;if(strlen(HSfind.keyword)=0)HSfind.con=tem;return find; for(find=0;findkey;find+) /再找前面的位置tem+;if(strlen(HSfind.keyword)=0)HSfind.con=tem;return find; return -1; /哈希表已满void ResetHX() /重置哈希表，int i;for(i=0;iHASHLEN;i+)strcpy(HSi.keyword,); /不能用等号赋值HSi.count=0;HSi.con=0; int GetKey(char *keyword) /哈西函数 /Hash函数为：Hash(Key)=(Key的首字母序号)*100+(Key的尾字母序号) Mod 41return ( keyword0*100+keywordstrlen(keyword)-1 ) % 41; /这里不要忘了减1 int isKeyWords(char *word) /判断是否关键字int i;for(i=0;iTOTAL;i+)if(strcmp(word,KeyWordsi)=0) return 1; return 0; 五程序测试：文件一：HASH序号关键字频数冲突数0 while 903 return 804 long 305 typedef 106 goto 207 if 38010 do 1013 void 15014 case 10015 default 1019 sizeof 1021 int 29122 switch 1024 else 16027 char 13228 unsigned 2033 struct 4034 break 100总关键字数：164总冲突数：3文件二：HASH序号关键字频数冲突数0 while 1103 return 13004 long 2606 goto 107 if 194010 do 14013 void 1014 case 12015 default 5016 static 37019 sizeof 12021 interrupt 97022 int 6