天津科技大学大数据结构与算法课程设计报告材料-源程序地相似性

1、数据结构与算法课程设计报告设计题目：源程序的相似性专业计算机科学与技术学号姓 名 傅开煤2017年1月10日源程序的相似性一、问题描述对于两个C+语言的源程序代码，用哈希表的方法分别统计两个程序中使用C+语言关 键字的情况，并最终按定量的计算结果，得出两份程序的相似性。二、需求分析建立C+语言关键字的哈希表，统计在每个源程序中C+关键字出现的频度，得到两个 向量X1和X2,通过计算向量X1和X2的相对距离来判断两个源程序的相似性。例如：关键字VoidIntForCharif else whiledobreakclass程序1关键字频度4304307002程序2关键字频度4205405201X

2、= 4,3,0,4,3,0,7,0,0,2 1X2=4,2,0,5,4,0,5,2,0,1设s是向量X和X的相对距离，s=sqrt( (x i-x i) 2),当X =X时，s=0,反映 121212出可能是同一个程序；s值越大，则两个程序的差别可能也越大。三、概要设计为了实现上述功能，可以用结构体表示哈希表，因此需要哈希表的抽象数据类型。哈希表抽象数据类型的定义：ADT hashtable数据对象：D=a |a GElemType,且各不相同，i=1,2.,n,nN0数据关系：R二基本操作：Hashfunc(char str);Hashfind(char *words);creathash(

3、void);resethash(int n);isletter(char ch);readc(char * filename);getkey(char *str,int len);copycount(int x,int n);check(int *x1, int *x2);本程序实现模块主程序模块哈希表程序模块：实现哈希表的抽象数据类型 调用关系图如下：主程序模块哈希表程序模块计算相似度和向量的几何距离的模块四、详细设计1、各个子函数的设计创建哈希表函数函数原型：void creathash(void);输入：读取存储了 32个关键字的文件keyword.txt思路：通过对keyword.tx

4、t文件逐行赋值给创建的str字符数组，并将该数组调入 Hashfunc 函数。将关键字根据哈希函数放入哈希表中的指定位置的函数函数原型：void Hashfunc(char str);思路：对调进来的str数组通过调用getkey函数得到该关键词的key值后放入哈希表 中的特定位置，并用线性探索来解决冲突。在哈希表中找是否该words为关键字，并统计频度的函数函数原型：int Hashfind(char *words);思路：将调进来的word字符数组先调用getkey函数获取key值，然后在哈希表里查找 是否存在该字符串，如果存在则该关键字对应的频度加1。重置哈希表函数函数原型：void r

5、esethash(int n);功能：当n为0时，将指向哈希表中关键字的指针置成Null，同时将频度全部置为0. 而当n为1时，仅仅将频度置为0。获取单词key的函数函数原型：int getkey(char *str,int len);思路：用key1存储关键字的首字母，key2存储关键字的末字母，然后通过哈希函数得 到key的值并返回。判断是否为字母的函数函数原型：int isletter(char ch);思路:如果调进来的ch字符的ASCI I值在az或AZ范围内的话则返回1,否则返回0。读取源程序文件中的单词的函数函数原型：int readc(char * filename);思路：为

6、了读取源程序文件中的单词，所以一个字符一个字符的，如果读的超过最大关 键字长度将会跳过当前识别区域，读取下一个单词，将得到的该单词调入Hashfind函数， 来判断是否为关键字，并统计频度。将频度拷贝到数组里的函数函数原型：void copycount(int x,int n);功能：将哈希表中关键字的频度复制到x数组中，以便进行后面相似度等的计算。检查两个源程序是否相似的函数函数原型：void check(int *x1, int *x2);思路：对调进来的x1和x2数组进行相似度计算，若相似度大于设定好的阈值，则再进 行几何距离计算，最后给出两个文件是否相似的判断。取模函数函数原型：flo

