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

兵译和执上孝

数据结构与算法课程设计报告设计题目：源程序的相似性专业计算机科学与技术学号 姓名傅开煤2017年1月10日数据结构与算法课程设计报告14101103-傅开煤源程序的相似性一、问题描述对于两个C++语言的源程序代码，用哈希表的方法分别统计两个程序中使用C++语言关键字的情况，并最终按定量的计算结果，得出两份程序的相似性。二、需求分析建立C++语言关键字的哈希表，统计在每个源程序中C++关键字出现的频度，得到两个向量X1和X2,通过计算向量X1和X2的相对距离来判断两个源程序的相似性。例如：关键字VoidIntForCharifelsewhiledobreakclass程序1关键字频度4304307002程序2关键字频度4205405201X1=[4,3,0,4,3,0,7,0,0,2]X2=[420,5,4,0,520,1]设s是向量X1和X2的相对距离，s=sqrt(2仅初二刖)2)，当X『X2时，s=0，反映出可能是同一个程序；s值越大，则两个程序的差别可能也越大。三、概要设计为了实现上述功能，可以用结构体表示哈希表，因此需要哈希表的抽象数据类型。哈希表抽象数据类型的定义：ADThashtable{数据对象：D={a.|a.£ElemType,且各不相同，i=1,2...,n,n三0}数据关系：RR基本操作：Hashfunc(charstr[]);Hashfind(char*words);creathash(void);resethash(intn);isletter(charch);readc(char*filename);getkey(char*str,intlen);copycount(intx[],intn);check(int*x1,int*x2);}endADT第1页共11页

数据结构与算法课程设计报告14101103-傅开煤本程序实现模块主程序模块哈希表程序模块：实现哈希表的抽象数据类型调用关系图如下：主程序模块数据结构与算法课程设计报告14101103-傅开煤本程序实现模块主程序模块哈希表程序模块：实现哈希表的抽象数据类型调用关系图如下：主程序模块哈希表程序模块计算相似度和向量

