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

..;.数据结构与算法课程设计报告设计题目：源程序的相似性专业计算机科学与技术学号14101103姓名傅开煤2017年1月10日..;.源程序的相似性一、问题描述对于两个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(∑(x1[i]-x2[i])2)，当X1=X2时，s=0，反映出可能是同一个程序；s值越大，则两个程序的差别可能也越大。三、概要设计为了实现上述功能，可以用结构体表示哈希表，因此需要哈希表的抽象数据类型。哈希表抽象数据类型的定义：ADThashtable{数据对象：D={ai|ai∈ElemType,且各不相同，i=1,2...,n,n≥0}数据关系：R=φ基本操作：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、各个子函数的设计（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）判断是否为字母的函数主程序模块哈希表程序模块计算相似度和向量的几何距离的模块..;.函数原型：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);..;.readc(filename3);copycount(x3,hashlen);cout\t哈希序号\t关键字\t频度1\t频度2\t频度3endl;for(inti=0;i41;i++){if(hasht[i].hash1!=NULL){cout\ti\thasht[i].hash1\tx1[i]\tx2[i]\tx3[i]endl;}}coutfilename1和filename2的相似情况为：endl;check(x1,x2);//检查相似度coutfilename1和filename3的相似情况为：endl;check(x1,x3);coutfilename2和filename3的相似情况为：endl;check(x2,x3);return0;}3、调用关系图调用关系图如下：main()resethashcreathashreadccopycountisletterhashfindhashfuncgetkeycheckDSDotMol..;.五、编码实现1.使用函数voidresethash(intn)来重置哈希表voidresethash(intn){//重置哈希表if(n=0)//完全重置哈希表{for(inti=0;i41;i++){hasht[i].hash1=NULL;hasht[i].count=0;}}elseif(n=1)//仅仅重置频度{for(inti=0;i41;i++){hasht[i].count=0;}}}2.使用voidcopycount(intx[],intn)来将频度拷贝到数组里的函数voidcopycount(intx[],intn){//拷贝频度for(inti=0;in;i++){x[i]=hasht[i].count;}}3.使用intgetkey(char*str,intlen)来获取单词key的函数intgetkey(char*str,intlen)//根据哈希函数获取该单词的key{charkey1,key2;intkey;key1=str[0];key2=str[len-1];key=(int)(key1*100+key2)%41;returnkey;}..;.4.使用voidcreathash(void)来创建哈希表函数voidcreathash(void)//对文件keyword.txt中的32个关键字创建哈希表{FILE*fp;intlength;charstr[size];//暂时存储关键字字符的数组char*s=NULL;for(inti=0;isize;i++){str[i]='\0';}if((fp=fopen(keyword.txt,r))==NULL){coutcan'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);}5.使用voidHashfunc(charstr[])来将关键字根据哈希函数放入哈希表中的指定位置的函数voidHashfunc(charstr[]){//将关键字根据哈希函数放入哈希表中的指定位置intkey,len;len=strlen(str);key=getkey(str,len);while(hasht[key%41].hash1!=NULL){key++;//线性探索}hasht[key%41].hash1=(char*)malloc(sizeof(char)*(len+1));strcpy(hasht[key%41].hash1,str);}..;.6.使用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;findhashlen;find++)/*如果不在key位置则向往后线性查找，然后再从头找*/{//线性探查法顺序查找哈希表中是否已存在关键字if(hasht[find].hash1!=NULL){if(strcmp(hasht[find].hash1,words)==0){hasht[find].count++;return1;}}}for(find=0;findkey;find++){if(hasht[find].hash1!=NULL){if(strcmp(hasht[find].hash1,words)==0){hasht[find].count++;return1;}}}return0;}7.使用intreadc(char*filename)来读取源程序文件中的单词的函数intreadc(char*filename){//读取源程序文件中的单词..;.FILE*fp1=NULL;charwords[maxlen],ch;inti;if((fp1=fopen(filename,r))==NULL){coutcannotcreatfile!\n;exit(0);}while(!feof(fp1))//结束返回1{i=0;ch=fgetc(fp1);//一个字符一个字符的读while(isletter(ch)==0&&feof(fp1)==0){ch=