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

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

2、0,0,2X2=4,2,0,5,4,0,5,2,0,1设s是向量X1和X2的相对距离，是同一个程序；s值越大，则两个程序的差别可能也越大。s=sqrt(刀(Xi-x2i)2 ），当X1=X2 时，s=0,反映出可能三、概要设计为了实现上述功能，可以用结构体表示哈希表，因此需要哈希表的抽象数据类型。 哈希表抽象数据类型的定义：ADT hashtable数据对象:D=ai |a i C ElemType,且各不相同，i=1,2.,n,n > 0数据关系:基本操作:Hashfu nc(char str); Hashfi nd(char *words); creathash(void); res

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

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

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

6、数函数原型：int readc(char * file name);如果读的超过最大关Hashfind 函数,思路：为了读取源程序文件中的单词， 所以一个字符一个字符的， 键字长度将会跳过当前识别区域，读取下一个单词，将得到的该单词调入 来判断是否为关键字，并统计频度。(8) 将频度拷贝到数组里的函数函数原型：void cop ycou nt(i nt x,i nt n);功能：将哈希表中关键字的频度复制到x数组中，以便进行后面相似度等的计算。(9) 检查两个源程序是否相似的函数函数原型：void check(i nt *x1, i nt *x2);思路：对调进来的x1和x2数组进行相似度计算

7、，若相似度大于设定好的阈值，则再进行几何距离计算，最后给出两个文件是否相似的判断。(10) 取模函数函数原型：float Mol(i nt *x);思路：通过求向量模值的数学知识求x数组的模。(11) 点积函数函数原型：int Dot(i nt *x1, i nt *x2)思路：通过点积的数学知识对两个向量求点积。(12) 求相似度S的函数函数原型：float S(i nt *x1,i nt *x2);思路：根据题目给的求相似度的公式求x1和x2数组的相似度。(13) 求距离D的函数函数原型：float D(i nt *x1, i nt *x2);思路：用题目给的球几何距离的公式求x1和x2数

8、组的几何距离。2、主函数伪码int mai n()char file name1="test1.txt"char file name2="test2.txt"char file name3="test3.txt"int x1hashle n,x2hashle n,x3hashle n; /* 算*/resethash(0); /* creathash(); / readc(file name1); / cop yco un t(x1,hashle n);resethash(1); / readc(file name2); / cop

9、yco un t(x2,hashle n);resethash(1);存储频度的数组，用于相似度S的计完全重置哈希表，即哈希指针置为NULL频度置为0*/通过文件ckey.txt创建哈希表读取第一个测试源程序文件讲统计好的频度复制给x数组仅仅将频度count置为0同上/readc(file name3);cop yco un t(x3,hashle n);cout<<"t"<<"哈希序号"<<" t"<<" 关键字"<<" t"<

10、<" 频度 1"<<" t"<<" 频度 2"<<" t"<<" 频度 3"<<endl;for (int i = 0; i < 41; i+)if(hashti.hash1!=NULL)t"<<hash ti .hash1<<"cout<<"t"<<i<<"t"<<x1i<<&qu

11、ot;t"<<x2i<<"t"<<x3i<<e ndl;cout<<file name1<<"和"<<file name2<<"的相似情况为："<<e ndl;check(x1,x2); /检查相似度cout<<file name1<<"和"<<file name3<<"的相似情况为："<<e ndl;check(x1,

12、x3);cout<<file name2<<"和"<<file name3<<"的相似情况为："<<e ndl;check(x2,x3);return 0;3、调用关系图调用关系图如下:readccopycounresethaislettemain()creathashhashfi nd1p rgetkeyhashfu ncDotcheckDMol五、编码实现1.使用函数 void resethash(int n)来重置哈希表void resethash(i nt n) /if(n=0)/重置哈

13、希表 完全重置哈希表for(i nt i=0;i<41;i+)hashti.hash仁NULL; hashti.co un t=0;else if (n=1)/仅仅重置频度for(i nt i=0;i<41;i+) hashti.co un t=0;2.使用 void copycount(int x,int n)来将频度拷贝到数组里的函数void cop yco un t(i nt x,i nt n) /for (int i = 0; i < n; i+) xi=hashti.co unt;拷贝频度3.使用 int getkey(char *str,int len) int

