哈希表判断源程序相似性

#includestdio.h#includestdlib.h#includemath.h#includestring.htypedefstructnode{charc[10];intlen;//记录关键字的长度structnode*q;}keynode;//关键字结点，认为关键字的长度不超过10个字符typedefstructtable{charw;keynode*p;}hash;//定义哈希表类型voidinit_value(hashkey[],charstack[],intinformation1[],intinformation2[])//初始化函数{inti;for(i=0;i100;i++)key[i].p=NULL;for(i=0;i10;i++)stack[i]='\0';for(i=0;i20;i++){information1[i]=0;information2[i]=0;}}voidcreate_hash(hashkey[])//创建哈希表函数{inti,num=0,k;//num表示关键字的数量，k表示单个关键字的长度charch;FILE*fp;keynode*p1;//p1为指向关键字结点类型的指针hashp2;//p2为指向hash类型的指针for(i=0;i26;i++)key[i].w='a'+i;//哈希表每个结点的字符域存储26个字母fp=fopen(C:\\keyword.txt,r);//打开写有关键字的文件，文件存储在C盘上while(num100)//假设关键字的个数少于100{k=0;while(k10)//假设关键字的长度少于10{ch=fgetc(fp);//从文件中读一个字符，遇空格则退出if(ch==32)break;if(k==0)p1=(keynode*)malloc(sizeof(structnode));//若不是空格，且是关键字的第一个字母，则开辟关键字结点空间(*p1).c[k]=ch;k++;}i=0;while(i26)//将一个关键字读入关键字结点后，将该结点链接到哈希表上{if((*p1).c[0]!=key[i].w)i++;else{key[i].p=p1;p1-q=NULL;p1-len=k;}}num++;if(feof(fp))//如果该文件已读完，则关闭文件{fclose(fp);break;}}}voidget_compare1(charstack[],hashkey[],intinformation1[])//从给出的一个源程序中读关键字,将该关键字存入字符数组{FILE*fp;charch;inti,j;keynode*q1;fp=fopen(C:\\program1.txt,r);//打开存储在C盘的源程序do{i=0;while(i10)//读取时认为关键字的长度小于10{ch=fgetc(fp);//从文件中读取时一个字符一个字符来读，遇到空格则退出if(ch==32)break;stack[i]=ch;i++;//读取下一个字符}i=0;while(i26)//将该关键字与哈希表中的关键字比较{if(stack[0]!=key[i].w)i++;else{q1=key[i].p;while(q1){if(strcmp(stack,q1-c)!=0)//若待比较的关键字与当前指向的关键字不同，则指向下一个关键字q1=q1-q;else//若待比较的关键字与当前指向的关键字相同，则对应位置的频数加1{j=(*q1).len;information1[j]++;break;}}break;}}}while(ch!=EOF);//若该源程序已读完，则关闭文件fclose(fp);}voidget_compare2(charstack[],hashkey[],intinformation2[])//从给出的另一个源程序中读关键字,将该关键字存入字符数组{FILE*fp;charch;inti,j;keynode*q1;fp=fopen(C:\\program2.txt,r);do{i=0;while(i10){ch=fgetc(fp);if(ch==32)break;stack[i]=ch;i++;}i=0;while(i26){if(stack[0]!=key[i].w)i++;else{q1=key[i].p;while(q1-q){if(strcmp(stack,q1-c)!=0)q1=q1-q;else//若待比较的关键字与当期指向的关键字相同，则对应位置的频数加1{j=(*q1).len;information2[j]++;break;}}break;}}}while(ch!=EOF);fclose(fp);}floatsimilarity(intinformation1[],intinformation2[])//利用广义余弦法计算这两个程序的相似度{intk=0,m=0,n=0,p=0,q=0;floatr,l,i;while(k100){n+=information1[k]*information2[m];p+=information1[k]*information1[k];q+=information2[m]*information2[m];k++;m++;r=sqrt(p);l=sqrt(q);i=n/(l*r);return(i);//i即为两源程序的相似度}}intmain(void){floati;hashkey[100];//建立一个hash结构的数组空间，该数组中存放26个字母charstack[10];//建立一个字符数组空间，其中存放待比较源程序的关键字intinformation1[20],information2[20];init_value(key,stack,information1,information2);//初始化数组create_hash(key);//创建哈希表get_compare1(stack,key,information1);//比较第一个源程序get_compare2(stack,key,information2);//比较第二个源程序i=similarity(information1,information2);//计算相似度printf(姓名：上官武悦\t学号：2010312050\t实验四：用哈希表判断源程序相似性\n\n);printf(***************************************************************\n\n);printf(\n两个程序的相似度为:%f\n\n,i);}