7、at Mol(int *x);思路：通过求向量模值的数学知识求x数组的模。点积函数函数原型：int Dot(int *x1, int *x2)思路：通过点积的数学知识对两个向量求点积。求相似度S的函数函数原型：float S(int *x1,int *x2);思路：根据题目给的求相似度的公式求x1和x2数组的相似度。求距离D的函数函数原型：float D(int *x1, int *x2);思路：用题目给的球几何距离的公式求x1和x2数组的几何距离。2、主函数伪码 int main()(char filename1=test1.txt;char filename2 = test2.txt;ch

8、ar filename3 = test3.txt;int x1hashlen,x2hashlen,x3hashlen; /*存储频度的数组，用于相似度 S 的计 算*/resethash(0);/*完全重置哈希表，即哈希指针置为NULL，频度置为0*/creathash();/通过文件ckey.txt创建哈希表readc(filenamel); /读取第一个测试源程序文件copycount(x1,hashlen); /讲统计好的频度复制给x数组resethash(l);/仅仅将频度count置为0readc(filename2);/同上copycount(x2,hashlen);resetha

9、sh(1);readc(filename3);copycount(x3,hashlen);coutt哈希序号t关键字t频度 1t频度 2t频度 3endl;for (int i = 0; i 41; i+)(if(hashti.hash1!=NULL)(couttithashti.hash1tx1itx2itx3iendl;coutfilename1和filename2 的相似情况为：endl;check(x1,x2);/检查相似度coutfilename1和filename3 的相似情况为：endl;check(x1,x3);coutfilename2和filename3 的相似情况为：en

10、dl;check(x2,x3);return 0;3、调用关系图调用关系图如下:getkey五、编码实现1.使用函数void resethash(int n)来重置哈希表 void resethash(int n)重置哈希表if(n=0)/完全重置哈希表for(int i=0;i41;i+)hashti.hash1=NULL;hashti.count=0;else if (n=1)/仅仅重置频度for(int i=0;i41;i+)hashti.count=0; 2.使用void copycount(int x,int n)来将频度拷贝到数组里的函数 void copycount(int x,

11、int n)/拷贝频度for (int i = 0; i n; i+)xi=hashti.count;使用 int getkey(char *str,int len)来获取单词 key 的函数int getkey(char *str,int len)/根据哈希函数获取该单词的keychar key1,key2;int key;keyl=str0;key2=strlen-1;key=(int)(key1*100+key2)%41;return key;使用 void creathash(void)来创建哈希表函数void creathash(void)/对文件keyword.txt中的32个关键

12、字创建哈希表(FILE *fp; int length; char strsize;/暂时存储关键字字符的数组char *s=NULL; for (int i = 0; i size; i+) ( stri=0; if(fp=fopen(keyword.txt,r)=NULL) ( coutcant creat file!n; exit(0); while (fgets(str,size,fp)!=NULL)/读取一行写入一行( if (str=NULL) ( break; length=strlen(str); strlength-1 = 0;/调试后发现的，没有这里就停止运行了Hashfu

13、nc(str); fclose(fp); 使用voidHashfunc(char str)来将关键字根据哈希函数放入哈希表中的指定位置的函 数void Hashfunc(char str)/将关键字根据哈希函数放入哈希表中的指定位置int key,len; len=strlen(str); key=getkey(str,len); while (hashtkey%41.hash1!=NULL)(key+;/线性探索hashtkey%41.hash1 = (char*)malloc(sizeof(char)*(len+1);strcpy(hashtkey%41.hash1,str);使用int

14、Hashfind(char *words)来在哈希表中找是否该words为关键字，并统计频度的 函数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.hash1,words)=0)(hashtkey.count+;return 1;for(find=key+1;findhashlen;find+)/*如果不

15、在key位置则向往后线性查找，然后再从头找*/(/线性探查法顺序查找哈希表中是否已存在关键字if(hashtfind.hash1!=NULL)(if(strcmp(hashtfind.hash1,words)=0)(hashtfind.count+;return 1;for(find=0;findkey;find+)(if (hashtfind.hash1!=NULL)(if(strcmp(hashtfind.hash1,words)=0)(hashtfind.count+;return 1;return 0使用int readc(char * filename)来读取源程序文件中的单词的函数

16、 int readc(char *filename) /读取源程序文件中的单词FILE *fp1=NULL; char wordsmaxlen,ch; int i; if(fp1=fopen (filename,r)二二NULL) coutcan not creat file!n; exit(0); while (!feof(fp1)/结束返回 1 i=0; ch=fgetc(fp1);/一个字符一个字符的读while (isletter(ch)=0&feof(fp1)=0) ch=fgetc(fp1); while (isletter(ch)=1&feof(fp1)=0) if (i=max

17、len) while (isletter(ch)=1&feof(fp1)=0) ch=fgetc(fp1); i=0; break; 超过最大关键字长度将会跳过当前识别区域，读取下一个单词 else wordsi+=ch; ch=fgetc(fp1); wordsi=0; Hashfind (words);/*将得到的该单词调入Hashfind函数，来判断是否为关键字，并统计频度*/ fclose(fpl) return 0;使用float Mol(int *x)来取模函数 float Mol(int *x)/取模函数int i = 0, sum = 0;for (i = 0; i N; i+

18、)sum += (xi * xi);return (float)pow(float)sum,0.5)int Dot(int *x1, int *x2)/点积函数int i = 0, sum = 0; for (i = 0; i N; i+)sum += x1i * x2i;return sum;使用 float S(int *x1,int *x2)、float D(int *x1, int *x2)和 void check(int *x1, int *x2)来分别求相似度S的函数、求几何距离D函数和检查两个源程序是否相似的函数 float S(int *x1,int *x2) return D

19、ot(x1, x2)/(Mol(x1)*Mol(x2); /求相似度 Sfloat D(int *x1, int *x2)/求几何距离int xN, i = 0;for (i = 0; i N; i+) 向量相减 xi= x1i - x2i;return Mol(x);/再求模void check(int *x1, int *x2) float xs = 0, xd = 0;xs = S(x1, x2);cout相似度 xs=xs Smax) /先判断S,若S大于阈值再计算几何距离 (xd = D(x1, x2);cout几何距离 xd=xdendl;if (xd Dmin) /如果几何距离小

20、于阈值则判断为相似 cout 这两个文件内容确实可能相似endl;elsecout 这两个文件内容可能不相似endl;return;cout 这两个文件内容不相似endl;/否则不相似return;六、实验结果与分析实验上机测试结果如下图所示:U C:Users傅开|Desktop|g构与算法课设Debug|S构与算法课设.exe12 3 4 50123456783456901345789011111111122222333333334enum extern goto int long signed sizeof switch union char void auto const short

21、double struct typedef volatile for if do break while default return else register unsigned staticcase continue floatl2no 116026000100testl. txt和test2. txt的相似情况为 相似度xs=0. 920507 几向距离xd=13. 1149这两个文件内容可能不相似搜疝排音圣：角似情况为分析：实验上机运行结果与实际结果相符，即可以认为该程序是正确无误的。七、总结在本次的课程设计上机操作的时候，在调试每个模块设计的时候，有些模块由于本人的 粗心大意把=与=的问题弄混淆了，使调试出现了报错。这是由于本人平时没