14、getkey(char *str,i nt len) /来获取单词key的函数 根据哈希函数获取该单词的_keychar key1,key2;int key;key1=str0;key2=strle n-1;key=(i nt)(key1*100+key2)%41;return key;4.使用void creathash(void)来创建哈希表函数对文件keyword.txt 中的32个关键字创建哈希表void creathash(void) / FILE *fp;暂时存储关键字字符的数组int len gth;char strsize; /char *s=NULL;for (int i =

15、 0; i < size; i+)stri='0'if(fp=fo pen ("keyword.txt",T')=NULL)cout<<"ca n't creat file!' n" exit(0);while (fgets(str,size,fp)!=NULL)if (str=NULL)break;len gth=strle n( str);strle ngth-1='O' /Hashfu nc(str);fclose(fp);/读取一行写入一行调试后发现的，没有这里就停止运行了

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

17、rds)来在哈希表中找是否该words为关键字，并统计频度的函数int Hashfi nd(char *words) /int key,le n,find;len=strle n( words);key=getkey(words,le n);while(hashtkey.hash1=NULL)key+;key=key%41;if(strcm p( hashtkey.hash1,words)=0)在哈希表中找是否该 words为关键字，并统计频度hashtkey.co un t+; return 1;for(fin d=key+1;fi nd<hashle n;fin d+) /*然后再从

18、头找*/线性探查法顺序查找哈希表中是否已存在关键字if(hashtfi nd.hash1!=NULL)if(strc mp (hashtfi nd.hash1,words)=0)hashtfi nd.co un t+;return 1;如果不在key位置则向往后线性查找,for(fin d=0;fi nd<key;fi nd+)if (hashtfi nd.hash1!=NULL)if(strc mp (hashtfi nd.hash1,words)=0)hashtfi nd.co un t+; return 1;return 0;7.使用 int readc(char * file n

19、ame) int readc(char *file name)/读取源程序文件中的单词来读取源程序文件中的单词的函数FILE *fp仁NULL;char wordsmaxle n,ch;int i;if(fp1=fo pen (file name,"r")=NULL)cout<<"ca n not creat file!' n" exit(0);while (!feof(fp1) /i=0;ch=fgetc(fp1); /结束返回1一个字符一个字符的读while (isletter(ch)=0&&feof(fp1)=0

20、) ch=fgetc(fp1);while (isletter(ch)=1 &&feof(fp1)=0)if (i=maxle n) / elsewhile (isletter(ch)=1 &&feof(fp1)=0)ch=fgetc(fp1);i=0;break;超过最大关键字长度将会跳过当前识别区域，读取下一个单词wordsi+=ch; ch=fgetc(fp1);wordsi='0'Hashfind (words); /* 将得到的该单词调入 Hashfind函数，来判断是否为关键 字，并统计频度*/fclose(fpl);return 0

21、;8.使用 float Mol(int *x)来取模函数float Mol(i nt *x) /取模函数int i = 0, sum = 0;for (i = 0; i < N; i+)sum += (xi * xi);return (float )po w(float)sum,0.5);int Dot(i nt *x1, i nt *x2) 点积函数int i = 0, sum = 0;for (i = 0; i < N; i+)sum += x1i * x2i;return sum;/9.使用 float S(int *x1,int *x2)、float D(int *x1,

22、int *x2)和 void check(int *x1,int *x2) 来分别求相似度 S的函数、求几何距离 D函数和检查两个源程序是否相似的函数 float S(int *x1,int *x2)return Dot(x1, x2)/(Mol(x1)*Mol(x2); /float D(i nt *x1, i nt *x2) /求相似度S求几何距离int xN, i = 0;for (i = 0; i < N; i+) / xi= x1i - x2i;return Mol(x); /向量相减再求模void check(i nt *x1, i nt *x2)float xs = 0,

23、xd = 0;xs = S(x1, x2);cout<<"相似度 xs="<<xs<<endl;if (xs > Smax) / 先判断S,若S大于阈值再计算几何距离 xd = D(x1, x2);cout<<"几何距离 xd="<<xd<<endl;if (xd < Dmi n) /如果几何距离小于阈值则判断为相似cout << "这两个文件内容确实可能相似"<<e ndl;Xelsecout << "这

24、两个文件内容可能不相似"<<e ndl;return;cout << "这两个文件内容不相似"<<e ndl; / 否则不相似 return;六、实验结果与分析实验上机测试结果如下图所示: ' ©Use说博开燉De曲（3小数険构弓S送课设Debu或数据结构与算送课说ew哈希序号关键字频度1频度2频度30enum0001estern0002goto0003int2136214long1015signed0006sizeof0007switch2123union00010char51511void1271212au

25、to00013const00014short00015double00016struct0I017typedef0101Svolatile00023for86824if13171325do20226break1041029while63630default01031return21233else65634register00035Unsigned00037static0I03Scase1141139continue00040float I000test 1. txt和test2, txt的相似情况为：相似度兀沪0. 920b07几何距离莖1149这两个文件内容可能不相似搜狗拼音输入法全：t的相似情况为：仔“一 1test 1. txt和test2. txt的相似悄况为： 相似度直护0. 920507几何距离xd=13. 1149这两个文件内容可能不相似test 1. txt和tests, t其t的相似情况为： 相似度丫沪1/L伺駆离xd - 0这两个文件内穽确实可能相似tests, txt和tEst击txt的相似情况为： 相似度乳沪920507几何距离xdT3* 1149这两个文件内容可能不相似请按任竜键继续，* * a狗拼音输入法全：分析：实验上机运行结果与实际结