哈希表技术判别源程序的相似性--实验分析报告.docx

《哈希表技术判别源程序的相似性--实验分析报告.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、哈希表技术判别源程序的相似性--实验报告————————————————————————————————作者：————————————————————————————————日期：23哈希表技术判别两个源程序的相似性实验报告USER2014-12-2623一.问题描述实验题目：对于两个C语言的源程序清单，用哈希表的方法分别统计两程序中使用C语言关键字的情况，并最终按定量的计算结果，得出两份源程序的相似性。要求与提示：C语言关键字的哈希表可以自建，也可以采用下面的哈希函数作为参考：Hash(key

2、)=(key第一个字符序号*100+key最后一个字符序号)%41表长m取43。此题的工作主要是扫描给定的源程序，累计在每个源程序中C语言关键字出现的频度。为保证查找效率，建议自建哈希表的平均查找长度不大于2。扫描两个源程序所统计的所有关键字不同频度，可以得到两个向量。如下面简单的例子所示：根据程序1和程序2中关键字出现的频度，可提取到两个程序的特征向量X1和X2，其中X1=(4304307002)TX2=(4205405201)T一般情况下，可以通过计算向量Xi和Xj的相似值来判断对应两个程序

3、的相似性，相似值的判别函数计算公式为:23最后的相似性判别计算可分两步完成:第一步用式(3-1)计算S，把接近1的保留，抛弃接近。的情况(把不相似的排除);第二步对保留下来的特征向量，再用式(3-2)计算D，如D值也比较小，说明两者对应的程序确实可能相似(慎重肯定相似的)。S和D的值达到什么门限才能决定取舍?需要积累经验，选择合适的阑值。3)测试数据:做儿个编译和运行都无误的C程序，程序之问有相近的和差别大的，用上述方法求S}并对比差异程度。4)输入输出:输入为若干个c源程序，输出为程序问的相似

4、度以及向量的几何距离。基本要求：建立哈希表，统计源程序中关键字出现的频度，并计算多个源程序之间的相似度。测试数据：自己在网上找到一些C语言程序，分别为test1.txt,test2.txt,test3.txt等。运行结果应为输出每个源程序关键字的出现的频度和源程序之间的相似度以及向量的几何距离。二．需求分析231.本程序用来通过建立哈希表求源程序关键字的出现的频度和源程序之间的相似度以及向量的几何距离。2.用户可以将源程序的.txt文件放入hashtable文件夹中，运行程序就可以输出每个源程序

5、关键字的出现的频度和源程序之间的相似度以及向量的几何距离。三．概要设计为了实现上述功能，可以用结构体表示哈希表，因此需要哈希表的抽象数据类型。哈希表抽象数据类型的定义：ADThashtable{数据对象：D={ai

6、ai∈ElemType,且各不相同，i=1,2...,n,n≥0}数据关系：R=φ基本操作：Hashfunc(charstr[]);Hashfind(char*words);creathash(void);resethash(intn);isletter(charch);readc(

7、char*filename);getkey(char*str,intlen);copycount(intx[],intn);check(int*x1,int*x2);}endADT3.本程序实现模块主程序模块哈希表程序模块：实现哈希表的抽象数据类型主程序模块调用关系：哈希表程序模块计算相似度和向量的几何距离的模块四．详细设计1.各个子函数的设计1）创建哈希表函数函数原型：voidcreathash(void);输入：读取存储了32个关键字的文件ckey.txt思路：通过对ckey.txt文件逐行

8、赋值给创建的str字符数组，并将该数组调入Hashfunc函数。（2）将关键字根据哈希函数放入哈希表中的指定位置的函数23函数原型：voidHashfunc(charstr[]);思路：对调进来的str数组通过调用getkey函数得到该关键词的key值后放入哈希表中的特定位置，并用线性探索来解决冲突。（3）在哈希表中找是否该words为关键字，并统计频度的函数函数原型：intHashfind(char*words);思路：将调进来的word字符数组先调用getkey函数获取key值，然后在哈希表

9、里查找是否存在该字符串，如果存在则该关键字对应的频度加1.（4）重置哈希表函数函数原型：voidresethash(intn);功能：当n为0时，将指向哈希表中关键字的指针置成Null，同时将频度全部置为0.而当n为1时，仅仅将频度置为0.（5）获取单词key的函数函数原型：intgetkey(char*str,intlen);思路：用key1存储关键字的首字母，key2存储关键字的末字母，然后通过哈希函数得到key的值并返回。（6）判断是否为字母的函数函数原型：intisletter(char