程序的源代码的相似性判别

1、程序源代码的相似性一、课题内容和要求对于两个C+邮言的源程序代码，用哈希表的方法分别统计两个程序中使用C+邮言关键字的情况，并最终按定量的计算结果，得出两份程序的相似性。度，得到两个向量基本要求：建立 C+胡言关键字的哈希表，统计在每个源程序中C+铁键字出现的频X1和X2,通过计算向量X1和X2的相对距离来判断两个源程序的相似性。例如:关键字VoidIntForCharifelse while do break class程序1关键字频度 程序2关键字频度X1=4,3,0,4,3,0,7,0,0,2X2=4,2,0,5,4,0,5,2,0,1设s是向量X1和X2的相对距离,s=sqrt( E(

2、xi-xi2) 2 ),当 X1=X2时，s=0,反映出可能是同一个程序；s值越大，则两个程序的差别可能也越大。测试数据：选择若干组编译和运行都无误的 C+刑序，程序之间有相近的和差别大的，用 上述方法求s,对比两个程序的相似性。二、课题需求分析1 .需求分析软件的基本功能、输入/输出形式、测试数据要求。该软件能够比较两个源程序代码的相似度。需要用户输入两个源代码的文件名，系统会自动计算出两个程序中关键字的个数，并进行对比，而且计算出两个程序的相似度并输出，用户可以根据，系统输出相似度的大小，来估计两个程序相似的概率。2 .概要设计抽象数据类型、主程序流程及模块调用关系。该程序用到的数据结构主

