哈希表技术判别源程序的相似性实验报告.docx
《哈希表技术判别源程序的相似性实验报告.docx》由会员分享，可在线阅读，更多相关《哈希表技术判别源程序的相似性实验报告.docx（31页珍藏版）》请在冰点文库上搜索。
哈希表技术判别源程序的相似性实验报告
哈希表技术判别源程序的相似性--实验报告
[文档标题]
[文档副标题]
Administrator
2014-12-26
一.问题描述
实验题目：
对于两个C语言的源程序清单，用哈希表的方法分别统计两程序中使用C语言关键字的情况，并最终按定量的计算结果，得出两份源程序的相似性。
要求与提示：
C语言关键字的哈希表可以自建，也可以采用下面的哈希函数作为参考：
Hash（key）=（key第一个字符序号*100+key最后一个字符序号）%41
表长m取43。
此题的工作主要是扫描给定的源程序，累计在每个源程序中C语言关键字出现的频度。
为保证查找效率，建议自建哈希表的平均查找长度不大于2。
扫描两个源程序所统计的所有关键字不同频度，可以得到两个向量。
如下面简单的例子所示：
输入为若干个c源程序，输出为程序问的相似度以及向量的几何距离。
基本要求：
建立哈希表，统计源程序中关键字出现的频度，并计算多个源程序之间的相似度。
测试数据：
自己在网上找到一些C语言程序，分别为test1.txt,test2.txt,test3.txt等。
运行结果应为输出每个源程序关键字的出现的频度和源程序之间的相似度以及向量的几何距离。
二．需求分析
1.本程序用来通过建立哈希表求源程序关键字的出现的频度和源程序之间的相似度以及向量的几何距离。
2.用户可以将源程序的.txt文件放入hashtable文件夹中，运行程序就可以输出每个源程序关键字的出现的频度和源程序之间的相似度以及向量的几何距离。
三．概要设计
为了实现上述功能，可以用结构体表示哈希表，因此需要哈希表的抽象数据类型。
哈希表抽象数据类型的定义：
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
3.本程序实现模块
主程序模块
哈希表程序模块：
实现哈希表的抽象数据类型
调用关系：
计算相似度和向量的几何距离的模块
四．详细设计
1.各个子函数的设计
1）创建哈希表函数
函数原型：
voidcreathash（void）;
输入：
读取存储了32个关键字的文件ckey.txt
思路：
通过对ckey.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[]={"test12.txt"};
charfilename3[]={"test13.txt"};
intx1[hashlen],x2[hashlen],x3[hashlen];//存储频度的数组，用于相似度S的计算
resethash（0）;//完全重置哈希表，即哈希指针置为NULL，频度置为0
creathash（）;//通过文件ckey.txt创建哈希表
readc（filename1）;//读取第一个测试源程序文件
copycount（x1,hashlen）;//讲统计好的频度复制给x数组
resethash
（1）;//仅仅将频度count置为0
readc（filename2）;//同上
copycount（x2,hashlen）;
resethash
（1）;
readc（filename3）;
copycount（x3,hashlen）;
cout<<"\t"<<"哈希序号"<<"\t"<<"关键字"<<"\t"<<"频度1"<<"\t"<<"频度2"<<"\t"<<"频度3"<for（inti=0;i<41;i++）
{
if（hasht[i].hash1!
=NULL）
{
cout<<"\t"<}
}
cout<"<check（x1,x2）;//检查相似度
cout<"<check（x1,x3）;
cout<"<check（x2,x3）;
return0;
}
3.调用关系图
S
D
Mol
Dot
getkey
isletter
main（）
hashfunc
resethash
creathash
readc
copycount
hashfind
check
五．调试分析
1.遇到的问题分析
1）‘=’与‘==’的问题
赋值号与等号的问题虽然平时一直都会注意，但是有时候粗心也容易犯错，就比如在该语句中：
if（（fp=fopen（"ckey.txt","r"））==NULL）写成了if（（fp=fopen（"ckey.txt","r"））=NULL），导致运行时出现下图
看到过一本讲编程的书说为了避免这种错误，可以#define==equal，这样就变成了if（（fp=fopen（"ckey.txt","r"））equalNULL）。
虽然这样确实可以避免该类错误，但是我觉的也没有太大的必要，只要平时注意点小心点就是了。
而且如果在visualstudio2012上编程时，一般是不允许出现fopen这种不安全函数的，要使用它推荐的fopen_s函数，使用如下
2）第二个问题出现在creathash函数中，也比较难找。
当时程序没有红色的那两句，
while（fgets（str,size,fp）!
=NULL）//读取一行写入一行
{
if（str==NULL）
{
break;
}
length=strlen（str）;
str[length-1]='\0';
Hashfunc（str）;
}
fclose（fp）;
}
接下来的是没有那两句的运行后的窗口截图
如果加上那两句红色的语句后的运行窗口就是这样的
后来调试时发现，（就拿文件ckey.txt中的第一个关键字为例）
在没有那两句红色语句时，调试窗口是这样显示的
说明在执行逐行读取关键字的那段代码时，它把每一行的换行号也读进了str数组里，导致输出时，每个关键字都做了换行，便有了上面的第一个截图。
所以我的解决办法就是加入红色的那两句，即length=strlen（str）;str[length-1]='\0';也就是把最后的换行号替换为‘\0’.
3）第三个问题出现在readc函数中。
在下面代码中原本没有注销的那一语句。
所以导致这样的结果：
即统计不到源程序文件中的关键字的频度，均显示为0.
然后进行调试发现（就以读取到的第一个单词include为例）：
从调试窗口可看出读取完一个完整的单词后，它自己不能给该word数组赋值‘\0’来结束，这样导致的结果将会发生在Hashfind函数中的strcmp函数中，即
通过上网查资料后知道，strcmp函数进行两字符串比较时是两个字符串自左向右逐个字符相比（按ASCII值大小相比较），直到出现不同的字符或遇'\0'为止。
而我的hasht[key].hash1数组里的字符串为{i,n,c,l,u,d,e’\0’},而words数组为{i,n,c,l,u,d,e}，所以比较的结果是它们不相等，就统计不到关键字的频度。
所以我的解决办法即注销的那句：
words[i]='\0';对每次读到的单词后都加一个‘\0’。
4）第四个问题出现在求几何距离的D函数。
原本我是这样写的
float D（int *X1, int *X2）
{
int *X;
X = Sub（X1, X2）;
return Mol（X）;
}
int*Sub（int*X1,int*X2）
{
intX[N],i=0;
for（i=0;i{
X[i]=X1[i]-X2[i];
}
returnX;
}
floatMol（int*X）
{
inti=0,sum=0;
for（i=0;i{
sum+=X[i]*X[i];
}
return（float）pow（sum,0.5）;
}
这样运行的结果就是求出来的几何距离是个很奇怪的随机数，每运行一次得出的结果都不一样。
原因在于在Sub函数中X数组是个局部变量，返回的X只能是个指针，此时它已经不代表刚才指向的那个数组了，然后调进Mol函数中，进行的操作也只是对X的地址进行操作，因为地址是随机数，所以返回的也是个随机数。
我所以我将这D和Sub两个函数直接合并为一个D函数
floatD（int*x1,int*x2）//求几何距离
{
intx[N],i=0;
for（i=0;i{
x[i]=x1[i]-x2[i];
}
returnMol（x）;//再求模
}
2.复杂度的分析
本程序中没有用到循环嵌套，所以每个函数的时间复杂度基本为O（n），空间复杂度也基本为O（n）。
六．使用说明，本程序的主要功能就是统计源程序之间的相似度，所以使用者只需要将要检测的源程序的txt文件放入该程序的工程文件夹中
然后在修改读取的文件名便可直接运行了。
七．测试结果
结果与实际结果相符，故可以认为该程序是成功的。
八．心得与体会。
1.通过本实验让我用程序对文件的操作有了更深的理解，知道了如果直接的逐行读取文件的话，换行号也会被读进去的。
2.对局部变量有了更好的理解。
3学会了建立哈希表的过程，以及更好的掌握了调试这一功能。
4.由于本程序的编写和调试我是在visualstudio2012进行的，所以上述截图均为在该编辑环境中进行的。
使用visualstudio编程体会到了其功能之强大和方便。
而且也更安全，例如它一般不允许fopen，strcpy这种不安全函数，所以原本我用的是
和
这种visual推荐的安全函数。
只是后来将代码拷贝的VC++后这些安全函数不能用后，我又换了回来，但其他的基本不用改。
九．附完整源程序
//哈希表统计源程序的相似度
#include"iostream"
#include"stdlib.h"
#include"string"
#include"math.h"
#defineN32//关键字个数
#definesize256
#definemaxlen9//关键字数组长度
#definehashlen41//哈希表长度
#defineSmax0.9//相似度s的阈值
#defineDmin2//D的阈值
structhashtable//结构体数组哈希表
{
char*hash1;//指向关键字的指针
intcount;//记录频度
}hasht[hashlen];
usingnamespacestd;
voidHashfunc（charstr[]）;//将关键字根据哈希函数放入哈希表中的指定位置
intHashfind（char*words）;//在哈希表中找是否该words为关键字，并统计频度
voidcreathash（void）;//创建哈希表
intisletter（charch）;//判断是否为字母
floatMol（int*x）;//取模函数
intDot（int*x1,int*x2）;//点积函数
floatD（int*x1,int*x2）;//求距离D的函数
floatS（int*x1,int*x2）;//求相似度S的函数
intreadc（char*filename）;//读取源程序文件中的单词
intgetkey（char*str,intlen）;//获取该单词的key
voidresethash（intn）;//重置哈希表
voidcopycount（intx[],intn）;//将频道拷贝到数组里
voidcheck（int*x1,int*x2）;//检查两个源程序是否相似
intmain（）
{
charfilename1[]={"test1.txt"};
charfilename2[]={"test12.txt"};
charfilename3[]={"test13.txt"};
intx1[hashlen],x2[hashlen],x3[hashlen];//存储频度的数组，用于相似度S的计算
resethash（0）;//完全重置哈希表，即哈希指针置为NULL，频度置为0
creathash（）;//通过文件ckey.txt创建哈希表
readc（filename1）;//读取第一个测试源程序文件
copycount（x1,hashlen）;//讲统计好的频度复制给x数组
resethash
（1）;//仅仅将频度count置为0
readc（filename2）;//同上
copycount（x2,hashlen）;
resethash
（1）;
readc（filename3）;
copycount（x3,hashlen）;
cout<<"\t"<<"哈希序号"<<"\t"<<"关键字"<<"\t"<<"频度1"<<"\t"<<"频度2"<<"\t"<<"频度3"<for（inti=0;i<41;i++）
{
if（hasht[i].hash1!
=NULL）
{
cout<<"\t"<}
}
cout<"<check（x1,x2）;//检查相似度
cout<"<check（x1,x3）;
cout<"<check（x2,x3）;
return0;
}
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）
{//拷贝频度
for（inti=0;i{
x[i]=hasht[i].count;
}
}
intgetkey（char*str,intlen）//根据哈希函数获取该单词的key
{
charkey1,key2;
intkey;
key1=str[0];
key2=str[len-1];
key=（int）（key1*100+key2）%41;
returnkey;
}
voidcreathash（void）//对文件ckey.txt中的32个关键字创建哈希表
{
FILE*fp;
intlength;
charstr[size];//暂时存储关键字字符的数组
char*s=NULL;
for（inti=0;i{
str[i]='\0';
}
if（（fp=fopen（"ckey.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[]）
{//将关键字根据哈希函数放入哈希表中的指定位置
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）;
}
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{
//线性探查法顺序查找哈希表中是否已存在关键字
if（hasht[find].hash1!
=NULL）
{
if（strcmp（hasht[find].hash1,words）==0）
{
hasht[find].count++;
return1;
}
}
}
for（find=0;find{
if（hasht[find].hash1!
=NULL）
{
if（strcmp（hasht[find].hash1,words）==0）
{
hasht[find].count++;
return1;
}
}
}
return0;
}
intisletter（charch）
{//判断是否ch为字母
if（（ch>='a'&&ch<='z'）||（ch>='A'&&ch<='Z'））return1;
retur
升级会员 