利用哈希技术统计C源程序关键字出现频度（完整版）

1、利用哈希技术统计C源程序关键字出现频度目录1. 需求分析说明32. 总体设计33. 详细设计44. 实现部分55. 程序测试106. 总结11一、需求分析说明1课程设计目的本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。2题目要求1）题目内容：利用Hash技术统计某个C源程序中的关键字出现的频度2）基本要求：扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度。用线性探测法解决Hash冲突。设Hash函数为：Hash（key）（

2、key的第一个字母序号）*100+（key的最后一个字母序号 ）MOD 41二、总体设计一.算法思想描述首先读取关键字文件以建立二叉排序树以供后续查询，每个树节点保存一个关键字字符串及指向左右子树的指针。同时创建一Hash表，每个节点除应保存关键字字符串外，还应保存关键字频数及该存储单元冲突次数。然后扫描一个C源程序，每次扫描一行，从中循环分离出每个单词，每次均查找其是否为关键字，若是，则按计算公式计算其KEY值并在Hash表中进行相应操作，若该节点为空则插入否者比较其是否与现有关键字相同，若相int max;/ max为Hash表长度同则增加其频数，否则增加其冲突次数并继续线性探测下一个存储

3、单元，完了继续操作下一个分离出来的单词，如此循环运行直至扫描结束。编写本程序时，使用了二叉树创建、二叉 树查找、Hash表的建立和操作及文件操作等基本算法。2. 三、详细设计3. （程序结构/Hash表存储结构/定义/num为频数，time为冲突次数/定义typedef struct node char s20;int num,time;node;二叉排序树结构定义typedef struct nod char s20;struct nod *left,*right; nod;倆()将Hash表中数据初始化strcmp()字符串比较strcp()字符串复 一制函数说明：nod *creat()

4、:读关键字文件，按照关键字中字符字母先后顺序建立二叉排序树，每个节点中保存一 个关键字；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 町：判断Hash表中第

5、k个单元中有无关键字，若无则将当前关键字存入该单元，返回；否则比较两关键字是否相等，相等则将该单元频数加一，返回；不相等则将该单元冲突数加一并循环线性探测下一个存储单元；int strcmp(char t,char s):字符串比较；void prin(nod *head):以左根右的顺序将二叉排序树打印在屏幕上;四、实现部分#i nclude #in clude #i nclude using n amespace std;const int TOTAL=39; 39 个关键字const int MAXLEN=10; / 关键字长度const int HASHLEN=41; / 哈希表长度i

6、n t co nt=0; /统计哈希表中的关键字个数void jiemia n();void Show(i nt key);void Select(i nt choice);int Read(char *file name);int In put();int isLetter(char ch);int isKeyWords(char *word);int Fin dHX(char *keyword);int CreatHX(char *keyword);int GetFreePos(i nt key);void ResetHX();int GetKey(char *keyword);char

7、KeyWordsTOTALMAXLEN=/构造二维数组存储39个关键字asm,auto,break,case,cdecl,char,co nst,co ntin ue,default,do,double,else,e nu m,extern,far, float,for,goto,huge,if,in t,i nterrupt,lo ng, near,pascal, register,return,short,sig ned,sizeof, static,struct,switch,typedef,u nio n,un sig ned,void,volatile,while,;I*typede

8、f struct HASHchar keywordMAXLEN;in t cou nt; /出现次数(频度)in t co n; /冲突次数HASH HSHASHLEN;/* */class HASH /哈希表类public:char keywordMAXLEN;in t cou nt; /出现次数(频度)in t co n; /冲突次数;HASH HSHASHLEN;int main()ResetHX(); /先清空哈希表coutte ndl;coutt*欢迎使用该软件，请按提示操作*e ndl;coutt*该程序功能是统计一个文件中 C语言关键字的频度*e ndl;coutt*统计开始前请

