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

-程序源代码的相似性一、课题内容和要求对于两个C++语言的源程序代码，用哈希表的方法分别统计两个程序中使用C++语言关键字的情况，并最终按定量的计算结果，得出两份程序的相似性。基本要求：建立C++语言关键字的哈希表，统计在每个源程序中C++关键字出现的频度,得到两个向量X1和X2，通过计算向量X1和X2的相对距离来判断两个源程序的相似性。例如:关键字VoidIntForCharifelsewhiledobreakclass程序1关键字频度4304307002程序2关键字频度4205405201X1=[4,3,0,4,3,0,7,0,0,2]X2=[4,2,0,5,4,0,5,2,0,1]设s是向量X1和X2的相对距离，s=sqrt(∑(xi1-xi2)2)，当X1=X2时，s=0,反映出可能是同一个程序；s值越大，则两个程序的差别可能也越大。测试数据:选择若干组编译和运行都无误的C++程序，程序之间有相近的和差别大的，用上述方法求s,对比两个程序的相似性。二、课题需求分析1．需求分析软件的基本功能、输入/输出形式、测试数据要求。该软件能够比较两个源程序代码的相似度。需要用户输入两个源代码的文件名，系统会自动计算出两个程序中关键字的个数，并进行对比，而且计算出两个程序的相似度并输出，用户可以根据，系统输出相似度的大小，来估计两个程序相似的概率。2．概要设计抽象数据类型、主程序流程及模块调用关系。该程序用到的数据结构主要是哈希表，其次是顺序表：哈希表的功能是统计文件里出现的关键字的个数，通过++模式，该程序主要统计了C++的十个常用关键字break,char,class,do,else,for,if,int,void,while出现的频度，在Hash类里定义了一个哈希表，哈希表的大小为十个整形数据，哈希表里的十个数据是与已知的十个关键字一一对应的，顺-序表用于存放处理后的数据。主程序流程：图2.1图2.1主程序流程3．详细设计实现概要设计的数据类型、主程序以及其它模块的算法描述。数据类型有哈希表，顺序表。ADT类classHash如图2.2：-图2.2ADT类classHash这个程序主要包括三个函数(1)主函数intmain()负责调用其他的函数(2)文件处理函数countfileProcessed(charsourceData[],count)对文件进行处理(3)相似度计算函数doublepossibality(Hashhash1,Hashhash2)根据已有的公式计算相似度。三、课题相关数据结构及算法设计1主要数据结构主程序为：intmain(){charoperation;cout其他键开始比较E程序结束：endl;cinoperation;-while(operation!='E'){intcount1=1;//1,2用于判断第一个文件或者第二个文件intcount2=2;//定义两个字符数组，用于存放经过处理后的文件的字符///////charsourceData1[M];///////第一个字符数组///////////////charsourceData2[M];///////第二个字符数组///////////////count1=fileProcessed(sourceData1,count1);//数组赋值并返回字符个数count2=fileProcessed(sourceData2,count2);Hashhash1(sourceData1,count1);//定义第一个哈希表Hashhash2(sourceData2,count2);//定义第二个hash1.calcuNum();//计算1中每个关键字的频度hash2.calcuNum();coutbreakcharclassdoelseforifintvoidwhileendl;hash1.Display();//输出第一个哈希表中关键字的个数hash2.Display();//输出第二个cout相似度为:possibality(hash1,hash2)endl;cinoperation;}return0;}2、文件处理函数intfileProcessed(charsourceData[],intcount)类型：全局函数,返回值为文件中字符的个数，为查找做准备。目的：取消连续的空格或空行，以减少查找时间，并把处理后的字符存到字符数组中。（1）从文件里读取字符，将字符进行简单处理：把所有的括号包括”()”,”[]”,”{}”，””替换成空格，（2）将字符读到firstProcessed.txt文件中；代码为：//括号边空格部分代码-while(infile.get(ch)){if(ch=='('||ch==')'||ch=='{'||ch=='}'||ch=='['||ch==']'){ch='';}if(ch==','||ch==''||ch==''){ch='';}outfile.put(ch);}//字符读到数组里的代码while(infile2.get(ch)){if(ch==''&&sourceData[i-1]==''){//取消连续的空格}elseif(ch==';'){//添加空格sourceData[i]='';i++;sourceData[i]=ch;}else{sourceData[i]=ch;i++;-}}3.相似度计算函数doublepossibality(Hashhash1,Hashhash2)参数hash1，hash2里分别存放两个文件中关键字的次数；原理为：公式：s=sqrt(∑(xi1-xi2)2)；返回值为double型值；功能：计算两个文件相似度；代码为：doublepossibality(Hashhash1,Hashhash2){inti;doublesum=0;doublepos=0;for(i=0;i10;i++){sum=sum+(hash1.hashTab[i]-hash2.hashTab[i])*(hash1.hashTab[i]-hash2.hashTab[i]);}pos=sqrt(sum);returnpos;}复杂度分析：本程序时间复杂度为O(n),空间复杂度为charsourceData[10^4]四、源程序代码Main.cpp程序源代码:#includemath.h//#includeHash.h#includeHash.cppintfileProcessed(charsourceData[],intcount);//将处理后的文件保存到字符数组里，该函数返回字符数组里字符的总个数doublepossibality(Hashhash1,Hashhash2);//根据两个哈希表和已有公式计算相似度-intmain(){charoperation;cout其他键开始比较E程序结束：endl;cout输入操作endl;cinoperation;while(operation!='E'){intcount1=1;//1,2用于判断第一个文件或者第二个文件intcount2=2;//定义两个字符数组，用于存放经过处理后的文件的字符///////charsourceData1[M];///////第一个字符数组///////////////charsourceData2[M];///////第二个字符数组///////////////count1=fileProcessed(sourceData1,count1);//数组赋值并返回字符个数count2=fileProcessed(sourceData2,count2);Hashhash1(sourceData1,count1);//定义第一个哈希表Hashhash2(sourceData2,count2);//定义第二个hash1.calcuNum();//计算1中每个关键字的频度hash2.calcuNum();coutbreakcharclassdoelseforifintvoidwhileendl;hash1.Display();//输出第一个哈希表中关键字的个数hash2.Display();//输出第二个cout相似度为:possibality(hash1,hash2)endl;cout输入操作：endl;cinoperation;}return0;}intfileProcessed(charsourceData[],intcount)-{///////////////////////处理第一个文件////////////////////////////////////////////////////////////////if(count==1){inti=0;charch;charfirst[10];cout第一个文件的文件名:endl;cinfirst;ifstreaminfile(first,ios::in);ofstreamoutfile(firstProcessed.txt,ios::out);if(!infile){cerropenfirsterrorendl;}if(!outfile){cerropenfirstProcessederrorendl;}//处理文件即将()[]{}替换为空格保存在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();ifstreaminfile2(firstProcessed.txt,ios::in);//打开firstProcessed需要比较的第一个文件count=0;if(!infile2){cerropenfirstProcessederror!endl;}//把文件存储在sourceData数组里并进行进一步处理把多个空格合并为一个空格以减少空间开销2//while(infile2.get(ch)){if(ch==''&&sourceData[i-1]==''){//取消连续的空格}elseif(ch=='\n'&&sourceData[i-1]=='\n'){//取消连续的空行}elseif(ch==';'){//添加空格sourceData[i]='';i++;sourceData[i]=ch;}-else{sourceData[i]=ch;i++;}}count=i;////////////////////////////////////////////////////////////////////////////2////infile2.close();returncount;}else{inti=0;charch;charsecond[10];cout第二个文件的文件名:endl;cinsecond;ifstreaminfile(second,ios::in);ofstreamoutfile(secondProcessed.txt,ios::out);if(!infile){cerropenseconderrorendl;}if(!outfile){cerropensecondProcessederrorendl;}///////////////////////////处理文件即将()[]{}替换为空格/////////////////////////1//while(infile.get(ch))-{if(ch=='('||ch==')'||ch=='{'||ch=='