数据结构代码相似度检测

1、思路：首先，对要进行比较的所有代码段进行词法分析，并转化为特定的标记 (token)串，自己制定一个转换规则。接着，通过两两比较标记(token)串来确定 代码之间的相似性，并由此确定代码之间抄袭的程度，过程如图2.1所示。图2.1源代码复制检测过程示意图将这两个代码分别转换为token串后，基于算法 RKR-GST( running-karp-rabin greedy-string-tiling )算法思想，循环求取两 个标记串中未被匹配部分的最大公共子串，将其用空格代替，并根据如下公式求 出两个token串A，B的相似度:H I + B I(2.3)1/ y仁 jitchl.ai ni a

2、r hi j j tij t mathen length过程论述流程图首先要对整个设计做一个整体规划，即设计一个流程图，如图3.1。主程序main#示欢迎界面-司调用tcik巳Q函数生成tcik巳口串U工调用simple函数，token串的相似度n图3.1程序流程图程序清单#include #include #include #include #include #include #include #define N 10000#define M 10000#define MAXSTRLEN 10000/定义最大串长typedef int status;typedef unsigned char

3、 SStringMAXSTRLEN+1;串的定长顺序存储表示SString a3 = int,long,short;SString b2 = (float,double;SStringc15 = &，|，+，-，+，-，*，/，二，=， ,;SString d12 = ，(，)，；，#，；，.;SStringe29 = auto,break,case,char,const,continue,default,do,else,enum，extern,for,goto,if,main,printf,register,return,signed,sizeof，static，struct，switch，

4、typedef，union，unsigned，void，while ，volatile;HANDLE hOut;DWORD written;void ShadowWindowLine(char *str);char type(char *str);void token(char name,char list,char token口，FILE *table);void simple(int MinMatchLen,FILE *fp1,FILE *fp2);status replace(SString s,int pos,int len,int Ls);int copy(float n);void

5、 ShadowWindowLine(char *str)(SMALL_RECT rc;CONSOLE_SCREEN_BUFFER_INFO bInfo; / 窗口缓冲区信息WORD att0,att1,attBack;int i, chNum = strlen(str);GetConsoleScreenBufferInfo( hOut, &bInfo ); / 获取窗口缓冲区信息 /计算显示窗口大小和位置rc.Left = (bInfo.dwSize.X - chNum)/2 - 2;rc.Top = 8; /原代码段中此处为bInfo.dwSize.Y/2 - 2，但是如果您的 DOS屏幕有

6、垂直滚动条的话，还需要把滚动条下拉才能看到，为了方便就把它改 为10rc.Right = rc.Left + chNum + 4;rc.Bottom = rc.Top + 4;att0 = BACKGROUND_RED |BACKGROUND_BLUE; / 阴影属性att1 = FOREGROUND_RED |FOREGROUND_GREEN |FOREGROUND_BLUE | FOREGROUND_INTENSITY | BACKGROUND_RED | BACKGROUND_BLUE | BACKGROUND_INTENSITY;/ 文本属性attBack = BACKGROUND_R

7、ED |BACKGROUND_GREEN |BACKGROUND_BLUE | BACKGROUND_INTENSITY; / 背景属性/设置阴影然后填充COORD posShadow = (rc.Left+1, rc.Top+1), posText = (rc.Left, rc.Top,posBack=0,0;for (i=0;i25;i+) ( FillConsoleOutputAttribute(hOut, attBack,80, posBack, &written); posBack.Y+; for (i=0; i5; i+) ( FillConsoleOutputAttribute(

8、hOut, att0, chNum + 4, posShadow, &written);posShadow.Y+; for (i=0;i5;i+) (FillConsoleOutputAttribute(hOut, att1,chNum + 4, posText, &written); posText.Y+; /写文本和边框 posText.X = rc.Left + 2;posText.Y = rc.Top + 2;WriteConsoleOutputCharacter(hOut, str, strlen(str), posText, &written);SetConsoleTextAttr

9、ibute(hOut, bInfo.wAttributes); / 恢复原来的属 性 char type(char *str)/此函数判断单词类型( int i; for(i=0;i3;i+)/a 中的关键字( if(strcmp(str,ai)=0) return K; for(i=0;i2;i+)/b 中的关键字( if(strcmp(str,bi)=0) return E; for(i=0;i15;i+)/c 中的符号( if(strcmp(str,ci)=0) return A; for(i=0;i12;i+)/d 中符号( if(strcmp(str,di)=0) return R;

10、 for(i=0;i29;i+)/e 中的关键字( if(strcmp(str,ei)=0) return Y;if(isdigit(str0) /0 9 是数字(return N;一般的变量与字符if(!isalnum(str0)return H;else return C;/变量void token(char name,char list,char token口，FILE *table) /将两个文件中的字符串分别切割转换为token串(FILE *in,*out;char ch,c,bufferN,*linkM;int i=0,j=0,k=0,LenLink=0;if(in=fopen(

11、name,r+)=NULL)(printf(源文件无法打开！ n);exit(0);if(out=fopen(list,w+)=NULL)(printf(文件写入失败！ n);exit(0);if(table=fopen(token,w+)=NULL)(printf(文件写入失败！ n);exit(0);while(!feof(in)/逐字读取文件(ch=fgetc(in);if(ch=t | ch=| ch= n) /去掉空格、制表符、回车continue;if(isalpha(ch)/如果首字符是字母(while(isalnum(ch)&(iN) /其他位是字母或数字(bufferi+=c

12、h;ch=fgetc(in);bufferi=0;linkj+ = (char*)malloc(sizeof(char)*(strlen(buffer)+1);strcpy(linkj-1,buffer);i=0;fseek(in,-1L,1); /在文件当中定位else if(isdigit(ch)如果首字符是数字(while(isalnum(ch)&(i|ch=,=,!=这些需被认为是一个符号(bufferi+=ch;bufferi+=c;bufferi=0;linkj+ = (char *)malloc(sizeof(char)*3);strcpy(linkj-1,buffer);i=0

13、;else(bufferi+=ch;bufferi=0;linkj+ = (char *)malloc(sizeof(char)*2);strcpy(linkj-1,buffer);i=0;fseek(in,-1L,1);else if(ch=，+，|ch=二，-，|ch=二，&，|ch=二，|，|ch=，=，)(if(c=fgetc(in)=ch)/+,-,&,|,二二这些需被认为是一个符号(bufferi+=ch;bufferi+=c;bufferi=，0，;linkj+ = (char *)malloc(sizeof(char)*3);strcpy(linkj-1,buffer);i=0

14、;elsebufferi+=ch;bufferi=0;linkj+ = (char *)malloc(sizeof(char)*2);strcpy(linkj-1,buffer);i=0;fseek(in,-1L,1);else其他符号(bufferi+=ch;bufferi=0;linkj+ = (char *)malloc(sizeof(char)*2);strcpy(linkj-1,buffer);i=0;LenLink = j-1; 存到link中的总长度for(i=0;iLenLink;i+) 打印 token 中的内容(c=type(linki); /if(c=N|c=A|c=R)

15、/数字，符号在表中保留 fputs(linki,table);if(c=C) /变量均替换为id fputs(id,table);if(c=K)/关键字 int,short,long 替换为 zh fputs(zh,table);if(c=E)/关键字 float,double 替换为 fu fputs(fu,table);if(c=Y)/其他关键字不变 fputs(linki,table);if(c=H)/汉字删掉fputs(0,table);fclose(table);fprintf(out,t*单词类型观察表*n );/打印list中的内容fprintf(out,tK -int,shor

16、t,long n);fprintf(out,tE -float,doublen);fprintf(out,tY -其他关键字n)；fprintf(out,tA -运算符号n).fprintf(out,tR -语言符号 n ),fprintf(out,tN -数字n)；fprintf(out,tH -汉字n),fprintf(out,tC -一般变量或标识符n)；fprintf(out,t*n);for(i=0;iLenLink;i+)(c=type(linki); 判断单词的类型fputc(,out);fputc(c,out);fputc(,out);fputs(linki,out);fput

17、c(,out);fprintf(out,%d,i);fputc(),out);fputc(n,out);void simple(int MinMatchLen,FILE *fp1,FILE *fp2)/ 此函数计算相似度，MinMatchLen:公共子串要达到的最小长度(SString A,B;char ch,h;int i=0,j=0,k,t,s,a=1,La,Lb,lena,lenb,x,y;float n;int MatchLen=0;/所有公共子串的总长度int maxmatch;/当前最大公共子串长度if (fp1=fopen(f:token1.txt,r)=NULL)/ 设定文件位

18、于当前目 录下，可更改为绝对路径(printf(文件打开失败！)；getch();exit(0);A+i=fgetc(fp1);while(!feof(fp1)A+i=fgetc(fp1);fclose(fp1);La=i-1;printf(token 串 1 长度为%d，,La);if (fp2=fopen(f:token2.txt,r)=NULL)/ 设定文件位于当前目 录下，可更改为绝对路径(printf(文件打开失败！)；getch();exit(0);B+j=fgetc(fp2);while(!feof(fp2)B+j=fgetc(fp2);fclose(fp2);Lb=j-1;pr

19、intf(token 串 2 长度为%dn”,Lb);printf（是否要查看这两个token串？ Y/N ）;h=getchar();if(h=，Y，|h=，y，)(ShellExecute(NULL,open，F:token1.txt，NULL,NULL,SW_SHOWNORMAL);ShellExecute(NULL,open，F:token2.txt，NULL,NULL,SW_SHOWNORMAL);getchar();printf (-n将超过指定长度的公共子串用空格替换，是否要查看细节？ Y/N );ch=getchar();lena=i-1;lenb=j-1;do(maxmatc

20、h二MinMatchLen;for(i=1;i=La;i+)(for(j=1;j=Lb;j+)(k=0;while(k=La-i)&(kmaxmatch)(maxmatch=k;x=i;y=j;if(maxmatchMinMatchLen)(replace(A,x,maxmatch,La);replace(B,y,maxmatch,Lb);La二La-maxmatch+1;Lb二Lb-maxmatch+1;MatchLen+=maxmatch;if(ch=，Y，|ch=，y，)(printf(第%d次检查两串中的匹配串n,a);a+;for(s=1;s=La;s+)printf(%c,As);printf(n)；for(s=1;sMinMatchLen);printf(n已经没有能够匹配的公共子串了n);n=(2.0*MatchLen)/(lena+lenb);printf(公共子串的总长 为%d,MatchLen);printf(根据公式n);printf(tt n);printf(tt|相似度二(2X公共子串长度)：(串A长度+串