的几何距离的模块四、详细设计1、各个子函数的设计（1）创建哈希表函数函数原型：voidcreathash（void）;输入：读取存储了32个关键字的文件keyword.txt思路：通过对keyword.txt文件逐行赋值给创建的str字符数组，并将该数组调入Hashfunc函数。（2）将关键字根据哈希函数放入哈希表中的指定位置的函数函数原型：voidHashfunc（charstr口）;思路：对调进来的str数组通过调用getkey函数得到该关键词的key值后放入哈希表中的特定位置，并用线性探索来解决冲突。（3）在哈希表中找是否该words为关键字，并统计频度的函数函数原型：intHashfind（char*words）;思路：将调进来的word字符数组先调用getkey函数获取key值，然后在哈希表里查找是否存在该字符串，如果存在则该关键字对应的频度加1。（4）重置哈希表函数函数原型：voidresethash（intn）;功能：当n为0时，将指向哈希表中关键字的指针置成Null，同时将频度全部置为0.而当n为1时，仅仅将频度置为0。（5）获取单词key的函数函数原型：intgetkey（char*str,intlen）;思路：用key1存储关键字的首字母，key2存储关键字的末字母，然后通过哈希函数得到key的值并返回。（6）判断是否为字母的函数第2页共11页O氏作加换上笏数据结构与算法课程设计报告 14101103准开煤函数原型：intisletter（charch）;思路:如果调进来的ch字符的ASCII值在a~z或A~Z范围内的话则返回1，否则返回0。（7）读取源程序文件中的单词的函数函数原型：intreadc（char*filename）;思路：为了读取源程序文件中的单词，所以一个字符一个字符的，如果读的超过最大关键字长度将会跳过当前识别区域，读取下一个单词，将得到的该单词调入Hashfind函数，来判断是否为关键字，并统计频度。（8）将频度拷贝到数组里的函数函数原型：voidcopycount（intx口，intn）;功能：将哈希表中关键字的频度复制到x数组中，以便进行后面相似度等的计算。（9）检查两个源程序是否相似的函数函数原型：voidcheck（int*x1,int*x2）;思路：对调进来的x1和x2数组进行相似度计算，若相似度大于设定好的阈值，则再进行几何距离计算，最后给出两个文件是否相似的判断。（10）取模函数函数原型：floatMol（int*x）;思路：通过求向量模值的数学知识求x数组的模。（11）点积函数函数原型：intDot（int*x1,int*x2）思路：通过点积的数学知识对两个向量求点积。（12）求相似度S的函数函数原型：floatS（int*x1,int*x2）;思路：根据题目给的求相似度的公式求x1和x2数组的相似度。（13）求距离D的函数函数原型：floatD（int*x1,int*x2）;思路：用题目给的球几何距离的公式求x1和x2数组的几何距离。2、主函数伪码intmain(){charfilename1[]={"test1.txt"};charfilename2[]={"test2.txt"};charfilename3[]={"test3.txt"};intx1[hashlen],x2[hashlen],x3[hashlen];/*存储频度的数组，用于相似度S的计算*/resethash(0); /*完全重置哈希表，即哈希指针置为NULL，频度置为0*/creathash(); 〃通过文件ckey.txt创建哈希表readc(filename1);〃读取第一个测试源程序文件copycount(x1,hashlen);〃讲统计好的频度复制给x数组resethash(1); 〃仅仅将频度count置为0readc(filename2);//同上copycount(x2,hashlen);resethash(1);第3页共11页

数据结构与算法课程设计报告14101103-数据结构与算法课程设计报告14101103-傅开煤readc(filename3);copycount(x3,hashlen);cout<<〃\t〃<<〃哈希序号〃<<〃 \t〃<<〃关键字〃<<〃 \t〃<<〃频度1〃<<〃 \t〃<<〃频度2〃<<〃 \t〃<<〃频度3"<<endl;for(inti=0;i<41;i++){if(hasht[i].hash1!=NULL){cout<<"\t"<<i<<" \t"<<hasht[i].hash1<<”\t"<<x1[i]<<" \t"<<x2[i]<<" \t"<<x3[i]<<endl;))cout<<filename1<<"和"<<filename2<<”的相似情况为："<<endl;check(x1,x2); 〃检查相似度cout<<filename1<<"和"<<filename3<<”的相似情况为："<<endl;check(x1,x3);cout<<filename2<<"和"<<filename3<<”的相似情况为："<<endl;check(x2,x3);return0;)3、调用关系图调用关系图如下:readcislettehashfindgetkeycreathashhashfunc调用关系图如下:readcislettehashfindgetkeycreathashhashfunc第4页共11页数据结构与算法课程设计报告14101103-数据结构与算法课程设计报告14101103-傅开煤五、编码实现1.使用函数voidresethash(intn)来重置哈希表voidresethash(intn){ 〃重置哈希表if(n=0) 〃完全重置哈希表{for(inti=0;i<41;i++){hasht[i].hash1=NULL;hasht[i].count=0;))elseif(n=1) 〃仅仅重置频度{for(inti=0;i<41;i++){hasht[i].count=0;))).使用voidcopycount(intx[],intn)来将频度拷贝到数组里的函数voidcopycount(intx[],intn){ //拷贝频度for(inti=0;i<n;i++){x[i]=hasht[i].count;)).使用intgetkey(char*str,intlen)来获取单词key的函数intgetkey(char*str,intlen) //根据哈希函数获取该单词的key{charkey1,key2;intkey;key1=str[0];key2=str[len-11;key=(int)(key1*100+key2)%41;returnkey;)第5页共11页

数据结构与算法课程设计报告.使用voidcreathash(void)来创建哈希表函数14101103-傅开煤voidcreathash(void) //对文件keyword.txt14101103-傅开煤{FILE*fp;intlength;charstr[size]; 〃暂时存储关键字字符的数组char*s=NULL;for(inti=0;i<size;i++){str[i]=，\0，;)if((fp=fopen("keyword.txt","r"))==NULL){cout<<"can'tcreatfile!\n";exit(0);)while(fgets(str,size,fp)!=NULL) //读取一行写入一行{if(str==NULL){break;)length=strlen(str);str[length-1]='\0'; 〃调试后发现的，没有这里就停止运行了Hashfunc(str);)fclose(fp);).使用voidHashfunc(charstr口)来将关键字根据哈希函数放入哈希表中的指定位置的函数voidHashfunc(charstr[]){ 〃将关键字根据哈希函数放入哈希表中的指定位置intkey,len;len=strlen(str);key=getkey(str,len);while(hasht[key%41].hash1!=NULL){key++; 〃线性探索)hasht[key%411.hash1=(char*)malloc(sizeof(char)*(len+1));strcpy(hasht[key%411.hash1,str);)第6页共11页O氏由甜换上挈数据结构与算法课程设计报告 14101103准开煤.使用intHashfind(char*words)来在哈希表中找是否该words为关键字，并统计频度的函数intHashfind(char*words)//在哈希表中找是否该words为关键字，并统计频度{intkey,len,find;len=strlen(words);key=getkey(words,len);while(hasht[key].hash1==NULL)key++;key=key%41;if(strcmp(hasht[key].hash1,words)==0){hasht[key].count++;return1;)for(find=key+1;find<hashlen;find++)/*如果不在key位置则向往后线性查找，然后再从头找*/{〃线性探查法顺序查找哈希表中是否已存在关键字if(hasht[find].hash1!=NULL){if(strcmp(hasht[find].hash1,words)==0){hasht[find].count++;return1;)))for(find=0;find<key;find++){if(hasht[find].hash1!=NULL){if(strcmp(hasht[find].hash1,words)==0){hasht[find].count++;return1;)))return0;).使用intreadc(char*filename)来读取源程序文件中的单词的函数intreadc(char*filename){ 〃读取源程序文件中的单词第7页共11页

