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

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

2、离，s=sqrt( E(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(char

4、prccessedr|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

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

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

7、为:possibality(hash1,hash2)operation;return 0;2、文件处理函数int fileProcessed(char sourceData,int count)类型：全局函数,返回值为文件中字符的个数，为查找做准备。目的：取消连续的空格或空行，以减少查找时间，并把处理后的字符存到字符数组中。(1) 从 文 件 里 读 取字 符 ，将 字 符 进 行 简 单 处 理 ： 把 所 有 的 括 号 包括”( ) ” , ” ” , ” ”，”替换成空格，( 2)将字符读到firstProcessed.txt 文件中；代码为：/ 括号边空格部分代码while(infi

8、le.get(ch)(if(ch = ( | ch = ) | ch = | ch = | ch = | ch =)(ch =;if(ch = , | 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)参数h

9、ashl, 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;复杂度分析：本程序

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

11、ation;cout 其他键开始比较E 程序结束：endl ;cout输入操作operation;while(operation != E)int count1 = 1;/1,2 用于判断第一个文件或者第二个文件int count2 = 2;/定义两个字符数组，用于存放经过处理后的文件的字符/char sourceData1M;/第一个字符数组 /char sourceData2M;/第二个字符数组 /count1 = fileProcessed(sourceData1,count1); /数组赋值并返回字符个数count2 = fileProcessed(sourceData2,count2

12、);Hash hash1(sourceData1,count1); /定义第一个哈希表Hash hash2(sourceData2,count2); /定义第二个hash1.calcuNum();/计算1 中每个关键字的频度hash2.calcuNum();coutbreak char class do else for if int void whileendl;hash1.Display(); /输出第一个哈希表中关键字的个数hash2.Display(); /输出第二个cout”相似度为:possibality(hash1,hash2)endl;cout”输入操作：operation;r

13、eturn 0;/ 处理第一个文件/if(count = 1)int i = 0;char ch;char first10;cout”第一个文件的文件名：first;ifstream infile(first,ios:in);ofstream outfile(firstProcessed.txt,ios:out);if(!infile)cerropen first errorendl;if(!outfile)cerropen firstProcessed errorendl;/处理文件即将()替换为空格保存在firstProcessed中while(infile.get(ch)if(ch =

14、( | ch = ) | ch = | ch = | ch = | ch = )ch = ;if(ch = , | ch = )ch = ;outfile.put(ch);infile.close();outfile.close();ifstream infile2(firstProcessed.txt,ios:in);/ 打开 firstProcessed需要比较的第 个文件count = 0;if(!infile2)cerropen firstProcessed error!endl;/把文件存储在sourceData数组里并进行进一步处理把多个空格合并为一个空格以减少空间开销2/whil

15、e(infile2.get(ch)if(ch = & sourceDatai - 1 = )/取消连续的空格else if(ch = n & sourceDatai - 1 = n)/取消连续的空行else if(ch = ;)/添加空格sourceDatai = ;i +;sourceDatai = ch;elsesourceDatai= ch;i +;count = i;/2/ infile2.close();return count;elseint i = 0;char ch;char second10;cout第二个文件的文件名：second;ifstream infile(secon

16、d,ios:in);ofstream outfile(secondProcessed.txt,ios:out);if(!infile)cerropen second errorendl;if(!outfile)cerropen secondProcessed errorendl;/ 处理文件即将() 替换为空格/1/while(infile.get(ch)if(ch = ( | ch = ) | ch = | ch = | ch = | ch = ) ch = ;if(ch = ,| ch = )ch = ;outfile.put(ch);infile.close();outfile.clos

17、e();ifstream infile2(secondProcessed.txt,ios:in);/需要比较的第二个文件count = 0;if(!infile2)cerropen secondProcessed error!endl;/把文件存储在sourceData数组里并进行进一步处理把多个空格合并为一个空格以减少空间开销2/while(infile2.get(ch)if(ch = & sourceDatai - 1 = )/取消连续的空格else if(ch = ;)/添加空格 sourceDatai = ;i +;sourceDatai = ch;/coutch; else sour

18、ceDatai= ch;i +;/coutch;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.hashTabi);pos = sqrt(sum);return pos;Hash.cpp 源代码：/Hash.cpp:

19、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 个整数来记录出现关键字的次数其中【 9】分别为break,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 +)couthashTabiII.cout 1000#pragma once#endif / _MSC_VER 1000#include #include const int M = 10000;using namespace std;class Hashpublic:Hash(char processed,int n_count);void calcuNum();void Display();void Cumulating(int