9、先读取一个文件*e ndl;coutt*e ndl;coutt*by黄耀广*e ndl;coutt=e ndle ndl; jiemia n();Select(I nput(); return(O);void jiemia n()主菜单函数coute ndl;couttt1.读取一个文件endl;couttt2.输出Hash表(关键字总数，冲突次数)endl; couttt3.查询某关键字在 Hash表中的情况endl; coutvtt4.显示Hash表中的冲突关键字endl;couttt5.显示C语言关键字的Hash函数值(作为对照)endl; couttt6.回主菜单endl;couttt

10、7.退出 choice)if(choice7)coutvv输入范围不正确，请重新输入e ndl; elsecoutvv输入错误，请重新输入endl;cin .clear();while(!isspace(ci n.get() /功能：判断字符是否为空白符 说明：当字符为空白符时，返回非零值，否则返回零。/空白符指空格、水平制表、垂直制表、换页、回车和换行符。con ti nue; coutvve ndl;retur n choice;void Show(i nt key)/显示出某关键字的频度if(key=HASHLEN)coutvv关键字不存在!endl;return;if(strle n(

11、HSkey.keyword)=O)cout哈希表位置：vvkeyvv 记录是空的endl; return ;coutvv哈希表位置：vvkeyvv 关键字：HSkey.keyword出现次数HSkey.count file name;coutvve ndl;Read(filename);/read函数从一个文件读字节到一个指定的存储器区 域，由长度参数确定要读的字节数Select(I nput(); break;case 2:coutvv每次显示5行，请按回车键继续！vvendlvvendl;for(i=0;ivHASHLEN;i+)Show(i);if(i+1)%5=0) getchar()

12、; /为了清晰，每次显示 5 行coutvv关键字总数为：vvco ntvve ndl;Select(I nput(); break;case 3:coutvv请输入你想要查找的关键字：;cin word; coutvve ndl;Show(Fi ndHX(word); Select(I nput(); break;case 4: coutt冲突关键字列表endlendl;coun t=0;for(i=0;i0)key=GetKey(HSi.keyword);if(key!=i)coun t+;coutt关键字:HSi.keyworde ndl; coutt哈希表当前位置:iendl; cou

13、tt冲突次数:HSi.conendlendl;if(co un t=0)cout没有冲突endl;elsecoutt 冲突关键字共：count个endl;Select(I nput();break;case 5:cout C语言中的关键字和其在哈希表的位置:endl;for(i=0;iTOTAL;i+)coutvsetiosflags(ios:left)vvvvsetw (2)GetKey(KeyWordsi) vvsetiosflags(ios:left)vvsetw(11)v=a&chv=z)|(ch=A&chv=Z) ) return 1;else return 0;是字母就返回1,否则

14、返回0值int Fin dHX(char *keyword)/查找哈希表，分块查找int key,fi nd,tem=0;if(!isKeyWords(keyword) return -1;key=GetKey(keyword);if(strcmp(HSkey.keyword,keyword)=0) return key;for(fin d=key+1;fi ndvHASHLEN;fi nd+)线性探查法顺序查找哈希表中是否已存在关键字tem+; 统计冲突次数if(strcmp(HSfi nd.keyword,keyword)=0)HSfi nd.co n=tem;return fin d;

15、for(fin d=0;fi ndvkey;fi nd+)tem+;if(strcmp(HSfi nd.keyword,keyword)=0)HSfi nd.co n=tem;return fin d; return -1;int CreatHX(char *keyword) / 建立哈希表int key;if(!isKeyWords(keyword) return -1; key=GetKey(keyword); / 计算哈希值if(strlen(HSkey.keyword)0) /判断关键字表中该位置是否存在关键字 /已经存在有关键字if(strcmp(HSkey.keyword,keyw

16、ord)=0)再判断哈希表中该位置的关键字是否相同HSkey.cou nt+;return 1;key=Fi ndHX(keyword); 不相同，继续查找if(key0) key=GetFreePos(GetKey(keyword); if(key0) return -1;strcpy(HSkey.keyword,keyword); / 将关键字插入哈希表 if(key0) return -1;HSkey.cou nt+;else /该位置为空，直接将关键字插入该位置中strcpy(HSkey.keyword,keyword);HSkey.cou nt+;return 1;int GetFr

17、eePos(int key) /在哈希表中给关键字找个位置插进去int fin d,tem=0;if(key=HASHLEN) retur n -1;for(fin d=key+1;fi ndHASHLEN;fi nd+)/ 先找后面的位置tem+;if(strle n(HSfi nd.keyword)=0)HSfi nd.co n=tem;return fin d; for(fin d=0;fi ndvkey;fi nd+)/ 再找前面的位置tem+;if(strle n(HSfi nd.keyword)=0)HSfi nd.c on=tem; return fin d; return -1

18、; 哈希表已满void ResetHX()重置哈希表，int i;for(i=0;ivHASHLEN;i+)strcpy(HSi.keyword,); / 不能用等号赋值HSi.cou nt=0;HSi.co n=0;int GetKey(char *keyword) / 哈西函数 /Hash函数为：Hash(Key)=(Key的首字母序号)*100+(Key的尾字母序号) Mod 41return ( keyword0*100+keywordstrlen(keyword)-1 ) % 41; / 这里不要忘了减1int isKeyWords(char *word) 判断是否关键字int i;

19、for(i=0;ivTOTAL;i+)if(strcmp(word,KeyWordsi)=0) return 1;return 0;5. 程序测试:文件一：0while903return804long305typedef106goto207if38010do1013void15014case10015default1019sizeof1021int29122switch1024else16027char13228un sig ned2033struct4034break100总关键字数：164总冲突数：3文件二：HASH序号关键字频数冲突数0while1103return13004long2606goto107if194010do14013void1014case12015default5016static37019sizeof12021in terrupt97022int69123for75224else68225far1126switch1027char73128u