版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、哈希表技术判别两 个源程序的相似性实验报告Admi nistrator 2014-12-26一. 问题描述实验题目:对于两个 C语言的源程序清单,用哈希表的方法分别统计两程序中使用C语言关键字的情况,并最终按定量的计算结果,得出两份源程序的相似性。要求与提示:C语言关键字的哈希表可以自建,也可以采用下面的哈希函数作为参考:Hash(key)=(key第一个字符序号*100+key最后一个字符序号)41表长m取43。此题的工作主要是扫描给定的源程序,累计在每个源程序中C语言关键字出现的频度。为保证查找效率,建议自建哈希表的平均查找长度不大于2。扫描两个源程序所统计的所有关键字不同频度,可以得到两
2、个向量。如下面简单的例子所示:关键字voidiritforcharifelaewhile程序1中关键字频度4:343702程序2中关犍字频度4254521哈希地址012345678g根据程序1和程序2中关键字出现的频度,可提取到两个程序的特征向量X1和X2,其中X1= (4 3 0 4 3 0 7 0 0 2)X2= (4 2 0 5 4 0 5 2 0 1)一般情况下,可以通过计算向量Xi和Xj的相似值来判断对应两个程序的相似性,相似值的判别函数计算公式为:其A I "質/肌览的值介于o.nZ间,也称广义余弦,即 S<X =cose. X =X 时,(X r X 1 -1.
3、0-0: XX,并别恨大时.S )接近S 时姿近耐器 如Xl=«l 0厂庄2=(。丄)"则SXXj = OJ 6=»/2t町以用下山啲二维的團示来直观地衣示向戢的HI似用L色烏|:u章相做度示意圏fr此惜况卜一,连而粳做进一步的韦恵*亦卜一图所吓;国3. 4向星JL何和离从图中石: 圧悴S(扎,乂和g(芷龟)的估雄If的,但席规上必更郴忱囚此当£值搖近工的时僦.为邂免惺判和個性5J能是夬州很小模值很大的囱量X应当再次计亂Z何的“几科距离“ D(X,XJB Jt计祥含貰均:也尤八X討T K上J(£ 疋訂(*厂X#)<3-21最后的相似性判别
4、计算可分两步完成:第一步用式(3-1)计算S,把接近1的保留,抛弃接近。的情况(把不相似的排除);第二步对保留下来的特征向量,再用式(3-2)计算D,如D值也比较小,说明两者对应的程序确实可能相似(慎重肯定相似的)。S和D的值达到什么门限才能决定取舍?需要积累经验,选择合适的阑值。3)测试数据:做儿个编译和运行都无误的C程序,程序之问有相近的和差别大的,用上述方法求S并对比差异程度。4)输入输出:输入为若干个c源程序,输出为程序问的相似度以及向量的几何距离。基本要求:建立哈希表,统计源程序中关键字出现的频度,并计算多个源程序之间的相似 度。测试数据:自己在网上找到一些C语言程序,分别为test
5、1.txt,test2.txt,test3.txt等。运行结果应为输出每个源程序关键字的出现的频度和源程序之间的相似度以及向量的几何 距离。二. 需求分析1. 本程序用来通过建立哈希表求源程序关键字的出现的频度和源程序之间的相似度以及向 量的几何距离。2. 用户可以将源程序的.txt文件放入hashtable文件夹中,运行程序就可以输出每个源程序 关键字的出现的频度和源程序之间的相似度以及向量的几何距离。三. 概要设计为了实现上述功能,可以用结构体表示哈希表,因此需要哈希表的抽象数据类型。哈希表抽象数据类型的定义:ADT hashtable数据对象:D=ai |a i ElemType,且各不
6、相同,i=1,2.,n,n >0数据关系:R=0基本操作:Hashfu nc(char str);Hashfi nd(char *words); creathash(void); resethash(i nt n); isletter(char ch);readc(char * file name); getkey(char *str,i nt len); copyco un t(i nt x,i nt n); check(i nt *x1, i nt *x2);end ADT3. 本程序实现模块主程序模块哈希表程序模块:实现哈希表的抽象数据类型 调用关系:主程序模块|哈希表程序模块计算
7、相似度和向量的几何距离的模块四详细设计1.各个子函数的设计1) 创建哈希表函数函数原型:void creathash(void);输入:读取存储了32个关键字的文件 ckey.txt思路:通过对 ckey.txt文件逐行赋值给创建的str字符数组,并将该数组调入Hashfunc 函数。(2) 将关键字根据哈希函数放入哈希表中的指定位置的函数函数原型:void Hashfu nc(char str);思路:对调进来的str数组通过调用getkey函数得到该关键词的key值后放入哈希表中的特定位置,并用线性探索来解决冲突。(3) 在哈希表中找是否该words为关键字,并统计频度的函数函数原型:in
8、t Hashfi nd(char *words);思路:将调进来的word字符数组先调用getkey函数获取key值,然后在哈希表里查找是否存在该字符串,如果存在则该关键字对应的频度加1.(4) 重置哈希表函数函数原型:void resethash(i nt n);Null,同时将频度全部置为功能:当n为0时,将指向哈希表中关键字的指针置成0.而当n为1时,仅仅将频度置为 0.( 5)获取单词 key 的函数函数原型: int getkey(char *str,int len);思路:用 key1 存储关键字的首字母, key2 存储关键字的末字母,然后通过哈希函 数得到 key 的值并返回。
9、(6) 判断是否为字母的函数函数原型: int isletter(char ch);思路:如果调进来的ch字符的ASCII值在az或AZ范围内的话则返回1,否则返回 0.(7) 读取源程序文件中的单词的函数函数原型: int readc(char * filename);思路:为了读取源程序文件中的单词,所以一个字符一个字符的,如果读的超过最 大关键字长度将会跳过当前识别区域,读取下一个单词,将得到的该单词调入Hashfind 函数,来判断是否为关键字,并统计频度。(8) 将频度拷贝到数组里的函数函数原型: void copycount(int x,int n);功能:将哈希表中关键字的频度复
10、制到 x 数组中,以便进行后面相似度等的计算。(9) 检查两个源程序是否相似的函数函数原型: void check(int *x1, int *x2);思路:对调进来的 x1 和 x2 数组进行相似度计算,若相似度大于设定好的阈值,则 再进行几何距离计算,最后给出两个文件是否相似的判断。( 1 0)取模函数函数原型: float Mol(int *x);思路:通过求向量模值的数学知识求 x 数组的模( 1 1)点积函数函数原型: int Dot(int *x1, int *x2);思路:通过点积的数学知识对两个向量求点积(12) 求相似度S的函数函数原型: float S(int *x1,in
11、t *x2);思路:根据题目给的求相似度的公式求x1和x2数组的相似度(13) 求距离D的函数函数原型: float D(int *x1, int *x2);思路:用题目给的球几何距离的公式求 x1 和 x2 数组的几何距离2主函数伪码int main()char filename1="test1.txt"char filename2="test12.txt"char filename3="test13.txt"int x1hashlen,x2hashlen,x3hashlen;/存储频度的数组,用于相似度S的计算resethash(
12、0);/完全重置哈希表,即哈希指针置为NULL频度置为0creathash();/通过文件ckey.txt 创建哈希表 readc(filename1);试源程序文件 copycount(x1,hashlen);频度复制给 x 数组 resethash(1);count 置为 0 readc(filename2); copycount(x2,hashlen); resethash(1); readc(filename3); copycount(x3,hashlen); cout<<"t"<<" 哈希序号 "<<&quo
13、t;/t"<<" 关键字 "<<"读取第一个测讲统计好的仅仅将频度 同上t"<<" 频度 1"<<"t"<<" 频度 2"<<" t"<<" 频度 3"<<endl; for (int i = 0; i < 41; i+)if(hashti.hash1!=NULL)cout<<"t"<<i<<
14、;"t"<<hashti.hash1<<"t"<<x1i<<"t"<<x2i<<" t"<<x3i<<endl;cout<<filename1<<" check(x1,x2);和"<<file name2<<"的相似情况为:/"<<endl;相似度cout<<filename1<<"和 &
15、quot;<<filename3<<"的相似情况为:"<<endl;check(x1,x3);cout<<filename2<<"和 "<<filename3<<"的相似情况为:"<<endl;check(x2,x3);检查return 0;3. 调用关系图readcisletterhashfi ndgetkeycopycountresethashcreathashhashfu ncSDotcheckDMol五调试分析1.遇到的问题分析1)
16、 ='与=的问题赋值号与等号的问题虽然平时一直都会注意,但是有时候粗心也容易犯错,就比如在 该 语 句 中 :if(fp=fope n("ckey.txt","r")=NULL)写 成 了if(fp=fope n( "ckey.txt","r")=NULL),导致运行时出现下图Microsoft Visual C + + Debug LibraryDebug Assertion FailedlProgram F;数另詰沟皇脸h日5htabIELbughashtabIe.exeFile;Lin 居:50Exp
17、resdon: str != MULLFor nformatton on houv your program car cause an assertion failure-. $亡亡 the Vkusl C+ documentation on asserts.(Pfes& Retry to dbug the application中止舛葩(R)«M<B看到过一本讲编程的书说为了避免这种错误,可以#define = equal,这样就变成了if(fp=fope n( "ckey.txt","r")equalNULL)。虽然这样确实可
18、以避免该类错误,但是我觉的也没有太大的必要,只要平时注意点小心点就是了。而且如果在visual studio2012上编程时,一般是不允许出现fopen这种不安全函数的,要使用它推荐的fopen_s函数,使用如 下errno_t err:if (err-fopen_s t&fp, rF:WEiial Studio codeWHashWckey. txt % "e") ) 1=0) 'coutcan't ere at f lie iXri"exit (0):2) 第二个问题出现在creathash函数中,也比较难找。当时程序没有红色的那两句,
19、while (fgets(str,size,fp)!=NULL)/if (str=NULL)break;len gth=strle n( str);strle ngth-1='0:读取一行写入一行Hashfu nc(str); fclose(fp);接下来的是没有那两句的运行后的窗口截图bbC:wi 口 d owssyste m32cmd.exe哈希序号1floata频度i频度2U2tiF or050004vo Ltlie8&ault0Q7du0隹adoubleaEl7typedef0&11breakaa12rctjistGr3&13returnaa14if如果
20、加上那两句红色的语句后的运行窗口就是这样的C:wi ndowssystem 3 2cmd.exe哈希序号012710111Z131415161718232425262?Z? 自闾关畤frnutnint lonar ined s izenF quitch un ion chai* UD±d AUtO const &hoi*t double struct typedef volatile f ur*(1。 break float uh Lie频度1002000阿000000a000000&10 0 0后来调试时发现,(就拿文件ckey.txt中的第一个关键字为例)ckey
21、lxt -记事本文件(F) 锚旧艳式Q直春M 勰動H)auto b 匚 wak case char cons t continue default do double else enuin estern floa t for goto if int long register return shor t signed sizeof static struct switch typedef在没有那两句红色语句时,调试窗口是这样显示的1 4 X阖nxn*rhar吕魏窗口胃部变昼 饑程 擡块.说明在执行逐行读取关键字的那段代码时,它把每一行的换行号也读进了str数组里,导致输出时,每个关键字都做了换
22、行,便有了上面的第一个截图。所以我的解决办法就是加入红色的那两句,即length=strlen(str); strlength-1='O:也就是把最后的换行号替换为0 '.3) 第三个问题出现在 readc函数中。在下面代码中原本没有注销的那一语句。1=0;wards i-n-=ch; rh=fgetc(fpl):/words if l;*/ Hashf ind (鸭qrd):felosa|fpl):所以导致这样的结果:C:windowsAsystem32ctTid.exe哈希序号黄键字频度i频度20enuri001exterriAM2int003longf004&
23、163;griecl00&Srj.HeDF00&quitch7un Lon19char11wid12Aura13const丄415double1&&truGt001?def001Bvolatlie陌02,3f or0024if0025du002&break002?float0027uh lie00即统计不到源程序文件中的关键字的频度,均显示为0.然后进行调试发现(就以读取到的第一个单词in elude为例):M誨口轄期从调试窗口可看出读取完一个完整的单词后,它自己不能给该 word数组赋值0 '来结束,这样导致的结果将会发生在Hashfind函数
24、中的strcmp函数中,即FTitchar 柿 ord?int keyj len,f ini.1 enF st r 1 en (wa r As):key=etkey (vords, len):whilr- (hasht key. hash 1 -MBLL)key+ ;key=key41.i i (st rciip (hasht k ey. hash w. i Is) =0)!hasht key * count+:ESt llfll 1 :for (find=jey+L : fen ; f ind.+)f线性探晋法li it (liasht £in.dj . tiash I !=J.
25、.Ll.)if (stramp (hashi: f ind. liashl、w r'is)=D)通过上网查资料后知道,strcmp函数进行两字符串比较时是两个字符串自左向右逐个字符相比(按ASCII值大小相比较),直到出现不同的字符或遇'0'为止。而我的 hashtkey.hash1 数组里的字符串为i, n,c,l,u,d,e0 '而 words 数组为i, n,c,l,u,d,e,所以比较的结果是它们不相等,就统计不到关键字的频度。所以我的解决办法即注销的那句:wordsi='0:对每次读到的单词后都加一个0 '。4) 第四个问题出现在求几何
26、距离的D函数。原本我是这样写的float D(int *X1, int *X2)int *X;X=Sub(X1, X2);return Mol(X);int *Sub(i nt *X1, i nt *X2)int XN, i = 0;for (i = 0; i < N; i+) Xi= X1i - X2i;return X; float Mol(i nt *X)int i = 0, sum = 0;for (i = 0; i < N; i+) sum += Xi * Xi;retur n (float)pow(sum,0.5);这样运行的结果就是求出来的几何距离是个很奇怪的随机数,
27、每运行一次得出的结果都不一样。原因在于在Sub函数中X数组是个局部变量, 返回的X只能是个指针,此时它已经不代 表刚才指向的那个数组了,然后调进 Mol函数中,进行的操作也只是对 X的地址进行操作,因为地址是随机数,所以返回的也是个随机数。我所以我将这 D和Sub两个函数直接合并为一个D函数float D(i nt *x1, i nt *x2)/int xN, i = 0;for (i = 0; i < N; i+)/xi= x1i - x2i;return Mol(x);/2.复杂度的分析本程序中没有用到循环嵌套,所以每个函数的时间复杂度基本为 基本为0 (n)。六.使用说明,本程序的
28、主要功能就是统计源程序之间的相似度,求几何距离向量相减再求模0(n),空间复杂度也所以使用者只需要将要检测的源程序的txt文件放入该程序的工程文件夹中计算fl (FO卜墩掲结构实验 hashtable大小Debug2014/12/2& 星期ickeyntxt2014/12/2星期亠文4必档1 <B雪划0 hashtable.cpp2014/12/21.CPP文件g kb+* haGhtabla.dep2014/12/2&B.U.VC + + 6 Project4 KB hashtableTcb2014/12/26 星期¥匚十十 Intellisens,.41 K
29、Bhashtable, opt2O14/12/2&.U.OPT爻蚌4S KB_ haihtable.plg2014/12/2&B.U.,PLG文件1 KBtC5t1 tXt2014/12/3星朝1 KBtest2.txt234修4星期“1 KBte?t3.b<t2014/12/4 星眼,.1 KBtestl 1 .txtL T2014/12/43 KBtestl 2.txt.=2014/12/4 <.2 KBtesti 3.txt2014/1/4星期34乂植2 K8test21.txt2014/12/4星期乂4 乂稿4 KBtest22.txt2014/12/4 B
30、.3 KBte±t2 士 txt2014/12/4星朝亠乂奉乂植3 K8然后在修改读取的文件名便可直接运行了。 七测试结果H口冲J P关键字瓠度1频度28enum0001extern0002int211e3longa3&4s igrned&00bsizeof£switchaa07unionaa010ClldFa0011uoida2312auto90013const母B014sliorta00IEdoublea90structa111?t j/pedef母22ISvolatilea0023f Ol*12424ifa3125do母BQ26breaka00a?f
31、loats9029uhilea1Q3Gdefault母a031return12033e Is e3994registeraaQ35mi? irntd0母B37statica0038case&0039cont inue&ae4Gsroto0Q8tcstl .Et和.txt的利似情况为:=0.872503迸两f文件内春不相位的拥似情况为:.txt相似度 xs=0.83770fi 迸两个文件内容不相似ItestlZ .m和te$tl3 . txt;的相愎情i兄为-似度 xs =0.927684|TL 何距离 x(l=4*79583 橋如并音萤薙半:穌才md" F:凿据站构实
32、验 hashtab1eDebughashtd ble .exe'结果与实际结果相符,故可以认为该程序是成功的。八心得与体会。1. 通过本实验让我用程序对文件的操作有了更深的理解,知道了如果直接的逐行读取文件 的话,换行号也会被读进去的。2. 对局部变量有了更好的理解。3学会了建立哈希表的过程,以及更好的掌握了调试这一功能。4.由于本程序的编写和调试我是在visual studio2012 进行的,所以上述截图均为在该编辑环境中进行的。使用 visual studio编程体会到了其功能之强大和方便。而且也更安全,例如它一般不允许 fopen , strcpy这种不安全函数,所以原本我用的
33、是Errnq_t err;if C(err-faperL.s,'r:Visu.al Studio codeWHshXXckey* txt'j "r") J=0)亡a'± err felt file ! _n":exit (0);st rcpy_s Oiasht ke沖41. h弱hllen+l7 s : rj :这种visual推荐的安全函数。只是后来将代码拷贝的VC+后这些安全函数不能用后,我又换了回来,但其他的基本不用改。九附完整源程序/哈希表统计源程序的相似度#in clude"iostream" #i
34、nclude"stdlib.h" #i nclude"stri ng"#i nclude"math.h"关键字个数关键字数组长度哈希表长度相似度s的阈值的阈值#defi ne N 32/#defi ne size 256#defi ne maxle n 9/#defi ne hashlen 41/#defi ne Smax 0.9/#defi ne Dmin 2Dstruct hashtable/char *hash1;/int count;/结构体数组哈希表指向关键字的指针 记录频度void Hashfu nc(char str);
35、/亠疋位置int Hashfi nd(char *words);/统计频度void creathash(void);/int isletter(char ch);/float Mol(i nt *x);/int Dot( int *x1, i nt *x2);/hashthashle n;using n amespace std;将关键字根据哈希函数放入哈希表中的指在哈希表中找是否该 words为关键字,并创建哈希表判断是否为字母取模函数点积函数float D(int *x1, int *x2);/求距离 D 的函数float S(int *x1,int *x2);/求相似度 S 的函数int
36、 readc(char * filename);/读取源程序文件中的单词int getkey(char *str,int len);/获取该单词的 keyvoid resethash(int n);/重置哈希表void copycount(int x,int n);/将频道拷贝到数组里void check(int *x1, int *x2);/检查两个源程序是否相似int main()char filename1="test1.txt"char filename2="test12.txt"存储频度的数组,用完全重置哈希通过文件 ckey.txt 读取第一
37、个测试源 讲统计好的频度 仅仅将频度 同上char filename3="test13.txt"int x1hashlen,x2hashlen,x3hashlen; / 于相似度 S 的计算resethash(0); /表,即哈希指针置为NULL,频度置为0creathash(); / 创建哈希表readc(filename1); / 程序文件copycount(x1,hashlen); / 复制给 x 数组resethash(1); /count 置为 0 readc(filename2); /copycount(x2,hashlen);resethash(1);read
38、c(filename3);copycount(x3,hashlen);关键字 "<<" t"<<" 频度 1"<<" t"<<"cout<<"t"<<" 哈希序号 "<<" t"<<"频度 2"<<" t"<<" 频度 3"<<endl;for (int i = 0;
39、 i < 41; i+)cout<<"t"<<i<<"if(hashti.hash1!=NULL)t"<<hashti.hash1<<"t"<<x1i<<" t"<<x2i<<" t"<<x3i<<endl; cout<<filename1<<" 和 "<<filename2<<"
40、的相似情况为: "<<endl;check(x1,x2); / 检查相似 度cout<<filename1<<"和 "<<filename3<<" 的相似情况为:"<<endl;check(x1,x3);cout<<filename2<<"和 "<<filename3<<" 的相似情况为: "<<endl;check(x2,x3); return 0;void resetha
41、sh(int n) /if(n=0) /for(int i=0;i<41;i+)hashti.hash1=NULL; hashti.count=0;else if (n=1) /for(int i=0;i<41;i+)hashti.count=0;void copycount(int x,int n) /for (int i = 0; i < n; i+)xi=hashti.count;int getkey(char *str,int len)/词的 keychar key1,key2;int key;key1=str0;key2=strlen-1; key=(int)(ke
42、y1*100+key2)%41;return key;重置哈希表完全重置哈希表仅仅重置频度拷贝频度根据哈希函数获取该单void creathash(void) 键字创建哈希表 FILE *fp; int length; char strsize; char *s=NULL; for (int i = 0; i < size; i+) stri='0' if(fp=fopen("ckey.txt","r")=NULL) /对文件 ckey.txt 中的 32 个关暂时存储关键字字符的数组cout<<"can
43、9;t creat file!n" exit(0);while (fgets(str,size,fp)!=NULL) /if (str=NULL)break;length=strlen(str); strlength-1='0'止运行了Hashfunc(str); fclose(fp);读取一行写入一行/调试后发现的,没有这里就停void Hashfunc(char str) 放入哈希表中的指定位置 int key,len; len=strlen(str); key=getkey(str,len); while (hashtkey%41.hash1!=NULL) ke
44、y+;/hashtkey%41.hash1=(char*)malloc(sizeof(char)*(len+1); strcpy(hashtkey%41.hash1,str);将关键字根据哈希函数线性探索在哈希表中找是否该如果不在 key 位线性探查法顺序查找哈希表int Hashfind(char *words) / words 为关键字,并统计频度int key,len,find; len=strlen(words); key=getkey(words,len); while(hashtkey.hash1=NULL)key+; key=key%41;if(strcmp(hashtkey.h
45、ash1,words)=0)hashtkey.count+;return 1;for(find=key+1;find<hashlen;find+) / 置则向往后线性查找,然后再从头找/ 中是否已存在关键字if(hashtfind.hash1!=NULL) if(strcmp(hashtfind.hash1,words)=0) hashtfind.count+; return 1;for(find=0;find<key;find+)if (hashtfind.hash1!=NULL)if(strcmp(hashtfind.hash1,words)=0)hashtfind.count+;return 1;return 0;int isletter (char ch)判断 / 是否 ch 为字母if(ch>='a'&&am
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 采购合同执行流程的案例分享3篇
- 采购合同预付款的会计处理方法3篇
- 采购合同培训学员感言3篇
- 采购合同的履行合同诉讼3篇
- 采购合同协议书范本样式3篇
- 采购合同的种类分析3篇
- 2024年卫生间节水节能改造升级合同3篇
- 采购合同管理的改进措施3篇
- 采购合同管理的要点解读与实践3篇
- 采购合同风险评估的指导原则3篇
- (2024年)羊水栓塞完整版pptx
- 《中国近现代史纲要(2023版)》课后习题答案合集汇编
- 医院关于成立安全生产领导小组的通知
- 【施工方案】空调百叶施工方案
- 先张法U型梁施工与管理
- 国家开放大学电大《可编程控制器应用》形考任务(课程实验)答案
- 基坑开挖-降水
- 施工队结算单
- 死因调查记录示例
- 中南大学电气工程基础课程设计
- 毕业设计论文千斤顶液压缸加工专用机床电气控制系统设计
评论
0/150
提交评论