利用Hash技术统计C源程序中关键字的频度

1、利用Hash技术统计C源程序中关键字的频度.设计题目:扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的度。用线性探测法解决Hash冲突。设Hash函数为：Hash（Key）=（Key的首字母序号）*100+（Key的尾字母序号）Mod41关键字：asmdefaultfloatlongsizeofvoidbreakdofornearstaticvolatilecasedoublegotopascalstructwhilecdeclelsehugeregisterswitchcharenumifreturntypedefconstexternintshortun

2、ioncontinuefarinterruptsignedunsigned。.题目分析:1.数据存放形式：关键字已列出是字符串型，因此关键字表存储结构为：typedef struct因此关键字表存储结构为：/* 关键字表的存储结构*/charstrchar_max;key_node;Hash表要记录：相应关键字、频度、冲突次数，所以Hash表结构为：typedef struct/*Hash 表中的结点结构*/* 关键字 */*频度 */* 冲突次数 */charstrchar_max;intfrequency;intconflictTimes;hash_node;2. 数据输入方式：程序设计要

3、求是扫描一个已有C语言源代码，故一定要有文件流以操作文件从中读出信息，但也有人工输入程序或为了改变冲突（关键字出现顺序可改变冲突）而采用手工写入程序或关键字，这时从屏幕输入信息也是有必要的。3. 如何识别关键字：不管是何种方式输入信息总会有无关信息的存在，所以过虑信息也十分重要。我采用逐个扫描字符的方法来从长字串中取出单词，然后将取出的单词与关键字表中的关键字进行比较。比较时我采用的是顺序查找，因为我在建立关键字表时没有进行排序。4. Hash函数（线性探测法）：此函数是按设计要求：Hash（Key）=（Key的首字母序号）*100+（Key的尾字母序号）Mod41写出的。由些可知Hash表的

4、大小要小于等于41，为此我把HASH表大小设计为41。根据“Hash（Key）=>地址”找出相应位置，如果当前位为空则插入，但如当前位有数据则判断是否为要找的数据，是则频度加1，不是则顺序往下找，找到则频度增加，找不到则调整冲突并插入数据。伪语言为：if（当前位为空）直接写入数据关键字个数加1else/*如果当前位有关键字存在*/while（找关键字，找到时、或找不到时停止）i=（i+1）%hash_number;/*线性探测*/if（找到）则频度加1else/*如果找不到*/冲突加1加入新关键字关键字个数加15. 数据统计：在完成数据输入后对数据进行处理并作出统计。在程序中输出冲突次数

5、、频率、总关键字个数等信息。三程序结构与流程图：1. 总体结构：程序由三大模块组成：输入与菜单选择模块、数据统计模块、图形绘制模块。其中主要部分是：数据统计模块，它完成数据的统计（即程序的主要目的：对C源文件中关键字的统计）；最复杂部分是：输入与菜单选择模块，它完成人机交互工作和数据输入工作，如不考虑界面则非常得简单，但与窗口界面相结合时则有很多难以实现和细节。如：如何取得键值、如何过虑按下的无用键值、如何将有效键值内容形象地输出在窗口界面中来模拟输入界面等等。图形绘制是最繁的模块，其中大量代码便是绘图代码。其编译环境图形界面方面不是做的太好，很多东西都要自己用代码写，如画主窗体、画立体控制面