数据结构与算法课程设计报告14101103-数据结构与算法课程设计报告14101103-傅开煤FILE*fp1=NULL;charwords[maxlen],ch;inti;if((fp1=fopen(filename,"r"))==NULL){cout<<"cannotcreatfile!\n";exit(0);)while(!feof(fp1)) 〃结束返回1{i=0;ch=fgetc(fp1); 〃一个字符一个字符的读while(isletter(ch)==0&&feof(fp1)==0){ch=fgetc(fp1);)while(isletter(ch)==1&&feof(fp1)==0){if(i==maxlen){while(isletter(ch)==1&&feof(fp1)==0){ch=fgetc(fp1);)i=0;break;}〃超过最大关键字长度将会跳过当前识别区域，读取下一个单词else{words[i++]=ch;ch=fgetc(fp1);))words[i]='\0';Hashfind(words); /*将得到的该单词调入Hashfind函数，来判断是否为关键字，并统计频度*/)fclose(fp1);return0;).使用floatMol(int*x)来取模函数floatMol(int*x) 〃取模函数{第8页共11页

数据结构与算法课程设计报告14101103-数据结构与算法课程设计报告14101103-傅开煤inti=0,sum=0;for(i=0;i<N;i++){sum+=(x[i]*x[i]);)return(float)pow((float)sum,0.5);)intDot(int*x1,int*x2){ 〃点积函数inti=0,sum=0;for(i=0;i<N;i++){sum+=x1[i]*x2[i];)returnsum;).使用floatS(int*x1,int*x2)、floatD(int*x1,int*x2)和voidcheck(int*x1,int*x2)来分别求相似度S的函数、求几何距离D函数和检查两个源程序是否相似的函数floatS(int*x1,int*x2){returnDot(x1,x2)/(Mol(x1)*Mol(x2));//求相似度S)floatD(int*x1,int*x2) 〃求几何距离{intx[N],i=0;for(i=0;i<N;i++)〃向量相减{x[i]=x1[i]-x2[i];)returnMol(x); 〃再求模)voidcheck(int*x1,int*x2){floatxs=0,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<Dmin)〃如果几何距离小于阈值则判断为相似cout<<〃这两个文件内容确实可能相似〃<<endl;第9页共11页数据结构与算法课程设计报告14101103-傅开煤elsecout<<〃这两个文件内容可能不相似〃<<endl;return;)cout<<〃这两个文件内容不相似〃<<endl; 〃否则不相似return;)六、实验结果与分析实验上机测试结果如下图所示:哈希序号至鞋字频度L0哈希序号至鞋字频度L0enjtn01extern02goto03int214long15signed06sizeof07jswitch-18ijnion010char□11void1212auto013constC14short016double016struct017typedel-018volatile023for824if1323do226break1029vhi1e630default031returnqz33else634regisLer03d□nsigned037static038case1139continue040float10■CW伸开/口光质即\数据结构与箕法课设M岫四联斓结构与算法具设ch币67^--0009.-0001017000011061049.-175001400频度300021100■I0u120000000813210600001100testl.tst和test2.txt的相似情况为:相似度工&=0.920507几何距离xd=l%口49这两个文件内容可能不相似搜狗拼音输入法全：二的相似情况为:第10页共11页0夭亦却按上笏数据结构与算法课程设计报告14101103-傅开煤■CW犍咚照开特Desk(。口避据结胸与算法课设'Debug联谑结构与算法建设ce依工和test?,txt的相似情况为:丽似度xs=O.920507□.何距离xdIX1149这两个文件内容可能不相似7estL txt的相慨情况为:相似度机；=1□.何距离Xd=0这两个文件内容确实可能相似test2.txt^ltest3.txt的相似情况为t相似度焚尸Cl@£0307几何距离xd=l左口】妁这两个文件内容可能不相似清按任意键继续，..搜狗拼音