哈希实验报告.doc

一、 问题描述 1. 实验题目：利用哈希表统计两源程序的相似性2. 基本要求：1）内容： 对于两个 C 语言的源程序清单，用哈希表的方法分别统计两程序中使用C语言关键字的情况，并最终按定量的计算结果，得出两份源程序的相似性。 2）要求与提示： C 语言关键字的哈希表可以自建，也可以采用下面的哈希函数作为参考： Hash(key)=(key第一个字符序号*100+key最后一个字符序号)%41 表长m取43。此题的工作主要是扫描给定的源程序，累计在每个源程序中C语言关键字出现的频度。为保证查找效率，建议自建哈希表的平均查找长度不大于2。 扫描两个源程序所统计的所有关键字不同频度， 可以得到两个向量。如下面简单的例子所示： 关键字 void int forchar ifelse while 程序1中 关键字频度4 3 4 3 7 0 2 程序2中 关键字频度4 2 5 4 5 2 1 哈希地址 0 1 2 3 4 56 7 8 9 根据程序1和程序2中关键字出现的频度，可提取到两个程序的特征向量X1和X2，其中 X1=(4 3 0 4 3 0 7 0 0 2)TX2=(4 2 0 5 4 0 5 2 0 1)T一般情况下，可以通过计算向量Xi和Xj的相似值来判断对应两个程序的相似性，相似值的判别函数计算公式为: 其中，。S(Xi,Xj)的值介于0,1之间，也称广义余弦，即S(Xi,Xj)=COS。Xi=Xj 时，显见S(Xi,Xj)=1，=0；XiXj 差别很大时，S(Xi,Xj)接近0，接近/2。如X1=(1 0)T,X2=(0 1)T,则S(Xi,Xj)=0，=/2。当S值接近1 的时候，为避免误判相似性（可能是夹角很小，模值很大的向量），应当再次计算之间的“几何距离” D(Xi,Xk)。其计算公式为：最后的相似性判别计算可分两步完成： 第一步 用式（3-1）计算S，把接近 1的保留，抛弃接近0的情况（把不相似的排除）； 第二步 对保留下来的特征向量，再用式（3-2）计算D，如D值也比较小，说明两者对应的程序确实可能相似（慎重肯定相似的）。 S和D的值达到什么门限才能决定取舍？需要积累经验，选择合适的阈值。 3) 测试数据: 做几个编译和运行都无误的C程序，程序之间有相近的和差别大的，用上述方法求S，并对比差异程度。二、 需求分析 1.本程序能够打印根据关键字建立的哈希表及利用该表统计的C语言源程序关键字使用情况，得出源程序的相似性。2.将关键字输入key.txt中，关键字均为char型，以空格分开，将要比较的源程序存入不同文本文档中，运行时按提示输入源程序个数和相应的文档名称，若输入多个源程序，比较时输入相应的源程序序号（序号为输入源程序的顺序）。3.输出建立的哈希表，按哈希表统计的源程序关键字使用情况，所比较的两个程序间的相似度以及向量的几何距离。三、 概要设计 为了实现上述功能，需要哈希表抽象数据类型。哈希表抽象数据类型定义： ADT HashList 数据对象：D是相同类型元素构成的结合。 数据关系：R=集合内的元素之间是松散关系 基本操作： int Dimension(LinkHashList HT);/求哈希表元素总个数int HashFunc(char *e); /哈希函数void InitHashList(LinkHashList &HT,int m,FILE *fp); /创建哈希表void InsertHT(LinkHashList &HT,char *e);/插入元素LNode * SearchHT(LinkHashList HT,char *e);/查找元素void HashBuild(FILE *fp,LinkHashList &HT);/统计源程序每个关键字频度void Hashclear(LinkHashList &HT,int m);/将哈希表每个关键字频度置零void TraverseHT(LinkHashList HT); /输出哈希表 ADT HashList5.本程序保护模块： 主程序模块 哈希表单元模块：实现哈希表抽象数据类型 调用关系：主程序模块-哈希表单元模块四、 详细设计 1.结点类型和结点指针类型： typedef struct LNodechar data10;int account;struct LNode *next;LNode,*ppLNode;typedef structppLNode head;int length;LinkHashList;2.哈希表的实现求哈希表元素总个数int Dimension(LinkHashList HT)int d,count=0;LNode *p;for(d=0;dnext;count+;return count;哈希函数int HashFunc(char *e)int i;for(i=0;idata,e);p-account=0;p-next=HT.headd;HT.headd=p;/查找元素LNode * SearchHT(LinkHashList HT,char *e) int d=HashFunc(e);LNode *p=HT.headd;while(p&strcmp(p-data,e)!=0)p=p-next;return p;/创建哈希表void InitHashList(LinkHashList &HT,int m,FILE *fp) int i,d;char str10;HT.head=new LNode *m; HT.length=m; for(i=0;idata,0); p-account=0; p-next=HT.headi; HT.headi=p;char ch=fgetc(fp);while(ch!=EOF)if(ch= &ch!=EOF) doch=fgetc(fp);while(ch= ); i=0; while(ch!= &ch!=EOF)stri+=ch;ch=fgetc(fp);stri=0; InsertHT(HT,str);统计源程序每个关键字频度void HashBuild(FILE *fp,LinkHashList &HT)int i,d;char str10;char ch=fgetc(fp);while(ch!=EOF) while(ch122)&ch!=EOF) ch=fgetc(fp); i=0;if(ch96&ch96&chaccount+;ch=fgetc(fp);将哈希表每个关键字频度置零void Hashclear(LinkHashList &HT,int m) LNode *p; int i; for(i=0;iaccount=0;p=p-next;/遍历哈希表void TraverseHT(LinkHashList HT) LNode *p;p=HT.head0-next;cout0next)coutdata;coutaccount;p=p-next;coutendl;for(int i=1;iHT.length;i+)p=HT.headi;coutinext)coutdata;coutaccount;p=p-next;coutendl;/for3.函数调用关系图主函数InitHashListHashclearDimensionCosine（求相似度）HashBuildDistance（求几何距离）TraverseHT五、调试分析1.hashbuild函数中，在文件中搜索字符时，采用的方法是比较ASC码的值，但是总是执行后无法继续，后来发现是ch在最后被赋值为EOF而没有经外层循环的判断跳出，因而在内层循环中也添加了一个判断。2.原先利用哈希表对源程序关键字计数时，没有考虑在统计完一个程序后，要对哈希表计数的量重新置零，得到的结果总是不对，后来添加了hashclear函数，得到了正确的结果。3.输出统计结果时，注意到哈希表的插入是对head前插，所以每个单元最后一个节点没有赋关键字符值，还是初始值零，输出时跳过，但是后面将统计结果赋值给数组时，这些值也赋值进去了，因为全部是零，所以不影响后面的相似度判断，只是增加了向量的维度而已。4.最后比较相似度是，取S值为0.9，D值为10。若有更合理的阈值，要对它们进行修正。5.复杂度分析函数 时间复杂度 空间复杂度Dimension O(n+d) O(1)InitHashList O(n+d) O(n+d)HashBuild O(n+d) O(1)Hashclear O(n+d) O(1)Cosine O(n+d) O(1)Distance O(n+d) O(1)六、使用说明程序运行后根据提示输入所要进行的操作，输入关键字存储文件名，源程序存储文件名。程序将打印建立的哈希表，对源程序的统计结果，相似度和几何距离。七、调试结果使用joseph,parking两个源程序用上述方法求S，D，并对比差异程度。建立的哈希表joseph.txt源程序：int MinEdge(float low,int Vexnum)int i,j,m,flag=0;float k;for(i=0;iVexnum;i+)for(j=0;jVexnum;j+)if(lowi=0&lowj!=0)k=lowj;m=j;flag=1;break;if(flag) break;for(i=0;iVexnum;i+)for(j=0;jlowj)m=j;k=lowj;return m;统计结果parking.txt源程序int i01,j,k;i=1000;float lowcostMAX_VEX_NUM;ArcNode *p;for(i=0;iadjvex;lowcostj=p-weight;adjvexj=v0;p=p-nextarc;if(!VexJudge(G,v0,i) lowcosti=1000;统计结果比较结果八、附录源代码Hash.htypedef struct LNodechar data10;int account;struct LNode *next;LNode,*ppLNode;typedef structppLNode head;int length;LinkHashList;int Dimension(LinkHashList HT);int HashFunc(char *e); /哈希函数void InitHashList(LinkHashList &HT,int m,FILE *fp); /创建哈希表void InsertHT(LinkHashList &HT,char *e);LNode * SearchHT(LinkHashList HT,char *e);void HashBuild(FILE *fp,LinkHashList &HT);double Cosine(int (*w)76,int a,int b,int m);double Distance(int (*w)76,int a,int b,int m);void Hashclear(LinkHashList &HT,int m);void TraverseHT(LinkHashList HT);Hash.cpp#include #include #include #include#include#include hash.hint Dimension(LinkHashList HT) /求哈希表中元素总个数int d,count=0;LNode *p;for(d=0;dnext;count+;return count;int HashFunc(char *e)int i;for(i=0;idata,e);p-account=0;p-next=HT.headd;HT.headd=p;LNode * SearchHT(LinkHashList HT,char *e) /查找元素int d=HashFunc(e);LNode *p=HT.headd;while(p&strcmp(p-data,e)!=0)p=p-next;return p;void InitHashList(LinkHashList &HT,int m,FILE *fp) /创建哈希表int i,d;char str10;HT.head=new LNode *m; HT.length=m; for(i=0;idata,0); p-account=0; p-next=HT.headi; HT.headi=p;char ch=fgetc(fp); /从文件中读取关键字while(ch!=EOF)if(ch= &ch!=EOF) doch=fgetc(fp);while(ch= ); i=0; while(ch!= &ch!=EOF)stri+=ch;ch=fgetc(fp);stri=0; InsertHT(HT,str);void HashBuild(FILE *fp,LinkHashList &HT) /对文件中关键字进行统计int i,d;char str10;char ch=fgetc(fp);while(ch!=EOF) while(ch122)&ch!=EOF) ch=fgetc(fp); i=0;if(ch96&ch96&chaccount+;ch=fgetc(fp);void Hashclear(LinkHashList &HT,int m) /统计量置零 LNode *p; int i; for(i=0;iaccount=0;p=p-next;double Cosine(int (*w)76,int a,int b,int m) /计算Sint i,s=0,v=0,u=0;double cos=0;for(i=0;im;i+)s=s+(*(*(w+a)+i)*(*(*(w+b)+i); u=u+(*(*(w+a)+i)*(*(*(w+a)+i); v=v+(*(*(w+b)+i)*(*(*(w+b)+i);cos=s/(sqrt(v)*sqrt(u);return cos;double Distance(int (*w)76,int a,int b,int m) /计算Dint i,s=0;for(i=0;inext;cout0next)coutdata;coutaccount;p=p-next;coutendl;for(int i=1;iHT.length;i+)p=HT.headi;coutinext)coutdata;coutaccount;p=p-next;coutendl;/for程序相似性比较.cpp#include #include #include #include#include#include hash.hvo