6、板等等，但有些编译环境在窗口工具上做的很好，如VB、BCB、VC、Delphi、Java等。2. 输入与菜单选择模块：菜单选顶有：1）输入文件名操作：F;2）输入字符串操作：P;3）清除已有Hash表操作：C;4）退出程序操作：ESC;其关系图如下：正常输入 或按(ESC) 时返回主 界面J空字符串时按回车或按(ESC)回主界面<_)显示清除 界面并在 5秒后返 回主界面终止程序，退出系统.)3.数据统计模块：数据统计模块是对C源代码进行关键字统计的主要模块，其中包含四个函数体：1)主体数据统计(voidstatistic(key_nodekeyList,hash_nodehashLis

7、t,char*str)；2)关键字判断函数(intisKeyword(key_nodekeyList口,char*str,intn);3)Hash函数(inthash(char*str,intn);4)Hash查找函数(voidhashSearch(hash_nodehashList,char*str,intn)。四个函数的关系图如下：4.图形绘制模块：图形绘制模块是界面程序的关键部分，它有定义、初始化、清除、重绘、刷新等功能。我根据其在程序中的特定功能分为了四个部分：1)图形界面的定义和初始化(放在main()主程序中)；2)清除区域函数(voidclear(intcolor,intfill

8、Color,intx1,inty1,intx2,inty2);3)画欢迎和操作说明图形函数(voiddrawWelcome();4)画表格函数(voiddrawTable(intnumber,key_nodekeyList,hash_nodehashList口)。功能示意图如下：Us：ing：:H自Mh.：口C：smUe出：F±1贷，M.ksyudrds：:：:：-：甘画欢迎和操作E明图形函更(_elcome0)所ElRPutinafileiprssslFToinputstrimgipress：PClearthehasih1istpres.SiCPresswEscIBtoExit,e

9、1iF始成ma初完在代代中卜面是程序下运行的其它界面：第一幅是文件名输入界面,下一幅是文件名输入后Hash表情况图。：>：UMic苗*口C0Mn：tCSourct-F出1处;MK出血立侬:INumiKeMuordNumKeyword1asn20eIse2deiFau1121Ihuge3float22regiister4long23kwitch5siz:eo1F24charGvoid25enun7break26ifedo27return9for28typdfirIOnear29conststmtit30extern12uolat±Je31int13case32shoft14dot

10、jble33union15goto34contLnue18昌鼻匚总135far17struet3Einterrupt18wh>ile37igoed19cdtec138unsignedInputFi1NaneITheIKeu。口rdIListPutinafileiprssslFToinputstrimgipress：Ptheihasih1istpres-S*CPressMEsc"toExit,Exit：Esc0：Xlogiehash.eStarthqFileIbyPut：PClearHas-hlListTheHa与hLis-tKuju口Count.Clash2Xhnr七SioSA

11、1on通I2：21o2-itzeofJL23sicjned1Clcase5±24NIILMILNIILqQOtO12Z5NIILNILHIL与31tchM1MBroir7JLrus-ar-J.O27if27711Ofloa't11D目=_LoS9laffii-alc弓O目csitilimiIL口3O口aoIOextern1o31Tar1oxxunionX32while7O12con-fcinuiiQ1口33tur-in4113dhar3223:4defaLi111o电void6.33NILH1L.NIL3.5asMX1aIsaX2216struct313：?"耳与自

12、己】11X7V431a把TJIHJL口3B片百口is-if1O18cflciuts-IsX口39uns±mcaH1O19const1o口static2O2Ostf3口int236|Cdunti3-fkciwor-dsI38E.Xit：E.5CSt-art13回File：F4itartbyrut：PClearhis.t：CIha：HAhi：to-：C'QUnt:发也短:Ifi1qj-s：5.程序伪码：程序的各个分支已经说明了，把几个分支组合在一起就形成了一个完整的:函数统计C源代码关键字的程序。以下是主要程序的代码：hashinthash(char*str,intn)41*/*

13、Hash（Key尸（首字母序号）*100+（尾字母序号）Modinttemp1,temp2;str=strlwr(str);tempi=*str;temp2=*(str+n-1);/*存放首字母和尾字母ASCII码值的中间变量*/*将字符串中大写字符变成小写*/*取关键字的首字母*/*取关键字的尾字母*/return(tempi-97)*100+temp2-97)%41;voidhashSearch(hash_nodehashList,char*str,intn)/*Hash查找/参数|hash表，关键字字符串及其长度*/chartempchar_max=""/*临时关键字

14、字符串*/inti,k;/*i,k存放hash值*/strncpy(temp,str,n);i=hash(temp,n);k=i;if(hashListi.frequency=NIL)数加1*/*如果当前位为空，为空则直接写入，关键字个strcpy(hashListi.str,temp);hashListi.frequency=1;hashListi.conflictTimes=0;/*字符串赋值*/count+; else/* 如果当前位不有关键字存在 */while(strcmp(hashListi.str,temp) 找到时、或找不到时停止*/&& hashListi.f

15、requency != NIL)/* 找关键字 ,i =(i+1)%hash_number;if(hashListi.frequency != NIL) hashListi.frequency +;else键字,且关键字个数加1*/* 线性探测 */* 如果找到，则频度加 1*/*如果找不到，则冲突加1 ，并加入新关hashListk.conflictTimes+;/*k是用来保存一开始的hash值*/strcpy(hashListi.str,temp);hashListi.frequency=1;hashListi.conflictTimes=0;count+;intisKeyword(ke

16、y_nodekeyList,char*str,intn)/*判断是否为关键字,用了有序表查找，因为所建表是无序的*/*参数：关键字表，要判断的字符串及其长度*/inti;/*循环变量*/chartempchar_max=""/*临时关键字字符串*/strncpy(temp,str,n);for(i=0;i<key_number;i+)if(!strcmp(keyListi.str,temp)break;if(i=key_number)/*找到返回1，找不到返回0*/return0;elsereturn1;voidstatistic(key_nodekeyList,ha

17、sh_nodehashList,char*str)/*统计函数，统计关键字出现次数*/*参数：关键字表，哈希表，外部读入的字符串*/inti=0,n=0;/*i标注外部string的位置,n单词中的位置*/intlength=strlen(str),booleanChar;/*length外部字符串长度booleanChar记录单个符号是否为字母*/charch;/*保存单个字母*/chartempchar_max=""/*保存单词*/while(i<strlen(str)/*判断完整个字符串时结束*/ch=*(str+i);/*从外部字符串中取一个字符*/boole

18、anChar=isascii(ch)&&isalpha(ch);/*判断是否为字母*/if(booleanChar&&n<char_max-1)/*当前字符是字母时，且小于关键字长度时*/tempn+=ch;/*单词中加入一个字母*/if(booleanChar&&i=length-1|!booleanChar)/*如果这是最后一个字母，或当前字符不是字母时*/if(n&&isKeyword(keyList,temp,n)/*字符不为空，且是关键字*/hashSearch(hashList,temp,n);/*把关键字加入哈

19、希表中*/n=0;/*单词个数清空以记录下一个单词*/i+;/*外部字符串位置加1以判断下一个字母*/四.问题与缺陷:1. 程序调试中出现的的问题：我在程序调试中出现了很多的问题，有基本的语法问题、程序设计问题等等不过主要有有下面几个问题：a) 界面输入问题：由于要有界面所以界面输入就是一个很大难题，如何输入数据，之前我只会用标准IO流进行数据的输入和输出，之后我找了一个有界面八皇后演示程序，其中有操作选择，其数据中从键盘上输入的。我看了其代码发现他是用汇编直接对内存进行读写来获得键盘输入的信息，我对他的代码不是很了解，于是我找了相关函数发现有一个bioskey()函数，它返回键值，于是从此入

20、手我解决了输入问题。b) 键盘信息过滤问题：键盘信息有些是功能键其没有输入意义，我要把这些数据过滤后才行，但有些又是重要的。如退格键、回车键、ESC键。我先做了一个测试程序来测出这些键盘的键值以保留其功能。程序中有些数字就是这些键的键值。c) 字符串问题：我用temp数组存放键盘写入的字符，但清除数组时程序只是把temp中串结束符放在第一个而没有真的除其中的数据，当我再写入一个比之前一个短的字符串这时之前串的部分字符便会出现。于是我引入了一个变量n以记录有用字符个数，并在字符串copy之后在尾部加上串结束符，如此就可以解决字符串问题。d) 转义符问题：转义符，我们在写打开文件路径时写”e:lo

21、gichash.c”，但在写入数组，再由数组中字符串打开文件时只能写”e:logichash.c”这时再多写转义符就错了，我一开始不知道以为是其它方面问题找了半天才发现原来是这出了问题。e) DOS下文件名问题：我在打开文件时要写文件全名，可有的文件名过长。我开始是写全名发现总打不开文件，改短点就打开了，后来发现是DOS下文件名只能有八位，过长时就采用自身的命名方式把文件名改短。如：e:logicfirsthash.c在DOS下文件名为：e:logicfirsth1.c。所以在写文件名时要注意这一点以免打不开文件。2. 程序可以改进的地方：a) 输入界面：输入界面是模拟出来的，程序中有一个记录键盘输入的信息，然后再将此信息在屏幕上以字符串方式输出，所以输入界面没有光标来作提示，这样在你打空格时就不太容易看出有没有按。如加上光标就能轻松看出。b) 动态演示：程序在输入数据后直接给出统计结果，没有让使用者看程序是如何运行的、算法上是如何实现的，如果把