3、要是哈希表，其次是顺序表：哈希表的功能是统计文件里出现的关键字的个数，通过+模式，该程序主要统计了 C+的十个常用关键字 break,char,class,do,else,for,if,int,void,while出现的频度，在 Hash 类里定义了一个哈希表，哈 希表的大小为十个整形数据，哈希表里的十个数据是与已知的十个关键字一一对应的，顺序表用于存放处理后的数据主程序流程：图2.1图2.1主程序流程3 .详细设计实现概要设计的数据类型、主程序以及其它模块的算法描述 数据类型有哈希表，顺序表。ADT 类 class Hash 如图 2.2 :+Hash+Hash(charprccessedr

4、|pint n count):+ calcuNum()： void+ Display。： void+Cumulating(int location： void+-Hash()s virtual+ hashTab10: intdataM： charcount： int图 2.2 ADT 类 class Hash这个程序主要包括三个函数(1)主函数int main()负责调用其他的函数 文件处理函数 count fileProcessed(char sourceData口,coun劫文件进行处理 相似度计算函数double possibality(Hash hash1,Hash hash2)t据已

5、有的公式计算相似度三、课题相关数据结构及算法设计1主要数据结构主程序为：int main()char operation;cout<<"其他键开始比较E程序结束："<<endl<<""cin>>operation;while(operation != 'E')(int countl = 1;/1,2用于判断第一个文件或者第二个文件int count2 = 2;/定义两个字符数组，用于存放经过处理后的文件的字符/char sourceData1M;/第一个字符数组 /char sourceDa

6、ta2M;/第二个字符数组 /count1 = fileProcessed(sourceData1,count1); / 数组赋值并返回字符个数count2 = fileProcessed(sourceData2,count2);Hash hash1(sourceData1,count1); /定义第一个哈希表Hash hash2(sourceData2,count2); /定义第二个hash1.calcuNum();/计算1中每个关键字的频度hash2.calcuNum();cout<<"break char class do else for if int void

7、while"<<endl;hash1.Display(); /输出第一个哈希表中关键字的个数hash2.Display(); /输出第二个cout<<”相似度为:"<<possibality(hash1,hash2)<<endl;cin>>operation;return 0;2、文件处理函数 int fileProcessed(char sourceData口,int count) 类型：全局函数，返回值为文件中字符的个数，为查找做准备。目的：取消连续的空格或空行，以减少查找时间，并把处理后的字符存到字符数组中。

8、(1)从文件里读取字符，将字符进行简单处理：把所有的括号包 括“()“，” 口”，“”，“ <>" 替换成空格，(2)将字符读到firstProcessed.txt文件中；代码为：/括号边空格部分代码while(infile.get(ch)(if(ch = '(' | ch = ')' | ch = '' | ch = '' | ch = '' | ch ='')(ch =''if(ch = ',' | ch = '<' |

9、 ch ='>')ch =''outfile.put(ch);字符读到数组里的代码while(infile2.get(ch)if(ch = ' ' && sourceDatai - 1='')/取消连续的空格else if(ch ='')/添加空格sourceDatai=''i +;sourceDatai = ch;elsesourceDatai= ch;i +;3.相似度计算函数 double possibality(Hash hash1,Hash hash2)参数hashl

10、, hash2里分别存放两个文件中关键字的次数；原理为：公式：s=sqrt( E(x-xi2)2 )；返回值为double型值；功能：计算两个文件相似度；代码为：double possibality(Hash hash1,Hash hash2)int i;double sum = 0;double pos = 0;for(i = 0; i < 10; i +)sum = sum + (hash1.hashTabi - hash2.hashTabi)*(hash1.hashTabi - hash2.hashTabi);)pos = sqrt(sum);return pos;)复杂度分析：本

11、程序时间复杂度为 O(n),空间复杂度为char sourceData10A4四、源程序代码Main.cpp程序源代码：#include<math.h>/#include "Hash.h"#include"Hash.cpp"int fileProcessed(char sourceData口,int count);/将处理后的文件保存到字符数组里，该函数返回字符数组里字符的总个数double possibality(Hash hash1,Hash hash2);/根据两个哈希表和已有公式计算相似度int main() ( char opera

12、tion;cout<<"其他键开始比较E程序结束："<<endl<<""cout<<"输入操作"<<endl;cin>>operation;while(operation != 'E') (int count1 = 1;/1,2用于判断第一个文件或者第二个文件int count2 = 2;/定义两个字符数组,用于存放经过处理后的文件的字符/char sourceData1M;/第一个字符数组 /char sourceData2M;/第二个字符数组

13、/count1 = fileProcessed(sourceData1,count1); /数组赋值并返回字符个数count2 = fileProcessed(sourceData2,count2);Hash hash1(sourceData1,count1); /定义第一个哈希表Hash hash2(sourceData2,count2); /定义第二个hash1.calcuNum();/计算1中每个关键字的频度hash2.calcuNum();cout<<"break char class do else for if int void while"<

14、<endl;hash1.Display(); /输出第一个哈希表中关键字的个数hash2.Display(); /输出第二个cout<<”相似度为:"<<possibality(hash1,hash2)<<endl;cout<<"输入操作："<<endl; cin>>operation;return 0;int fileProcessed(char sourceData口,int count)(/ 处理第一个文件 /if(count = 1)(int i = 0;char ch;char

15、 first10;cout<<”第一个文件的文件名:"<<endl;cin>>first;ifstream infile(first,ios:in);ofstream outfile("firstProcessed.txt",ios二out);if(!infile)(cerr<<"open first error"<<endl;if(!outfile)(cerr<<"open firstProcessed error"<<endl;/处理文件

16、即将()替换为空格保存在firstProcessed中while(infile.get(ch)if(ch = '(' | ch = ')' | ch = '' | ch = '' | ch = '' | ch ='')ch =''if(ch = ',' | ch = '<' | ch ='>')ch =''outfile.put(ch);)infile.close();outfile.close();ifst

17、ream infile2("firstProcessed.txt",ios二in);打开 firstProcessed需要比较的第 个文件count = 0;if(!infile2)cerr<<"open firstProcessed error!"<<endl;)/把文件存储在sourceData数组里并进行进一步处理把多个空格合并为一个空 格以减少空间开销2/while(infile2.get(ch)if(ch = ' ' && sourceDatai - 1='')/取消连续的

18、空格)else if(ch = 'n' && sourceDatai - 1 = 'n')/取消连续的空行)else if(ch = '')/添加空格sourceDatai = ' 'i +;sourceDatai = ch;else( sourceDatai= ch; i +；)count = i;/2/ infile2.close();return count;)else(int i = 0;char ch;char second10;cout<<"第二个文件的文件名："<

19、<endl;cin>>second;ifstream infile(second,ios:in);ofstream outfile("secondProcessed.txt",ios二out);if(!infile)(cerr<<"open second error"<<endl;)if(!outfile)(cerr<<"open secondProcessed error"<<endl;)/ 处理文件即将()替换为空格/1/while(infile.get(ch)if

20、(ch = '(' | ch = ')' | ch = '' | ch = '' | ch = '' | ch ='') (ch =''if(ch = ','| ch = '<' | ch ='>')ch =''outfile.put(ch);infile.close();outfile.close();ifstream infile2("secondProcessed.txt",ios:

21、in);/需要比较的第二个文件count = 0;if(!infile2)cerr<<"open secondProcessed error!"<<endl;/把文件存储在sourceData数组里并进行进一步处理把多个空格合并为一个空格以减少空间开销2/while(infile2.get(ch)if(ch = ' ' && sourceDatai - 1='')/取消连续的空格else if(ch ='')/添加空格 sourceDatai=''i +；sourceDa

22、tai = ch;/cout<<ch;) else ( sourceDatai= ch; i +;/cout<<ch;)count = i;infile2.close();return count;)/ 相似度比较 /double possibality(Hash hash1,Hash hash2)(int i;double sum = 0;double pos = 0;for(i = 0; i < 10; i +)(sum = sum + (hash1.hashTabi - hash2.hashTabi)*(hash1.hashTabi- hash2.hashT

23、abi);)pos = sqrt(sum);return pos;)Hash.cpp源代码：/Hash.cpp: implementation of the Hash class.#include "Hash.h"/ Construction/DestructionHash:Hash(char processed,int n_count)int i;count = n_count;for(i = 0; i < count; i +)datai = processedi;hashTab 0-)/*哈希表长度为10;存放10个整数来记录出现关键字的次数其中91分别为bre

24、ak,char,class,do,else,/for,if,int,void,while*/for(i = 0; i < 10; i +)hashTabi = 0;)Hash:Hash()void Hash:Display()int i;for(i = 0; i < 10; i +)cout<<hashTabi<<II.)cout<<endl;)void Hash:Cumulating(int location)(hashTablocation +;)void Hash:calcuNum()(/int a = 0;int i = 0;while(

25、i != count)(if(datai = 'i')(if(datai - 1 = ' ' | datai - 1 = 'n' | datai - 1 = 9 |i = 0) (i+;if(datai = 'f')(i +;if(datai = ' ' | datai = 'n')(Cumulating(6);) else(while(datai != ' ' && datai != 'n')()else if(datai = 'n'

26、)(i +；if(datai = 't')(i +；if(datai = ' ' | datai = 'n')(Cumulating(7);)else(while(datai != ' ' && datai != 'n') (i +;)else(while(datai != ' ' && datai != 'n')(i +;)else(while(datai != ' ' && datai != 'n')

27、(i +；)else(while(datai != ' ' && datai != 'n')(i +；)else if(datai = 'f)(if(datai - 1 = ' ' | datai - 1 = 'n' | datai - 1 = 9 |i = 0) (i+;if(datai = 'o')(i +;if(datai = 'r')(i +;if(datai = ' ' | datai = 'n')(Cumulating(5);els

28、e(while(datai != ' ' && datai != 'n') (i +；)else(while(datai != ' ' && datai != 'n')(i +；)else(while(datai != ' ' && datai != 'n')(i +；)else(while(datai != ' ' && datai != 'n')(i +；if(datai -1 = ''

29、; | datai -1 = 'n' | datai -1 = 9 |i = 0)i+；i+；if(datai = 'e')(i +；if(datai = 'a')i +； if(datai = k)(i +；if(datai = '' | datai = 'n')(Cumulating(O);elsewhile(datai !=''&& datai != 'n')else(while(datai != ' ' && datai !=

30、'n')(i +；)else(while(datai != ' ' && datai != 'n')(i +；)else(while(datai != ' ' && datai != 'n')(i +；)else(while(datai != ' ' && datai != 'n')()else(while(datai !=''&& datai != 'n')(i+；)else if(da

31、tai = 'c')(if(datai -1 = '' | datai -1 = 'n' | datai -1 = 9 |i = 0) (i+；if(datai = 'h')(i+；if(datai = 'a')(i +；if(datai = 'r')(i+；if(datai = '' | datai = 'n')(Cumulating(l);) else while(datai != ' ' && datai != 'n

32、9;) (i +；)else(while(datai != ' ' && datai != 'n')(i +；)else(while(datai != ' ' && datai != 'n')(i +；)else if(datai = 'l')(i +；if(datai = 'a')(i +；if(datai = 's')i +；if(datai = 's')(i +；if(datai = ' ' | datai = &

33、#39;n')(Cumulating(2);)else(while(datai != ' ' && datai != 'n')(i +;)else(while(datai != ' ' && datai != 'n')(i +;)else(while(datai != ' ' && datai != 'n')(i +;)else(while(datai != ' ' && datai != 'n'

34、)(i +；)else(while(datai != ' ' && datai != 'n')(i +；)/*else(while(datai != ' ' && datai != 'n')(i +；)*/)else(while(datai != ' ' && datai != 'n')i +；)else if(datai = 'd')(if(datai - 1 = ' ' | datai - 1 = 'n

35、9; | datai - 1 = 9 |i = 0) (i+;if(datai = 'o')(i +;if(datai = ' ' | datai = 'n')(Cumulating(3);)else(while(datai != ' ' && datai != 'n')(i +;)else(while(datai != ' ' && datai != 'n')(i +;)else(while(datai != ' ' &&am

36、p; datai != 'n')(i +；)if(datai = 'e')(if(datai - 1 = ' ' | datai - 1 = 'n' | datai - 1 = 9 |i = 0) (i+;if(datai = 'l')(i +;if(datai = 's')(i +;if(datai = 'e')(i +;if(datai = ' ' | datai = 'n')(Cumulating");)elsei +；)else(wh

37、ile(datai != ' ' && datai != 'n')(i +；)else(while(datai != ' ' && datai != 'n')(i +；)else(while(datai != ' ' && datai != 'n')(i +；)else(while(datai != ' ' && datai != 'n')(i +；)else if(datai = 'v'

38、)(if(datai - 1 = ' ' | datai - 1 = 'n' | datai - 1 = 9 |i = 0) (i+;if(datai = 'o')(i +;if(datai = 'i')(i +;if(datai = 'd')(i +;if(datai = ' ' | datai = 'n')(Cumulating(8);)else(while(datai != ' ' && datai != 'n')else( wh

39、ile(datai != ' ' && datai != 'n') (i +；)else(while(datai != ' ' && datai != 'n')(i +；)else(while(datai != ' ' && datai != 'n')(i +；)while(datai != ' ' && datai != 'n')(i +；)if(datai = 'w')(if(data

40、i - 1 = ' ' | datai - 1 = 'n' | datai - 1 = 9 |i = 0) (i+;if(datai = 'h')(i +;if(datai = 'i')(i +;if(datai = 'l')(i +;if(datai = 'e')(i +;if(datai = ' ' | datai = 'n')(Cumulating(9);) elsei +；)else(while(datai != ' ' &&

41、datai != 'n') (i +；)else(while(datai != ' ' && datai != 'n')(i +；)else(while(datai != ' ' && datai != 'n')(i +；)(i +；)else(while(datai != ' ' && datai != 'n')(i +；)i +；)Hash.h源代码：/ Hash.h: interface for the Hash class.IN

42、CL/#if !defined(AFX_HASH_H_BAA39B75_B9BC_41A9_897A_446BA55CEB44.UDED_)#defineAFX_HASH_H_BAA39B75_B9BC_41A9_897A_446BA55CEB44_INCLUDED_#if _MSC_VER > 1000#pragma once#endif / _MSC_VER > 1000#include <iostream>#include <fstream>const int M = 10000;using namespace std;class Hashpublic

43、:Hash(char processed,int n_count);void calcuNum();void Display();void Cumulating(int location);virtual Hash();int hashTab10;protected:char dataM;int count;#endif五、测试数据及其结果分析对文件进行处理，处理之后返回处理后的文件，但是由于刚接触文件对文件的很多操作都 不了解，调试时总是提示错误，后来就换了一种解决方法，但是文件传递的问题还一直在 我的头脑中，想想弄明白，但是一直明白不了，随着以后更深入，广泛的学习，我觉得应 该这个问题会的

44、得到很好的解决。(6)由函数返回一个数组的问题，这个问题也是困扰了我很长的时间1.结果分析(1)首先列出一个菜单，提示按E键结束，按其他键开始比较。如图一图一菜单用户输入想要的操作(2)输入a进行比较，然后根据提示输入需要比较两个文件的文件名：如图图二文件输入(3)系统自动输出每个关键字的次数，并根据次数计算出相似度并输出：如图三l>r-eaJ< cJiai'cla.ssdoe l.s：efor'ifintuo id02?02a414002?02sq340产似度为：2，一个文件的文件名：1_ .txt第二个文件的文件名二3. txtchar clissdoelseF

45、oi*ifintuoS.dwhile3290204140S1801932841相似度为；36.3315图三 结果输入(4)按“E”键退出，如图四修一个文件的文件名：1 ,txt第二个文件的文件名:3.txthi?Eakctiardoe Lsef orbifintuolduhllem29020414SE1Q1?32841作似度为:30.3315Fi'ess mn斗 ke. to continuB图四退出系统7.测试结果用户能够根据提示循环输入多组数据进行测试，如图五其他键开始比较程序结束; a第一个文件的文件名：l.txt第二个文件的文件名二2-txtbreak char classdo

46、elseforifintuoiduhile02902Q4140029020434相似度为二2富一个文件的文件名二l-txt第二个文件自收件名：9-txtbi*eak diar classdoe Isef OPIFintuoiduhlle029e2Q414051001932S41件目似度为m 30-331E图五整体系统结果六、课题完成过程中遇到的问题及解决方法(1)文件的处理：以前学文件的时候就没学明白，但是这个程序一定要用到文件，有将近一天的时间我都在 学文件，当然有C的，也有C+勺，后来还是觉得C+的比较简单，于是就开始确定了用 C+文件，又在别人的帮助下，逐渐明白一些。对文件有了大致的了解，已经会读写了， 虽然读写对有些人来说轻而易举，但是当我学会了后，还是很兴奋的，我喜欢每次解决问